Official

A - 水の均等化 / Equalizing Water Editorial by kyopro_friends


初心者の方へ - AtCoder をはじめたばかりで何をしたらよいか分からない方は、まずは [practice contest](https://atcoder.jp/contests/practice/) の問題A「Welcome to AtCoder」を解いてみてください。基本的な入出力の方法が載っています。 - また、プログラミングコンテストの問題に慣れていない方は、[AtCoder Beginners Selection](https://atcoder.jp/contests/abs) の問題をいくつか解いてみることをおすすめします。 - [C++入門 AtCoder Programming Guide for beginners (APG4b)](https://atcoder.jp/contests/APG4b) は、競技プログラミングのための C++ 入門用コンテンツです。 - [Python入門 AtCoder Programming Guide for beginners (APG4bPython)](https://atcoder.jp/contests/APG4bpython) は、競技プログラミングのための Python 入門用コンテンツです。
---- $A$ の合計が $N$ の倍数でないとき答えは `No` 、 $N$ の倍数のとき答えは `Yes` になります。 操作によって水の総量は変化せず、どのタンクの水の量も整数のままなので、もし全てのタンクの水量を等しくできたとすると、水の総量は $N$ の倍数です。 逆に水の総量が $N$ の倍数のとき、$ X=\frac{1}{N}\sum_i A_i$ とすると、タンク $1,2,3,\ldots$ の順に「水が $X$ リットルより多いなら右隣のタンクにあげる、少ないなら右の方のタンクからもらう」とすることで、全てのタンクの水の量を $X$ リットルにすることができます。
補足 タンク $i$ の水が $X$ リットルより多いとき、その時点でタンク $i$ までに入っている水の量は $iX$ リットルより多いため、仮定より $i< N$ であり、右隣のタンクが存在する。
タンク $i$ の水が $X$ リットルより少ないとき、その時点でタンク $i$ までに入っている水の量は $iX$ リットル未満であるため、仮定よりタンク $i+1$ 以降に水を含むタンクが存在する。タンク $i+1$ 以降のタンクのうち水の入ったものを任意に1つとりタンク $j$ とすると、タンク $j$ から $j-1$ へ、$j-1$ から $j-2$ へ、……、$i+1$ から $j$ へ、と水を移す操作により、タンク $i$ の水を増やすことができる

総和を計算する際にはオーバーフローに注意してください。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
  int n;
  cin >> n;
  long long s=0;
  for(int i=0;i<n;i++){
    int a;
    cin >> a;
    s+=a;
  }

  if(s%n==0){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}

実装例 (Python)

N = int(input())
A = list(map(int,input().split()))

if sum(A) % N == 0:
  print("Yes")
else:
  print("No")

posted:
last update: