グラフ問題って実装でケアレスミスしてもどこがバグってるのかわかりづらい。
ライブラリもっときましょうね。
等差数列の和といえば、初項 $a$、公差 $d$、項数 $k+1$($k \ge 0$)として、総和は $\dfrac{(k+1)(a+(a+dk))}{2}$ となる。
これが $N$ となればよいので、$d=1$ を代入して整理すると $2N=(k+1)(2a+k)$。
各変数は整数なので、$2N$ の約数を列挙して $(k+1, 2a+k)$ の組を全て調べればよい。これが $a$ を整数として成り立つなら、そのような等差数列を作れる。
よく見ると $(k+1,2a+k)$ は必ず偶数・奇数が異なり、またそれさえ満たせば必ず整数解を作れるので、そのことを利用する解法もある。
つまり、$N$ を2で割れるだけ割った結果を $M$ とすると $M$ の約数は必ず奇数、それとかけあわせて $2N$ となる相方は必ず偶数となる。
あとは約数1個につきどちらが $k+1$ でどちらが $2a+k$ かの2通りあるので、$Mの約数の個数 \times 2$ が答えとなる。
始点に戻らなくてよい巡回セールスマン問題。直帰型と呼ぼう。1)
一列に並べるので、$c_i$ に含まれるある石からある石へ最短で繋げて、を繰り返すのがよい。
枝分かれしていいならハブのような石の存在を気にしなきゃいけないけど、その必要は無い。
なので、まずは「隣り合わせられる石のルール」1つをグラフの長さ1の辺1本とみなし、$c_i$ に含まれる全頂点間の最短距離を求める。
ここで、$N$ 頂点全ての点間の最短距離を求めるのはTLE,MLEなので注意。
そもそも到達できない2頂点があれば、不可能。
求められたら、$K$ 頂点で巡回セールスマン。
Pythonではライブラリが豊富なので、「巡回セールスマン」で検索してもAtCoderでは使えないライブラリとか近似解法の説明とかが出てくる。
「競プロ」とか添えて検索するとよい。
転倒数の意味の1つが「正しくない順序($i \lt j$ なのに $a_i \gt a_j$)となっているペア数」とわかっていれば、差分に着目すれば比較的簡単。
E問題よりすぐ解けた人も多そう。
まずは、$k=0$ の時の転倒数を求める。
さて、1個シフトしたらどうなるか。
3 1 4 0 2 ↓ 1 4 0 2 3
この時、動かす数(3)以外のペアは変わらない。
そして、
これで差分が計算できる。
今回は親切なことに順列なので、
と、$a_i$ の値だけからその個数が計算できる。