3完。3問目をガチのスピードで解きに行けるようになりたいね。
C - Attention
WとEがどっちの向きを指しているのかわからない。もちろん少し考えればわかるけど、問題を解くうえで何度も使う概念、思考を要するようでは話にならない。さすがに問題文に東西がわからん人でも解けるよう説明があるはずと思い数秒探したが見つからず。今見たら「西から i 番目」と書いてあったのでこれでわかりますねー。やはり先週ほどではないけど体調は万全じゃない。落ち着いて「ギューン」と考えたいね。
300点にしては難しいという感覚。とはいえ時間をかけて問題を見ていれば、累積和があれば（牛刀かもしれないけど）解けるとわかる。300点だから思考停止で解けるのだ。そのまま深く考えず実装した。
D - Xor Sum 2
怖い問題名（1はまだ解いてない）。条件はどんなのかすぐわかった（O(N^2)でよければすぐ解けた）のだけど、そこからがやはり難しい。少ししてAが20bitで表せる制約なことに気づく（思い出す）。難しいのでその制約を足がかりにアイデアを出し、20個の各bit位置に対して直近の現れた位置を記録していく方法を思いついた。Aをなめていって、現在の位置を終端とする通り数を求める。直前の被ったbitがある場所の次から全部が条件を満たすはず。
実装したが、サンプルが通らない（サンプルに助けられた）。しばらく考えて、現在の位置と被るかしか見てないのはダメだと気づいた。真ん中に衝突してるペアが含まれてたら当然ダメ。なのでそれをとりあえず書き足した。衝突はその都度記録できるはず。衝突したペアの若い番号のほうの次からOK。サンプルが通った。今回は即座に提出した。AC。自信はなかった。ダメだった原因の一つを潰しただけだから。
と思ってたらしゃくとりで行けたらしい。はー。
E - Range Minimum Queries
いくつかの例を考える。333331333332333313333（3で揃える）、634193341431499（1で揃える）。こういうのをどれも解けるような解法でなければならない。やはり難しい。かなり考えてから、また制約を頼りに（あまり行儀のよろしくないメタ読みで）解法を探る。Nが2000なのでO(N^2logN)になりそうだ。tourist回のbitDPもちょっと思い出していた。2乗だから3乗の解法を2乗に落とすか、あるいは2乗も色々な方向が考えられる。
色々考えて行けそうな方針が出てきた。最小値（Y）をN通りに固定すると、それより小さいAで全体を区切れば、その区間内で小さいものから順に取ることは可能（「最小のものを取り除く」からね）。このときは、固定したY=A_iが最小だから必ず取れると思っていたが、Kより狭い区間に入ってたらダメだ。狭い区間からは取れないのわかってたのに、そこにすべてのYがあるという状況を考えられなかった。まあそこは b[q - 1] - b[0] と書いてたので問題にならず（b[0]をa[i]と書いていたらWAになるところだった）。
実装上の工夫として、区切って区間にする処理をするためAのvectorをN+2の長さとし、両端を-1にして必ず区切りになる番兵とした。あとそういえば最近、初期化する必要がない変数もわかりにくいバグを恐れて初期化するようになってきたな。
計算量は、全区間でソートしてもO(NlogN)以下で済むので大丈夫。実装はけっこう面倒で、元のAを壊してはいけないのでコピーしてソートになる。空のvectorにpushしていくのを考えたが、実行時間が気になる。reserveしても使ってからclearしたら解放されちゃう？一応N個のpush_backはO(N)なんだっけ？頭の中ではもう（定数倍も含めた）計算量のイメージが出来上がっており、それを変更するのはかなりの負荷になる。なのでメモリは最初に確保して自分で管理する実装にした。この実装はパターン化されているので速いしバグも入りにくい。小さい数をかき集めたら、改めてソートしてX-Yで最小値を更新する。長い長い実装だったが、ある程度の時間を残して書き切ることができた。
F - Donation
まあ解けないと思って読んでるわけですよ。残り時間もないし。ARC全完ってそれがそのまま早解きなんだなーって思う。早解きできても難しい問題が解けるとは限らないが、難しい問題をコンテスト中に通す人は早解きできている。
色々考えて、逆からやるとよさそうだなあと思う。逆から見れば、寄付はその頂点に初めて着いたときにするとしていいし、探索とかするのにもA円の制限は頂点に着いた時点でWを調節すればいい、お金は増える一方だから同じ頂点は何も考えず再訪できる。まあしかし、どこからスタート（ゴール）するのとか全然わからんしね。Bだけで決まるわけでもないし、A-Bみたいな量を使ったりするのかなとか思ったけど。まあO(N^2)が通らない制約なのでなんか上手いDPをするんだろうなという感じ。
