概要

\(N\) 個のタンクに入っている水の合計を \(N\) 等分できるかどうかを判定する問題です。隣接するタンク間で水を自由に移動できるため、最終的に均等にできるかは合計が \(N\) で割り切れるかだけで決まります。

考察

重要な気づき：操作の自由度

一見すると「隣り合うタンク間でしか水を移動できない」という制約が厳しそうに思えます。しかし、よく考えると、隣り合うタンクを中継地点として使えば、任意のタンクから任意のタンクへ水を運べます。

例えば、タンク \(1\) からタンク \(3\) に水を \(1\) リットル運びたい場合： 1. タンク \(1\) → タンク \(2\) に \(1\) リットル移す 2. タンク \(2\) → タンク \(3\) に \(1\) リットル移す

これでタンク \(2\) の水量は変わらず、実質的にタンク \(1\) からタンク \(3\) に直接水を移したのと同じ結果になります。

問題の本質

操作を何回でも行えて、水を任意の場所に自由に移動できるということは、水の総量は保存されるという条件のもとで、好きな配分に変えられることを意味します。

すべてのタンクの水量を等しくするには、各タンクに \(\frac{\sum A_i}{N}\) リットルずつ入っている状態にする必要があります。これが整数でなければ実現不可能です（操作は \(1\) リットル単位のため、水量は常に整数です）。

したがって、判定条件は：

\[\sum_{i=1}^{N} A_i \mod N = 0\]

素朴なシミュレーションではダメな理由

実際に水の移動をシミュレーションしようとすると、\(A_i\) が最大 \(10^9\) と非常に大きいため、\(1\) リットルずつ移動する操作回数が膨大になり TLE になります。上記の考察により、シミュレーションは不要であり、割り切れるかの判定だけで十分です。

アルゴリズム

1. \(N\) 個の水量 \(A_1, A_2, \ldots, A_N\) を読み込む
2. 合計 \(S = \sum_{i=1}^{N} A_i\) を計算する
3. \(S \mod N = 0\) なら Yes、そうでなければ No を出力する

具体例

• \(N = 3\), \(A = [1, 2, 3]\)：合計 \(= 6\)、\(6 \mod 3 = 0\) → Yes（各タンク \(2\) リットルにできる）
• \(N = 3\), \(A = [1, 2, 4]\)：合計 \(= 7\)、\(7 \mod 3 = 1 \neq 0\) → No（均等に分けられない）

計算量

• 時間計算量: \(O(N)\)（配列の合計を計算するのに \(N\) 個の要素を走査）
• 空間計算量: \(O(N)\)（配列 \(A\) を格納するため）

実装のポイント

• \(A_i\) が最大 \(10^9\)、\(N\) が最大 \(10^5\) なので、合計は最大 \(10^{14}\) 程度になります。Python では整数のオーバーフローを気にする必要はありませんが、C++ などを使う場合は long long 型を使いましょう。

• 問題の本質は「合計が \(N\) で割り切れるか」という単純な判定であり、水の移動を実際にシミュレーションする必要はありません。

  ソースコード

N = int(input())
A = list(map(int, input().split()))
print("Yes" if sum(A) % N == 0 else "No")

---

この解説は claude4.6opus-thinking によって生成されました。