情報オリンピック予選 2012-2013

4完 + 部分点4点 = 84
だと思う。
1

#include <cstdio>
#include <algorithm>
using namespace std;

int main(){
	int l, a, b, c, d;
	scanf("%d %d %d %d %d", &l, &a, &b, &c, &d);
	printf("%d\n", l - max((a+c-1)/c, (b+d-1)/d));
	return 0;
}

2

#include <cstdio>
#include <algorithm>
using namespace std;

int main(){
	int n;
	scanf("%d", &n);
	int a[n][3];
	for(int i = 0; i < n; i++){
		scanf("%d %d %d", &a[i][0], &a[i][1], &a[i][2]);
	}
	int score[n];
	fill(score, score + n, 0);
	for(int k = 0; k < 3; k++){
		for(int i = 0; i < n; i++){
			bool f = true;
			for(int j = 0; j < n; j++){
				if(i==j)continue;
				if(a[i][k] == a[j][k])
					f = false;
			}
			if(f){
				score[i] += a[i][k];
			}
		}
	}
	for(int i = 0; i < n; i++)
		printf("%d\n", score[i]);
	return 0;
}

3

#include <iostream>
#include <algorithm>
using namespace std;

int main(){
	int n;
	string name;
	cin >> n;
	cin >> name;
	int ans = 0;
	for(int k = 0; k < n; k++){
		string old;
		cin >> old;
		for(int i = 0; i < old.size(); i++){
			if(old[i] != name[0]) continue;
			for(int j = i+1; j < old.size(); j++){
				if(old[j] != name[1]) continue;
				int d = j - i;
				bool f = true;
				for(int p = 2; p < name.size(); p++){
					if(i + d * p >= old.size()){
						f = false;
						break;
					}
					if(old[i + d * p] != name[p]){
						f = false;
						break;
					}
				}
				if(f){
					ans++;
					goto fin;
				}
			}
		}
fin:
		;
	}
	cout << ans << endl;
	return 0;
}

4
2通りの方法でコード書いてあってるか確認して提出しました
メモ化再帰

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_N = 200;
const int MAX_D = 200;
int D, N;
int T[MAX_D];
int A[MAX_N], B[MAX_N], C[MAX_N];

int memo[MAX_D][MAX_N][MAX_N];
//d日目、前日の服q 今日の服p
int solve(int d, int q, int p){
	int m;
	if(d == 0)
		m = 0;
	else
		m = abs(C[q] - C[p]);
	if(d == D-1) return m;
	if(memo[d][q][p] != -1) return memo[d][q][p];
	int ret = 0;
	for(int i = 0; i < N; i++){
		if(A[i] <= T[d+1] && T[d+1] <= B[i]){
			ret = max(ret, solve(d+1, p, i));
		}
	}
	return memo[d][q][p] = ret + m;
}
int main(){
	scanf("%d %d", &D, &N);
	for(int i = 0; i < MAX_D; i++)
		for(int j = 0; j < MAX_N; j++)
			for(int k = 0; k < MAX_N; k++)
				memo[i][j][k] = -1;
	for(int i = 0; i < D; i++)
		scanf("%d", &T[i]);
	for(int j = 0; j < N; j++){
		scanf("%d %d %d", &A[j], &B[j], &C[j]);
	}
	int ans = 0;
	for(int i = 0; i < N; i++){
		if(A[i] <= T[0] && T[0] <= B[i]){
			ans = max(ans, solve(0, 0, i));
		}
	}
	printf("%d\n", ans);
	return 0;
}

動的計画法

#include <cstdio>
#include <algorithm>
using namespace std;

int D, N;
int T[201];
int A[201], B[201], C[201];
int dp[201][201];
int main(){
	scanf("%d %d", &D, &N);
	for(int i = 0; i < D; i++)
		scanf("%d", &T[i]);
	for(int i = 0; i < N; i++)
		scanf("%d %d %d", &A[i], &B[i], &C[i]);
	for(int i = 1; i < D; i++){
		for(int j = 0; j < N; j++){
			if(!(A[j] <= T[i-1] && T[i-1] <= B[j]))continue;
			for(int k = 0; k < N; k++){
				if(!(A[k] <= T[i] && T[i] <= B[k]))continue;
				dp[i][k] = max(dp[i][k], dp[i-1][j] + abs(C[j] - C[k]));
			}
		}
	}
	int ans = 0;
	for(int i = 0; i < N; i++){
		ans = max(ans, dp[D-1][i]);
	}
	printf("%d\n", ans);
	return 0;
}

5
部分点解法

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX = 101;
int a[MAX][MAX][MAX];
int main(){
	int n, k;
	scanf("%d %d", &n, &k);
	for(int i = 0; i < n; i++){
		int x1, y1, d1, x2, y2, d2;
		scanf("%d %d %d %d %d %d", &x1, &y1, &d1, &x2, &y2, &d2);
		for(int x = x1; x < x2; x++)
			for(int y = y1; y < y2; y++)
				for(int d = d1; d < d2; d++)
					a[x][y][d]++;
	}
	int ans = 0;
	for(int x = 0; x < MAX; x++)
		for(int y = 0; y < MAX; y++)
			for(int d = 0; d < MAX; d++)
				if(a[x][y][d] >= k) ans++;
	printf("%d\n",ans);
	return 0;
}