読者です 読者をやめる 読者になる 読者になる

Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

JOI予選 2012-2013

JOI

順当にいけば104点だと思います.

(2以外の)解答も載せるので良ければ参考にしてください.
一応ソースや解答, validationのために作ったプログラムは

http://www1.axfc.net/uploader/so/2717504

に置いています.

1.

解法 :
答えは L - max(国語を終わる日数, 算数をおわる日数)で, それぞれの切り上げを忘れない様に引き算を行う.

#include <cstdio>
#include <algorithm>

using namespace std;

typedef __int64 lint;

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);
}
13
5
27
3
9

2.

解法 : バケットを作って, 実際に1つしかないかを各ターン毎に見ていく.

#include <cstdio>
#include <cstring>

using namespace std;

typedef __int64 lint;

int main()
{
	int n;
	int a[200][3];
	int occ[101][3];
	int point[200];
	
	scanf("%d", &n);
	
	memset(occ, 0, sizeof(occ));
	
	for (int i = 0; i < n; i++){
		for (int j = 0; j < 3; j++){
			scanf("%d", &a[i][j]);
			occ[a[i][j]][j]++;
		}
	}
	
	memset(point, 0, sizeof(point));
	
	for (int i = 0; i < n; i++){
		for (int j = 0; j < 3; j++){
			point[i] += (occ[a[i][j]][j] == 1 ? a[i][j] : 0);
		}
	}
	
	for (int i = 0; i < n; i++) printf("%d\n", point[i]);
	
	return (0);
}

3.

解法 : ずらす量と先頭位置を決めて全探索すれば良い. 境界が怖いので配列を大きく取ってごまかした(が、実際は長さと比べて適切にbreakすれば良い.

#include <cstdio>
#include <cstring>

using namespace std;

typedef __int64 lint;

int main()
{
	int n;
	int len;
	char name[32];
	int ans = 0;
	
	scanf("%d", &n);
	scanf("%s", name);
	
	len = strlen(name);
	
	for (int i = 0; i < n; i++){
		static char query[10240];
		int qlen;
		memset(query, -1, sizeof(query));
		scanf("%s", query);
		qlen = strlen(query);
		
		for (int dx = 1; dx <= 34; dx++){
			for (int pos = 0; pos < qlen; pos++){
				bool ok = true;
				int k = 0;
				for (int p = pos; k != len; p += dx){
					if (name[k] != query[p]){
						ok = false;
						break;
					}
					k++;
				}
				if (ok){
					ans++;
					goto next;
				}
			}
		}
		next:;
	}
	
	printf("%d\n", ans);
	
	return (0);
}
7
11
63
42
47

4.

解法 : (日付, その日に来たシャツ)を状態としてもちDPをする. 2年前からの問4DPシリーズでは比較的取り組みやすいように感じた.

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;

typedef __int64 lint;

int main()
{
	int n, d;
	int dp[256][256]; //i日目に服jを着た時の最大値
	int heat[256];
	int mi[256], ma[256], val[256];
	
	memset(dp, 0, sizeof(dp));
	
	scanf("%d %d", &d, &n);
	
	for (int i = 1; i <= d; i++){
		scanf("%d", heat + i);
	}
	
	for (int i = 0; i < n; i++){
		scanf("%d %d %d", mi + i, ma + i, val + i);
	}
	
	for (int i = 2; i <= d; i++){
		for (int j = 0; j < n; j++){
			if (!(mi[j] <= heat[i] && heat[i] <= ma[j])) continue;
			for (int k = 0; k < n; k++){
				if (!(mi[k] <= heat[i - 1] && heat[i - 1] <= ma[k])) continue;
				dp[i][j] = max(dp[i][j], dp[i - 1][k] + abs(val[j] - val[k]));
			}
		}
	}
	
	int ans = -1;
	for (int i = 0; i < n; i++) ans = max(ans, dp[d][i]);
	
	printf("%d\n", ans);
	
	return (0);
}
235
409
18586
19556
19148

5.

扱う数の範囲に対して直方体の数が少ないので, 座標圧縮を行う.
その後に配列を塗りつぶし, K以上の数の直方体が被っている区間の大きさを足せば良い.

#include <cstdio>
#include <cstring>
#include <map>
#include <vector>
using namespace std;

typedef __int64 lint;

int main()
{
	int N, K;
	static int cube[128][128][128];
	int x1[64], x2[64], y1[64], y2[64], z1[64], z2[64];
	vector<int> xs, ys, zs;
	map<int, int> convx, convy, convz;
	map<int, int> motox, motoy, motoz;
	
	scanf("%d %d", &N, &K);
	
	for (int i = 0; i < N; i++){
		scanf("%d %d %d %d %d %d", x1 + i, y1 + i, z1 + i, x2 + i, y2 + i, z2 + i);
		xs.push_back(x1[i]); xs.push_back(x2[i]);
		ys.push_back(y1[i]); ys.push_back(y2[i]);
		zs.push_back(z1[i]); zs.push_back(z2[i]);
	}
	
	sort(xs.begin(), xs.end());
	sort(ys.begin(), ys.end());
	sort(zs.begin(), zs.end());
	
	int idx = 0;
	convx[xs[0]] = idx;
	motox[idx++] = xs[0];
	for (int i = 1; i < 2 * N; i++){
		if (xs[i] != xs[i - 1]){
			convx[xs[i]] = idx;
			motox[idx++] = xs[i];
		}
	}
	
	idx = 0;
	convy[ys[0]] = idx;
	motoy[idx++] = ys[0];
	for (int i = 1; i < 2 * N; i++){
		if (ys[i] != ys[i - 1]){
			convy[ys[i]] = idx;
			motoy[idx++] = ys[i];
		}
	}
	
	idx = 0;
	convz[zs[0]] = idx;
	motoz[idx++] = zs[0];
	for (int i = 1; i < 2 * N; i++){
		if (zs[i] != zs[i - 1]){
			convz[zs[i]] = idx;
			motoz[idx++] = zs[i];
		}
	}
	
	for (int i = 0; i < N; i++){
		//printf("%d %d %d %d %d %d\n", convx[x1[i]], convy[y1[i]], convz[z1[i]], convx[x2[i]], convy[y2[i]], convz[z2[i]]);
		for (int x = convx[x1[i]]; x < convx[x2[i]]; x++){
			for (int y = convy[y1[i]]; y < convy[y2[i]]; y++){
				for (int z = convz[z1[i]]; z < convz[z2[i]]; z++){
					cube[x][y][z]++;
				}
			}
		}
	}
	
	lint ans = 0;
	for (int i = 0; i < 128; i++){
		for (int j = 0; j < 128; j++){
			for (int k = 0; k < 128; k++){
				/*if (cube[i][j][k] >= K){
					printf("!!\n");
					printf("motox[i + 1] = %d motox[i] = %d motoy[j + 1] = %d motoy[j] = %d motoz[k + 1] = %d motoz[k] = %d\n", motox[i + 1], motox[i], motoy[j + 1], motoy[j], motoz[k + 1], motoz[k]);
				}*/
				ans += (cube[i][j][k] >= K ? (lint)(motox[i + 1] - motox[i]) * (motoy[j + 1] - motoy[j]) * (motoz[k + 1] - motoz[k]) : 0);
			}
		}
	}
	
	printf("%I64d\n", ans);
	
	return (0);
}
1801
347149566041429203
124015464949851877
991380998439054609
65264947770876113

6.
わからなかったので部分点狙いの再帰関数を書いた. 想定解法は直前の6手をもつbitDPらしいです. ほえ~

#include <cstdio>
#include <algorithm>

using namespace std;

typedef __int64 lint;


int w, h;
char field[64][64];
bool vis[64][64][3];
int ans;
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

void search(int ny, int nx, int left, int val)
{
	if (ny == h - 1 && nx == w - 1){
		ans = max(val, ans);
		if (left == 0) return;
	}
	
	for (int i = 0; i < 4; i++){
		if (left == 0 && i >= 2) continue;
		int ty = ny + dy[i], tx = nx + dx[i];
		if (ty < 0 || tx < 0 || ty >= h || tx >= w || field[ty][tx] == '#') continue;
		if ('1' <= field[ty][tx] && field[ty][tx] <= '9'){
			int plus = field[ty][tx] - '0';
			field[ty][tx] = '.';
			//if (!vis[ty][tx][left - (i >= 2)]){
				vis[ty][tx][left - (i >= 2)] = true;
				search(ty, tx, left - (i >= 2), val + plus);
				field[ty][tx] = plus + '0';
				vis[ty][tx][left - (i >= 2)] = false;
			//}
		}
		else {
			//if (!vis[ty][tx][left - (i >= 2)]){
				vis[ty][tx][left - (i >= 2)] = true;
				search(ty, tx, left - (i >= 2), val);
				vis[ty][tx][left - (i >= 2)] = false;
			//}
		}
	}
	return;
}

int main()
{
	int k;
	
	scanf("%d %d %d", &h, &w, &k);
	
	for (int i = 0; i < h; i++){
		scanf("%s", field[i]);
	}
	
	search(0, 0, k, 0);
	
	printf("%d\n", ans);
	
	return (0);
}
21
?
?
?
?


去年からやってきたことが, 少しは実った気がするので良かったです.
本選にいけることを祈ります.