KUPC2013 : A - 旧総合研究７号館、B - ライオン

さて京都大学プログラミングコンテスト2013本戦。
あいにく当日参加できなかったので復習。
今のところEまでは解けているので、参加してもひどい結果にはならなかったはず…
http://kupc2013.contest.atcoder.jp/tasks/kupc2013_a
http://kupc2013.contest.atcoder.jp/tasks/kupc2013_b

A - 旧総合研究７号館

建物の名前が変わった年と、変わった後の名前が時間順で与えられる。
ある年が与えられるとき、その時の名前を答えよ。

年と名前の一覧を順に見て、答えるべき年より後の数字が出てきたら、その直前の名前を返す。

void solve() {
	int f,r,i,j,k,l,x,y,tx,ty;
	int N,Q;
	string S="kogakubu10gokan";
	
	cin>>N>>Q;
	FOR(i,N) {
		cin>>j;
		if(Q<j) break;
		cin >> S;
	}
	
	cout << S << endl;
}

B - ライオン

N個の檻のなかに、ライオンが0～X匹のいずれか入っている。
ここで、M個の情報として、L[i]～R[i]の檻の中に合計S[i]匹いることがわかっている。
ライオンの総数が最大になるような檻のライオンの数を答えよ。

N<=6、X<=10なので、各檻0～10匹全パターン試しても問題ない。
全パターン列挙して、M個の情報とマッチするものを返す。

int N,X,M;
int L[11],R[11],S[11];
int MM[11],ma,T[11];

void dfs(int cur) {
	int i;
	if(cur==N) {
		FOR(i,M) {
			int tot=0,j;
			for(j=L[i]-1;j<=R[i]-1;j++) tot+=T[j];
			if(tot!=S[i]) return;
		}
		
		int tot2=0;
		FOR(i,N) tot2+=T[i];
		if(tot2>ma) {
			ma=tot2;
			memcpy(MM,T,sizeof(MM));
		}
		return;
	}
	
	FOR(i,X+1) {
		T[cur]=i;
		dfs(cur+1);
	}
}

void solve() {
	int f,r,i,j,k,l,x,y,tx,ty;
	
	cin>>N>>X>>M;
	FOR(i,M) cin>>L[i]>>R[i]>>S[i];
	ma=-1;
	dfs(0);
	
	if(ma<0) {
		cout << -1 << endl;
	}
	else {
		FOR(i,N) {
			_P("%d",MM[i]);
			_P((i<N-1)?" ":"\n");
		}
	}
}

まとめ

まだこのあたりはラクだね。
Bは値の小ささに気が付くと簡単。