全国統一プログラミング王決定戦本戦:C - Come Together
問題
https://atcoder.jp/contests/nikkei2019-final/tasks/nikkei2019_final_c
考え方
難しいが過去にも300点で似たような問題があるので、点数は相応な気はする...
どこに着目して考察するべきだったか
まずは H 軸、W 軸ごとに独立して考えることにしよう。W 軸についてコマを揃えることを考える。
サンプル 1 の例で考えると以下の図のようにそれぞれの列ごとに 1 0 2
マスのコマがあることになる。
これをある列 x にすべて揃えたい。i 列目にあるコマの数を 個としよう。その時のコストを とすると
である。この関数 の最小値を求めたいが、各 について考えると となり間に合わない。しかし は凸関数であることに気づくと三分探索を用いることができて計算量 で最小値を求めることができる。
よって W 軸についてある位置 x にするときの最小値を求めることができた。H 軸についても同様に最小値を求めて、それぞれの最小値の和が解となる。
Submission #4345231 - 全国統一プログラミング王決定戦本戦
何がバグっていたか
得た知見(典型ポイント)
- xy軸を独立に考える
- 差の絶対値の和は三分探索
- 中央値で最小値を取る
類題
- C - Linear Approximation 凸関数の最小値を求めるのに三分探索が使えます。中央値でもOK