6完。黄パフォとれてよかった。コンテスト前に自分のレーティングを確認したとき、最近こんなに黄パフォ多かったんだなって思った。レーティングが1950以上になってるんだからそりゃそうだ。
A - Counting Passes
言われたとおりに実装。問題文をほとんど読んでいない。サンプルが通ったら問題文のページをもう1回ざっと確認して提出。46秒しかかかってないので、そんな感じ。
B - Minimize Abs 1
ぐにゃぐにゃ動く変数がXYの2つも出てきて全然数式が読めない。添え字のiがあったりなかったり、そもそもどこで登場した変数かわかんなくなる（1個確認してるうちに他の1個を忘れる）。各A_iについて、近くにXを置きたい。これはclampだ。XとYが動く範囲同じなんだねえ。今にして思えばXの距離をできるだけ小さくすれば他に答えはありえない（一意って書いてある）。実行時間が思ったより長くてびっくりしたけどIO高速化忘れてた。
C - Minimize Abs 2
まあ全探索しましょう。xとyに大小関係を入れてもいいが、無しでやったほうが楽と判断した。最初、非負整数は1以上だと思っててやばかった。xを全探索する。最小値を与えるxについてx^2がDを超える可能性もあるので、超えたのを探索したらループを抜けることにした（D以上だったら抜けてよかった）。相手のyはsqrtで求まる（10^12くらいの整数はdoubleで厳密に扱えるのでsqrtも多分大丈夫）。切り捨てて、1大きいのも試す。sqrtの中身が負にならないように注意。気をつけるべき点が多くて大変。
D - Counting Ls
この三つ組には「軸」が存在する。条件を満たすものを構成すると、そのうちの一つの'o'であって同じ行にも同じ列にも（その三つ組内の）別の'o'が存在するものがちょうど一つ存在する。それを軸と呼ぶことにする。あとは、各行・各列の'o'の個数を前計算しておいて軸を全探索するだけ。答えはO(N^4)になるので64bit整数に収まる。計算量O(N^2)で、掛け算まではintでできる。意外と簡単だった。
E - Mex and Update
mexだけど、一番簡単なやつ。Aに含まれないN以下の非負整数をstd::setで管理する。Aと、Aに含まれるN未満の非負整数それぞれの個数を管理して、個数が0かどうかが変化したときsetに出し入れする。set使わなくても解けるんだねえ。
（追記）setを使わない解法。「ない数」をpriority_queueで管理する。削除はできないが、topがない数じゃない間popし続ければよい（pop回数はpush回数以下なので計算量も大丈夫）。segtreeを使う場合、最小値を求めるやつで、ない数のところだけその数を入れて他はNを入れる。全体の最小値が答え。
F - Minimize Bounding Square
図を描いて考える。その図とは別に、xy独立に考えられることに気づく。改めて図を見て、xy両方の方向に動くものを分けて考えていたことを思い出し、「うそだろ」って言った（図があてにならないやつ）。とりあえずxyそれぞれソートしていい。移動コストを観察すると、端（両端）のものはコスト1で点の存在する区間の幅を1小さくできる。その1個内側の場所からは、コスト2になる。ブルアカの神名のカケラみたいだと思った。中心をどこにしてもこれよりコストを下げる方法はなさそう。つまり、区間が（長さ0のものも含めて）N-1個あり、1,2,3,4,3,2,1みたいにコスト倍率がかかってる。倍率毎に区間の長さの和（そのコスト倍率で減らせる幅の最大値）を持っておく。二分探索っぽいけど、正方形のサイズでやるか、コストでやるか。単に正方形のサイズでよかった。xyでコストを奪い合うこともなく、最小でどれだけコストがかかるか普通に計算できる。難しそうに見えて、普通のステップを進むだけで解けている。答えの範囲は0から10^9までなのでその範囲で二分探索する。
G - Inversion Squared
こんなシンプルでこのAC数やば。こういうのって典型になる前だったらARCにも出せるのかなとか思ってたら、解説に「大変な場合分けの練習問題」って書いてあって草。えーなんか箱根駅伝みたいなやばい方法があると期待してたのに。現実ってそういうもんだよな。俺の考えが甘すぎた。
