小さいサイズのスライドパズルを解く
この記事は
の11日目がなんか空いていたので24日の朝に書いている記事です。
前日分は hakatashi さんの たぶん TSG CTF 開催記 、翌日分は hideo54 さんの なんかかく でした。 今は24日の朝なのにどっちも書かれてないのはなんでなんですかね(すっとぼけ)
導入
TSG は Slack での活動を含むサークルで、Slack の雑談チャンネルではプログラミング系サークルらしくいくつかの bot が動いています。
このようなゲーム bot たちが動く Slack 上で一定の地位を得るための手段として、何かしらのゲームが上手になるというのがあります。 本記事では、そのゲームとして「あほくさスライドパズル」を取り上げ、コツを紹介します。
あほくさスライドパズルとは
15パズルという古典的なパズルは皆さんもご存知かと思います。15パズルのように、並進対称性のあるピース(一般に平行四辺形であることが多い)が並んでいる盤面があり、その盤面の唯一ピースの存在しないマスに向けて隣接するピースを移動させることを繰り返して目標の状態にするパズルをスライドパズルと呼びます。
上の画像に「あほくさスライドパズル」で与えられる盤面がありますが、これは「なんでも言うことを聞いてくれるアカネチャン」というGYARI(ココアシガレットP)さんによるVOICEROID楽曲の一場面を模した画像を6つに分割して並べ替え、1ピース分抜いたものです。
あほくさスライドパズルは与えられた盤面から(存在していないピースを除いて)
く[茜ちゃんの頭部]あ
さ[茜ちゃんの胴部]ほ
の並びになるような操作をpostするゲームです。
一般にスライドパズルでは解くことができない盤面が与えられることはありません が、あほくさスライドパズルではランダムな盤面が与えられるため約1/2(1/2より少し大きい)の確率で解けない盤面が与えられます。 このときに「不成立」と指摘することもあほくさスライドパズルの目的です。
というサイズは非自明な最小のスライドパズルのサイズです。1 TSG の Slack にはあほくさスライドパズルをはじめとした複数のスライドパズルが存在しますが、あほくさスライドパズルが多く遊ばれている理由の一つにこの最小性があると思います。
解き方
「あほ」もしくは「くさ」のピースは常に存在するので、存在するほうを取ってきてこれを基準に考えます。以下では「くさ」をベースに考えますが、「あほ」しか存在しない場合は左右反転して考えてください。
くさを作る
しばらく、あほや茜ちゃんは無視して、「くさ」を正しくすることに注力します。 こうなると吉です。
向きの正しいくさ
次のようなくさがすぐに作れるとき、ラッキーです。このようなくさができればこれを回す(左2上右2下 を繰り返す)ことで正しいくさを作ることができます。
そうでないくさができているような場合、少し面倒です。
向きの正しくないくさ
そうでないくさがある場合、多少頑張る必要があります。 今回の初期盤面は向きの正しくないくさです。 解決法ですが、いずれの正しくないくさも(回転させるなどして)左上に持ってきて、これをします。 向きが正しくなりました。
残り
あとは回して、 くさ以外を動かすと解けました。 くさ以外をいくら回しても正しくならない場合、不成立盤面です。
速く、短く解く
上の解き方では23手かかっています。 が、この盤面の最短手数は17手です。 この節では最短手数を出すコツについて話します。
揃える手順に上のものを採用したとしても「あほ」から揃えるか「くさ」から揃えるか、あるいは「(頭)あ」や「く(頭)」などから揃えることもできるなどの選択肢があります。この中で最も短くなりそうなものを選んで打つのが得です。
また、同じ組から揃え始めるとしても向きの反転を修正する方法は複数あるので、それのどれを選ぶか(他のピースの状態が綺麗になるものを選ぶといいことが多いです)で手数が短くなるかが決まります。
この取捨選択が高速になるとあほくさスライドパズルが高速に解けるようになります。 タイピング速度やスレッドを開くのにかかる時間もありますが、最短がn手の盤面をn秒以内に解けると「速く解けたな」という気になります。
〆
後半雑じゃないか?数やって直感を鍛えよう
どんなスライドパズルも最後に残るのは2x3盤面であることが多いと思うのでここを高速にするとスライドパズルが高速に解ける場合とそうでない場合があるぞい
-
は空きマスを正しい場所に動かすだけで解け、 はぐるぐる回しているだけで解けます。↩
ACPC2019に参加しました
ウオ〜〜〜〜
Day 1
朝3:10に起きる 天才か???? 集合5:30のところ5:15くらいに着く 天才か????
当該人間と合流する
いけだくんから今日の行程を聞いてありえねぇっつってる
— てんぷら (@tempura_cpp) 2019年9月17日
ヌムヌムヌァンコォ
— てぃーいけ (@1119_2916) 2019年9月17日
天才C++erこと@tempura_cppとてぃーいけさん@1119_2916と合流して会津に向かうなどしている
— もっちりとしたナン(仮) (@naan112358) 2019年9月17日
今日のシャ今
シャミ子?🌸🌸今日のご飯何?
— てぃーいけ (@1119_2916) 2019年9月17日
えげつない行程を経て会津大学に到着する このへん全然ツイートしてなくないか やめてえ
ELECTRICAL COMMUNICATION駅 pic.twitter.com/C1R8V7Rw65
— こたつがめ (@kotatsugame_t) 2019年9月18日
|会|津|大|学| pic.twitter.com/y7yIGM0ivi
— てぃーいけ (@1119_2916) 2019年9月18日
いろいろあってコンテストが始まる
てぃーいけさんとplatypusさんと組んでACPC_pnaanty_ikeとして出る
自分がA、てぃーいけさんがB、platypusさんがCを解くことにする 残りは適当にやる
ここからコンテスト
Aを通す 1:51 オンサイトFA+5秒 死んだやが... てぃーいけさんとplatypusさんがBとCを通す この時点では悪くない時間だった 最高!
残りの問題を読むとなんか解けそうな問題がなくて死んでしまう オイオイ 得意が尖りすぎていないか
Dの方針をplatypusさんから聞く 木だからDFSでいけるやろ〜〜(ヘラヘラ)をする 子の順をどうする念 少し実験をして重みの昇順でやる←ここが嘘だった 通らない 無限に68/70で終了してしまう
おやつルームにいくとなぜかきゅうりが置いてある だれやきゅうり書いたん きゅうりおいしい〜〜〜(は???) ボリボリ食べながら唯一行けそうなGを考える
損をしない連結をいくつか思いついて2人が実装していないうちに書くが損をしうる連結で頭が壊れて死ぬ
Eの方針が2人の間で話されている O(N3)から高速化が厳しいみたいな話が聞こえる 死んでしまった
platypusさんのDが破滅しているのでてぃーいけさんが書くことになる
書ききる前にコンテスト終了してしまった
コンテストここまで
3完激冷え太郎になってしまった グオー
beetさんがえげつない嘘でDを通していて笑ってしまった
Dは昇順ソートで落ちたので、降順ソートを投げたら通りました(なんで?
— beet (@beet_aizu) 2019年9月18日
Dがコストの降順で通るの意味不明の極みか?????
— もっちりとしたナン(仮) (@naan112358) 2019年9月18日
Dのテストケースが弱かったんですが、強かったら通せなかったのでOKです
— beet (@beet_aizu) 2019年9月18日
昇順でダメなら、降順だろ
— beet (@beet_aizu) 2019年9月18日
今日のbeet君の言動水色にしか見えねえな
— olphe (@_olphe) 2019年9月18日
Dすきなんですが、嘘が通ってびーとくんがいきっているのは😩
— うーちゃん (@ei1333) 2019年9月18日
Gはパズルでも解けるらしい 🌳びしい
てんぷらさんのチームが全完していた やべ〜〜
これすき pic.twitter.com/zYWQeGRg6I
— もっちりとしたナン(仮) (@naan112358) 2019年9月18日
悲しい気持ちを引き連れてゲームセンターに行く 一日目終了
金枠取りなさーい!
— ヒトデマン (@sushi44295) 2019年9月19日
Day 2
朝起きたら6:00!勝ったなガハハ 寝て起きたら9:10 なんやこれ やめてえ
寝てめっちゃ起きてめっちゃ寝て起きた(は?)
— もっちりとしたナン(仮) (@naan112358) 2019年9月18日
てぃーいけさんとこたつと組む ACPC_AIZUDAI_DROPOUT
A ナン B てぃーいけ C こたつ でやることを決める
ここからコンテスト
Aを通す 気が動転してCEを出す 修正する 気が動転してWAを出す 修正する 気が動転してACを出す オンサイトFA
てぃーいけ「Bみたいなのは天才がやるといい」などと言って渡されたBをやる ACする FAじゃーん 楽しい
Gを見ると組み合わせゲームで見るからにgrundy ウオオ俺は天才という気持ちで手で実験をする
こたつくんからMの考察が流れてくるので閉じた式にする 通ったっぽい すげえ
Gの実験結果を見るとM/xのmsbを見ればいい気持ちになり書いたら通る FAじゃーん 楽しい
てぃーいけさんとこたつくんがなんかLを通す 天才か????
横目で見ながらIを眺めるとなんか自明なので通しておく
Hが包除に見えるので式を書く こたつくんに投げるとサンプルが合わないらしい こたつがめは天才なので合わない原因を突き止めてくれる 修正した式を投げると通る 強すぎる
なんかみんなE通してんな 見るか 順列を0/1にうつすならそれは置換の偶奇だろ(は?) いやN=Kで破滅するやんけ こたつがめ「自明を場合分けしたらよくない?」 天才か〜〜〜?????? 場合分けしたら照明が回ってパーティーナイト
Jをこたつと2人で考える セグメント木よくわかんね〜〜 平方分割書きたくない?? 書きたいね なんか適当な気持ちで遷移を考える まあTLEなんですが この後コンテスト終了までなんだかんだあって14ペナルティを生やす
Dをてぃーいけさんが考えている たかだかブラスター2個でなんとかなるらしい わからねえ
いやもう人外向けしか残ってないんだよな つれえ
Kはなんもわからん
Fは自明な考察をする まあバス1本だけ乗ればええやろ てぃーいけさんが天才なのでCHTを貼れるのでは?という気持ちになる
考察が完了する 人間にはバグらせずに実装するのは不可能で〜〜〜す 時間切れ 人生終了 saikaiが劇的な通し方をしてびっくりしちゃう
コンテストここまで
オンサイト優勝やんけ〜〜〜〜 おるふぇ冷えてるか〜〜みたいなことを言う いや完数同じですが… コンテスト中うるさくしてごめんね(submitするたびに 行きますよ〜せーのっ!プシュゥ… とか言ってた)
人としてふざけているチームに負けてしまった
— olphe (@_olphe) 2019年9月19日
今日のシャ今
シャミ子?🌸🌸今日のご飯何?
— てぃーいけ (@1119_2916) 2019年9月19日
Fは3周させると実装が楽らしい ほええ Jも面白い また実装したいね
懇親会で渾身の懇親をする 中華料理がおいしい beetさんが酔いつぶれる 酒 is こわい
Day 3
beetさんとdrogskolさんと組む ナン「チーム名ACPC_beet_yopparaiでいいですか」beet「ダメです」 チーム名がACPC_sakenichiaに決定する
drogskolさんがA、beetさんがB、自分がCを読むことに決まる
ここからコンテスト
drogskolさんがAを通す beetさんがBを読んで通す 天才 BのFA
Cを読むと自明に全探索なので書くとなんか通らない 何? その間にbeetさんがEを読んで通す drogskolさんを呼んでデバッグしてもらうがわからない 困った 仕方がないのでbeetさんを呼ぶと答えが0の時がコーナーであることがわかる 天才〜〜〜〜 修正すると通る ご迷惑をおかけしました...
Dが桁DPということでdrogskolさんが書く その間にFとGを読むとFはDPでできそうなことがわかる beetさんがSA+LCP+range addで解けることを見抜いて書いて通る プロ 世界一典型に強い根菜
Gのコードを読解する なんか回る順をindexの昇順にしたときのオイラーツアーについてある頂点iがA[i]+1回出てくる直前までの長さが答えであることがわかる beetさんに投げるも直接全方位にできなさそうと言われる
Dがバグる 全員でデバッグにあたる beetさんが修正を加えて通る プロ 世界一デバッグに強い根菜
その間に木DPを比較的ましな形に変える 結合的じゃなくてヤバので左右から累積和をとるやつができないね 破滅です
フルスクラッチで全方位木DPを書いてもらう ご迷惑を... まず普通の木DPを書いて投げる 当然二乗なので落ちると思ったら3ケースめでWA 悲しいね 修正すると24ケースめでTLE それはそうだね
ここからが本当の地獄! beetさんがつらそうにしていた まあ自分もこの全方位木DPは書きたくないですね ご迷惑を... 実装が破滅してきたので一部マージをサボってO(N2)っぽいものを提出する 3ケースめでWA なんで?? デバッグをする beetさんが修正を加えたものを投げると3ケースめでWAではなくなる TLEを待っているとなぜかACしている なんで?? 世界一競技プログラミングに強い根菜の力は並大抵ではなかった...
olpheチームから1位風船を強奪してくる(ヤクザ) ペナルティではゴリゴリで負けなので通されたら悲しいね〜みたいなことを言いながらおやつを食べる
beet_aizu「コンテスト終了して戻ったら1位風船消えてたら面白いから終わるまで順位表見ないでおこうぜ」
drogskolさんが今週の謎解きみたいな何かをしている なんか爆速で解けたので煽っておく(性格が悪すぎる)
コンテストここまで
そうこうしているうちに終了する 誰もGを通していなかった 優勝です! 自分以外の力で取った優勝は楽しいか?それはそうで、勝てたら、楽しいだろ
beet_aizuをチームメイトにするの、人間C++インタプリタへのこーどと同様にチートめいている
— もっちりとしたナン(仮) (@naan112358) September 20, 2019
beet許さねえ~~~~~~~
— olphe (@_olphe) September 20, 2019
解説が終わったあと学食に行く 懐かしいなあ チーズカレーパスタなる謎のメニューを注文し美味しそうなものが出てきてびっくりする いやよく考えたらチーズもカレーもパスタもうまいのにうまくないものが出るわけがない 食べると当然美味しい
platypusくんとこたつくんをゲに誘うと電車の時間が破滅するらしく来てくれなかった 悲しい気持ちになりながら一人で歩いてゲでンドボをした たのしいね
帰りも鈍行で帰る
東京に戻るの日付変わるころで戦慄している
— もっちりとしたナン(仮) (@naan112358) September 20, 2019
今日のシャ今
シャミ子?🌸🌸今日のご飯何?
— てぃーいけ (@1119_2916) September 20, 2019
無事帰り着き、おしまい
Day 5
しばらく放置されていた参加🌳を思い出し、書き書きする 内容を確認して、公開ボタンにマウスポインタを重ねる
TSG LIVE! 3 day 2 ライブ競技プログラミング write up
TSG LIVE! 3 day 2 早朝プログラミング競技プログラミングに参加しました。
write upを書くぞ〜という気持ちで書きます write upってこういうのなんですか どっちかというと競技プログラミング系の不明瞭参加記のほうに近い
Day 1 - 開始直前
Google Code Jam Round 2 に出る 0完 冷えすぎる 風呂に入って寝る
起床 絶起やんけ 朝食を食べて向かう
到着 優秀なので集合時間に間に合う
地下着 わいわい 提出は1人しかしてはいけないらしいのでCoiL氏とざっくり分業の相談をする ← レギュレーション思ってたのと違ったっぽい(違ったっぽいので)
競技開始
開始して問題を読む とりあえずsubmissionするか!ということで縦にW回横にH回動くやつをする HとW逆だったらしいけどまあこのテストケースやったらうまくいってるしええやろ!w
提出すると1072点、意外と点数のスケールが小さいことがわかる(10:05:41)
アルゴ脳なので一瞬でDPが思いつく 実況で2行持つ全探索とか言われていた 違います
dp : vector<vector
これが大きいケースでうまくいくのはそれはそうで、例えば30x30の最短路は58 C 29 = 30067266499541040通りあって、値域が-6000から6000なのでさすがに-1,0,1のやつは存在することがとんでもなく期待される 10x10だと48620通りあって値域が-1000から1000なので 盤面がランダムなら中央付近の期待値爆上がりなので(正規分布に近似されていく)そこそこ期待できる 5x5だと70通りを-500から500 まあそれなりに 知らんけど
提出するとINF点 あれ???→左右間違えて盤外に出ていた 修正して提出すると71点 勝ったなガハハ!w(10:47:42)
CoiL氏が全探索が書けたらしいのでマージする しようと思ったらお互いグローバルに無限にものがあって困っちゃったのでnamespace CoiL{}とnamespace Naan{}で囲む 別にイキってnamespaceをつけたわけではないんじゃ
マージしたコードを投げると3x3がやばいスコアになっている これは乱数ガチャやろ〜と思って大量になげる
どうにもおかしい(最初の最短路全探索より悪いのしか出ない)ので全探索こわれてないかということになる 二人で修正にとりかかる 自分は一から書く時間とCoiL氏のコードを読み解く時間もなかったので手で全列挙をする おねえさんの問題を3x6まで全列挙した経験が生きる!!!!! 実際3列の場合はフロンティア法の状態がたかだか5個なので一瞬で列挙が可能 なので一瞬で列挙した
書いて投げる 57点でわいわい(11:11:32)
5x5も全列挙するか〜という気持ちになるけど8512通りは頭がこわれる上フロンティア法の状態が無限個あって禿げた もはやコード修正の時間はなさそう †偶然†持っていたまちカドまぞく(1-4巻,伊藤いづも,芳文社)をPCの前にお供えしていい乱数を引けるように祈祷して提出する 乱数乞いに成功して36点(11:17:05) 残り1分切ったし優勝では?→優勝
競技終了
優勝して気が大きくなる インタビューに答える LIVEのアーカイブを見ると想定した1/100倍くらいしか声が伝わっていなくておっぱげた
CoiL氏の功績があんまり実況側に伝わっていなさそうで悲しかった バグは入出力高速化の位置が原因でnaanがコードをマージするときに埋め込んだっぽい 申し訳なさすぎて申し訳のNASAofNASAになった そこ修正したら16点くらい出た これマジ? 反省した
駒場に+200点!実質グリフィンドール(ほんまか) いやーなんだかんだ言って実質アルゴみたいなアプローチができたので楽しかった 次の駒場祭ではもっと貢献していきてえなあ俺もなあ
いろいろ終了後
帰り道新ABCに出た なんとか全完した やったぜ。 アルゴ最高〜〜〜 次回のTSG LIVE! ライブ競技プログラミングはアルゴとマラソンの2回開催ってマジ? マジじゃないです
RUPC2019 参加記 Day 0 - 3
たのしかった
Day 0
寝ようと思ったら気がついたら起きていた こたつがめが滋賀に来た
ぬぁごや pic.twitter.com/1ubwUymcF3
— こたつがめ (@kotatsugame_t) 2019年3月4日
↑これは名古屋だね
Day 1
歯医者の時計止まってるけど ギャグか?
— もっちりとしたナン(仮) (@naan112358) 2019年3月5日
歯医者に行く 敗北者…? 取り消せよ…! 最後に全力でフロスされて歯ァガタガタ言わされてしまった
#RUPC2019 ついたて pic.twitter.com/QcOPqaAjMN
— もっちりとしたナン(仮) (@naan112358) 2019年3月5日
到着してしまう こたつとエンカ!w
naan pic.twitter.com/90ocDKcd5n
— こたつがめ (@kotatsugame_t) 2019年3月5日
自己紹介フェーズでいづみちはるさんがこたつを名乗っていてウケた beetさんが「AtCoderのレーティングがたぶん会場で1位です」みたいなことを言っていて怖くなってしまう それ以外は忘れてしまった 悲しい
randomに組むか〜wと思っていたらなんとくじでbeetさんと当たる かてません
drogskolさん beetさんと組んでチーム名をrupc_ukuku09にする うっくっくwwwwwwえいえいえt(←いずらいt)
drogskolさんがABCを、beetさんと自分でDEFGを担当しようということになる
ここからコンテスト
Dを読むと構築なので担当したい気持ちになる
drogskolさんがABを通してくれている間にDとか構築インタラクティブやしにぶたんやろ〜とヘラヘラしながらbeetさんに無を持っていくと無であることを指摘される
無を有にするうちにAとBが通っているので有を実装すると通る ここまで32分くらい
drogskolさんが実験をして天才になってCを通していた beetさんが一瞬でEを通していた こわいなあ(50分)
その間にFとGを読んでGは苦手だなあ やめるか!wという気持ちになってFを考えておく 絶対値なので大小関係を考えるをすると大小関係の変動しない交換は意味がないことがわかる
beetさんにGが「燃やす埋める」っぽいと言われるが燃やす埋めるを解いたことがなく フローで解けるらしい くらいの理解しかなかったため相槌を打つオタクと化してしまう
同色罰金がうくだけど二部グラフなので頂点反転!wをしてもうまくいかない 終わってから聞いたんですが電球を頂点にすると破滅するらしい 悲しいね
悲しいのでFを考察する わからんわからんと言いながらa[i],i,a[j],jの大小関係実質12通りを書き下すと、a[i]とiの間 と a[j]とjの間 が重なっていないものはswapするべきで 得られるスコアは2つの区間の距離の2倍っぽいことがわかる
貪欲以外のアプローチが思いつかなかったので証明のない貪欲を書く monoidであることをbeetさんが気づくのでbeetさんのセグメント木ライブラリに乗せて殴る→サンプルは合うのにWA
適当に自明assertを入れることを提案するとREする えらかった がんばって直すと通る 159分
残り時間はGがわからず いやー燃やす埋めるに見えるけど 実はDPか?とか言っているとコンテストが終了していた
コンテストここまで
rupc_ukuku09でオンサイト3位でした!(Dを担当してFの証明のない貪欲をbeetさんに投げました) #rupc2019
— もっちりとしたナン(仮) (@naan112358) 2019年3月5日
オンサイト1位と2位は組んでたチームだから実質1位!ガハハw まあ3位なんですが
D問題なかなか自分の実装がよさそうだったのでイキる やめようね! ビットごとにめっちゃ辺を張る実装もすこなんや
懇親会で渾身の懇親をする 実はほとんど知っていた人としか話してないね コミュ障なので
olpheくんとか自分とか「どうやったら競プロうまくなれますか」
beetさん「4000問解くと、実力が上がるので安定して、レートがこんなふうになることがなくなります(手を大きく上下させる)」
うしさん「?(机に寝ていた状態から起き上がる)」
↑これすき
懇親会後ゲーセン勢に合流してmaimaiをする いづみちはるさん音ゲーが上手すぎないか 帰ろうとしたら終電ギリギリアウトでこわれてしまった Day 1終了
は?乗れたが 敗北が知りたい
— もっちりとしたナン(仮) (@naan112358) 2019年3月5日
終電に温情で乗せてもらったので勝ち
Day 2
やば こわ ミュートしました
— heno11101111 (@heno_code) 2019年3月6日
へのkと不明瞭にいちゃつく けんちょん olphe ナン でrupc_olnanchonとしてチームを組んでおいた
わたてん9話を見た ノアちゃんがガチめいてきた 星野みやこに変身セットあたりで目覚めましたねクォレハ… まあひなたちゃん優しいからね、仕方ないね
問題数13問でおっぱげた
olpheくんがA ナンがB けんちょんさんがCをまず読んで残りはよしなにすることになる
ここからコンテスト
olpheくんがAを爆速で通す 1分
Bがシミュレーションに見えたのでシミュレーションを書いてしまう Sample 4を手元で実行して禿げる 算数をしないといけない気持ちになりけんちょんさんのCの実装を優先してもらう けんちょんさんがCを通す 14分
算数をしようと思ったところ算数が苦手だったので泣いてしまった 諦めて別の問題をすることを決意
けんちょんさんがGを考えていて逆型ゲームに誤読しているっぽかった(最後の1本を食べきった人の負け に見えていそうだった)ので誤読を指摘する Gが通る 27分
(ほとんど関わっていなかったけどFの考察がこのへんで進んでいたらしい)
ここからが本当の地獄!
olpheくんを尻目に面白そうなL問題を考える すぐに原始根→離散対数→gcd (575)では?と言う 実装をしてもらって投げるとTLEしてしまう だめであることに気づくのに無限時間かかってしまった
Bをolpheくんが通す プロ 堅実 114分
けんちょんさんがHを通す 昨日見た燃やす埋めるらしい なるほどなあ ところで問題を読んでいません
並行してolpheと二人でIを考える 考えていると天から「逆順に見なさい」という声が聞こえるので逆順に見るといいなあとなる
2q d + A (0 <= A < 2q)の形が適当に作れるので上端と下端を生やすと判定がすぐにできる
満たすAについて適当をするとサンプルが合う WAが出るんですが自明assertをするとREでおっぱげる オーバーフローなどを直すと通る 197分
Dが冷静になるとただのDPなので書く デバッグ出力こわれるから高さを小さくしていたらWAになって踊った AC 225分
Eをみんなで考える olpheが思いついた感じだったので書く 実はほとんど寝ていたのでJとLを考えるマンになってしまう
Jが区間スケジューリングっぽいというのは最初の方にolpheから聞いていたので物理パートの方針ガチャをするとn回目でいい感じになる 受験物理の経験が生きたな(確信) 放物線はy=ax(T-x)なのでここのaを出す v=(vx, vy)として出した式と比較してvをaで表す 最小は1/Tっぽい 45°だなあ 最高
Eが通ったのでけんちょんさんがLをほげしていくのと並行してJを実装する 手が止まったらもう片方が奪う感じで目まぐるしく実装する人が入れ替わっていた
Jの実装が完了するがSampleが合わねえ おわり とりあえず投げる 当然WAなんですが
コンテストここまで
おもむろにJのソートを逆順にすると通ってキレる
J問題、終了5分後にソートを逆順にして投げたら通って禿げてしまった #RUPC2019
— もっちりとしたナン(仮) (@naan112358) 2019年3月6日
オンサイト7位 悪くはないんですが主観的冷えというものがあり Lも通したかったなあ 負けです
懇親会で渾身の食事をする 複数のよっぱらいが存在していて面白くなった これが†人生†や
懇親会の卓で500点以下の問題を作問して投げる遊びをする 自分も1問いい感じの300-400が生やせたのでヨシ beetさんが作問能力も高いことがわかりかてませんの意を強くした
懇親会後ゲーセンでmaimaiをする こたつがめとマッチング!w
帰ろうとしたら終電1本前でこわれてしまった Day 2終了
Day 3
こたつへのナンでチームを組むことにしていた
目覚まし止めてスヤスヤ眠る伝統芸能
— こたつがめ (@kotatsugame_t) 2019年3月6日
おはうく〜(前前前世)
— もっちりとしたナン(仮) (@naan112358) 2019年3月6日
2人して絶起をする
9時時点で誰も会場に来ていないチーム #rupc2019
— heno11101111 (@heno_code) 2019年3月7日
3人して遅刻をする
会場へ向かう途中にbeetさんのツイートを見る
包除数え上げが出そう(予言
— beet (@beet_aizu) 2019年3月6日
包除数え上げが出るのか〜(うく)
こたつが最遅だったのでチーム名をRUPC_Burningkotatsuにした こたつがめもやした
へのがA ナンがB こたつがCを読むことに
ここからコンテスト
へのkがAを通す rupc_H_E_N_T_A_Iに僅差で負けたらしい 悲しいね
自分がわからなくてこたつがCの方針が立ったらしいので実装してもらう
へのkにBの問題概要を伝えていたらこたつが読んでいたのがBであったことが発覚 何? まあBが一瞬で方針が立つのはこたつの異常能力な気がするのでそれが起きてよかった へのと一緒にCを読むとSampleがすべてを教えてくれるのでわかる どちらも通る 15分
Dをへのkが実装する そのうちにEFGを読もうとするがEは苦手なタイプの文字列なので無理だねとなる Fを読むと受験数学の勘がまず個数を固定しなさいと言ってくるので個数を固定する すると自明な包除の式が立つ(ここで脳内でbeetさんの方角を向いて礼拝した)ので綺麗にしたいなあとなってこたつに見せる するとこたつのおかげで冷静になってこのまま計算してもたかだかO(N2)じゃーんとなって終わる ホワイトボードを見るとhomu_aishiteruなる文字列がFの下に書かれていて泣いてしまった いや20分ってなんやねん
Dが通ったのでFを実装すると当然通る やったぜ。 39分→46分
その間にへのとこたつがEの考察を詰めていた Manacharとか使ったんじゃないかなあ しらんけど 線形とか回文とか言っていたけど結局ロリハで殴ったらしい なるほどなあ 待っていると通る 67分!!!!
悠々とGを考察し始めると思いつかなくて禿げる
いろいろなことを考える cycleの種類は上から見て1周するか1周しないかだなあとなる 1つ繋げるみたいなことを考え始める
Gに到達して30分ほどで27状態くらいを持つDPを思いつくが破滅なのでやめたくなる しかし重い腰をあげて実装に取りかかる(この頃には上下しながら1周するcycleの存在が頭から消えてしまっている)
地獄だなあと思いながら書く へのkとナンの2人で独立に書く←これはなに 二人ともSample 1は通るけど2が合わないね
へのkが上下しながら1周するcycleの存在を思い出して実装する 自分は忘れたまま悲しくなっていた
コンテストここまで
Burningkotatsu、Gで燃料切れだったな
— こたつがめ (@kotatsugame_t) 2019年3月7日
コンテスト開始直後のRUPC_Burningkotatsu「爆速6完‼大変お世話になりまさした‼やるな笑笑」
— もっちりとしたナン(仮) (@naan112358) 2019年3月7日
コンテスト中盤のRUPC_Burningkotatsu「なぜGのSample合わない⁉️数え上げ2問ありえない話し‼通れ‼通れ‼」
コンテスト終了時のRUPC_BurningkotatsuのG担当ナン「(自分が)あほしね」 #RUPC2019
つらすぎて朝青龍になる まあオンサイト2位だし多少はね?
出ました(オンサイト優勝
— beet (@beet_aizu) 2019年3月7日
老害がイキれるセット、すき
— beet (@beet_aizu) 2019年3月7日
地獄DPを実装しきることができるタイプのベテランになりたいね 素直に反省です いや地獄DPが本質じゃなくて考察が抜けていたんですが
解説ののち解散になった
ラーメンラウンドワン京都徹夜カラオケムーブをします(人はまだ増やせそう
— jj_funk (@jjfunk4) 2019年3月7日
ボウリングまではついていくことに決めた
funcsr もやし先輩 くちもちとくらさん きゅうりさん Pulmnさんで昼食を食べに行く バスで駅まで行くが来た道を戻る
ちょうど15時くらいで飲食店が次々と閉まる 残った選択肢がすいていそうな得々うどんか混んでいるにぼ次郎でにぼ次郎を選んだ
にぼ三郎を頼んで完飲をした おいしかった オタク必ずしも完飲をしないことを学んだ
ボウリングに行った 申し込み用紙に「ナン」と書いたら名前を「ナニ」と間違えられて泣いた
きゅうりさんとくちもちとくらさんがお上手 funcsrとナンが無だった かなしいね
みなさん、参加記を書くまでがRUPCですよ? #RUPC2019
— そすうさ(素数うさぎ) (@wk1080id) 2019年3月7日
参加記を書くまでがRUPCらしいのではてなブログをはじめて参加記を書くオタクをしている
— もっちりとしたナン(仮) (@naan112358) 2019年3月7日
ボウリングから帰って参加記を書く ブログがなかったのではてなブログに登録する
とりあえず記事内で言及している人に読んでもらってから公開するお気持ちになる Day 3 終了
感想
楽しかった 問題が良質だった Day 2, 3の"あと一問"が解きたかった...(いやDay 2はほんまお前お前)
来年も申し込みTLEしない限り行こうと思います 他の大学オンサイトとかも行ければ行く いやよく考えたら遠いな 破滅してしまった
おまけ
おれやんけ
— もっちりとしたナン(仮) (@naan112358) 2019年3月7日
去年の参加記書いてないね 長いイベントだなあ(詠嘆)