- A. Shizuku Hoshikawa and Farm Legs
- B. Yuu Koito and Minimum Absolute Sum
- C2. Renako Amaori and XOR Game (hard version)
- D. Rae Taylor and Trees (easy version)
- E. Anisphia Wynn Palettia and Good Permutations
- F. Rae Taylor and Trees (hard version)
- G. Sakura Adachi and Optimal Sequences
- H. Shiori Miyagi and Maximum Array Score
A. Shizuku Hoshikawa and Farm Legs
偶数のとき $\lfloor n/4\rfloor+1$．何かの全探索でもよいです．
B. Yuu Koito and Minimum Absolute Sum
最小化すべき量は単に $|a_n-a_1|$ です．この $2$ 数を適切に定めてそれ以外のところは $0$ 埋めします．
C2. Renako Amaori and XOR Game (hard version)
A のスコアを $a$，B のスコアを $b$ とするとき，$S=a\oplus b$ が戦略に依存しないことに注意します．
$S=0$ なら引き分けです．そうでないときは，$S$ の topbit を $k$ とすると，$a,b$ の比較は $k$-th bit だけで決まります．これで C2 は C1 に帰着されます．
値を 01 列として，最後に $(a_i,b_i)=(0,1),(1,0)$ のどちらかであるような $i$ をプレイする側が最終的な値を選ぶ権利があり，勝者となります．
D. Rae Taylor and Trees (easy version)
私の考察では D が解けることと F が解けることが同値でした．F のところに書きます．
E. Anisphia Wynn Palettia and Good Permutations
mod 6 で，次のように周期 $12$ の配置を使いました．
$$1,2,4,5,6,3,1,3,6,5,4,2,\ldots$$
$6$ の倍数の個数まで並べたあと，最後に余った数を昇順に並べます．この部分も偶数が $2$ つある部分は大丈夫なので，$6$ 個という制限はやや余裕があるはず．
F. Rae Taylor and Trees (hard version)
十分抽象化すると，次のような問題になります：
- $n$ 頂点のグラフが与えられる．（ただし辺の個数は $O(n^2)$ で全列挙する時間・空間の余裕はない）．
- 全域木の存在判定をし，あるならばひとつ出力せよ．
連結判定（全域木取得）のためには，適当な点からはじめて bfs, dfs のような適当なグラフ探索すればよいです．この際，辺が列挙できていなくとも，
- 訪れた頂点 $v$ を使用済ということにする．
- $v$ に隣接する点のうち未使用の点があるならばそのうちひとつを見つける．
ということができればよいです．今回は隣接する点を見つけるのは，例えばセグメント木でできます．順列の中で $v$ の左にある小さい数や，右にある大きい数を取り出せばよいです．
全点に到達できていれば連結で，その過程で通った辺集合が全域木です．
G. Sakura Adachi and Optimal Sequences
double 操作を固定するごとに解く（最小回数と数え上げ）とします．
double, +1, +1 は +1, double に置き換えられるので，double 操作の直後に来る +1 操作は要素ごとに $1$ 回以下で，これは parity ごとに決まります．
操作を逆から見ると，
- もう double 操作を行わない場合：+1 操作の回数がコスト，その多項係数分の操作自由度が発生．
- double 操作を行う場合：奇数の要素に対する +1 操作の回数がコスト，その多項係数分の操作自由度が発生（こっちは多項係数といっても $0, 1$ ずつなので単に階乗です）．
ということになります．
多項係数 $\frac{n!}{n_1!n_2!\cdots n_k!}$ については，$n$ が階乗前計算できないほど巨大になりますが，
- 二項係数の積に分解して Lucas の定理を使う．
- $n_i$ は $\mathrm{mod}$ 未満なので，単に $n\geq \mathrm{mod}$ ならこの多項係数は $0$ である．
などの対処をします．
H. Shiori Miyagi and Maximum Array Score
$a_i=i$ という構築で $i-1$ 点獲得できるのが割と優秀で，それを大きく超えるものはあまりないだろう．という発想の解法です．
実際，$v(i,a_i)\geq 2$ とできる回数を考えると，$\sum_{k\geq 2}(m^{1/k}-1)$ で $O(\sqrt{m})$ しかないことから，$a_i$ までで獲得できるスコアは $[i-1,i+O(\sqrt{m})]$ になっています．
そこで次のような dp 解法を考えます．
- $a_i$ まで定めた時点で，スコア $s$ 以上を達成するための最小の $a_i$ を $\mathrm{dp}[s]$ とする．この dp テーブルを $i=1,2,\ldots$ 順に更新していく．
$i-1\leq s\leq i+O(\sqrt{m})$ の範囲のみこの値を保持することで，計算量 $O(m^{1.5})$ で解くことができます．計算量評価は $\sqrt{m}$ というのは毎回理論値スコアをとるというような非現実的な見積もりでもあるので，実際にはオーダーレベルでもっと小さい可能性もあります．
私の実装では，dp テーブルのうち重要な要素だけを列挙する形で保持しています．$s_1<s_2$ かつ $\mathrm{dp}[s_1]\geq \mathrm{dp}[s_2]$ ならば，後者は捨ててよいです．
