去年部分点を出来るだけ取るスタイルで成功したが、逆にあれ以上の点数はほぼ取れなさそうなので満点を狙う方針に切り替えようと思い、このバチャではその方針を取った。

まず全ての問題に目を通す、Combo の設定がだいぶ恣意的に見えたので考えてみると 3N+3 回クエリを送る方法はすぐ分かる。1 文字を 1 回で特定できればよいが、4N 文字まで送れることを考えると AA,AB,AX,B を末尾にそれぞれつけたものを送れば 1 文字ずつ 1 回で特定できる。だが、これだと最後の文字を 2 回聞く必要があるため、N+3 回クエリが必要になってしまった。ただよく考えると最初の 1 文字は 2 回で特定できるのでこれでクエリが N+2 回になって満点。まず 3N+3 回の部分点解法を実装して 10 点を取ってから 1 文字ずつ聞く部分を変えて 100 点を取った。(39:10)

Seats は砂の城を思い出すような設定でかなり苦しそうだったので Werewolf を考えることにする。小課題 3 までは簡単ですぐ解けたが、満点解法が分からない。そこで、小課題 3 のように人間のときに行ける場所と狼のときに行ける場所を考えるとそれぞれ Union Find のマージ過程を表す木の部分木になることが分かった。なので、Union Find のマージ過程を表す木をそれぞれに対して構築して、オイラーツアー順に頂点 1 から N を並べる。すると、それぞれのクエリに対して移動することの出来る頂点は列の区間になることが分かる。よって、問題は (1,2,...,N) の順列が 2 個与えられるため、それぞれの順列で区間が指定されて共通要素を持つか？というクエリを処理することになる。この問題は、片方の順列が (1,2,...,N) であるとしてよく、すると片方の順列である区間のうち、値が L 以上 R 以下であるものはいくつあるか？を解けばよくこれは平面走査で解くことが出来る。まず前者パートを実装して帰着後を愚直に解くコードを書く。その後平面走査を書くことで 100 点を取った。(1:07:45)

このあと min R,min C,max R,max C が更新されない場合その前の状態では条件を必ず満たさないことを利用して小課題 3 を取ろうとするが何故か通らない。謎の RE が出てしまいコメントアウトを利用したサブミットデバッグを行うが全てを外しても RE が出る。挙句の果てには問題からダウンロードできるサンプルコードすら RE してしまう。

ジャッジがバグっているという情報を得たので oj.uz で解くことにする。(このジャッジバグによって 1 時間半を失ってしまった。)だがまた RE が出てしまうと思ったらこれは MLE だった。修正するが今度は TLE が出てしまう。頑張って定数倍を詰めて 20 点を取る。この小課題 TL 厳しすぎませんか？(3:47:01)

満点解法を考えるも分からなかった。コンテスト後に考えると 2 × 2 の正方形の白黒のパターン 16 通りについて個数の条件を詰めると解けそうな気がする。ただ証明がかなり苦しそう。

100-70-100 で 270 点だった。満点を 2 問獲得することが出来たが、このセットではその戦法が上手く行くセットだけだった気がしている。