April Fools Day Contest 2014 : G. On a plane、H. A + B Strikes Back、I. Feed the Golorp

まだ続く変な問題。
http://codeforces.com/contest/409/problem/G
http://codeforces.com/contest/409/problem/H
http://codeforces.com/contest/409/problem/I

G. On a plane

N個の2次元座標が与えられるので、実数を答えよ。

テストケースの座標をプロットすると、「5+AVG Y」という文字列が出てくる。
そのためY座標の平均値に5を足せばよい。

void solve() {
	int f,i,j,k,l,x,y;
	double r=5;
	
	cin>>j;
	FOR(i,j) {
		double X,Y;
		cin>>X>>Y;
		r+=Y/j;
	}
	cout << r << endl;
}

H. A + B Strikes Back

A,Bに対しA+Bを答えよ。

A+Bを返すコードを繰り返しsubmitすればよい。
よく見るとWAのメッセージが毎回切り替わっているのがわかる。

本番はよくわからず何度もsubmitしているうちに正解してしまった。

void solve() {
	ll x,y;
	cin>>x>>y;
	cout << (x+y) << endl;
}

I. Feed the Golorp

謎の言語が与えられる。
各変数には0～9のいずれかの数値が与えられるので、数値の与え方のうち最小値を求めよ。

どうやら各文字列は"):-"で区切られていることがわかる。
連続した"_"をその数で置換し、演算子をカンマで置き換えると以下のようになる。

?(______________________/____+_______*__-_____*______-___):-__<___,___<____,____<_____,_____<______,______<_______.
↓
?(22,4,7,2,5,6,3):-2<3,3<4,4<5,5<6,6<7

右辺は各変数が満たすべき大小関係であり、左辺は答える変数名である。
よって右辺の大小関係から生成したグラフにより、変数をトポロジカルソートして0から9を順に割り当てていけばよい。

string S;
vector<int> V;
vector<int> E[1024];
vector<int> R[1024];
int inin[1024],num[1024];

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>S;
	S=S.substr(2);
	j=0;
	FOR(i,S.size()) {
		if(S[i]=='_') j++;
		else V.push_back(j),j=0;
		if(S[i]==')') break;
	}
	i+=3;
	x=j=0;
	for(;i<S.size();i++) {
		if(S[i]=='_') j++;
		else if(S[i]=='<') x=j,j=0;
		else if(S[i]=='>') x=-j,j=0;
		else {
			if(x>0) {
				E[x].push_back(j);
				R[j].push_back(x);
				inin[j]++;
			}
			else {
				E[j].push_back(-x);
				R[-x].push_back(j);
				inin[-x]++;
			}
			j=0;
			if(S[i]=='.') break;
		}
	}
	set<int> Q;
	MINUS(num);
	FOR(i,1024) if(inin[i]==0) Q.insert(i);
	
	while(!Q.empty()) {
		int k=*Q.begin();
		Q.erase(Q.begin());
		num[k]=0;
		FOR(i,R[k].size()) num[k]=max(num[k],num[R[k][i]]+1);
		if(num[k]>=10) return _P("false\n");
		FOR(i,E[k].size()) if(--inin[E[k][i]]==0) Q.insert(E[k][i]);
	}
	
	FOR(i,V.size()) if(num[V[i]]==-1) return _P("false\n");
	FOR(i,V.size()) _P("%d",num[V[i]]);
	_P("\n");
}

まとめ

入力のパースのめんどくささはともかく、内容はIが一番おもしろかった。
まぁ問題自体は大小関係のトポロジカルソートという割とオーソドックスな題材だけどね。