Codeforces Round 1107

A. Divide and Conquer

単に約数にうつれます．

$x=8588$ なら $y=10001, xy=85888588$ などとすればよいです．

01 列には長さ $3$ 以上ならば回文がとれて，$1$ 文字削除できます．よって長さ $2$ 以下には必ずできます．

11110000 のように，連長圧縮成分が $2$ 個のときは，それを減らせません．よって答は $2$ です．

成分が $1$ 個のときも $3$ 個以上のときも，片方の文字を殲滅するようにしていけば長さ $1$ にできます．

長さ $K+2$ の操作は長さ $K$ の操作と長さ $2$ の操作に分割できます．

よって長さ $1,2$ の操作しかしないとしてよいです．

先に長さ $2$ の操作 $(+1,-1)$ を全部やることにします．右側から見ていって，必要最小回数ずつ行っていきます．

これで $a_i\leq b_i$ になっていれば ok です．

木の $3$ 頂点の meet $x$ で場合分けをします．

すると条件は $x$ に書かれている値が平方数であることと同値になります．

あとは $x$ ごとに計算します．各頂点では周囲の subtree size をもとに， $O(\deg(x))$ かけて計算という形になります．

実験して合うものを出力．という感じで解きましたが，少し観察も必要でした．

まず，末尾の 1 は転倒数に影響しないので無視して構いません．先頭の 0 も同様です．入力は「1…0」の形としてよいです．

この上で実験結果を出すと，いい感じでした．（この除去をする前は眺めても確信を持ちにくかったです．）

結論は連長圧縮の任意のブロックが偶数のときだけ負けです．

以下の証明方針は AC 後に考えたものです．

上の負け条件以外のパターンについて，ある境界をとって，

であるようにできます．これらを削除すると，残る列は 00001111 の形になって，後手は操作できず負けです．

連長圧縮がいたるところ偶数長で，上の先手勝ちパターンに遷移しないようにしようとすると，転倒数が偶数になってしまうことが証明できます．これもちょっと非自明だとは思うのですが．

転倒数偶奇の計算にあたって，00 や 11 であるような部分文字列は削除して計算しなおしてもよい．というところに注目すると証明できます．

$l=1,r=n$ とします．

まず操作は次の形になります．

$a_i$ には，$a_1,a_2,\ldots,a_{i-1}$ の $\mathbb{Z}$ 線形結合を自由に足せる．したがって $g_i=\gcd(a_1,\ldots,a_{i-1})$ の倍数を自由に足せる．

$a_1=x$ として，$a_k$ が $x$ の倍数でないような最小の $k$ をとります．

$a_1$ は動かせず，$a_k$ は仮に $x$ に一番近くなるように動かして，$y$ とします．

すると $a_{k+1}$ 以降はすべて $x,y$ の間（$[x,y]$ または $[y,x]$）に入るように動かせることが分かります．それ以降の gcd は $|x-y|$ 以下だからです．

よって，この $a_k$ を最適に動かした $|x-y|$ が区間の答えとなります．

$L$ ごとに答えをまとめて求めることにして， $a_L\nmid a_K$ となる最小の $K$ を検出する問題が解ければよいです．これは区間 GCD がはじめて変化するところです．