Autumn Fest

結果 : ooox------- 30+50+60=140pts, 63rd.

感想 :
最後の一時間は参加していなかったものの、結局これ以上の点は望めなかったと思う. 実力通りかなあ.
結局答え聞いちゃえば分かるんだけど、閃かなかったら何にもならないし、それがコンテストなんだと思う.
あと、Dの埋め込みは思いついたけど不安でやらなかったので、取り敢えず次からは"思いついたことは(ある程度正当性を示して)できるだけ実装する"ことを心がけようと思う.

解答 :

A. 焦っていたので汚いです.

#include <cstdio>
#include <algorithm>

using namespace std;

int main()
{
	int N, T;
	int part[20], ptr[20];
	pair<int, int> tbl[20][10];
	scanf("%d %d", &N, &T);
	
	for (int i = 0; i < N; i++){
		scanf("%d", &part[i]);
	}
	
	int idx;
	for (int i = 0; i < 2; i++){
		idx = 0;
		for (int j = 0; j < N; j++){
			for (int k = 0; k < part[j]; k++){
				int t;
				scanf("%d", &t);
				if (i == 0){
					tbl[j][k].first = t;
				}
				else {
					tbl[j][k].second = t;
				}
			}
		}
	}
	memset(ptr, -1, sizeof(ptr));
	int res = 0;
	int time = 0;
	
	while (1){
		int flg = true;
		for (int i = 0; i < N; i++){
			if (ptr[i] + 1 != part[i]){
				flg = false;
				break;
			}
		}
		if (flg) break;
		pair<int, int> mx = make_pair(10000, 10000);
		int pos = -1;
		for (int i = 0; i < N; i++){
			if (ptr[i] + 1 != part[i] && mx.first > tbl[i][ptr[i] + 1].first){
				mx = tbl[i][ptr[i] + 1];
				pos = i;
			}
		}
		if (time + mx.second > T) break;
		else {
			ptr[pos]++;
			time += mx.second;
		}
	}
	
	for (int i = 0; i < N; i++){
		if (~ptr[i]) res += tbl[i][ptr[i]].first;
	}
	
	printf("%d\n", res);
	
	return (0);
}

B. 縦と横で累積和を取ってdfs. UnionFindでも良いらしい.

#include <cstdio>
#include <algorithm>

using namespace std;

char str[128][128];
int h[128][128], w[128][128];
int H, W;

bool v[128][128];
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

void dfs(int ty, int tx)
{
	v[ty][tx] = true;
	for (int i = 0; i < 4; i++){
		int mx = tx + dx[i], my = ty + dy[i];
		if (0 <= mx && mx < W && 0 <= my && my < H && !v[my][mx] && str[my][mx] == str[ty][tx] && (w[my][mx] >= 3 || h[my][mx] >= 3)){
			dfs(my, mx);
		}
	}
}

int main()
{
	scanf("%d %d", &H, &W);
	
	for (int i = 0; i < H; i++) scanf("%s", &str[i]);
	for (int i = 0; i < W; i++) h[0][i] = 1;
	for (int i = 0; i < H; i++) w[i][0] = 1;
	
	for (int i = 0; i < H; i++){
		for (int j = 1; j < W; j++){
			w[i][j] = (str[i][j] == str[i][j - 1]) ? w[i][j - 1] + 1 : 1;
		}
		for (int j = W - 2; j >= 0; j--){
			w[i][j] = (str[i][j] == str[i][j + 1]) ? w[i][j + 1] : w[i][j];
		}
	}
	/*
	for (int i = 0; i < H; i++){
		for (int j = 0; j < W; j++){
			printf("%d%c", w[i][j], j == W - 1 ? '\n' : ' ');
		}
	}
	*/
	for (int i = 0; i < W; i++){
		for (int j = 1; j < H; j++){
			h[j][i] = (str[j][i] == str[j - 1][i]) ? h[j - 1][i] + 1 : 1;
		}
		for (int j = H - 2; j >= 0; j--){
			h[j][i] = (str[j][i] == str[j + 1][i]) ? h[j + 1][i]: h[j][i];
		}
	}
	/*
	for (int i = 0; i < H; i++){
		for (int j = 0; j < W; j++){
			printf("%d%c", h[i][j], j == W - 1 ? '\n' : ' ');
		}
	}
	*/
	int res = 0;
	for (int i = 0; i < H; i++){
		for (int j = 0; j < W; j++){
			if (!v[i][j] && (h[i][j] >= 3 || w[i][j] >= 3)){
				res++;
				dfs(i, j);
			}
		}
	}
	
	printf("%d\n", res);
	
	return (0);
}

C. dpだったり数学だったりするらしい. ACした中では一番コードが短いです.

#include <cstdio>

#define TEST (20000000)

using namespace std;

int main()
{
	int N;
	int dat[20];
	double res;
	
	scanf("%d", &N);
	int tot = 0;
	for (int i = 0; i < N; i++){
		scanf("%d", &dat[i]);
		tot += dat[i];
	}
	printf("%.7lf\n", tot * 1.0 / N * (N - 1));
	
	return (0);
}

D以降は、解けたら掲載します.