Codeforces Global Round 10 G. Omkar and Pies
Codeforces Global Round 10 G. Omkar and Pies についての記事です．
問題へのリンク
経緯
全然見当もつきませんでした．editorial を読んですごく勉強になったように思います．
解法
以下，ほぼ editorial のまま．
まず，「1をできるだけ多く重ねる」問題だと思って良い．なぜなら，そのときに0も一番多く重なるから．
最初の文字列を$s$, 目標文字列を$t$ と書くことにする．また，$l$ から $r$ までの変換を合成したものを， $T(l, r+1)$ と書くことにする．
さて，仮に「$l$, $r$ を適当に選んで，変換結果をtに一致させられるか?」という問題だったとする． 愚直だと $O(n^2)$ で間に合わない．次の事実に注目する．
$T(l, r)(s) = t$ であることと，$T(l, n)(s) = T(r, n)(t)$ であることとは同値
すると，変換結果はたかだか $2^k \leq 2^{20} \sim 10^6 $ しかないので，各 $i \leq n$ について， $T(i, n)(s)$ と $T(i, n)(t)$ を全部求めて，一致するものがあるかどうか見れば解ける．なるほど....
ちなみに，$T(i, n)(s)$ を全部求めようとするとき，$T(n,n)(s)$ から $T(0,n)(s)$ まで逆に求めていくのだが， $i$ 番目の互換を $c(i)$ と書いたとき，$T(i,n)(s) = T(i+1,n)(c(i)s)$ というふうに，望む方と反対側に来てしまう． $T(\cdot,\cdot)$ の逆変換 $S(\cdot,\cdot)$ を考えれば，$S(i,n)(x) = c(i)S(i+1,n)(x)$ と，うまい方向に来る． $S$ だの $T$ だのは $k$ の置換なので，長さ $k$ のベクトルで表せて，逆変換は $O(k)$ で作れるから，これでOK．
もとの問題に戻る．さっきの解はちょっと見方を変えると，$\{1,\ldots,k\}$ の各部分集合 $w$ に対して，
- $is[w] =$ 「$T(i,n)(s) = w$ となる $i$ があればそのどれか．なければ -1」
- $it[w] =$ 「$T(i,n)(t) = w$ となる $i$ があればそのどれか．なければ -1」
というのを作って，$is[w] \geq 0$, $it[w] \geq 0$ となる $w$ があるかどうか調べた，ということになる． そうすると，「$T(i, n)(\cdot) = w$」の部分を，「$w \subseteq T(i, n)(\cdot)$ 」というふうに変えてやり， しかも，$is[w]$ については，できるだけ小さなインデックスを，$it[w]$ についてはできるだけ大きなインデックスをとるように してやると，$it[w] \geq 0$, $\,is[w] \geq 0$, $\,it[w] - is[w] \geq m $ となる $w$ で，1を最もたくさん含むもの，を求めれば良いことになる． うーん．これもなかなか....
これを実装するには，次のようにすれば良い (ここは editorial には漠然としか書いてなかったので，コードを読んだ)．
- 最初に，上の簡易問題に対する is, ts を作る．is は大きく，ts は小さくとる．
- $\{1, \ldots, k\}$ の部分集合 $w$ を大きい方から見ていって， $w$ の各要素 $j$ に対して，$is[w - \{j\}]$ を $\min(is[w - \{j\}], is[w])$ で更新する． $it$ も同様．
