東京工業大学プログラミングコンテスト2015 : K - 麻雀

最初解き方にてこずったけど、落ち着いたら解けた。
http://ttpc2015.contest.atcoder.jp/tasks/ttpc2015_k

問題

N人で総当たりで麻雀大会を行った。
すなわちC(N,4)通りの組み合わせで１回ずつ麻雀を行っている。

各人が１位を取ったと主張する回数A[i]が与えられる。
状態を満たすような順位の組み合わせが存在するか判定せよ。

解法

Nをソートし、A[i]の多い順で処理する。
N人で総当たりを行うと、各人が参加する試合数はC(N-1,3)である。
よって最多勝利者に対しA[N]≦C(N-1,3)ならばよいし、そうでなければ矛盾する。
A[i]＜C(N-1,3)の場合、余った(C(N-1,3)-A[i])試合はより合計１位回数の少ない人のために予備として取っておく。
この予備の累積をLとする。

以後、NをデクリメントしながらA[N]≦C(N-1,3)+Lか判定し、余った試合はLに繰り越していく。
最終的にL==0なら条件を満たす。

ll N;
ll A[10100];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	sort(A,A+N);
	
	ll left=0;
	while(N) {
		ll game=(N-1)*(N-2)*(N-3)/6;
		if(left+game<A[N-1]) return _P("NO\n");
		left = left+game-A[N-1];
		N--;
	}
	if(left==0) _P("YES\n");
	else _P("NO\n");
}

まとめ

一見複雑そうで、コードに落とすと単純なのは解いてて気持ちがいいね。