Codeforces Round 959 sponsored by NEAR

A. Diverse Game

すべての数をインクリメントする，全体を rotate する，など．

$S = \text{00001….}$ と $k$ 文字目ではじめて $1$ が登場するとき，$S$ の $k+1$ 文字目以降を自由にいじることができます（長さ $k$ の区間で操作する）．$k$ 文字目も，最後に $0$ に変更できます．

先頭 $k-1$ 文字は変更することはできません．これで必要十分の条件になります．

各 $i$ をスタートしたときにはじめて $x$ を超えるところを計算します（二分探索や尺取り）．すると，各 $i$ に対して右端の個数は降順に dp で求まります．

鳩の巣原理より操作順 $n-1$ の辺が存在します．この辺を使うことにして，頂点についてはどちらか一方だけを残します．あとはサイズ $n-1$ の場合に帰着します．

単にそれぞれの木の頂点数を $a_i$ として，$x_i\in [1,a_i]$ を選び OR を最大化するという問題になります．

$x=\max a$ として，$2^k\leq x<2^{k+1}$ となる $k$ をとります．$2^k\leq a_i$ となる $i$ が $2$ つあれば，$2^k \mathrm{OR} (2^k-1)=2^{k+1}-1$ が作れてこれが理論値です．

そのような $i$ がちょうどひとつのとき，その $i$ から $2^k$ 以上の値をとることを確定させます．$x_i=2^k+x’_i$ として $x’_i$ を選ぶ問題に言い替えて，部分問題を再帰的に解きます．

白辺と黒辺がある．黒辺は連結である．白辺をいくつか削除してグラフを Eulerian にせよ．という問題です．

黒辺に関する連結成分ごとに解きます．各頂点について偶・奇のどちらになって欲しいかどうかが決まっています．連結成分内に，奇数になって欲しい頂点の個数が偶数個でなければなりません．

この必要条件のもと構築可能です．全域木をとって，葉側から決めていきます．親に向かう辺で調整すれば，根以外は目的通りにできます．必要条件のもと根は自動的に目的の parity になります．

普通に桁 dp でよいです．繰り上がりの回数を状態とします．

まず “aa” を質問すると $p$ が特定できます（制約より）．

$2$ 回目で $ask(X)$，返り値 $Y$ だとします．$m$ は $X-Y$ の約数ということになり有限個の候補に絞られます．なのですが，$2$ 回目の質問が下手だと $3$ 回目で特定することが理論上不可能ということが起きえて，実はここが難所です．

$X=[26,26,26,26,26,26,26,26,26,26]$ とします．$[X-2Y-1,X-Y]$ 内に，$p$ 進表記の各桁が $[1,26]$ に収まるものがあることが，$p\leq 50$ から分かります．これを $3$ 回目のクエリとすればよいです．