A. farmpiggie and Subset Sum
$S_i$ が偶数からなるように調整すればよいです．
B. ezraft and Array
総和を $S$ として，$b_i=S/a_i$ とすると，$\sum 1/b_i=1$ です．
LCM をおさえてこういう単位分数を作る問題だと思います．
だいたいこんな感じで作れます．
- $2,4,8,16,32,32$ としてみるとこれは distinct ではないが逆数和は $1$ である．
- $2,4,8,16,32,48,96$ とすると distinct かつ逆数和は $1$ である．
$N=2$ だけ不可能ケースであとは上の要領で．
C. 0mar and Alternating Sums
結構ややこしや．
まず全体から偶数個とるパターンを考えます．
+-/+-/+-
と区切ることで，総和が $0$ 以下になることが分かります．すると総和が $0$ になるのは，$2$ 個ずつでマッチングになっている場合しかありません．
次に全体から奇数個とるパターンを考えます．
+/-+/-+/-+/
と区切ると，先頭のブロック以外は交代和への寄与が非負です．よって
-1, [a,a], [b,b], …, [c,c], [x,x+1], [d,d], [e,e], …
のようなパターンしかありません．$x$ を固定するごとに適当な計算をします．
D. diss_quack and Array Game
- Alice が全体 $/2$ を選択できる回数：lowbit の min.
- それ以外：Bob が $2$ 番目に奇数がある状態にして，Alice は先頭に対する操作しかできない．
結局，
- ひとつの数に対してだけ操作する場合のコスト $c_i$
- 全部が $2^k$ で割り切れるような最大の $k$
を使って，$\sum c_i – kN$ のようなコストになります．
$c_i$ はおおよそ popcnt, topbit で書けます．
$K$ を固定して解きます． $a_i$ としてはまず最小の $2^K$ の倍数までインクリメントしたあとで，さらに $c_i$ を小さくするためのインクリメントが可能です．
しかし，popcnt, topbit のような評価関数なのでコストを大量にかけるのは明らかに無駄で，このフェーズのインクリメントは適当な小さな範囲を探索すればよいです．
E. lce4113 and Security Game
まず adaptive な以上，bit 同士の区別はなくて， $x$ は popcnt 分の選択肢しかありません．
$(m_0,m_1)$ については $(m_0\oplus c, m_1\oplus c)$ を送るのと同じことになるので， $m_0=0$ として考えればよいです．
$o(v,x)=x$ のとき以外は簡単です．$o(v,x)$ と $x$ が不一致であるような桁を見れば $v$ の $k$ 桁目が決まるので， $m_1=2^k$ を送ればよいです．
$o(v,x)=x$ のときだけが問題です．
$x=1$ で解けます．難しいケースというのは，「$v$ は $0$ または奇数」の場合です．
このあと $m=m_1$ を奇数から乱択します．このとき，
- $0\oplus 0$
- $0\oplus m$
- $odd\oplus 0$
- $odd\oplus m$
について， $\oplus$ されたものが区別できればよいです．
$odd \oplus 0$, $odd \oplus m$ がそれぞれ偶然に $m,0$ になってしまうと判定失敗で，それが起こらないと信じると判定成功します．
判定失敗は $m$ を乱択したとき $1/2^{29}$ 程度です．
F. Whoname and Unsorted Array
超厳密には未証明だがまあ大丈夫だろうという解法です．
とりあえず parity の必要条件は処理します．
例えば $N=9$ とするとき，次のように近づけていきます．
- 7……..
- 67…….
- 567……
- 4567…..
- 34567….
- 234567…
- .234567..
そしてこの過程および最後の仕上げで大事な操作があります．
- A234567BC
- BA234567C
- B234567CA
手前，または末尾 $N-1$ 項の操作によって，端の方だけを rotate できます．この中央一帯が不動になっています，これはよく見ると問題文の操作が「右へまとめて移動」「左へまとめて移動」同士でおおよそ打ち消せるためです．
結局，次のようにします．
- 次に先頭に持ってきたい数の位置に注目．末尾でなければ $1$ 手で持ってこれる．
- そうでなければ，先頭末尾付近の調整をして，$3$ 手で持ってこれる．
「最後の仕上げ」では parity の調整ができないので，雑な評価で「確率 1/2 で成功」ということになります．
とはいえこれは決定的アルゴリズムなので，確率とは状態ですが．
最初に $N$ 手以下ランダムに操作してから上のような解法に突っ込むことで，AC を得ることができました．
