ARC 079 C - Decrease (Judge ver.)

• 問題
• AC

増減する数を選べるとすると、$N+1$回操作をしたとき、最大値を取る$a_i$が$N+1$減ってその他の数が変化しないようにできることに注目する。

ステップ1

すべての数が$N$以上になる、またはすべての数が$N$未満になるまでシミュレーションする。後者の場合はここで終わりである。${\mathcal O}(N^2)$。

ステップ2

上に書いた通り、数を適当に選んで$N+1$回操作をすると、最大の$a_i$が$N+1$減ってその他の数が変化しないようにできることに注目すると、すべての数が$2N$以下（かつ$N$以上）になるまでの操作回数をまとめて数えられる。

具体的に述べれば、$a_i$に対して$(N+1)\lceil (a_i - 2N)/(N+1) \rceil$回の操作をすると、$a_i$が同じだけ減って$N \le a_i \le 2N$になる。¹

ステップ1が必要なのは、$(a_i)$の最小値が$N$未満だと$N+1$回の操作の途中で問題の条件を満たしてしまう場合があるからである。入力例4がこれに該当する。 ${\mathcal O}(N)$。

ステップ3

すべての数が$N$未満になるまでシミュレーションする。${\mathcal O}(N^2)$。

---

1. 実際には$a_i$を選んで操作できるわけではないが、最大値が$2N$以下になるまでにそれぞれの$a_i$に対して$(N+1)\lceil (a_i - 2N)/(N+1) \rceil$回の操作をすることには変わりないので、順番は気にしなくてよい。 ↩︎