小さいサイズのスライドパズルを解く

この記事は

adventar.org

の11日目がなんか空いていたので24日の朝に書いている記事です。

前日分は hakatashi さんの たぶん TSG CTF 開催記 、翌日分は hideo54 さんの なんかかく でした。 今は24日の朝なのにどっちも書かれてないのはなんでなんですかね(すっとぼけ)

導入

TSG は Slack での活動を含むサークルで、Slack の雑談チャンネルではプログラミング系サークルらしくいくつかの bot が動いています。

f:id:naan11235813:20211224032253p:plain
さまざまなbot

このようなゲーム bot たちが動く Slack 上で一定の地位を得るための手段として、何かしらのゲームが上手になるというのがあります。 本記事では、そのゲームとして「あほくさスライドパズル」を取り上げ、コツを紹介します。

あほくさスライドパズルとは

15パズルという古典的なパズルは皆さんもご存知かと思います。15パズルのように、並進対称性のあるピース(一般に平行四辺形であることが多い)が並んでいる盤面があり、その盤面の唯一ピースの存在しないマスに向けて隣接するピースを移動させることを繰り返して目標の状態にするパズルをスライドパズルと呼びます。

上の画像に「あほくさスライドパズル」で与えられる盤面がありますが、これは「なんでも言うことを聞いてくれるアカネチャン」というGYARI(ココアシガレットP)さんによるVOICEROID楽曲の一場面を模した画像を6つに分割して並べ替え、1ピース分抜いたものです。 あほくさスライドパズルは与えられた盤面から(存在していないピースを除いて)
く[茜ちゃんの頭部]あ
さ[茜ちゃんの胴部]ほ
の並びになるような操作をpostするゲームです。

f:id:naan11235813:20211224032730p:plain
スライドパズルを解いているところ

一般にスライドパズルでは解くことができない盤面が与えられることはありません

f:id:naan11235813:20211224034311p:plain
15パズルの有名な不可能配置 wikipedia「15パズル」より
が、あほくさスライドパズルではランダムな盤面が与えられるため約1/2(1/2より少し大きい)の確率で解けない盤面が与えられます。 このときに「不成立」と指摘することもあほくさスライドパズルの目的です。
f:id:naan11235813:20211224032759p:plain
不成立のスライドパズルを見抜いているところ

2\times3というサイズは非自明な最小のスライドパズルのサイズです。1 TSG の Slack にはあほくさスライドパズルをはじめとした複数のスライドパズルが存在しますが、あほくさスライドパズルが多く遊ばれている理由の一つにこの最小性があると思います。

f:id:naan11235813:20211224035722p:plain
ゲーム「きららファンタジア」のカードを 4x3 に分割したスライドパズル「千矢スライドパズル」もある。難しい

解き方

「あほ」もしくは「くさ」のピースは常に存在するので、存在するほうを取ってきてこれを基準に考えます。以下では「くさ」をベースに考えますが、「あほ」しか存在しない場合は左右反転して考えてください。

f:id:naan11235813:20211224041258p:plain
初期盤面

くさを作る

しばらく、あほや茜ちゃんは無視して、「くさ」を正しくすることに注力します。

f:id:naan11235813:20211224040433p:plain
くさ
こうなると吉です。

向きの正しいくさ

次のようなくさがすぐに作れるとき、ラッキーです。このようなくさができればこれを回す(左2上右2下 を繰り返す)ことで正しいくさを作ることができます。

f:id:naan11235813:20211224040735p:plain
向きの正しいくさ

そうでないくさができているような場合、少し面倒です。

向きの正しくないくさ

そうでないくさがある場合、多少頑張る必要があります。

f:id:naan11235813:20211224041028p:plain
向きの正しくないくさ
今回の初期盤面は向きの正しくないくさです。 解決法ですが、いずれの正しくないくさも(回転させるなどして)左上に持ってきて、これをします。
f:id:naan11235813:20211224041503p:plain
解決法
向きが正しくなりました。

残り

あとは回して、

f:id:naan11235813:20211224041625p:plain
回転してくさを正しい位置に
くさ以外を動かすと解けました。
f:id:naan11235813:20211224041721p:plain
右4つを回す
くさ以外をいくら回しても正しくならない場合、不成立盤面です。

速く、短く解く

上の解き方では23手かかっています。 が、この盤面の最短手数は17手です。 この節では最短手数を出すコツについて話します。

f:id:naan11235813:20211224041911p:plain
最短手順

揃える手順に上のものを採用したとしても「あほ」から揃えるか「くさ」から揃えるか、あるいは「(頭)あ」や「く(頭)」などから揃えることもできるなどの選択肢があります。この中で最も短くなりそうなものを選んで打つのが得です。

また、同じ組から揃え始めるとしても向きの反転を修正する方法は複数あるので、それのどれを選ぶか(他のピースの状態が綺麗になるものを選ぶといいことが多いです)で手数が短くなるかが決まります。

この取捨選択が高速になるとあほくさスライドパズルが高速に解けるようになります。 タイピング速度やスレッドを開くのにかかる時間もありますが、最短がn手の盤面をn秒以内に解けると「速く解けたな」という気になります。

後半雑じゃないか?数やって直感を鍛えよう

どんなスライドパズルも最後に残るのは2x3盤面であることが多いと思うのでここを高速にするとスライドパズルが高速に解ける場合とそうでない場合があるぞい


  1. 1\times n は空きマスを正しい場所に動かすだけで解け、2\times 2 はぐるぐる回しているだけで解けます。

ACPC2019に参加しました

ウオ〜〜〜〜

Day 1

朝3:10に起きる 天才か???? 集合5:30のところ5:15くらいに着く 天才か????

当該人間と合流する

今日のシャ今

えげつない行程を経て会津大学に到着する このへん全然ツイートしてなくないか やめてえ

いろいろあってコンテストが始まる

てぃーいけさんと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を通していて笑ってしまった

Gはパズルでも解けるらしい 🌳びしい

てんぷらさんのチームが全完していた やべ〜〜

悲しい気持ちを引き連れてゲームセンターに行く 一日目終了

クソリプ

Day 2

朝起きたら6:00!勝ったなガハハ 寝て起きたら9:10 なんやこれ やめてえ

てぃーいけさんとこたつと組む 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するたびに 行きますよ〜せーのっ!プシュゥ… とか言ってた)

今日のシャ今

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を通していなかった 優勝です! 自分以外の力で取った優勝は楽しいか?それはそうで、勝てたら、楽しいだろ

解説が終わったあと学食に行く 懐かしいなあ チーズカレーパスタなる謎のメニューを注文し美味しそうなものが出てきてびっくりする いやよく考えたらチーズもカレーもパスタもうまいのにうまくないものが出るわけがない 食べると当然美味しい

platypusくんとこたつくんをゲに誘うと電車の時間が破滅するらしく来てくれなかった 悲しい気持ちになりながら一人で歩いてゲでンドボをした たのしいね

帰りも鈍行で帰る

今日のシャ今

無事帰り着き、おしまい

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> として、dp[i][j][k] := i行j列まで来たときkが作れる <=> 1 とすると、dp[i][j] = (dp[i - 1][j] | dp[i][j - 1]) >> n[i][j] となるので計算量がO(HW Σn)程度 H,W <= 30, -6000 <= Σn <= 6000なので余裕でDPによる全探索が可能(bitsetで定数倍 /64も乗るし) 実行時間 10^-1 s オーダーくらいじゃないですかね 知らんけど なんで H,W <= 100じゃないんやろなあ〜(ヘラヘラ) いや実況でビジュアライザが点になるからって言われてたやんけ

これが大きいケースでうまくいくのはそれはそうで、例えば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

寝ようと思ったら気がついたら起きていた こたつがめが滋賀に来た

↑これは名古屋だね

Day 1

歯医者に行く 敗北者…? 取り消せよ…! 最後に全力でフロスされて歯ァガタガタ言わされてしまった

到着してしまう こたつとエンカ!w

自己紹介フェーズでいづみちはるさんがこたつを名乗っていてウケた 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か?とか言っているとコンテストが終了していた

コンテストここまで

オンサイト1位と2位は組んでたチームだから実質1位!ガハハw まあ3位なんですが

D問題なかなか自分の実装がよさそうだったのでイキる やめようね! ビットごとにめっちゃ辺を張る実装もすこなんや

懇親会で渾身の懇親をする 実はほとんど知っていた人としか話してないね コミュ障なので

olpheくんとか自分とか「どうやったら競プロうまくなれますか」
beetさん「4000問解くと、実力が上がるので安定して、レートがこんなふうになることがなくなります(手を大きく上下させる)」
うしさん「?(机に寝ていた状態から起き上がる)」

↑これすき

懇親会後ゲーセン勢に合流してmaimaiをする いづみちはるさん音ゲーが上手すぎないか 帰ろうとしたら終電ギリギリアウトでこわれてしまった Day 1終了

終電に温情で乗せてもらったので勝ち

Day 2

への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のソートを逆順にすると通ってキレる

オンサイト7位 悪くはないんですが主観的冷えというものがあり Lも通したかったなあ 負けです

懇親会で渾身の食事をする 複数のよっぱらいが存在していて面白くなった これが†人生†や

懇親会の卓で500点以下の問題を作問して投げる遊びをする 自分も1問いい感じの300-400が生やせたのでヨシ beetさんが作問能力も高いことがわかりかてませんの意を強くした

懇親会後ゲーセンでmaimaiをする こたつがめとマッチング!w

帰ろうとしたら終電1本前でこわれてしまった Day 2終了

Day 3

こたつへのナンでチームを組むことにしていた

2人して絶起をする

3人して遅刻をする

会場へ向かう途中にbeetさんのツイートを見る

包除数え上げが出るのか〜(うく)

こたつが最遅だったのでチーム名を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の存在を思い出して実装する 自分は忘れたまま悲しくなっていた

コンテストここまで

つらすぎて朝青龍になる まあオンサイト2位だし多少はね?

地獄DPを実装しきることができるタイプのベテランになりたいね 素直に反省です いや地獄DPが本質じゃなくて考察が抜けていたんですが

解説ののち解散になった

ボウリングまではついていくことに決めた

funcsr もやし先輩 くちもちとくらさん きゅうりさん Pulmnさんで昼食を食べに行く バスで駅まで行くが来た道を戻る

ちょうど15時くらいで飲食店が次々と閉まる 残った選択肢がすいていそうな得々うどんか混んでいるにぼ次郎でにぼ次郎を選んだ

にぼ三郎を頼んで完飲をした おいしかった オタク必ずしも完飲をしないことを学んだ

ボウリングに行った 申し込み用紙に「ナン」と書いたら名前を「ナニ」と間違えられて泣いた

きゅうりさんとくちもちとくらさんがお上手 funcsrとナンが無だった かなしいね

ボウリングから帰って参加記を書く ブログがなかったのではてなブログに登録する

とりあえず記事内で言及している人に読んでもらってから公開するお気持ちになる Day 3 終了

感想

楽しかった 問題が良質だった Day 2, 3の"あと一問"が解きたかった...(いやDay 2はほんまお前お前)

来年も申し込みTLEしない限り行こうと思います 他の大学オンサイトとかも行ければ行く いやよく考えたら遠いな 破滅してしまった

おまけ

去年の参加記書いてないね 長いイベントだなあ(詠嘆)