AGCと比べれば緊張しないよねーと言いつつ、Cを読んでトイレに行った。少し前にも行ったんだがなあ。ただ、やはり気持ちはふわふわしていて、1時間以上経過して2完で終わる未来が見え始めてもそんなに焦りはなかった。それがいいかわるいかは置いといて、いい面は「2完でレーティングを落としてもそれはそれで」という気持ちだったことで、たまたま失敗しても今回は過剰に落ち込んだりしないで済みそうだと思っていた。まあ、そういうときって、悪くない立ち回りができてしまうわけで、残り10分を切ったところで600点を通すことができた。ABDの3完でレーティングも上がった。
A - Regular Triangle
ちょっと面食らう問題文。「さすがにこれより簡単には書けんよな」と思いつつ普通に書いて提出。ジャッジが終わったのがB問題より遅かった。
B - Red or Blue
珍しく簡単なB。'R'の個数だけ数える方針にした。
C - Snuke the Wizard
ここからは、いつものように3問を並列に考える（解けそうになったらそれに注力する）。まずCを読んでトイレで考えて、Cの難しさを垣間見て帰ってくる。10分は使ったが何も見えない。
左右どっちで消えるか分けて考えるとか、逆から見るとかしたけど、できそうにない。一番左にある文字にLが来たときしか排出されないので、そのクエリで区切れるなとか。移動すると複数のゴーレムが重なるけど、その様子が全然整理できない。しかも左右両方に動く。これは無理だった。
D - Modulo Operations
O(2^N)以上かかるDPはわりとすぐ思いついたけど、N<=200という微妙さだし、そこから何も進まない。
2完を覚悟して最後に。Eはできなかったし、Cは点数が低いし、Dはある程度解かれている。ということでDに取り組んだ。Sは降順にソートしておく。今までに使ったS_iより大きいのが来ても、黒板に書かれた数xは変化しない。使うS_iは単調減少だし、何番目に現れる何番目の数が何通りとかわかるかもしれないし、DPできるかもと思った。しかし、max(S)が最初に来るのが何通りとかはわかっても、他はさっぱりだし、なかなかこのDPが通る未来が見えないという気分になってきた。
それでも解ける可能性はけっこうあるという気分だった。Nが一つ小さい問題に帰着させる方針を探って、実際に解けた。最近よくやってる方針な気がする。S_0を使うのは、S_0が先頭にある(N-1)!通りで、そのケースはXをX%S_0に置き換えてS_0を削除した問題が解ければいい。そうでないときは、当然N!-(N-1)!通りで、XはそのままでS_0を削除した問題が解ければいい。いつもの再帰を書く。サンプルがいきなり通る。もう時間もないし提出するか？いや、これはTLEの危険性がある。再帰で2つに分岐しているから、これをN回やったらO(2^N)になりかねない。メモ化再帰にすれば大丈夫そう。ここで、メモの存在をどう判定するかで悩む。偶然0になる可能性は否定できない。-1で埋めれば大丈夫だろう。ここで、コーディング時間を優先しmemsetを使った。memsetは1byteの値を埋めることしかできない（intの配列を全部3にするみたいなことはできない）。しかし、0か-1であれば問題ない。ただ、当然のように知っている事柄とはいえ行儀は悪く実際に書いた経験も少ない。不安はあった。提出すると、RE。WAもある。うぇ。しかしREがあるなら単なる範囲外アクセスのミスとかの可能性が高い。見直すと、DP配列のサイズが10001だった。100001に直して提出、AC。体が人権で満たされる音がした。
E - Black or White
有理数を答えるのはWTFのEで見たやつだ。かなり簡単そうに見える。両方残っていれば1/2にしかならない、というのがやや非日常的で、人間界の生活に慣れすぎた自分にはわかりづらかった。片方がなくなれば残ったのを取り続けて終わり。ここで、「白がi回選ばれる前に黒をB回選ぶ確率」を考える。これがわかれば、B+i回目に白しか出ない状態になってる確率がわかる。さて、普通に二項係数で考えるが、たとえば白が2回出る前に黒が3回出る確率を考えると（頭が弱いので具体例で考える）5C3のうち黒で終わるのはダメで白で終わればOK？で、5C4とかはOKだし、5C2とかはダメ。
しばらくして考えると、「白をi回以下しか選ばないうちに黒をB回選ぶ確率」でB+i+1回目に白しか残ってない確率がわかり、それは単に5C3+5C4+5C5じゃないかと。なんでシンプルになったかわからず混乱。まあ、片方が空になっても黒が空になるという結論に変わりがないルールだし、問題ないよね。んで具体的に確率を計算する。パスカルの三角形で考えると、でかい正三角形（B+W）の下のほうに2つの正三角形（BとW）があって、それぞれ0,1/2,1の重みがあるという感じ。細部はともかくとしてこれで解けたと思ったが、よく考えるとこの三角形の面積はO(N^2)だしまとめて計算する方法は浮かばない。毎度のことながら、問題の核心に達する*1のが遅すぎる。この問題はめちゃくちゃ混乱して頭が熱くなっていた。
*1:「到達する」の「到」を削除しても送り仮名成立してるの面白いね
