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

Come Together

方針

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

目的関数を求める

最終的に駒が集まる位置を \( (y, x) \) とします。ここで、取り除かれる駒が一つもなかったと仮定します。このときの目的関数を \( f(y, x)\) とすると、

\[f(y, x) = \displaystyle \sum_{ i = 1 }^{ H } \sum_{ j = 1 }^{ W } (|y – i| + |x – j|)\]

となります。ここで、\( x \) は列に対応し、\( y \) は行に対応するとしているので、\( f(y, x) \) と表記しています。

次に取り除かれたマスも考慮すると、取り除かれマスに対応する操作回数は \( 0 \) としなければいけないので、\( f(y, x) \) は、

\[\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 \) 個あるようなデータです。これは以前にも出題された内容です。

https://atcoder.jp/contests/abc102/tasks/arc100_a

中央値をもとめる

\( i \) が \( a_i \) 個あるようなデータの総数 \( n \) は、残っているマスの総数なので、\( n = HW – K\) となります。また、データを整列させたときの中央値の要素番号 \( m \) は、

\[ m = \lfloor\dfrac{n + 1}{2} \rfloor \]

とします。データ数が偶数のときの中央値もこの値を使用して大丈夫です。

どのようにして中央値を求めるかですが、\(v(y)\) を例にして考えて見ます。

ここで、\(h_i \) を \(i = R_i\) となるものの個数とすると、\(a_i\) は

\[ a_i = W – h_i \]

となります。よって、中央値は、\(c = a_1 + a_2 + \cdots + a_t\) が \( m\) 以上となる。最小の \( t \) となります。

コード

中央値

三分探索

感想

最初は三分探索の解法を思いついたんですが、バグが残っていまいました。解説を読んで中央値で解けることが分かりました。

シェアする

  • このエントリーをはてなブックマークに追加

フォローする