JOI予選解き直し+本選不参加記

予選落ちしたから、復習してみました。
本選はボーダー超えられるか試してみたかったけど、5を解きたくなったから断念しました。

2ヶ月前と比べるとだいぶ強くなったような気がしますが、まだまだですね。

予選
4.パスタ
結構バグが怖い。本番では2時間掛かってバグが取れなかったけど、さっき書いたら、一発で書けた。

int P[100],dp[100][3][2],ans;
//dp[日数][メニュー][二日連続で同じだった場合は1]

int main(){
	int n,k;
	cin>>n>>k;
	for(int i = 0; i < k; i++){
		int a,b;
		cin>>a>>b;
		P[a-1] = b;
	}
	if(P[0]){
		dp[0][P[0]-1][0] = 1;
	}else{
		dp[0][0][0]=dp[0][1][0]=dp[0][2][0] = 1;
	}
	for(int i = 1; i < n; i++){
		if(P[i]){
			dp[i][P[i]-1][0] = (dp[i-1][P[i]%3][0]+dp[i-1][(P[i]+1)%3][0]+dp[i-1][P[i]%3][1]+dp[i-1][(P[i]+1)%3][1]) % 10000;
			dp[i][P[i]-1][1] = dp[i-1][P[i]-1][0];
		}else{
			for(int j = 0; j < 3; j++){
				dp[i][j][0] = (dp[i-1][(j+1)%3][0]+dp[i-1][(j+2)%3][0]+dp[i-1][(j+1)%3][1]+dp[i-1][(j+2)%3][1]) % 10000;
				dp[i][j][1] = dp[i-1][j][0];
			}
		}
	}
	for(int i = 0; i < 3; i++){
		for(int j = 0; j < 2; j++){
			ans += dp[n-1][i][j];
		}
	}
	cout<<ans%10000<<endl;
	return 0;
}

5.イルミネーション
端っこから塗りつぶす。意外と難しかったので、2ヶ月前だったら絶対解けなかったと思います。

int dx[6] = {0,-1,-1,0,1,1};
int dy[2][6]= {{1,0,-1,-1,-1,0},{1,1,0,-1,0,1}};
int g[102][102],w,h,used[102][102],ans;


int check(int x, int y){
	int res = 0;
	for(int i = 0; i < 6; i++){
		if(g[x+dx[i]][y+dy[x%2][i]] == -1)res++;
	}
	return res;
}




int main(){
	cin>>w>>h;
	memset(g,-1,sizeof(g));
	for(int i = 1; i <= h; i++){
		for(int j = 1; j <= w; j++){
			cin>>g[i][j];
		}
	}

	for(int i = 1; i <= h; i++){
		for(int j = 1; j <= w; j++){
			if(i != 1 && i != h && j != 1 && j != w) continue;
			if(!g[i][j]){
				g[i][j]=-1;
				queue<pair<int,int> > qu;
				qu.push(make_pair(i,j));
				while(!qu.empty()){
					int x = (qu.front()).first;
					int y = (qu.front()).second;
					qu.pop();
					for(int i = 0; i < 6; i++){
						if(!g[x+dx[i]][y+dy[x%2][i]]){
							g[x+dx[i]][y+dy[x%2][i]] = -1;
							qu.push(make_pair(x+dx[i],y+dy[x%2][i]));
						}
					}
				}
			}
		}
	}
	for(int i = 1; i <= h; i++){
		for(int j = 1; j <= w; j++){
			if(g[i][j] == 1){
				ans += check(i,j);
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

6はまだ解いてません。解けるか分かりませんが。

本選
1.JJOOII (JJOOII)
前から見ていって、条件を満たしているかを確認する。一応サンプルは通りました。

string s;
int nj,no,ni,ans;

int main(){
	cin>>s;
	int len = s.size();
	int k = 0;
	while(k < len){
		while(k < len && s[k] == 'J'){
			nj++;
			k++;
		}
		while(k < len && s[k] == 'O'){
			no++;
			k++;
		}
		while(k < len && s[k] == 'I'){
			ni++;
			k++;
		}
		if(nj >= no && no <= ni){
			ans = max(ans,no);
		}
		nj = no = ni = 0;
	}
	cout<<ans<<endl;
	return 0;
}

2.たのしいカードゲーム(Card Game is Fun)
個人的に難しかった。O(n^3)なので少し修正だけしないといけないが、早く寝なきゃいけないのでそのまま。たぶんすぐ直せます。サンプルは通ります。

int a,b,A[5000],B[5000],ans;

bool f(int s, int t){//この関数と
	int k = 0;
	for(int i = s; i <= t; i++){
		while(k<a && A[k] != B[i]) k++;
		if(k>=a) return false;
	}
	return true;
}

int main(){
	scanf("%d %d",&a,&b);
	for(int i = 0; i < a; i++) scanf("%d",&A[i]);
	for(int i = 0; i < b; i++) scanf("%d",&B[i]);

	for(int i = 0; i < b; i++){
		for(int j = i; j < b; j++){//ここを直す
			if(ans<j-i+1 && f(i,j)){
				ans = j-i+1;
			}
		}
	}
	printf("%d",ans);
	return 0;
}

3.夜店(Night Market)
ナップサック問題を解く。後ろから数えるときにバグが発生して大変だったけど、たぶん大丈夫なはず。サンプルは通りました。

int n,t0,t1,A[3000],B[3000],dp0[3001][3000],dp1[3001][3000],ans;


int main(){
	scanf("%d %d %d",&n,&t1,&t0);
	t1 -= t0;
	for(int i = 0; i < n; i++){
		scanf("%d %d",&A[i],&B[i]);
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= t0; j++){
			for(int k = 0; k < i; k++){
				dp0[i][j] = max(dp0[i-1][j],j>=B[k] ? dp0[i-1][j-B[k]] + A[k] : 0);
			}
		}
	}
	for(int i = n-1; i >= 0; i--){
		for(int j = 1; j <= t1; j++){
			for(int k = n-1; k >= i; k--){
				dp1[i][j] = max(dp1[i+1][j],j>=B[k] ? dp1[i+1][j-B[k]] + A[k] : 0);
			}
		}
	}
	for(int i = 0; i <= n; i++){
		ans = max(ans,dp0[i][t0]+dp1[i][t1]);
	}
	printf("%d",ans);
	return 0;
}

4.釘(Nails)
全部塗りつぶしてみたけど、たぶん間に合わない。
辺若しくは点だけ塗りつぶして最後に全部塗るか、塗らずに数えれば間に合うような気がするけど、早く寝ないといけないので今日は諦める。短時間で実装できるかどうか分からないから、あとでやってみる。サンプルは通りました。

int n,m,tr[3001][3001],y[500000],x[500000],s[500000],ans;

int main(){
	cin>>n>>m;
	for(int i = 0; i < m; i++){
		scanf("%d %d %d",&x[i],&y[i],&s[i]);
	}
	for(int i = 0; i < m; i++){
		for(int j = 0; j <= s[i]; j++){
			for(int k = 0; k <= j; k++){
				tr[x[i]+j][y[i]+k] = 1;
			}
		}
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= i; j++){
			ans += tr[i][j];
		}
	}
	cout<<ans;
	return 0;
}

5.JOI 国のお祭り事情(Festivals in JOI Kingdom)
資料を見ても、解説見てもよく分からなかった。
とりあえず、dijkstra法で距離を求めてみたけど、そこから先が分からない。