開始前36.8、終了20分前36.4、終了時36.1。最近の俺、立ち回りが身の程知らずすぎる。Dまで順調に解いてから、EとFを1秒ずつ見てFをやっていた。しかし、Eは問題文を読めば（これには1分から3分ほどかかる）解き方を知っている問題だった（実装には時間かかるけど）。楽しむという意味では全く問題ない立ち回りだった（Eをどこで解こうがEに使う時間は一緒）が、さすがにもう少し「勝つための立ち回り」をするべきだった。まずEとFを両方読み、片方しか読んでない状態で解法がわかればもう片方を読まずにそれを実装してもいいという感じにしたい。Fに行ったのはxorだからというのもあるし、全完するなら順番は関係ないというのもある。最初に順位表を見たのはEを通したとき。Dを通した時点で見てもよかった。本当に雑すぎる。もうちょっとレーティングを気にしたほうがいい。もちろん楽しむの優先ではあるけど。で、順位表を見たら見たで「Fこれしか解けてないし無理に決まってる」と思ってしまう。体温の低下がそれを示している。コンテスト終了時には「時間をかければ解けそう？」くらいまで行ったので、頑張りたい。まあ小さい可能性に賭けるのは人間にとって難しいので仕方ないとも思ってるけど。今回に関しては、Fにしっかり1時間使ってこれなのでさすがにノーチャンスに近かったか。
昨日は熱があったので負けても「楽しめてよかった」という感じだったが、今日はわりと万全の状態だったので、かなりイヤな気持ちになっている。そもそも、前回も今回もレーティングの期待値を最大化する立ち回りを仮にしていたとして、それが成功してもレーティングは減ってたんだよね。根本的に問題が解けてない。狭い場所で解ける問題だけ解いてる感じだ。
A - Red or Not
「低いほうがred！？」と思った。一応指示通りに実装しサンプルも通って、改めてよく見るとこれはレッドコーダー前提の問題だ。色を自由に変えられるかを問うている。言われてみれば3200は赤と橙の境目じゃないんだけど、なかなか気づかなかった。
B - Resistors in Parallel
一応0除算とかに気をつけながら実装。
C - Alchemist
サンプル2の説明を見て、「最初に小さいの同士を合成するといいのかな」とややキケンな判断をする。これはたぶん正しいんだけど、最初に1個のサンプルから思い込みを持ってしまうのはこわい。まあ大きいやつの寄与を大きくしたいのでこれでいいはず。ただ、今証明を考えてみてもできない。頭が悪い。
D - Ki
各頂点から見て何が足されるかを考えると、DFSの通り道にあるクエリたちということになりけっこう簡単だ。使う変数（メモリ）を減らせそうだと思ったけどまあわかりやすく解けてるのでこのまま。サンプル2が親切で助けられた（考察を進めるうちに、同じところに何度も足すイメージが失われる）。
E - Strings of Impurity
簡単すぎてびっくりした。O(|S||T|)でいいならやるだけ。そこから高速化する方法も典型。ただ実装はそれなりに大変。sの各位置と英小文字の集合の各要素について、その位置から見てその英小文字が次に現れる位置を持つ。ループがややこしいので、sの2倍の長さにしてループを消す。「次に現れる位置」には2種類あり、現在の位置に現れるのを含めるかどうか。あやしいとは思っていたが、これに明示的に気づいたときには実装が進んでいたので実装したほうでそのまま進めた。まあこっちのが簡単かな？位置の初期値をn-1にするときれいに書ける。sを2倍にすることで次の文字までの距離もただの引き算で済む。位置の値だけN未満に維持する。
F - Coincidence
y/x==1&&(y|x)==yという条件が見える。xをxorすることによる増減は+xから-xまでと気づく。あるx視点でx以上x*2未満のy候補を考えると、yがxと同じ桁数なら簡単で、違ったらよくある桁毎に見るやつ。でもxを全探索できるわけじゃないんで、ここで詰まってEへ。
逆にy/x!=1&&(y|x)!=yとか求まらんか？厳しそうだけど別の視点も得られる。y視点を考えてみるがそれも無理。（あるkを固定して）k桁のペアはいくつあるかを考える（これはもっと早く思いつきたかった）。xとyは同じ桁数であることに気づく。yが桁数多いと、xにあるビットの他に上の桁のビットまであるので必ず2倍以上になってしまう（これがなかなかわからないのは感覚がにぶい）。あとはyの最上位以外の立ってるビット数がi個のものがkCi個でそれに対応するxが2のなんとか乗でとまとめて計算できそう。LとRで切られるのが大変。2進法で101000以上101100未満のxの相手のyの個数は、下2桁の0の個数によってさっきのk桁のときと似た計算ができそう。LとRが同じ桁数のときは考える時間がなかった。
