1週間前の精神ダメージがまだ治り切らず、まあ普通ではあるものの頭が悪く、つらかった。AGCでも結果が出せないようであれば、もうベースの頭の働きが一段階落ちてしまったということになり（なるは言いすぎだが気分的にはそう）立ち直れなくなる。持っている力は発揮したいと思っていた。昼間は競プロの復習を少しやって、夕食も食べすぎず、その後はアニメを見てリラックスしようとした。あと、コンテスト前の数時間は禁ぷよする。考察のために目を瞑ったとき、ぷよが浮かんでしまうから。爆死しても死ぬわけじゃないと言い聞かせ、淡々と解くことを目指した。DPが苦手なので、どうしても解けないならDPを考えてみる。頭が固いので、色々な角度から考えようとする。ラムネも用意して電池切れを防ぐ。体温は、開始時36.9、Cを通したあと37.0、終了時36.4。
A - Colorful Subsequence
この部分列は連続してなくてもいいやつ。「すべて異なる文字からなる」「正の個数」という条件がないなら2^Nが答え。異なる文字って条件が見慣れない。200点というわりに難しいじゃないか。だいぶ経って、26通りのそれぞれの文字について文字数をカウントすればいいのではと思い至る。高々1文字しか取れないので、どこから取るかとどこからも取らないのを掛け算していけばよさそう。やや考察が雑だが、これで通らないなら200点じゃないということで提出、AC。取り組み方が雑。今回は他の問題も含め考察の詰め方が雑だった。
B - Reversi
例によってBとCを交互に考える。どちらも全く解ける気がしない。これを160分かけて解かしていくのだ。全く解ける気のしないものが解けるという経験は何度もしている。先が見えないのはきついが、行こう。
無理を言われているように感じていたが、思ったよりは単純な状況だ。塗る範囲は被らない。塗り方はたくさんあるけど、重なる部分がないようにしか選べない。含まれたり食い込んだりしないというのは希望が持てる。まあ色々いじっているうちに、かなり時間が経ってたけど、†DP†を思いつく。同じ色は何度も現れるから扱いは難しそうだけど、重ならないという性質はまさにDP向きな気がする。DP苦手だしC問題のほうが好きなタイプなのでわりと後回しになった。CをACしたときやけに順位がよくて、みんなBを先に解いているようだった（100点差ではるか上の順位になるというずるいやつ、多少それを狙ってもいた）。想像ほどは厳しくないDPな可能性が高いと思い、適当に詰めていく。あとから考えれば正しそうだが、当時の思考はほんとに適当。同じ色が連続するときとか、そう処理する必然性がわかってない。同じ色がたくさんあるやつは、各区間のオンオフとして自然に（ここは最後よさげになったかな）。
というわけで、まさに苦手なDPだった。DPを意識していたことが生きた。感触としては、「やっただけ」。ちゃんと解けてた感じはあまりない。クソムズ700点と見せかけて自分以外はDPで解けてるというのをAGCでやられるとつらいけど、今回は回避できてよかった。
C - Differ by 1 Bit
こういうの、なんかあった気がしたけど、「グレイコード」っていうやつだった。ただまあ、知らなくてよかったかもしれない。グラフとして考えるのも思いついたが、これは「ハミルトン路」。これは知ってたら「名前が付いてると考えやすい」という効果はあったかも。結果的には、そういう用語は関係ない解法になった。AGCらしさがある。
まず、000から111にするのも難しい。途方に暮れる。立ってるビット数の偶奇が重要そうだと気づく。ABの偶奇が一致したら無理ということは、そうでなければできるという雰囲気がある。立方体を描いてみる。すると、けっこう簡単に経路が求まる。次元が高くなるほど簡単になりそう？3次元までしか描けないけど（無理すれば4次元は描けるが）。000を111にする方法はたぶん存在してたので、最初の001という動きを010にしても一般性を失わず違う結果をもたらす、たぶんこの問題は解法が存在しそうだという感触を得る。ただ、まだ実装は不可能な感じ。手で色々試していく。A,Bを0,AxorBとできるのは気づいていたけど使わなかったな。
2冪に分解しながらクルクルとってイメージはあったが、単にNが1小さい問題に帰着させることはできないだろうか。Nが1のときは可能だし。全て可能と仮定すれば行けそうだ。当時は証明せずにやってるつもりだったが、可能なら可能やんけ（本当にわかっているか疑わしいですね）。さて、全部可能だと仮定すると、AとBで最上位ビット（2^(N-1)）が異なるときは、（以降、ABCは最上位ビットが立ってない、1AはAに最上位ビットを足したものとする）AともBとも異なるCをとり、A...C, 1C...1Bと変化させることができる。A...Cと1C...1BはNが1小さい問題に帰着できている。最上位ビットがどっちも立ってないときは、まずN-1の問題でA...Bを生成しAの次の数をCとして、A, 1A...1C, C...Bとすればいい。両方立ってるときとかは全体に2^(N-1)をxorすればいいので、面倒ではあるけど解けていそう。結果的にはそこもきれいなソースにできた。
立ってるビットを数えるのにpopcntって関数を書いたけど、popcntという言葉を自然に知ってるのはコンピュータ将棋クラスタみある。
D - A Sequence of Permutations
イメージというものが頭の中にない。つるつるしていて手を引っかけることができない。このシンプルな問題で1000点というのはすごい。解きたいなあ。Nが10^5だから、シミュレーションも100回かそこらしかできない。シミュレーションは戻すこともできるなあ。ただ、何個かおきにという操作はできそうにない。対称群のWikipediaを開いたあたりで時間になった。時間が余っているようでも、やはり最後にはもう少し考えてみたくなる。
