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

日本情報オリンピック 第10回予選 自分の提出した解答

未だ正答は公表されていないので、あっているかどうかは分かりません。
じきに公開されると思います。

JOI 2010-2011 予選 問題・採点用入力

前年度の過去問にに比べれば難しい年だったと思うが、一昨年などより難しい年もあったようで、
問題も全体的にひっかけのような感じではなかった。

問1. 合計時間 (Total Time)

4行の各秒数の合計を分と秒に分けて出力しろ、というだけ。

#include <cstdio>

int main()
{
	int ha, ab, bc, ch;
	scanf("%d\n%d\n%d\n%d\n", &ha, &ab, &bc, &ch);
	int total = ha + ab + bc + ch;
	int tsec = total % 60;
	int tmin = (total - tsec) / 60;
	printf("%d\n%d\n", tmin, tsec);
	return 0;
}

問2. 指輪 (Ring)

リング状に並んでいる文字列が特定の文字列を含むか調べろというだけ。

#include <iostream>
#include <string>
using namespace std;
int main()
{
	string needle;
	cin>>needle;
	int N;
	cin>>N;
	int cnt = 0;
	for(int i = 0; i < N; i++){
		string haystack;
		cin>>haystack;
		string s = haystack + haystack + haystack;
		if(s.find(needle) != string::npos){
			cnt++;
		}
	}
	cout<<cnt<<endl;
	return 0;
}

問3. タイル (Tile)

少し悩んだが考えれば分かる。

#include <cstdio>
inline int colour(int N, int a, int b){
	if(a > N / 2) a = N - a + 1;
	if(b > N / 2) b = N - b + 1;
	if(a > b){
		int t = a;
		a = b;
		b = t;
	}
	return ((a - 1) % 3) + 1;
}
int main()
{
	int N, K;
	scanf("%d\n%d\n", &N, &K);
	for(int i = 0; i < K; i++){
		int a, b;
		scanf("%d %d\n", &a, &b);
		printf("%d\n", colour(N, a, b));
	}
	return 0;
}

問4. 1年生 (A First Grader)

解けず。簡単なDPだったらしい。直前にTwitterで「DPまだとけないとか絶望」みたいな事を書いた直後のこれなので非常に後悔。

問5. チーズ (Cheese)

ネズミが最短経路でチーズを食うが、チーズを食いライフがたまらないとより固いチーズは食えない。
レベル9の硬さまでのチーズしかないので、ライフが9になるまでチーズを食うごとに幅優先探索すれば良いだけ。

#include <iostream>
#include <string>
#include <vector>
#include <climits>
#include <queue>
using namespace std;
inline bool validate(int x, int y, int H, int W){
	return 0 <= x && x < H && 0 <= y && y < W;
}
int main()
{
	int H, W, N;
	cin>>H>>W>>N;
	vector<string> v(H);
	for(int i = 0; i < H; i++)
		cin>>v[i];
	int sx = 0, sy = 0;
	for(int i = 0, f = 0; i < H; i++){
		for(int j = 0; j < W; j++){
			if(v[i][j] == 'S'){
				f = 1;
				sx = i; sy = j;
				break;
			}
		}
		if(f) break;
	}

	int cheese = N;
	int dst = 0;
	int life = 1;
	while(cheese > 0){
		vector<vector<int> > w(H, vector<int>(W, INT_MAX));
		queue<pair<int, int> > q;
		q.push(make_pair(sx, sy));
		w[sx][sy] = 0;
		while(!q.empty()){
			const int tbl[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
			pair<int, int> p = q.front(); q.pop();
			const int x = p.first, y = p.second;
			if('1' <= v[x][y] && v[x][y] <= '9'){
				if(life >= (v[x][y] - '0')){
					life++;
					cheese--;
					v[x][y] = '.';
					if(life < 10 || cheese <= 0){
						sx = x, sy = y;
						dst += w[x][y];
						break;
					}
				}
			}
			for(int i = 0; i < 4; i++){
				int nx = x + tbl[i][0], ny = y + tbl[i][1];
				if(validate(nx, ny, H, W)){
					if(v[nx][ny] != 'X' && w[nx][ny] == INT_MAX){
						q.push(make_pair(nx, ny));
						w[nx][ny] = w[x][y] + 1;
					}
				}
			}
		}
	}
	cout<<dst<<endl;

	return 0;
}

問6. JOI 旗 (JOI Flag)

これもDPだったらしい。他で悩みすぎて6は考える時間もなかった。