全国統一プログラミング王決定戦本戦:C - Come Together

問題

https://atcoder.jp/contests/nikkei2019-final/tasks/nikkei2019_final_c

考え方

難しいが過去にも300点で似たような問題があるので、点数は相応な気はする...

どこに着目して考察するべきだったか

まずは H 軸、W 軸ごとに独立して考えることにしよう。W 軸についてコマを揃えることを考える。

サンプル 1 の例で考えると以下の図のようにそれぞれの列ごとに 1 0 2 マスのコマがあることになる。

f:id:d_tutuz:20190222153255p:plain

これをある列 x にすべて揃えたい。i 列目にあるコマの数を cnt_i 個としよう。その時のコストを f(x) とすると

f(x) = \displaystyle \sum_{i=1}^W |x - i| * cnt_i

である。この関数 f(x) の最小値を求めたいが、各 x\ (1 \le x \le W) について考えると O(W^2) となり間に合わない。しかし f(x) は凸関数であることに気づくと三分探索を用いることができて計算量 O(WlogW) で最小値を求めることができる。

よって W 軸についてある位置 x にするときの最小値を求めることができた。H 軸についても同様に最小値を求めて、それぞれの最小値の和が解となる。

Submission #4345231 - 全国統一プログラミング王決定戦本戦

何がバグっていたか

得た知見(典型ポイント)

  • xy軸を独立に考える
  • 差の絶対値の和は三分探索
  • 中央値で最小値を取る

類題