概要

\(N\) 個のタンクに入った水を、隣り合うタンク間で移動させることで、すべてのタンクの水の量を等しくできるかを判定する問題です。

考察

この問題を解くための重要なポイントは、「操作によってシステム全体の水の総量は変化しない」ことと、「水の移動の自由度」に注目することです。

1. 水の総量は不変（不変量）

隣り合うタンク間で水を移し替える操作では、一方のタンクの水が減った分だけもう一方のタンクの水が増えるため、全タンクの水の合計値 \(S = \sum A_i\) は操作の前後で変わりません。

2. 任意のタンク間で水を移動可能

操作は「隣り合うタンク間」に限定されていますが、これを繰り返すことで、例えばタンク 1 からタンク 3 へ水を移したい場合は「1 → 2 → 3」という経路で水を運ぶことができます。つまり、十分な回数の操作を行えば、どのタンクからどのタンクへも（水がある限り）自由に水を移動させることができます。

3. 均等化できる条件

すべてのタンクの水の量を等しくするためには、各タンクの水の量は最終的に \(S / N\) リットルになる必要があります。 ここで、問題の条件から以下のことが分かります。 - 初期の各タンクの水量は整数である。 - 操作は 1 リットル単位で行われる。

したがって、最終的な各タンクの水量 \(S / N\) も整数でなければなりません。もし \(S\) が \(N\) で割り切れない場合、どのように水を移動させても 1 リットル単位の操作では完全に均等に分けることは不可能です。 逆に、\(S\) が \(N\) で割り切れるのであれば、余分な水があるタンクから足りないタンクへ順番に水を運ぶことで、必ずすべてのタンクを \(S / N\) リットルに調整することができます。

以上のことから、この問題は「全タンクの水の合計 \(S\) が タンクの数 \(N\) で割り切れるか」を判定する問題に帰着されます。

アルゴリズム

1. 入力された \(N\) 個の整数の合計 \(S\) を計算します。
2. \(S\) を \(N\) で割った余りが \(0\) であるかを確認します。
3. 余りが \(0\) ならば Yes、そうでなければ No を出力します。

計算量

• 時間計算量: \(O(N)\)
  • \(N\) 個の要素の合計を計算するのに \(O(N)\) かかります。
• 空間計算量: \(O(N)\)
  • 入力された \(N\) 個の要素をリスト等に保持する場合、\(O(N)\) のメモリを使用します。

実装のポイント

• Python では int 型が任意精度（無限精度）整数を扱うため、合計値 \(S\) が非常に大きな値（最大 \(10^{14}\) 程度）になってもオーバーフローを心配せずに計算できます。

• 大量の入力を読み込む際は、sys.stdin.read().split() を使うと高速に処理できる場合があります。

  ソースコード

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、空白で分割します。
    # Nが最大10^5、各Aiが最大10^9であるため、この方法は効率的です。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 最初の要素はタンクの数 N です。
    n = int(input_data[0])
    
    # 残りの要素は各タンクの水量 A_i です。
    # 水の移動は1リットル単位で行われ、開始時の水量も整数であるため、
    # 最終的にすべてのタンクの水量を等しくするには、その値が整数である必要があります。
    # つまり、すべてのタンクの合計水量が N で割り切れることが必要十分条件となります。
    
    # 隣り合うタンク間で双方向に水を移動できるため、
    # 合計水量が N の倍数であれば、必ずすべてのタンクの値を均等（合計/N）にできます。
    
    # 合計水量を計算します（Pythonのint型は任意精度であるため、大きな和も扱えます）。
    total_water = sum(map(int, input_data[1:n+1]))
    
    # 合計水量が N で割り切れるかどうかを判定します。
    if total_water % n == 0:
        print("Yes")
    else:
        print("No")

if __name__ == '__main__':
    solve()

---

この解説は gemini-3-flash-thinking によって生成されました。