Codeforces Round 1049

A. Shift Sort

長さ $3$ の binary string を全部考えると，結局任意の $2$ 文字をスワップできることが分かります．

全体に $0$ が $k$ 個あるとして，左 $k$ 個のインデックス内にある $0$ を $1$ つずつ増やせます．

$y$ の桁数を $k$ として $x+y\mid (10^k-1)x$ という条件になります．$x+y=10^9-1$ となるようにすれば条件を満たします．

Bob が何かをやると Alice にオウム返しされて損するだけなので，Alice が $0$ 回または $1$ 回操作して Bob は必ず終了です．

$l,r$ の parity を決めるごとに，現在との差分を計算します．

条件を緩和して，$(i,j)$ をマークして $R_j-L_i$ を得るとしてもよいです．

$N$ が偶数ならすべて $-L_i$ を選んだ場合との差分を考えて，ちょうど $N/2$ 個を $R_i+L_i$ すると思えるので貪欲でよいです．$N$ が奇数ならば最後に残すものを全探索したうえで同じことをします．

まず列を固定したときのスコアについて考えます．

$v$ を固定して，$x\geq v$ にできるかの判定を考えます．すると列を $01$ 列にできます．列が $01$ の場合は適当な bit dp で計算できます．これで二分探索すれば，列を固定したときのスコアが計算できます．

さまざまな列に対するスコアの和を求めます．スコアを，$\sum_k [x\geq k]$ と分解します．すべての列とすべての $k$ に対して上の判定問題を解き，true になる回数を数えると言いかえます．

各 bit mask に対して，その bit mask が [$x\geq k$] の判定に登場するような列と $k$ の組の個数を数えればよいです．この値は bit mask の $0,1$ の個数だけから決まるので前計算しておきます．

以下 $N\geq 3$ を仮定します．

ソートしておきます．$A_N$ が変わることはありません．

「操作」は $y> 0$ となるものをだけを指すこととします．

$2\leq i$ かつ $A_i\not\equiv A_N\pmod{2}$ となる $i$ が存在する場合
- $(A_1,A_i)$ または $(A_1,A_N)$ について操作可能．$A_1 \to -\infty$ とできる．

$A_1$ 以外が減少する操作が可能なとき．
- 初期状態または操作後に $A_i\not \equiv A_N\pmod{2}$ が成り立つので $A_1\to-\infty$ とできる．
$A_1$ を減らす操作が $2$ 回以上可能な場合．
- どこかの時点で，$(A_1,A_2,A_3)$ について $A_2$ を減らす操作が可能となっているはずである．よって $A_1\to-\infty$ とできる．

よって，次ができれば問題を解くことができます．

前者のタイプの操作が不可能であるとき，次の必要条件があります．

$A_i\neq A_N$ かつ $\mathrm{lcm}\{1,2,\ldots,N\}\geq |A_i-A_N|$ ならばこの必要条件が成り立たないことから，この必要条件は $O(N\log A)$ 時間程度でチェックできます．

この必要条件のもと，長さ $N-2$ 以下の操作は $(A_1,\ldots,A_k)$ の形のものを考えればよく，長さ $N-1$ や長さ $N$ の操作は全探索可能なので，上で述べた $2$ 個の判定を $O(N)$ 時間で行えます．