はじめに
元の問題では入力で $K$ が与えられますが、任意の $K$ についても同じ計算量で解くことができます。
問題概要
長さ $N$ の整数列 $A, B$ が与えられます。$K = 0, 1, \dots , N - 1$ について以下の問いに答えてください。
長さ $N$ の AB からなる文字列 $S$ のコストとスコアを以下のように定義します。
コスト : 文字列 $T$ を $S$ の先頭に A 追加したものとして、$T$ の異なる文字が隣接している箇所の数
スコア : $i$ 文字目が A なら $A_{i}$ を、B なら $B_{i}$ を $x$ に加算するという操作を $i = 1, 2,\dots , N$ について $x = 0$ から始めたときの最終的な $x$
コストが $K$ 以下であるような文字列 $S$ に対するスコアの最大値を求めてください。
解法
$K$ を固定したときの答えを求めます。
$A, B, K$ について、以下が成り立っているとして良いです。
- $A_{1} = 0, B_{1} = -\inf$
- $A_{N} = -\inf, B_{N} = 0$
- $N$ は偶数
- $K$ は奇数
- $A_{i} < B_{i}$ ならば $A_{i + 1}\geq B_{i + 1}$
- $A_{i} \geq B_{i}$ ならば $A_{i + 1}< B_{i + 1}$
そうでない場合、以下のように置き換えます。
置き換え
コストの定義で $S$ の先頭に A を追加しているのが面倒くさいので、$A, B$ を以下のように置き換えます。
- $A = (0) + A$
- $B = (-\inf) + B$
すると、コストの定義はただ単に $S$ の異なる文字が隣接している箇所になります。
次に、$K$ が偶数なら $A, B$ を以下のように置き換えます。
- $A = A + (0)$
- $B = B + (-\inf)$
これは元 $S$ の末尾が A ならばコストを変えずにスコアを維持できます。そうでなくてもコストを $1$ 増やすだけでスコアを維持できるし、元のコストは $K$ 未満なので、$K$ を超えません。そして、$K + 1$ でも答えが変わらないので、$K$ に $1$ を加算することで $K$ が奇数の場合に帰着できました。
$K$ が奇数のとき、先ほどの理論と同様に、$A, B$ を以下のように置き換えても答えが変わりません。
- $A = A + (-\inf)$
- $B = B + (0)$
また、$A_{i} < B_{i}$ かつ $A_{i + 1} < B_{i + 1}$ なら $A, B$ を以下のように置き換えて良いです。
$A = (A_{1}, \dots , A_{i- 1}) + (A_{i} + A_{i + 1}) + (A_{i + 2}, \dots , A_{N}) $
$B = (B_{1}, \dots , B_{i- 1}) + (B_{i} + B_{i + 1}) + (B_{i + 2}, \dots , B_{N}) $
なぜならある $S$ について、$S_{i} \neq S_{i + 1}$ が成り立っているなら、$S_{i} = S_{i + 1} = $B とすることで、コストを増やすことなくスコアを上げられるからです。
この置き換えは $A_{i} \geq B_{i}$ かつ $A_{i + 1} \geq B_{i + 1}$ が成り立っているときでも行って良いです。
以上のように置き換えると、最初の条件を満たす数列になります。また、スコアの最大値は変わらないことも示せています。
JOI 飴への帰着
文字列 $T$ を AB を $\frac{N}{2}$ 回繰り返したものとします。
$S$ の最適解について、$K\neq 0$ であることから、$S_{1} = $A かつ $S_{N} = $B が成り立ちます。また、以下が成り立っています。
- $T_{i} \neq S_{i}$ かつ $T_{i} \neq S_{i + 1}$ が成り立つ $i$ は存在しない。
これは $S_{i} = S_{i + 1} = $B とすることで、コストを増やすことなくスコアを上げられるからです。
以上より、コストは $S_{i} \neq T_{i}$ が成り立つ $i$ の数の $2$ 倍に $1$ を足したものとして良いです。よって、「$S_{i} \neq T_{i}$ である $i$ の数が与えられるので、$S$ のスコアの最大値を求めてください。」という問題を解けば良いです。
$S_{i} \neq T_{i}$ を満たす $i$ の集合を $U$ としたとき、スコアは以下のように表せます。
- $\sum\max(A_{j}, B_{j}) - \sum_{i\in U} |A_{i} - B_{i}|$
よって、「隣接しないように $i$ を指定された数選び、そのような $i$ に対する $|A_{i} - B_{i}|$ の総和を最小化してください。」という問題に帰着できました。
これはまさしく JOI 飴であるので、同じ解法で解けます。また、指定された数は $0$ 以上 $N - 1$ 以下の任意の数について同時に求められるので、元の問題も任意の $K$ に対する答えが同時に求められます。
JOI 飴の参考文献
解説などもこのリンク先から辿れると思います。
コード
おまけ
コンテスト中は、monge d 辺最短路に帰着して解いていたため、TLE になってしまいました。より難しい問題に帰着して TLE ということを、最適化でよくしてしまうので注意した方がいいかもしれない。
