Codeforces Round 1010

A. Math Division

$n$ から $2$ 種の操作で到達可能な数の候補として，$\lfloor n/2^k\rfloor$ および $1+\lfloor n/2^k\rfloor$ の形の数に限定できます（桁数に比例する状態数）．これらに対して dp すればよいです．

$a_i>a_{i+1}$ を満たす $i$ の個数を $n$ とします．

$k=\lceil n/2\rceil$ とすると，$k$ 回以上の操作が必要です．一度の操作で解消できる “>” の個数が $2$ 個以下だからです．

$n$ が奇数のとき，$k$ 回の操作で達成可能です．先頭から見て $1$ 個，$2$ 個，$2$ 個，と “>” を解消していけます．

$n$ が偶数のとき，同じように $k+1$ 回で目標達成可能です．よって $k$ 回で達成できるかを判定する問題に帰着されます．

最初の “>” の左側を $x$，最後の “>” の右側を $y$ として，$k$ 回で $2$ つずつの “>” を解消しようとするとこれが不変です．よってこの間を狭義単調増加列にできるという必要条件があります．

これは十分条件にもなります．両端の $2$ 個の “>” を解消して間を好きに作り変えるというような操作を考えればよいです．

入力は，行和の頻度列と列和の頻度列だけに変換してしまってよいです．操作は，ある行和とある列和に同時に同じ値を XOR することと言い換えられます．

操作を行う行・列のペアに辺を張って，二部グラフを作ります．このとき，各連結成分について値の和が $0$ であるのが必要十分です．よってこのようなグラフを作ったときに連結成分数が最大になるようにしたいということになります．

帰着先．

$(L,0)$, $(L,1)$, $(L,2)$, $(L,3)$, $(R,0)$, $(R,1)$, $(R,2)$, $(R,3)$ という $8$ 種の点がたくさんある．
第 $2$ 成分の和が $0$ であるようなグループなるべくたくさんに分割せよ．
ただし，孤立点以外の成分は $L$, $R$ 両方の点を使う必要がある．

それっぽい貪欲を書いてストレステストすれば AC 可能だと思います．ちゃんと証明するのはちょっと大変です．

まず問題を分割ではなく，頂点を余らせてもよいというように緩和します．余った頂点は総和が $0$ でも L, R 片側に集中していると分割の $1$ グループにはできませんが，これまで作ったグループに入れてしまうことができるので，これによって最適解は変化しません．

このように緩和すると，

ことなどが証明可能になります．

上の方法でなるべくグループを作った残りの状態を考えると，非自明な状況は片側に $2$ 種，逆側に $1$ 種余っているときだけです．簡単のため $(L,1), (L,2), (R,3)$ だけが余っているとしてよいです．

この時点であとは $(L,1), (L,2), (R,3)$ や $(L,1), (L,1), (R,3), (R,3)$ などの作り方しか考慮する必要がなくて，あとは比較的簡単に証明できると思います．

小さい方から出る辺を考えます．

$ka\leq b_1<b_2<(k+1)a$ のとき，$(a,b_2)$ の辺は $(a,b_1)$ の辺と $(b_1,b_2)$ の辺に置き換えられます．よってこの辺は考えなくてよいです．

これで辺の候補が調和級数で抑えられます．

まず可能な限り葉側に移動させたあと，bottom up にマージしていきます．マージするときに順序を決めて，以降同じ subtree 由来のものの順序を保つようにします．

親辺にある同色の部分とのシャッフルのために，先頭の色と個数を状態として，木DPしていきます．

解説を見ても発想が分からず苦労したのですが，いくつかの提出を見て自分なりに納得できた考え方で解説します．

$n\geq 2$ ならば $n$ が偶数であることが必要です．

以下，具体的で分かりやすくするため $n=10$ として説明します．値を $\bmod 10$ で考えます．

$p = (0,1,-1,2,-2,3,-3,4,-4,5)$ とします．順列になっていて，$p_{i+1}-p_i$ が相異なるのが重要です．

$a_{i,j}=p_i+p_j$ とします．すると，各行や各列は明らかに順列になります．組 $(a_{i,j},a_{i,j+1})$ が distinct であることも確認できます．$p_{j+1}-p_j$ が distinct になるようにしておいたおかげです．

これで，和が $n-1$ になるという条件以外は成り立つ状態になっています．和が $n-1$ になるという要請がある $2$ 数組はこの時点では $(0,5),(1,6),(2,7),(3,8),(4,9)$ などとなっています．

これは適当にラベルを付けかえれば和が $n-1$ になるようにできます．

$n=(p_1p_2…p_k)*p_{k+1}$ として，最大素因数だけを分けた状態を考えます．このうち prefix $p_1\cdots p_k$ 部分が同じものをまとめて計算します．

$n/k$ 以外の形での prime cnt, prime sum が必要になるパターンが小さい範囲にしかないことが最大ケースを計算すればわかるので，小さいところや $n/k$ の形の数に対する prime cnt, prime sum がとれるように前計算しておけばよいです．

最後は定数倍バトルでした．整数除算より double 除算の方が高速であることなどを…．