第10回 2011年 日本情報オリンピック 予選 過去問 解答

6問目、解法はなんとか生えたけど実装してないので後で追加しておく。

JOI予選、ショートコーディングゲーになってる感否めない。
なんで今更予選の問題といているかというと予選落ちしたくないからです。

1

#include <bits/stdc++.h>

using namespace std;

int main(){
	int n=0,tmp;
	for(int i = 0;i < 4;i++)cin >> tmp,n+=tmp;
	cout << n / 60 << endl  << n % 60 << endl;
	return 0;
}

2

#include <bits/stdc++.h>

using namespace std;

int main(){

	int n,ans=0,naga;
	char ch[12];
	cin >> ch >> n;
	naga = strlen(ch);
	while(n--){
		char tmp[22];
		cin >> tmp;
		int len = strlen(tmp);
		for(int i = 0;i < len;i++) tmp[len+i] = tmp[i];
		for(int i = 0;i < len*2-naga;i++){
			for(int j = 0;j < naga;j++){
				if(tmp[i+j] != ch[j])goto out;
			}
			ans++;
			break;
			out:
			;
		}
	}
	cout << ans << endl;

	return 0;
}

3

#include <bits/stdc++.h>

using namespace std;
int n,k;
int main(){
	cin >> n >> k;
	while(k--){
		int a,b;
		cin >> a >> b;
		int ans =  min(min(a,n-a+1),min(b,n-b+1))%3;
		if(ans == 0)ans = 3;
		cout << ans << endl;
	}
	return 0;
}

4

#include <bits/stdc++.h>

using namespace std;
unsigned long long int dp[128][23];
int n;
int main(){
	cin >> n;
	dp[0][0] = 1;
	for(int i = 1;i <= n-1;i++){
		int k;
		cin >> k;
		for(int j = 0;j <= 20;j++){
			if(j-k >= 0)dp[i][j] += dp[i-1][j-k];
			if(j+k <= 20)dp[i][j] += dp[i-1][j+k];
			if(i == 1 && k == 0 && j == 0)dp[i][j]--;
		}
	}
	int ans;
	cin >> ans;
	printf("%lld\n",dp[n-1][ans]);
	return 0;
}

5

#include <bits/stdc++.h>
using namespace std;
const int INF = 10000000;
typedef pair<int,int> P;
int da[] = {1,0,-1,0};
int db[] = {0,1,0,-1};
int h,w,n,ans=0;
char m[1002][1002];
int d[1002][1002];
int main(){
	scanf("%d%d%d",&h,&w,&n);
	for(int i = 0;i < h;i++){
		scanf("%s",m[i]);
	}
	int a,b;
	for(int i = 0;i < h;i++){
		for(int j = 0;j < w;j++){
			if(m[i][j] == 'S'){
				a = i,b = j;
				break;
			}
		}
	}
	for(int c = 1;c <= n;c++){
		for(int i = 0;i <= h;i++){
			for(int j = 0;j <= w;j++){
				d[i][j] = INF;
			}
		}
		d[a][b] = 0;
		queue<P> que;
		que.push(P(a,b));
		while(que.size()){
			P p = que.front(); que.pop();
			int aa = p.first,bb = p.second;
			if(m[aa][bb] - '0' == c){
				ans += d[aa][bb];
				a = aa,b = bb;
				break;
			}
			for(int i = 0;i < 4;i++){
				int na = aa + da[i];
				int nb = bb + db[i];
				if(na >= 0 && na < h && nb >= 0 && nb < w && m[na][nb] != 'X' && d[na][nb] == INF){
					d[na][nb] = d[aa][bb] + 1;
					que.push(P(na,nb));
				}
			}
		}
	}
	printf("%d\n",ans);
	return 0;
}