Official
A - 水の均等化 / Equalizing Water Editorial
by
----
$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+1$ 以降に水を含むタンクが存在する。タンク $i+1$ 以降のタンクのうち水の入ったものを任意に1つとりタンク $j$ とすると、タンク $j$ から $j-1$ へ、$j-1$ から $j-2$ へ、……、$i+1$ から $j$ へ、と水を移す操作により、タンク $i$ の水を増やすことができる
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 入門用コンテンツです。補足
タンク $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:
