AGC045-B 01 Unbalanced 解説

面白かった

解説

累積和みたいなことを考えると、上矢印と下矢印をつなげて、縦幅をなるべく小さくする、みたいに読める。すなわち、初期位置を $0$ とすると、'0' が出てきたら位置に $-1$、'1' が出てきたら位置に $1$ を加算していって、その過程での最大値と最小値の差を最小化する問題に帰着できる。

このとき、初期位置を適当な非負整数に決めると、「位置が $[0, N]$ に収まるような $N$ のうち最小のもの」が答えとなる。よって、$N$ を決め打ちして実現可能性が判定できれば、二分探索によってこの問題が解ける。

これをベースにして、次の DP を考える。

この DP は更新に $O(|S|^2)$ （工夫すると $(|S|\log|S|)$ に落ちる？）かかるので、このままだと解けない。ここで、遷移をよく眺めると、次の事実が得られる。

$dp[i][j]$ が true であるような $j$ が複数存在するうちは、このような $j$ は必ず連続してひとつの区間に固まって現れる。
初めてこのような $j$ がひとつになったタイミングから先、このような $j$ は、あるひとつの区間のうちで parity が一定な場所に必ず、そしてそのような場所のみに現れる。

これを考えると、$j$ を唯一の区間として管理できて、DP の遷移が $O(1)$ になる。よって、$O(|S|\log|S|)$ でこの問題が解けた。