AtCoder Regular Contest 164 D - 1D Coulomb
メモ
以後以下のように言葉を定義する
S[i] := iの電荷(+か-)
R(s) := sと逆の電荷, R(+) == -, R(-) == +
cnt(i, s) := [0, i)にある符号sの数(つまりiより左にあるsの個数)
まず各iがどちらに動くかを考える
iが+の場合、i以外の合計は-1になり
iが-の場合、i以外の合計は+1になる
よって左右どちらかの合計が0の時、電荷は逆方向に動くため
以後同様に考えると、各電荷は括弧列の対応のように動くことが分かる。
具体的には
cnt(i, s[i]) >= cnt(i, R(S[i]))ならs[i]は左括弧として働き、そうでなければ右括弧として働く
そして最終的に作った括弧列が良い括弧列(すべての括弧について対応する括弧があるもの)である場合、対応する括弧同士の距離の総和が、あるTの決め方に対する答えになる。
よって良い括弧列のつくり方について、その距離の総和が求められれば
似たように問題を解くことができる
実際はiの符号についてcnt(i, +) == cnt(i, -)の時に、iには+をおいても-をおいても左括弧として扱えるため、答えは異なるが
総和を解く方法はいくつかある
解1
左括弧を置いたときに、その括弧が総和にどう寄与するかを考える
1 : ()
4 : (())
9 : ((()))
上のようにいくつか、距離の総和と括弧列の対応を書いてみると、
左括弧を置く際に、自分より左の閉じていない左括弧の数をocとして
距離の総和がoc * 2 + 1増えることが分かるため、
dp[i][j] := iまででj個左括弧が閉じていないものが残っているときの
(距離、場合の数)というペアを持つと解ける
(しつこいが実際は左括弧として+, -の両方の場合があるため
元の問題を解く際は、dp[p][m] := 左にある+の数をp, -の数をmとしたときのー
という風に扱ってそのp, mの数によって今おこうとしている電荷が左右どちらの括弧になるかを考えて実装する必要がある
)
解2
左括弧から右括弧への距離を、二つの数字の和で考える
例えば以下のように、_の部分には何かしらの括弧が入っていて
下に書かれている(と)が対応している場合
二つの距離は5だが、これは二つのインデックス2, 7について
-2, +7と計算しても同じものが導ける
__(____)__
よって左括弧があるインデックス集合をP, 右括弧があるインデックス集合をMとして
sigma(-Pi) + sigma(Mi)を求めれば、Tのある決め方についての総和が分かる
これは先ほどと同様に、dpに場合の数と距離の総和を持たせておけば解ける
