第11回日本情報オリンピック JOI2012 本選 問題1～4 解答ソース

問題1-JJOOII

やるだけ。実装。ちょい面倒。

#include <bits/stdc++.h>
using namespace std;

int ans,sum[4];;
char d[1000006];

void syokika(){
	for(int i = 0;i < 3;i++)sum[i] = 0;
}

int main(){
	scanf("%s",d);
	char mo[4];
	mo[0] = 'J';
	mo[1] = 'O';
	mo[2] = 'I';
	int len = strlen(d);
	int ban = 0;
	for(int nau = 0;nau < len;nau++){
		if(mo[ban] == d[nau]){
			sum[ban]++;
		}else{
			if(ban == 0){
				if(sum[0] == 0)continue;
				ban++;
				if(d[nau] == 'O'){
					sum[1]++;
				}else{
					syokika();
					ban = 0;
					continue;
				}
			}else if(ban == 1){
				if(sum[0] < sum[1] || d[nau] == 'J'){
					syokika();
					ban = 0;
					if(d[nau] == 'J')sum[0]++;
					continue;
				}
				sum[++ban]++;
			}else{
				if(sum[2] < sum[1] || sum[0] < sum[1]){
					syokika();
					ban = 0;
					if(d[nau] == 'J')sum[0]++;
					continue;
				}
				ans = max(ans,sum[1]);
				syokika();
				ban = 0;
				if(d[nau] == 'J')sum[0]++;
			}
		}
	}
	if(sum[0] >= sum[1] && sum[2] >= sum[1]){
		ans = max(ans,sum[1]);
	}
	printf("%d\n",ans);
	return 0;
}

問題2-たのしいカードゲーム

簡単なDP。簡単。メモリ注意。

#include <bits/stdc++.h>
using namespace std;

int ans,alen,blen,a[5004],b[5004],dp[3][5003];

int main(){
	scanf("%d%d",&alen,&blen);

	for(int i = 1;i <= alen;i++)scanf("%d",&a[i]);
	for(int i = 1;i <= blen;i++)scanf("%d",&b[i]);

	for(int i = 1;i <= blen;i++){
		for(int j = 1;j <= alen;j++){
			dp[i%2][j] = dp[i%2][j-1];
			if(b[i] == a[j]){
				dp[i%2][j] = max(dp[i%2][j],dp[(i-1)%2][j-1]+1);
			}
			ans = max(dp[i%2][j],ans);
		}
	}
	printf("%d\n",ans);
	return 0;
}

問題3-夜店

ちょっとだけ考えるDP。典型と言ってもいい。
花火の時間に気をつけるだけで後は単純ナップサック。

#include <bits/stdc++.h>
using namespace std;

int n,t,s,a[3004],b[3004],dp[3010][3010];

int main(){
	scanf("%d%d%d",&n,&t,&s);
	for(int i = 1;i <= n;i++)scanf("%d%d",&a[i],&b[i]);

	for(int i = 1;i <= n;i++){
		for(int j = 0;j <= t;j++){
			dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
			if(j-b[i] < 0)continue;
			if(s < j && s > j-b[i])continue;
			dp[i][j] = max(dp[i][j],dp[i-1][j-b[i]]+a[i]);
		}
	}
	printf("%d\n",dp[n][t]);
	return 0;
}

問題4-釘

いもす法。本番のメモリ制限は512MBで余裕があるけどAOJでは 65536 KBなのでint型の5000×5000の配列をとると厳しいのでわざわざvectorを使う作業が必要になる。

#include <bits/stdc++.h>
using namespace std;

int n,m;
vector<int> d[5020];

int main(){
	scanf("%d%d",&n,&m);

	for(int i = 0;i <= n+5;i++){
		d[i].resize(i+10);
	}

	while(m--){
		int a,b,x;
		scanf("%d%d%d",&a,&b,&x);

		d[a][b]++;
		d[a][b+1]--;
		d[a+x+1][b]--;
		d[a+x+2][b+1]++;
		d[a+x+1][b+x+2]++;
		d[a+x+2][b+x+2]--;
	}

	for(int i = 1;i <= n+3;i++){
		for(int j = 1;j <= i+3;j++){
			d[i][j] += d[i][j-1];
		}
	}

	for(int i = 1;i <= n+3;i++){
		for(int j = i;j <= n+3;j++){
			d[j][i] += d[j-1][i];
		}
	}

	for(int i = 1;i <= n+3;i++){
		for(int j = 1;j <= i+3;j++){
			d[i][j] += d[i-1][j-1];
		}
	}
	int ans = 0;
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= i+3;j++){
			if(d[i][j] > 0)ans++;
		}
	}
	printf("%d\n",ans);
	return 0;
}