- https://codeforces.com/contest/1411
- https://codeforces.com/contest/1464 (div1)
- https://codeforces.com/contest/1465 (div2)
問題番号は div1
A. Peaceful Rooks
$N$ 頂点のグラフを考え，駒 $(x,y)$ を $x$ から $y$ への有向辺とします．
- 常にどの頂点の入次数・出次数も $1$ 以下であることを保ってください．
- ひとつの有向辺を選び始点を変更できます．
- ひとつの有向辺を選び終点を変更できます．
- 最終的にループが $m$ 個ある状態にしてください．
ということになります．入力はパス・サイクルに分解できます．連結成分が $m$ 個になるようにしたいですが，最初からサイクルであるようなところへの操作では連結成分が増やせません．
B. Grime Zoo
0, 1 の個数を決めてみると，転倒数を最小化または最大化したいということになります．よって，”?” の部分の置き換え方は，000111 や 111000 のような形だけを考えればよいです．これを全部試せばよいです．単峰性を前提とした最小値の探索でも大丈夫です．
C. Poman Numbers
入力は $2$ のべき乗からなる数列だと思います．最終的に $f(S)$ は項の $\pm 1$ 倍の和となります．この符号のつけ方として何が可能かを考えます．
最後の項は $1$ 倍，直前の項は $-1$ 倍です．そのような符号列はすべて実現可能で証明も簡単です．見つけ方は全パターンを調べるコードを書くのが簡単だと思います．
最後の 2 項を処理したあと適切に言い換えれば，$A$ の項の部分和で与えられた値を作れるかという問題がのこります．これは大きな項から貪欲などで判定できます．
D. The Thorny Path
見返したら昔かなり嘘を実装していたのに通っていた…．ランダム順列マルチテストケースだと結構耐えるのでそういう感じだろうか．コンテスト準備側は分割を全部入れた方がいいだろうなあ．
サイクル長を考えます．総和が $n$ であるような整数列があって，$(x,y)\to (x+y)$ や $(x+y)\to (x,y)$ のような操作ができて，最小操作回数で総積の最大化をするという問題です．
総積の最大化は $2^a3^b$ を目指す $(0\leq a\leq 2)$ というもので，これは $4$ 以上の $x$ を $(2,x-2)$ にしたり $(2,2,2)$ を $(3,3)$ にすることを考えれば証明可能です．ただし $2^2$ 部分を $(4)$ として作ることも可能なので，全部 $2$ 以下にしなくてはいけないというわけではないです．
最終的に 3 以外の長さにするものは 4 つ以下です．ほとんどのものは貪欲に $3$ を作っていけばよいです．
サイクル長 $5$ 以上ならばまず $3$ と $n-3$ に分解してサイクル長 $4$ 以下に帰着できます．$4$ のものも大部分は $3+1$ と分けてしまってよいです．$1,2$ についても大部分は貪欲に $3$ を作るように組みます．あとは細かいところは最短路問題で最適化しました．
E. No Game No Life
各頂点の grundy 数を求めておきます．
$\text{ANS}[x] = \frac{1}{n+1} + \sum_v \frac{1}{n+1}\text{ANS}[x\oplus \text{grundy}[v]]$
のような連立方程式を解ければよいです．これは xor_convolution(ANS, f) = g のように書けます．
xor_convolution の Hadamard 変換による計算方法を考えれば，$f$, $g$ を Hadamard 変換して各点ごとに $g$ を $f$ で割り，Hadamard 逆変換で戻せば ANS が得られます．
$f$ による除算が発生しますが，割る数は $1$ に $n$ 個以下の $\frac{1}{n+1}$ を足し引きしたものであることが分かるので $0$ 除算は発生しません．
grundy 数は $n$ 以下だという評価を使いましたが，解説にある $O(\sqrt{m})$ と評価できて小さいということには気づいていませんでした（grundy 数 $k$ の頂点の出次数が $k$ 以上であることからわかる）．
F. My Beautiful Madness
パスを $(a_i,b_i)$，lca を $c_i$ とします．
解が存在するとして，その解のうちで最も根に近いものについて考えます．すると，交点の候補として，最も深い $c_i$ の $d$ 個上の先祖（なければ根）としてよいことが分かります．
つまり $v$ が与えられていて，すべてのパスが距離 $d$ 以下であるか判定できればよいということになります．
$c_i$ が $v$ から距離 $d$ 以下であればそれはもちろん条件を満たします．それ以外がどのようなものかを考えると，
- $v$ の $d$ 個上の先祖 $w$ が存在し，
- $w$ が $[a_i,c_i)$ または $[b_i,c_i)$ 上にある
ときであるということが分かります．したがって，距離 $d$ 以下のパスが次の和として数えられます．
- 距離 $d$ 以下にある $c_i$ の個数
- $[a_i,c_i)$ および $[b_i,c_i)$ に $+1$ するというパス加算を行ったときの $w$ での値
前者は重心分解の応用として有名（https://judge.yosupo.jp/problem/vertex_add_range_contour_sum_on_tree）で，後者も HLD の応用として有名です．
