Codeforces Round #673 (Div. 2) - 人間だけど競プロやる

C. k-Amazing Numbers

添字と境界条件の扱いがめんどくさい問題。
気づき

範囲を全部試すのは無理
ある値を選んだとき、全体を覆うのに必要な最短の範囲を求めることができる

現れる数字は1からNまでしかないので、順番にどれだけの範囲があれば全体をカバーできるかをもとめて、範囲の長さ1からNまで出力すれば良い。

解法

同じ数字が現れるインデックスを求める
数字ごとに全体をカバーするのに必要な最小の範囲を求める（一個前(と先頭と終端)のインデックスとの差のmax）
同じ範囲の大きさが必要な場合、数字が小さいほうが優先

という処理で B[範囲の大きさ] = 数字の配列を作って順番に出力すれば良い。

D. Make Them Equal

Cより簡単では疑惑
この手の問題を見たときはまず確認することがあって、

不変量に注目する

問題の操作をみると、同じ値を「足して」「引いて」いるから、全体の合計は変わらないことがわかる。
こういった不変量に注目すると問題がみえてくることがある。
今回は、合計がかわらないという条件で全体を等しくするので、それぞれは $\frac{sum}{N}$ で等しくなってそれ以外にない。
あとは、「 $1 \times x$ 」での操作が最も柔軟性が高いことにきづければ、なるべくインデックス1に移動させてから、それぞれのインデックスに、 $\frac{sum}{N}$ ずつ分配すれば良いことに気づく。
また、（インデックス1から順番に操作できるとは限らないが）、 $N \times 2$ 回あれば、全体をインデックス1に移動できることもわかる。

解法

sumを配列aの合計とする
$a_i$ が $i$ で割り切れるなら $a_1$ に移動する（ $a_i$ から $a_i$ を引いて、 $a_0$ に $a_i$ を足す）
$a_i$ が $i$ で割り切れないなら、 $m=i - (a_i \mod i)$ をインデックスmかインデックス1から移動して加算することで、 $i$ で割り切れるように調節する（そして2の操作）
$a_1$ がsum、 $a_2$ から $a_N$ が0になる
$a_1$ から各インデックスへ $\frac{sum}{N}$ ずつ移動する

$a_1$ に集めるのに $N \times 2$ 回、 $a_1$ から分配するのに $N$ 回で、合計 $N \times 3$ 回に収まる。