- A. New Year and the Christmas Ornament
- B. New Year and the Treasure Geolocation
- C. New Year and the Sphere Transmission
- D. New Year and the Permutation Concatenation
- E. New Year and the Acquaintance Estimation
- F. New Year and the Mallard Expedition
- G. New Year and the Factorisation Collaboration
- H. New Year and the Tricolore Recreation
A. New Year and the Christmas Ornament
$(x+1,x+2,x+3)$ として $x$ として可能な最大値を求める．
B. New Year and the Treasure Geolocation
総和は置換によらないので $nT = (\sum x_i + \sum a_i, \sum y_i + \sum b_i)$ となります．
C. New Year and the Sphere Transmission
$N$ の約数を全部試します．
D. New Year and the Permutation Concatenation
結局，$k, k+1$ 番目の順列を $P, Q$ として $P$ の prefix と $Q$ の prefix の lcp が加算されます．$n$ を固定したときに，先頭 $n$ 項が一致する確率を考えます．
E. New Year and the Acquaintance Estimation
Erdős–Gallai theorem の条件を実装します．
$k$ を固定したときに，答えが $d_k$ 以上かどうかに応じて式を作ります．
F. New Year and the Mallard Expedition
貪欲法．とりあえず最速で目的が達成できるようにしておき，ただし「今まで飛んだところを歩く・泳ぐように変更する」などを適切な優先順位で行います．
G. New Year and the Factorisation Collaboration
四則演算などだけでは素因数分解は難しいので，sqrt をいかに利用するかということになります．しかし適当な値を sqrt クエリしても高確率で存在しないという結果がかえってきて役に立ちません．（素因数が $k$ 個として存在するのは確率 $2^{-k}$ 程度）．
一方存在する場合には，sqrt は素因数の個数に応じてたくさん解を持つことになります（各素因数 $p$ に対して $\pm 1\pmod{p}$ のどちらかを選ぶ）．なので，$sqrt(a^2)$ というクエリの返答は $a$ でない値が返ってくることも多く，このようなクエリは意味を持ちます．
このクエリで $a^2=b^2\pmod{n}$ の解をたくさん作っておきます．各 $p$ に対して $p\mid a-b$ と $p\mid a+b$ のどちらかです．$\gcd(n,a-b)$ をとると，$p\mid a-b$ となる $p$ だけを集めた素因数の積だけを取り出すことができます．いろいろな方法で素因数の部分集合の積が作れて，それらの $\gcd$ を利用して素因数を取り出します．
H. New Year and the Tricolore Recreation
設定が込み入っていますがかなり簡単です．$(x,y)=(w-b-1,r-w-1)$ を考えると，どちらのプレイヤも行える操作は $x,y$ の一方から非負を保つように $k$ を引くというものです．なのでプレイヤの区別はなく，grundy 数が定義されます．
$n$ を $x$ の上限として $0\leq x\leq n$ に対する grundy 数が計算できればよいです．
grundy 数の最大値を $m$ とすると，bitset を使ってこの計算を $O(n^2/w + nm)$ 時間でできます．各 $m$ 通りの値に遷移可能であるかを表す $m$ 個の bitset を持てばよいです．
$m$ はあまり大きくならないようで（サンプルでは $52$ 以下．解説では $100$ 以下が主張されている）これで AC できます．
$m$ の値は ML, TL についてかなり余裕があるのでまあ通るだろうという解法ではありますが，すべての $f$ を試すことなく $m$ の上界について何かを証明する方法は私は思いつきませんでした．解説でも証明がなく，これを質問するコメントにも回答がなさそうです．
