体温測り忘れた。15分くらい経ってるけど36.8。
A - Connection and Disconnection
1回と2回の差を求めて掛け算するだけ系に見える。連続してX回同じ文字があったらX/2回必要。さて、本当に3回目以降も同じ増え方なのか？Sの最初と最後が同じ文字のときに現れる同じ文字の区間があるけど、それは1個でも違う文字があればそこで切られて3回目以降も同じになりそう。そうじゃないケースは簡単なので場合分けしてしまう。コードがかなり複雑になってしまったが、なんとかACできた。
B - Graph Partition
問題文の1行目を5回くらい読んでた気がする。問題文読むのほんと大変。問題を把握するのに5分以上かかった。有向だったらトポロジカルソートっぽいなと思った。最大値を与える向きがわかってたとしてどうするかとか考える。ダメそうなので普通に。二部グラフである必要があるのはすぐわかる。色々なグラフを考えてみるがよくわからない。グラフが木だったら簡単だ（直径より大きくはならないし直径は達成できる）。問題は偶閉路があった場合、それも複数あった場合だが、どう考えていいのかさっぱりわからない。例をいじっても何も出てこない。二部グラフを保ったまま変な辺を加えたら一気に縮こまっちゃうしな。Cも読みつつ21:45くらいまでBメインで考えていた。
C - Division by Two with Something
残りの100分ずっとCをやっていた。まず実験をしてみた。N=8の場合、256通り全部16。偶数の場合は簡単なのか？N*2だ。「本当に元に戻るのか？」と思わせといて1bitずつ反転させながらrotateしてるだけなのでN*2回かければ戻ると気づく。他も色々試すとだんだんわかってくる。もっと短いループもあるよという話だ。000111000111000みたいなのは周期3で同じのが交互に並んでるので3*2回で戻る。000が5回でなくとも、101が5回でもいいし、長さ3なので2^3通りが全部同じことになる。少しずつだけどけっこう考察が進むからずっとやってたわけだ。
こういうのは「X以下」より「X+1未満」のほうが考えやすいので1を足す。といってもXは20万桁だったりするので面倒。まあこのくらいなら簡単に書けるのでとりあえず書いちゃう。問題はN+1桁になってしまう場合だが、キャリーフラグをとりあえず持っておいた（結果的にそれでよかった）。N+1桁必要なのが不自然にも感じるけど、こういうのは2冪個ずつ処理するので、2^0から2^NまでN+1通りと考えればまあ。
実験していて他のパターンがなさそうなのでこれでやってみる。周期（ブロック長と呼んでいた）をMとして、N=M*奇数 となるものを見つける。計算量的にNの約数の個数が気になるが、「高度合成数」でググって（けっこう時間かけて）最大で160らしい。なんかNとlog(N)を混同していたみたいでNlogNとかメモしてあるけどN^2のことかな？計算量がきつそうだと心配していたけど、約数毎に上位j桁を見るのをjが小さい順にやっていけば、（約数毎に）O(N)で済む。約数のこういうのはyukicoderか何かで最近やった。周期Mは周期M*2とかにも含まれるのでそれを引いてしまう。例えば周期6なら、周期2と周期3と周期1を引けば、6未満の周期を持たない周期6だけが残る。これは逆に約数を小さいほうから見ていき、そういう周期を持つものが何個あるかを求めて、その約数のN以下の倍数から個数をマイナスしておけばいい。
さて、問題はその個数だが、2^N未満の全部ならわりと簡単で、M*2回以内で戻るものが2^M個ある。パターンとしては、例えばX+1が10011だったら、0以上10000未満と10000以上10010未満と10010以上10011未満を足せばいい。これはできそうだ。周期Mを調べてて上位j桁が確定してるとして、j>Mなら確定部分が周期になってたら1通り、j<=Mなら2^(最初のMbitのうち確定してないbit数)通り。確定部分が周期になってるか確認するのは順番にやればO(N)。個数の変数を小さい約数たちからもらったマイナスにして、足していく。それにM*2を掛けれたものを足していく。ん、もう解けてるのでは？サンプルを試すが落ちる。約数を探すときNと偶奇が一致する必要があるのでn%2を初期値にしていたが1+(n+1)%2とすべきだった。これで落ちなくなったが、しかし微妙に合わない。8多かったり少なかったりする。
この時点で23:00くらい。実装にめちゃくちゃ時間かかった。デバッグが全然できない。仕方ないのでソースコードを最初から丁寧に読み直す。しかし誤りは見つからない。なんか、（周期1でなくて）周期2でも周期3でもあるみたいの存在する？いやないよなあ。ちょっと自信なくなる。終了2分前くらいに気づく。10000以上10010未満を調べるときの確定ビットは1001?ではなく1000?だ！適当にソースを直すがこの残り時間で全然できない。終了後2分くらいで修正できたが、提出してWA。うーんコンテスト終了直後にACする実績解除したかった。コンテストが終わるとね、結果が確定した終了時と比べてどんどん落ち込んでくる。しばらく考えていたがわからず、ブログを書き始める。するとわかった。奇数と言っていた部分を奇数かチェックしてなかった。なまじNと約数の偶奇が一致する必要があるとか気づいたのがなあ。当時は解けてなかったからどんな情報でもメモしていた。そして、一から見直すべきだったのはソースコードではなく考察部分だった。そういうこともあるんだねえ。とはいえ、自力ACできたのはよかった。（終了直後は「まあそんなこともあるか」という感じだったのに）相当落ち込んでイライラしていたので、最低限それができてよかった。
