ICPC2011国内予選

team:IkannoI Mk-Iで参戦していました。

A

素数がどうのこうのという問題だったらしいですが、チームメイトに任せてたので自分は見てません。
1発AC。この段階で全体の3位だったらしいです。

#include <cstdio>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <cstring>
#include <deque>
#include <cstdlib>
#include <stack>
#include <cmath>
#include <iostream>

using namespace std;

#define reep(i,f,t) for(int i=f ; i<int(t) ; ++i)
#define rep(i,n) reep(i, 0, n) 

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;

int main()
{
	vector<int> prime(1000000, 1);
	
	prime[0] = prime[1] = 0;
	reep(i, 2, sqrt(1000000)){
		if( prime[i] == 1 ){
			for( int j = i*2; j < 1000000; j+=i ){
				prime[j] = 0;
			}
		}
	}
	
	int n;
	while(scanf("%d",&n), n!=0){
		int cnt = 0;
		for( int i = n+1; i <= 2*n; ++i ){
			cnt += (prime[i]==1?1:0);
		}
		
		printf("%d\n", cnt);
	}
	
	return 0;
}

B

チームメイトがAを解いてる裏でペーパーコーディングしてました。
最初は開カッコの最後の1文字だけ保存しておけば大丈夫かなと思っていたんですけど
ペーパーコーディングしているうちにstackにしないと駄目だなーと気づきました。
チームメイトにその旨を伝えて1発AC。この段階で5位くらい。

#include <cstdio>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <cstring>
#include <deque>
#include <cstdlib>
#include <stack>
#include <cmath>
#include <iostream>

using namespace std;

#define reep(i,f,t) for(int i=f ; i<int(t) ; ++i)
#define rep(i,n) reep(i, 0, n) 

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;

int main()
{
	string str;
	
	while(getline(cin, str), str!="."){
		stack<char> s;
		bool flag = true;
		rep(i, str.size()){
			if( str[i] == '(' || str[i] == '[' ){
				s.push(str[i]);
			}
			if( str[i] == ')' ){
				if( !s.empty() && s.top() == '(' ){
					s.pop();
				}
				else{
					flag = false;
					break;
				}
			}
			if( str[i] == ']' ){
				if( !s.empty() && s.top() == '[' ){
					s.pop();
				}
				else{
					flag = false;
					break;
				}
			}
		}
		
		if( flag && s.empty() ){
			puts("yes");
		}
		else{
			puts("no");
		}
	}
	
	return 0;
}

C

問題の意味を理解するのに5分ほどかかりました。
盤面のサイズが小さく、電極に接続されているのが左上のパネルで固定だったので全探索するプログラムを書きました。
少しだけバグにはまった…。

#include <cstdio>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <cstring>
#include <deque>
#include <cstdlib>
#include <stack>
#include <cmath>
#include <iostream>

using namespace std;

#define reep(i,f,t) for(int i=f ; i<int(t) ; ++i)
#define rep(i,n) reep(i, 0, n) 

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;

int counto(vvi& p, vvi& visited, int y, int x)
{
	const int dy[] = {-1, 0, 0, 1};
	const int dx[] = {0, -1, 1, 0};
	int h = p.size();
	int w = p[0].size();
	
	int ans = 1;
	int tmp = p[y][x];
	p[y][x] = -1;
	visited[y][x] = 1;
	rep(i, 4){
		int py = y+dy[i];
		int px = x+dx[i];
		if(py<0 || h<=py || px<0 || w<=px)
			continue;
		if(visited[py][px])
			continue;
		if(p[py][px] == tmp)
			ans += counto(p, visited, py, px);
	}
	p[y][x] = tmp;
	return ans;
}

void change(vvi& p, vvi& visited, int y, int x, int ne)
{
	const int dy[] = {-1, 0, 0, 1};
	const int dx[] = {0, -1, 1, 0};
	int h = p.size();
	int w = p[0].size();
	
	int tmp = p[y][x];
	p[y][x] = -1;
	visited[y][x] = 1;
	rep(i, 4){
		int py = y+dy[i];
		int px = x+dx[i];
		if(py<0 || h<=py || px<0 || w<=px)
			continue;
		if(visited[py][px])
			continue;
		if(p[py][px] == tmp)
			change(p, visited, py, px, ne);
	}
	p[y][x] = ne;
}

void dump(vvi& p){
	
	vvi v(p.size(), vi(p[0].size(), 0));
	printf("count = %d\n", counto(p, v, 0, 0));
	rep(i, p.size()){
		rep(j, p[i].size())
			printf("%d", p[i][j]);
		puts("");
	}
	puts("");
}

int search(vvi p, int d, int c)
{
	// printf("d=%d\n", d);
	// dump(p);
	// getchar();
	if(d == 5){
		vvi v(p.size(), vi(p[0].size(), 0));
		return counto(p, v, 0, 0);
	}
	
	int ans = 0;
	reep(i, 1, 7){
		if(i == p[0][0] || (d==4 && i!=c))
			continue;
		
		vvi next = p;
		vvi v(p.size(), vi(p[0].size(), 0));
		change(next, v, 0, 0, i);
		ans = max(ans, search(next, d+1, c));
	}
	
	return ans;
}

int main()
{
	int h, w, c;
	while(scanf("%d%d%d", &h, &w, &c), h){
		vvi panel(h, vi(w));
		rep(i, h) rep(j, w)
			scanf("%d", &panel[i][j]);
		
		int ans = search(panel, 0, c);
		printf("%d\n", ans);
	}
	
	return 0;
}

E

A→B→Cと比較的快調に解き進めた次はEに挑戦しました。
「なんか制約多い…めんどくさい…」と思ってたんですけど少し考えて累積和+領域のDPで解けることが分かったのでコーディング。
何故かmapを使ってメモ化再帰するという頭悪いコードになってますがご容赦ください。
Submitするときにデバッグ用の出力が入ったアウトプットファイルをそのまま出してしまい無駄な1WAを喰らってしまいました…。

#include <cstdio>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <cstring>
#include <deque>
#include <cstdlib>
#include <stack>
#include <cmath>
#include <iostream>

using namespace std;

#define reep(i,f,t) for(int i=f ; i<int(t) ; ++i)
#define rep(i,n) reep(i, 0, n) 

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;

vvi sum;
map<pair<pii, pii>, pii> memo;
int s;
int lack;

int get(int y, int x, int h, int w)
{
	return sum[y+h][x+w] - sum[y][x+w] - sum[y+h][x] + sum[y][x];
}

pii search(int y, int x, int h, int w)
{
	pair<pii, pii> hoge = make_pair(pii(y, x), pii(h, w));
	if(memo.count(hoge))
		return memo[hoge];
	
	pii ans(1, get(y,x,h,w));
	if(lack > get(y,x,h,w))
		return pii(-1, 0);
	
	reep(i, 1, w){
		pii a = search(y, x, h, i);
		pii b = search(y, x+i, h, w-i);
		if(a.first==-1 || b.first==-1)
			continue;
		pii ne(a.first + b.first, min(a.second, b.second));
		ans = max(ans, ne);
	}
	
	reep(i, 1, h){
		pii a = search(y, x, i, w);
		pii b = search(y+i, x, h-i, w);
		if(a.first==-1 || b.first==-1)
			continue;
		pii ne(a.first + b.first, min(a.second, b.second));
		ans = max(ans, ne);
	}
	return memo[hoge] = ans;
	
}

int main()
{
	int h, w;
	while(scanf("%d%d%d", &h, &w, &s), h){
		memo.clear();
		vvi field(h, vi(w));
		rep(i, h) rep(j, w)
			scanf("%d", &field[i][j]);
		
		sum = vvi(h+1, vi(w+1, 0));
		reep(i, 1, h+1) reep(j, 1, w+1){
			sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + field[i-1][j-1];
		}
		lack = sum[h][w] - s;
		
		pii ans = search(0, 0, h, w);
		printf("%d %d\n", ans.first, s-(sum[h][w]-ans.second));
	}
	
	return 0;
}

D

だいたい1時間強でここまで来たんですけど競技の残り時間を全てDに費やしてしましました…。
枚数が高々24枚なので、状態数は2^24ということでメモ化再帰で組んだんですけど
何故かWA。問題文を10回くらい見直してもWA。
最終的に51行目のbreak;を消去すると正常に動くよ！と競技終了後id:hyon さんに指摘された暁にはなんかもう虚無感が。

#include <cstdio>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <cstring>
#include <deque>
#include <cstdlib>
#include <stack>
#include <cmath>
#include <iostream>

using namespace std;

#define reep(i,f,t) for(int i=f ; i<int(t) ; ++i)
#define rep(i,n) reep(i, 0, n) 

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;

struct C
{
	int x, y, r, c;
	C(){}
	C(int x, int y, int r, int c) : x(x), y(y), r(r), c(c){}
};

bool okok(const C& a, const C& b)
{
	int sq = (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y);
	return (a.r+b.r)*(a.r+b.r) > sq;
}

vector<C> c;
map<int, int> memo;
int n;
int search(int mask)
{
	if(memo.count(mask))
		return memo[mask];
	
	vector<bool> top(n, true);
	rep(i, n){
		if(mask & (1<<i)){
			reep(j, i+1, n){
				if(mask & (1<<j) && okok(c[i], c[j])){
					top[j] = false;
					break;
				}
			}
		}
	}
	
	vi color(5, 0);
	rep(i, n){
		if(top[i]) ++color[c[i].c];
	}

	int ans = 0;
	rep(i, n){
		if(top[i] && (mask & (1<<i)) && color[c[i].c] >= 2){
			reep(j, i+1, n){
				if(top[j] && c[i].c == c[j].c && (mask & (1<<j))){
					int next = mask & ~((1<<i) | (1<<j));
					ans = max(2+search(next), ans);
				}
			}
		}
	}

	return memo[mask] = ans;
}

int main()
{
	while(scanf("%d", &n), n){
		c = vector<C>(n);
		memo.clear();
		rep(i, n){
			scanf("%d%d%d%d", &c[i].x, &c[i].y, &c[i].r, &c[i].c);
		}
		int ans = search((1<<n)-1);
		printf("%d\n", ans);
		fprintf(stderr, "%d\n", ans);
	}

	return 0;
}

F, G

Fは難しそうな幾何です。
GはDを解いたら考えるつもりでしたがそんな時間はありませんでした。

結果

4AC(1WA)の17位です。
Dで嵌らなければ10位以内には入れてたはずなんですけど…。ぐぅ。
しかしでもなんとかアジア地区予選には進める感じですし、高専1位を死守出来たのでこれは喜ぶべきですね。
アジア地区予選では英語の壁がありますができるだけ頑張っていきたいと思います。