[AtCoder] 全国統一プログラミング王決定戦本戦 (2019) C – Come Together

2019年5月25日2019年6月9日

問題

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

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly progr ...

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

方針

問題の解釈

問題文を理解すると、取り出した駒の順番は問題を解く上で関係ないことが分かります。まず初めに操作回数を表す関数を定義します。次にその関数の最小値を求めます。ある駒を別の位置に動かすための操作回数はマンハッタン距離であることが分かります。この考えを元にして目的関数を求めます。

目的関数

\[\begin{eqnarray}
f(y, x) &=& \displaystyle \sum_{ i = 1 }^{ H } \sum_{ j = 1 }^{ W } (|y – i| + |x – j|)\ – \displaystyle \sum_{ i = 1 }^{ K} (|y – R_i| + |x – C_i|)\\
&=& \displaystyle W\sum_{ i = 1 }^{ H } |y – i| – \displaystyle \sum_{ i = 1 }^{ K} |y- R_i|+ \displaystyle H\sum_{ i = 1 }^{ W } |x – i| – \displaystyle \sum_{ i = 1 }^{ K} |x – C_i|\\
&=& v(y) + u(x)
\end{eqnarray}\]

ここで、\( u(x), v(y) \) は、

\[\begin{eqnarray}
u(x) &=& \displaystyle H\sum_{ i = 1 }^{ W } |x – i| – \displaystyle \sum_{ i = 1 }^{ K} |x – C_i|\\
v(y) &=& \displaystyle W\sum_{ i = 1 }^{ H } |y – i| – \displaystyle \sum_{ i = 1 }^{ K} |y- R_i|
\end{eqnarray}\]

とします。

目的関数の最小化

\(f(y, x) = u(x) + v(y)\) と変数を分離して表現ができるので、\(f(y, x)\) を最小化するために、\(u(x)\) と \(v(y)\) を独立に考えて最小化すれば良いことが分かります。\( u(x) \) や \( v(y) \) を次の関数 \(g(x)\) で表すことにします。

\[ g(x) = a_1|x – 1| + a_2|x – 2| + \cdots + a_n|x – n|\]

ここで、\(a_i \) は \( 0 \) 以上の整数とします。\(u(x)\) は \( n = W\)、\(v(y)\) は \(n = H \) として表現することができます。なぜ、\(a_i \) は \( 0 \) 以上であるかというと、\(R_i = R_j\) となるものの個数が \( W \) を超えず、\(C_i = C_j\) では、\(H\) を超えないためです。別の言い方をすると、ある列または行において、その列や行の大きさ以上のマスが取り除かれることはないからです。

\( g (x) \) を最小化する \(x \) は三分探索で求めることができます。また、次のデータの中央値として求めることもできます。そのデータは、\( i \) が \( a_i \) 個あるようなデータです。これは以前にも出題された内容です。