ARC227 A - Fermat Point of Binary Strings

二進フェルマー点

考え方

$0$ 同士や $1$ 同士を入れ替えるのは、考えなくてよい。
コストだけかかって何も状況が変化しないからである。
したがって、A の $i$ 個目、B の $i$ 個目、C の $i$ 個目、の $1$ を同じ位置に揃えることになる。

それぞれの位置を $a,b,c$ として、位置 $x$ に揃えるとする。
この場合、揃えるコストは $|x-a|+|x-b|+|x-c|$ となる。
そして、この形の関数の最小値は、奇数個の和なら中央値で最小値を取る。
これを全ての $i$ 番目の組について実行すればよい。

問題は中央値の逆転が起こらないかどうか。
だが、$i$ 番目の組の中央値が $x_i$ だとして、$i+1$ 番目には、それより大きい値が $2$ つ以上ある。
よって、$x_{i+1}$ は必ず $x_i$ より大きい。
従って、前述の方法で問題は発生しないことが示された。

計算量は $O(N)$ となる。

入力を受け取る。

n: 2
a: "1100"
b: "1010"
c: "0011"

各文字列の 1 の位置を 0-indexed で見ると、次のようになる。

A: {0, 1}
B: {0, 2}
C: {2, 3}

$0$ 個目の 1 の位置は $0,0,2$ で、中央値は $0$ である。
したがって、構築する文字列では位置 $0$ を 1 にする。
この組の移動距離の合計は $2-0=2$ である。

$1$ 個目の 1 の位置は $1,2,3$ で、中央値は $2$ である。
したがって、位置 $2$ も 1 にする。
この組の移動距離の合計は $3-1=2$ である。

よって、構築する文字列は 1010 となる。
移動距離の合計は $2+2=4$ なので、最小値は $4$ である。

距離の和は、int 型からはみ出る。
long long 型を用いること。

特になし。