kmjp's blog

競技プログラミング参加記です

Codeforces #278 Div2 B. Candy Boxes

Codeforces

CF278に参加。
Cをさっさと解けたと思ったらコーナーケース見落とし、Bは問題文の読み間違えでpretest通せず、という散々な出来。
今回のDiv2Bはポイントを見ると難易度的にDiv1Aと同等、ということでここで扱ってみる。
http://codeforces.com/contest/488/problem/B

問題

４つの数値X[i]が昇順に並んでいる数列がある。この数列に対して以下の３値を考える。

  • 平均：４値の和を４で割ったもの
  • メディアン：X[1]+X[2]を２で割ったもの
  • 範囲：X[3]-X[0]

条件を満たす数列とは、上記３つの値が一致するものを指す。

ここで、X[i]のうち0～4個の値が与えられる。
４個に満たない分は1～10^6の範囲の数値を埋めることで、条件を満たす数列が生成できるか答えよ。

解法

３つの条件を式で書くと、(X[0]+X[1]+X[2]+X[3])/4 = (X[1]+X[2])/2 = X[3]-X[1] となる。
この式から、以下の２つの関係がわかる。

  • X[3] = 3*X[0]
  • X[0]+X[3] = X[1]+X[2]
  • N==4の場合：
    • X[i]が上記関係を満たすかチェックするだけ
  • N==0またはN==1の場合：
    • N==1の場合は入力値を、N==0の場合は1をX[0]に入れる。
    • あとは上記式より、X[1]=X[2]=2*X[0]、X[3]=3*X[0]とすればよい。
  • N==2またはN==3の場合：
    • 未確定の値１つまたは２つを総当たりし、条件を満たすものを探す。
    • X[3] = 3*X[0]の条件より、登場する値は1500以下で済むはずなので、1500^2通り調べればよい。
#include <bits/stdc++.h>
using namespace std;
typedef signed long long ll;

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<to;x++)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N;
int A[4];

int ok() {
	int B[4];
	memmove(B,A,sizeof(B));
	sort(B,B+4);
	if(B[0]*3!=B[3]) return false;
	if(B[1]+B[2]!=B[0]+B[3]) return false;
	return true;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	sort(A,A+i);
	if(N==0 || N==1) {
		if(N==0) A[0]=1;
		_P("YES\n%d\n%d\n%d\n",A[0]*2,A[0]*2,A[0]*3);
		if(N==0) _P("%d\n",A[0]);
		return;
	}
	else if(N==2) {
		for(A[2]=1;A[2]<=1500;A[2]++) for(A[3]=1;A[3]<=1500;A[3]++) if(ok()) return _P("YES\n%d\n%d\n",A[2],A[3]);
	}
	else if(N==3) {
		for(A[3]=1;A[3]<=1500;A[3]++) if(ok()) return _P("YES\n%d\n",A[3]);
	}
	else if(N==4) {
		if(ok()) return _P("YES\n");
	}
	_P("NO\n");
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false);
	FOR(i,argc-1) s+=argv[i+1],s+='\n';
	FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	solve(); return 0;
}

まとめ

場合分けが面倒だけど、シンプルな問題設定でこれだけ場合分けさせられるのはなかなか良いね。