パソコン甲子園2012 本選

結果 :
ooo--o---- 4完 31点 3WAくらい.
9位でなみだらしい＞＜

感想 :
デバッグに2時間位費やした点以外はだいたい良かったと思う.
5は思いついていた解法の計算量を測り間違えて書かずに残念なことをしてしまった.
4も簡単な幾何だったので, ちゃんと読もうと思います.
オンサイトはじめては、自分らしさがでた結果になったとおもいます＞＜

コード :

1.アカ・ベコと40人の盗賊

グラフかと思って皆ガチ焦りしていた. 中身はやるだけでした.

#include <cstdio>

using namespace std;

int main()
{
	char s[128];
	int now;
	
	while (scanf("%s", s) && s[0] != '#'){
		now = 'A';
		
		for (int i = 0; s[i] != '\0'; i++){
			switch (now){
				case 'A':
					if (s[i] == '0'){
						now = 'X';
					}
					else {
						now = 'Y';
					}

					break;
				
				case 'X':
					if (s[i] == '1'){
						now = 'Z';
					}
					else now = -1;
					break;
				
				case 'Y':
					if (s[i] == '0'){
						now = 'X';
					}
					else now = -1;
					break;
				
				case 'Z':
					if (s[i] == '0'){
						now = 'W';
					}
					else {
						now = 'B';
					}
					break;
				
				case 'W':
					if (s[i] == '0'){
						now = 'B';
					}
					else {
						now = 'Y';
					}
					break;
				
				case 'B':
					if (s[i] == '0'){
						now = 'Y';
					}
					else {
						now = 'X';
					}
					break;
			}
		}
		
		if (now == 'B'){
			printf("Yes\n");
		}
		else printf("No\n");
	}
	
	return (0);
}

2.ブロックの三角形

Σbiの最大値が100*10^4で、その範囲でできる三角数は1500に満たないので, シミュレーションを単純に10^4回繰り返せば良い.

#include <cstdio>
#include <cstring>

using namespace std;

int main()
{
	int n;
	int d[1500];
	int e[1500];
	
	while (scanf("%d", &n) && n){
		
		memset(d, -1, sizeof(d));
		for (int i = 0; i < n; i++){
			scanf("%d", &d[i]);
		}
		
		int ct = 0;
		while (ct <= 10000){
			bool flag = true;
			for (int i = 0; i < 1500; i++){
				if (~d[i] && d[i] != i + 1){
					flag = false;
					break;
				}
			}
			
			if (flag == true){
				printf("%d\n", ct);
				goto end;
			}
			
			int nxt = 0;
			for (int i = 0; i < 1500; i++){
				if (~d[i]){
					d[i]--;
					nxt++;
				}
			}
			
			int idx = 0;
			int ok = 1;
			memset(e, -1, sizeof(e));
			for (int i = 0; i < 1500; i++){
				if (d[i] > 0){
					e[idx++] = d[i];
					ok = 1;
				}
				else if (d[i] == 0){
					ok = 0;
				}
			}
			e[idx] = nxt;
			
			for (int i = 0; i < 1500; i++){
				d[i] = e[i];
			}
			ct++;
		}
		
		printf("-1\n");
		end:;
	}
	
	return (0);
}

3.金剛の型

32bitの2進数のデータを10進数に変換する問題.
MSBは符号ビット, 2bit目~25bit目は整数値を表すビット, 残りは小数を表すビットである.
小数部の扱いがやや面倒だが, 定義通りの計算をdouble型で行えば誤差は生じないので, double型を使うと楽.

#include <stdio.h>
#include <string.h>

void bit_conv(char *bit, int hex)
{
	int i;
	
	if (hex >= '0' && hex <= '9'){
		hex -= '0';
	}
	else {
		hex -= 'a';
		hex += 10;
	}
	
	for (i = 3; i >= 0; i--){
		bit[3 - i] = 0;
		if ((hex >> i) & 1){
			bit[3 - i] = 1;
		}
	}
}

int mpow(int num, int n)
{
	int ret;
	
	ret = 1;
	while (n--){
		ret *= num;
	}
	
	return (ret);
}

int main(void)
{
	char bit[512];
	char input[512];
	int Q;
	int i, j, k;
	int ip;
	double fp;
	
	scanf("%d", &Q);
	for (i = 0; i < Q; i++){
		scanf("%s", input);
		for (j = 0; input[j] != '\0'; j++){
			bit_conv(&bit[j * 4], input[j]);
		}
		if (bit[0] == 1) printf("-");
		
		ip = 0;
		for (j = 1; j <= 24; j++){
			ip = (ip << 1) + bit[j];
		}
		printf("%d.", ip);
		int m = 0;
		fp = 0;
		double dec = 1.0;
		for (j = 0; j < 7; j++){
			dec /= 2.0;
			if (bit[j + 25] == 1){
				m = j;
				fp += dec;
			}
		}
		for (j = 0; j <= m; j++){
			printf("%d", (int)(fp * mpow(10, j + 1)) % 10);
		}
		printf("\n");
	}
	
	return (0);
}

4.風よ, 私の梅の香りを届けておくれ！

絵を見て幾何っぽくて捨てたが, 簡単な幾何だったらしい.
ライブラリ組んだし, この位置の幾何なんだから解くべきだった＞＜

5.モジュロ・クエリ

数列の数 mod M の最大値を, 異なるMのクエリに対して全て答える問題.
mod MはMを周期として循環するので, M, 2 * M, 3 * Mごとの区分で, 最も余りが大きいものを出力すれば良い.
与えられるMはすべて異なるので, 最悪計算量は3*10^5(1+1/2+...+1/10^5) = 3 * H_{10^5} ≒ 3 * 10^5 * 5log10 となる.
これ真っ先に思いついたけど計算量測り間違えて絶望していました;;

#include <cstdio>
#include <algorithm>

using namespace std;

int memo[300001];

int main()
{
	int n, q;
	int t, m;
	
	scanf("%d %d", &n, &q);
	
	for (int i = 0; i < n; i++){
		scanf("%d", &t);
		memo[t] = t;
	}
	
	for (int i = 1; i < 300001; i++){
		memo[i] = max(memo[i - 1], memo[i]);
	}
	
	for (int i = 0; i < q; i++){
		scanf("%d", &t);
		m = 0;
		for (int j = t - 1; j <= 300000; j += t){
			m = max(m, memo[j] % t);
		}
		m = max(m, memo[300000] % t);
		printf("%d\n", m);
	}
	
	return (0);
}

6.イヅア国語辞典

情オリ春合宿のanagramと大体一緒の問題. ただし, N(アルファベットの種類=文字数) ≦ 10^5, 全ての文字は相異なる という条件に変更されている.

基本的な方針はanagramと一緒だが(過去の記事を参照), そのままではO(N^2)になってしまう.
そこで, 今まで使われた文字をBITで管理することで, O(NlogN)時間でこの問題を解くことが出来る.

#include <cstdio>
#include <algorithm>
#include <set>
#include <cstring>

#define MOD (1000000007)

typedef long long lint;

using namespace std;

lint perm[100001];
lint a[100001];

int bit[100001], n;

int sum(int i)
{
	int s = 0;
	while (i > 0){
		s += bit[i];
		i -= i & -i;
	}
	return (s);
}

void add(int i, int x)
{
	while (i <= n){
		bit[i] += x;
		i += i & -i;
	}
}

int main()
{
	int m;
	perm[0] = 1;
	for (int i = 1; i <= 100000; i++){
		perm[i] = i * perm[i - 1];
		perm[i] %= MOD;
	}
	
	while (scanf("%d", &n) && n){
		for (int i = 0; i < n; i++){
			a[i] = i;
		}
		
		scanf("%d", &m);
		
		for (int i = 0; i < m; i++){
			int s, t;
			scanf("%d %d", &s, &t);
			swap(a[--t], a[--s]);
		}
		memset(bit, 0, sizeof(bit));
		lint res = 0;
		for (int i = 0; i < n; i++){
			int idx = 0;
			res = (res + (a[i] - sum(a[i] + 1)) * perm[n - i - 1]) % MOD;
			add(a[i] + 1, 1);
		}
		
		printf("%lld\n", res);
	}
	
	return (0);
}

7以降. むずかしいわかんない

まとめ :
バグが少ないコードを書いて, 思いついた解法の計算量の吟味をきちんと行おう.
来年は上を目指します.