体調がやや不安だったが、特に問題なし。1完に終わったが、座ってるだけではなくDとEを考えることができた。しかし100分ではWAを投げるところまでも行かない。なんか今後2000未満ratedの6問コンテストができるらしいが、ratedでABCのABを解くとしたら嫌だなあ。企業コンでたまにあるけど、うっかりミスでペナ食らったら理不尽すぎる。もちろん、1完でレートが付くのも嫌なので嬉しい変更ではある。
最近コンテスト中にトイレ行くことが多い気がして、コンテスト前に水を飲まないようにしてみた。微妙な策だとは思っていたが。開始直前には緊張で少し出たくなる部分もあった。結局、開始1時間くらいでトイレは行った。我慢はできたが、解ける気がしないので気分転換のような感じで。ちゃんと出た。夕食も控えめにはしてた。
C - Stones
「黒い石のすぐ右に白い石があっ」てはならない。ということは、黒い石がなければOKだし、白い石がなくてもOK。図を描くと、二分探索が使えるための条件と同じだと気づいた（概念を最初から持っているのは強い）。少し考えて区間の黒の個数が累積和で出せればいいとなる。あとは実装だが、ここまで必要なのかなあと思いながら累積和を書きN+1回最小値を取る。思いついた方針に固執することでスピードを出すかよりすっきりした解法を考えるかで大して迷わず前者を選んだ。時間がかかったのはn - i - (a[n] - a[i])のところ。後半部分の白石の数を求めるので全てが逆になってこんがらがる。i個とn-i個に分けているという意識があるとよかった。少し見直して提出。ジャッジが始まるまでに時間がかかったがなんとかACしてた。
D - Three Colors
三角不等式、Rが最大として一般性を失わないか？いや、1色で半分以上取ったらダメで、そうでないならOKということか。合計が大きい順に取るのは、正三角形とかのケースを考えても難しそう。そもそも全体の和が高々9万なのでDPができる（気づくのが遅い）。最終的に、最大の色が半分未満ならOKなので、そのように3つに分ける通り数（575）をDPで求めて6倍すればいい？と、そのDPの更新を考えていたら、三角形の条件がないなら3^Nが答えなことに気づいた（気づくのが遅い）。半分未満の和は大きいようで小さくもなるので3色の中で最大とは言えない。色をそのように固定するやり方とは限らないが、制限が大きく考えづらい。そこで、和が半分以上になる通り数を求めて3^Nから引けばいいのではと思いつく。0になる色が出るケースとかはかなり面倒そうだができそうではある。ただ、DPができない。最初のi個で和がkになる通り数は求まってる。しかし、最初のi個の中からj個を使って和がkになる通り数は300^4になってさすがに無理。残りを2色に分ける通り数が使った個数に依存してるのがきつい。色々考えたがどうやってもDPできない。
E - Polynomial Divisors
DとEを読んで絶対こっちのが面白いと思ったが、20分くらい投入しても先が見えないし、解いてる人も少なくて及び腰になる。
全部の係数の最大公約数を素因数分解して、それは使える。あとは、x(x-1)(x-2)みたいに因数分解できたら3の倍数になる。(x^2+2)とかもxを3で割ったあまりが1,2のときは3の倍数になる。まあNが微妙に小さいし因数分解とかはせずO(N)の確認を何千回かするという程度なんだろう。xに0を入れると、a_0が残るんで候補の素数は簡単に絞れる。10^9以下だから大した個数じゃないしxに1からNまで入れて調べれば十分な気もするが。ただ、それで行けたとしてもa_0=0のケースがある。x^c（cは正の整数）でくくったとして、x(x-1)(x-2)のような影響はあるのでやはり難しい。そもそも、答えが10^9超えることなさそうじゃない？N以下の素数を候補として全部チェックすればいいのでは。チェック方法がわからないけど、x=10^9+7として割り切れるか調べるだけでよかったりしない？f(x)の計算は、a_Nからスタートして、x倍してa_(N-1)を足す、x倍してa_(N-2)を足す、というのを繰り返せばよい。f(x)が巨大な数になるというのも困るが、1つの素数についてだけチェックするなら、mod pで計算するだけ。残り30分しかないしDもEも解ける気しないし、これで実装して終わりにするかと残り時間を見たら残り10分で草ァ！ただのARCだった。100分でこのセットはきついよ。
