5時間のバチャで、MとOが解けなかった。0-indexedにし忘れで時間食うとかしょうもないミスがけっこうあった。
A - 中央値
値ではなく名前を答える。名前が連番なので、ソートで中央値を求めてその値が何番目だったか検索した。
B - 電卓
切り捨てなので整数除算で100倍してto_stringから小数点を挿入すればいいと思った。しかしWA。0.11が.11と出力されてしまう。そこで整数部と小数部を別々に作ったが0.01が0.1になってしまいWA。足りない0を挿入するようにしてようやくAC。こんな問題で貴重なバチャの時間を10分以上浪費するのはクソ。
C - 隣接カウント
周囲にパディングを入れて各マスの周囲3*3を見る。
D - 分身
この位置の問題にしては考察がきつい（と思って解説見たら全探索だったでござる）。一番左から3マス連続して空いていたらxは3以上、みたいな条件がわかって、右も同様で、他の空きマスは左右どちらにも忍者がいるので操作回数に応じて空きマスの区間が狭くなる。よって、端を埋めるために最低限必要なxとyを求めそれでも埋まらない空き区間があればそのぶんを適当に足す。実装もそれなりに高度。
G - 村整備
全探索。連結判定はUnionFind（BFSはスピード出して書けない）。
H - マス目のカット
二次元累積和を持って全探索かなーと思って計算量を確認したら愚直が間に合って草。正方形を調べるときは各数字をカウントして一番多いものに変えればいいので、数字の種類数は実行時間にあまり影響しない。
I - ピザ
しゃくとり。丸いので配列は2倍にする。XがYより小さいケースも考えないといけないのでXを変化させるとき常に最小値をとっていく。片方を固定したときの最善を必ず拾えていることを確認する。
解説見たら、XがYより小さいケースは考える必要なかった。そりゃそうだ。頭が固い。
J - ワープ
それっぽい問題出てきた。ダイクストラ法に一工夫するやつ。ワープ用の頂点を3つ追加してコスト0でそこへ行けるようにする。ワープ用の辺をコストX_ABとかで追加して、コスト0で帰ってこれるように。しかしサンプルが全然合わない。ワープ用の頂点を介して同じワープ台を持つ町の間をコスト0で移動できてしまう。ワープに入る用とワープから出る用の6つの頂点が必要だった。
K - 転倒数
10^9+7じゃないの不安定になる。aの値が20種類しかないので、K個の数列の転倒数はBITとかを使わず個数カウントで求める（どっちが速いんだろ）。その転倒数はクエリで数列が連結されるときに足して、更にたとえば3が100個含まれていたら3より大きいものがこれまでに何個あったかを調べて掛け算（ここは大きい順にやれば累積和を順に計算できる）。けっこう重かった。
L - マンションの改築
難しそうだが、よく考えると高さを比較するのは常に番号が奇数と偶数のマンションだ。高さが等しい個数を毎回出力するのだが、これはつまり増分が奇数のほうが100多かったら隣り合っていて最初偶数側が100高かったものがカウントされるということだ。mapを使って各差の値が何個あるか数えておけばいい。一つのマンションの高さを増やすクエリもあって厄介だが、両側の差を消して新しい差を入れればいい。
M - 筆塗り
面白そう。LCAを求めて葉から塗っていくイメージはあったが具体的な方法が見えない。逆から見て既に塗ったところをスキップするのと、いもす法みたいに端だけ情報入れてmapで拾って合成しながら時刻最大のやつで塗っていくの（計算量が全くわからなかったけどダメっぽい）を考えた。面白さを15分ほど堪能して次へ行った。
LCAをやれば、ある頂点から親へ指定回数移動する（塗りながら）という処理になる。スキップするために親を変えるのは上手く行きそうに見えて全部張り直さないといけないから計算量がダメなんだよね。で、Twitterとか見てた影響もあると思うけどUnionFindでまとめてこいつらの親はこれですとrootの番号に持っておけばいいと気づく。いや気づいたというより、理論上はこれでできるけど感覚的にはこんな場所にいいものが残ってるわけないという感じ。実装はかなり時間をかけた（時間をかけたというか何もせず悩んでいたというか）。辺のインデックス持ってないといけないしな。解説と同じやり方だったの微妙にがっかり（解説からもっと得るものがあると思ってた）。
N - マス目の穴埋め
2行ずつ見ていくDPがわりとすぐ見えたが、なぜ思いついたのかもなぜ正しいのかもよくわからない。まあ苦手なDPも青コーダー並にはできるようになってきたということかね。2行の上が確定で下は中央値の条件を満たすかまだわからない状態。更新は3行ぶんのパターンを全部見て上2行から下2行へ条件を満たせば足す。入力で与えられた条件と中央値の条件は前計算しておく（2^(6*3)のループ内でO(1)判定できるように）。実装にかなり苦労して50分くらい使ってしまった。
O - 宝箱
簡単そうに見えてふわふわと逃げ回るような問題（これは問題の性質というより自分の性質だが）。何でDPするか、lとrどっちでソートするか、組み合わせは無限大な状況の中針の穴を通すような考察で解法を探さねばならない（これも単に問題に対して力不足なだけ感）。時間内には解けなかった。最終的に解けたのは、rでソートして鍵屋iを最後に使ったときの最大でDPというもの。aの累積和を持ち、新たな鍵屋のlでこれまでの鍵屋のrを二分探索、以前の鍵屋が開けた宝箱と被る場合は予めrに応じて差を付けセグ木に入れておいたものから最大値を知り差を補正する、それより前の鍵屋は累積最大値を持っておいて今の鍵屋のぶんはフルに足すだけ。解き応えあった。
