リアルタイム受験した。O以外を通して94点だった。今回は前半の複数の問題にはまってしまって、辛うじてエキスパートという結果だった。
G - 一日一歩
素直に考えると最短経路問題を解けばよくて、通りたい道の直近で通れる日はRMQ上の二分探索で突き止められるが、Gでそんなことする必要がある？ と悩んで時間を消費した。結局、最初に考えた通りに実装した。
H - カンカンマート
$T$の値によって2列にわけてどちらも昇順ソートして、$T=0$をできるだけ取るような構成にしてから$T=1$をひとつひとつ増やしていけばよい……のだが、それが見えずに三分探索などをして時間をかなり消費した。
L - 都市計画
道路の端点がタワーか環状交差点上になければならないという条件を見落としていて、解ける問題に見えなくて困っていた。
M - 等しい数
似た問題をCodeChefで解いたことがあったにも関わらず、長時間はまった。CodeChefの問題は平方分割で解いたのだが、実装が大変だった記憶があるし、この問題のほうがハッシュテーブルへのアクセスが多くなりそうだし、制約も厳しいし、ということで平衡二分木で解くことにした……のだが、複数箇所でバグらせてしまった。
区間を平衡二分木で管理するやつを改造して使うことにして、手持ちのものはmapではない（区間に対応する値がない）ので、区間$[l, r)$に入っている値は別に用意した配列の位置$l$に保持することにしたのだが、それが間違いだったかもしれない。区間の分割・消去・挿入などの操作間で、区間に入っている値を正しく保つための処理が複雑になってしまって、手におえなくなるところだった。
N - 活動
順番を固定できればラッキーと思って調べると、$a_i/b_i$の降順でソートしてよいことがわかるのでソートしてDPする。（しかし、最後の活動の取り方を素朴なDPで正しく扱えているのか自信がなかった。）
O - 最短距離クエリ
先に開いて少し考えたがわからなかった。似た設定の問題としてUTPC 2011 - 巡回セールスマン問題があったのを思い出したが、そもそもこれも解けていなかった。
