5完。楽しめる問題がない。Fは面白いけど自力では何もできなかった。Eをちゃんとやり切って、Fに30分以上残せたのはえらい。
A - September
サンプルが合わなくて、存在しないNを受け取っていた。12個って読んでたけど速攻で忘れてたね。
B - 1D Keyboard
逆引きを作らず毎回forで位置を求める。実装量を意識。
C - Max Ai+Bj
簡単すぎて意味がわからないが、i,jを一緒に全探索すると間に合わないということだと察する。別々にやっていいことを慎重に確認して実装。
D - Hidden Weights
連結成分毎に。1個決めれば他も決まる。逆辺が必要であることに気づいてなくてサンプル合わなかった。有向グラフであるという思い込み。サンプルと比べて、連結成分毎に定数の差になっていることを確認して提出。
E - How to Win the Election
難しかったので順位表を見たら、EFGがほとんど解かれていない。Dまでがかなり簡単だったので自分が早解きできていて、Eが難しかったためいつもより早く順位表を見て、そりゃあそうなる。FGを（ちゃんとは読まず）見て、FもGも難しそうなのでEを考えて、Eが一番いけそうなのでEをやった。これで自分がちゃんと解けるようなら、そのころにはみんなも通しているというのがいつものパターン。
全員同じ得票数なら全員当選する設定だが、それが明示的には書かれてないので不安になる。Aでソートする（インデックス付き）。コンテスト中は意識できていなかったが、落選させることができるかというイメージの問題。M人が自分より多く票を得ていたらダメ。自分以外の得票の多いM人に注目し、そこに票を入れる（他に入れるより効率よく落とせる）。二分探索できそうだ。そのM人は、最初のN-M人について考えるときは固定でいいが、より得票数の多い人を考えるときは順次入れ替えていく。実装上、長さMではなく長さNのvectorで管理する。累積和も必要そうなので書いていたが、めんどそうなのでBITにした（あとから考えると累積和は更新箇所がO(1)個では済まないのでBITにしてよかった）。二分探索内で、自分の票数以下の区間を二分探索で見つけ、そこの和から落選させるのに必要な票数を求め足りるか判定する。
（追記）書き忘れたが、N=Mのときは簡単なので場合分けしておく。票数の多いM人を入れ替える処理で、N=M=1みたいなケースで範囲外アクセスしちゃうなと思っていたが、この場合分けによって入れ替える対象が必ずいることになり、もやもやが解消された。範囲外アクセスに対応して済ませるのはよくなくて、なぜ自然な実装で範囲外アクセスが起こるのかまで解明しないと安心して実装できない。
F - Knapsack with Diminishing Values
k^2の項がなければ簡単（in-placeで逆順にしないでやるやつ）。それを書く。遷移の系列毎に何かできないか考えるが、2乗なのが厄介で最大値の計算を使い回せない。色々考えたが、この方針から抜け出せなかった。遅延セグ木も思いついたが、終了後に考えると区間maxと等差数列加算の両立が無理そう。
終了後、調和級数と聞いても何も思いつかなかったし、同じ重さを同時にと聞いても「どれを何個使うかDPしたら間に合わなそう」と思ったし、難しすぎる。ただ、w_iが大きいときO(W)で更新できることには気づきたかった。気づくというか当たり前なんだけど、「何にでも使える平方分割を頭の中でちょっと試す」をやっていたら意識していたはず。そっち方面にも行ってみるべきだった。
G - No Cross Matching
（追記）あまり考えてない。解説みて実装がしんどそうだったので、一番楽そうなやつでACだけ取った。解説読んでると、交差しないようにするのはけっこう簡単らしい。交差してる2つの線分があってRを入れ替えて交差を解消したら長さの和が減るということだが、証明がわからない。図を描くと明らかに減るし、解説でも三角形で説明されているが、その位置関係に必ずなる確信が持てない。幾何の証明できないなあ。で、それを認めると、交差を解消する操作を繰り返せば有限回で交差がなくなるのは明らかに思える（長さの和は高々N!通り）。あとは実行時間が間に合うかだが、間に合いそうには思えるが、証明どころかそれっぽいイメージもできない。
