これは嘘解法だったらしいのですが、オンサイトFAなのでまあ良しとしましょう(あとから聞いた話だと、bitsetを使っても通らなかったチームもあったらしい。本来はFFTを使って頑張るらしいけど、知らなかったのでやっぱりダメ。EよりもHが解かれているらしい。文字列Sと同じ長さで、Sのどの接頭辞もどの接尾辞とも一致しない文字列を数え上げる問題。条件を満たさない方を数え上げたほうがいいのでは、という話になりSuffixArrayやローリングハッシュを使ってどうにかやろうとしたけどわからず終了。algorithmというものがあることを知る。一応SAやロリハでゴリ押すこともできたらしいけど、こういうやつは幾何と同じで知らないとつらそうだなぁ。夜はボドゲを見ながらKMP法とかの復習。初の5時間コンテストで疲れたり、ごちうさの3期が決まったりして感激した結果、9時にオフトンinして翌3時に起きる偉業を達成。二度寝に成功したものの、さすがに人間なので9時間睡眠で起床。朝食は昨日の反省を踏まえ白米を食べる。荷物をまとめて会場へ。最初は同じムーブを取る。Cはナップサック問題をちょっと捻った感じ。dpの添字が大きくなるなあ、と思っていたらこたつがめが次元を落とすやつを教えてくれた。IとJが解かれまくっているらしい。Iを読んでいたらこたつがめが式変形を終えていた。Jは素数は奇数だねって感じで拡張dijkstraをやる話になる。Fの実験をゆきのんが進めていて、xorが1になるよう取るといいっぽいことがわかる。実験をしてもらったおかげで初期状態でxorが0のコーナーにハマらなかった。お昼を食べてからはGの考察を一生していました。ヤバ構文解析っぽそうな感じだったが、いろいろ試しても糸口はつかめず。dpが頭をよぎって結局わからなかったけど、想定解はdpらしい。終わってからは解説を聞いて解散。同じ階にいたへのkさんとの再会を誓い、会場をあとにする。その後は昔からFFだったぽうえっとくんとエンカをキメてラーメンを食べたりオタクショップはしごをしたりして帰った。文字列と幾何とかの知識が弱そうなことには国内予選のときから薄々感づいてはいたものの、それが露呈した。あと3ヶ月くらいでどうにかしよう。コメントをキャンセルメールアドレスが公開されることはありません。