ACM/ICPC 国内予選 2011 提出コード

A問題

短く書こうとして関数名が省略形になってしまった

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
#define REP(i,x) for(int i=0;i<(int)x;i++)
vector<bool> e_s(int n){
	vector<bool> res(n+1);
	res[0]=res[1]=false;
	res[2]=true;
	int i,j,m=sqrt(n)+1e-9;
	for(int i=3;i<=n;i+=2){
		if(i<=m){
			if(res[i]==false){
				for(j=i+i+i;j<=n;j+=i+i){
					res[j]=true;
				}
			}
		}
		res[i]=!res[i];
	}
	return res;
}

int main(){
	vector<bool> ip=e_s(1000000);
	for(int n;cin>>n,n;){
		int res=0;
		for(int i=n+1;i<=n*2;i++){
			res+=ip[i];
		}
		cout<<res<<endl;
	}
	return 0;
}

B問題

あまり簡潔ではない

#include <iostream>
#include <algorithm>
using namespace std;
#define REP(i,x) for(int i=0;i<(int)x;i++)
string replace(string exp,string src,string dst){
	int L=exp.size(),l=src.size();
	string res;
	REP(i,L){
		if(i<=L-l&&exp.substr(i,l)==src){
			res+=dst;
			i+=l-1;
		}else{
			res+=exp[i];
		}
	}
	return res;
}
int main(){
	for(;;){
		string in;
		getline(cin,in);
		if(in==".")break;
		string r;
		REP(i,in.size()){
			if(in[i]=='['||in[i]==']'||in[i]=='('||in[i]==')'){
				r+=in[i];
			}
		}
		while(1){
			int mL=r.size();
			//cout<<r<<endl;
			r=replace(r,"[]","");
			r=replace(r,"()","");

			if(mL==r.size())break;
		}
		//cout<<r<<endl;
		if(r==""){
			cout<<"yes"<<endl;
		}else{
			cout<<"no"<<endl;
		}
	}
	return 0;
}

C問題

targetをHにReplaceするとデバッグ前のコードになります．

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <set>
#include <queue>
using namespace std;
#define REP(i,x) for(int i=0;i<(int)x;i++)
int MAP[10][10];
int cpy[10][10];
int W,H,c;
void show(){
	REP(i,H){
		REP(j,W){
			cout<<MAP[j][i]+1<<" ";
		}
		cout<<endl;
	}
	cout<<endl;
}
int ans=0;
typedef pair<int,int> P;
int dx[4]={0,-1,0,1},dy[4]={1,0,-1,0};
void BFS(int target){
	P p(0,0);
	queue<P> que;
	que.push(p);
	int sc=MAP[0][0];
	//cout<<sc<<endl;
	MAP[0][0]=-1;
	while(!que.empty()){
		P t=que.front();que.pop();
		//if(target==1)cout<<t.first<<","<<t.second<<":"<<sc<<endl;
		if(MAP[t.first][t.second]==target)continue;
		//if(target==1)cout<<"!"<<t.first<<","<<t.second<<endl;
		MAP[t.first][t.second]=target;
		REP(i,4){
			int nx=t.first+dx[i],ny=t.second+dy[i];
			if(nx>=0&&nx<W&&ny>=0&&ny<H){
				if(MAP[nx][ny]==sc)que.push(P(nx,ny));
			}
		}
	}
}
int BFSC(){
	P p(0,0);
	queue<P> que;
	que.push(p);
	int sc=MAP[0][0];
	int cnt=0;
	while(!que.empty()){
		P t=que.front();que.pop();
		if(MAP[t.first][t.second]==-1)continue;
		MAP[t.first][t.second]=-1;
		cnt++;
		REP(i,4){
			int nx=t.first+dx[i],ny=t.second+dy[i];
			if(nx>=0&&nx<W&&ny>=0&&ny<H)
				if(MAP[t.first+dx[i]][t.second+dy[i]]==sc)que.push(P(t.first+dx[i],t.second+dy[i]));
		}
	}
	return cnt;
}
int solve(int x){
	memcpy(cpy,MAP,sizeof(MAP));
	int tx=x;
	REP(i,4){
		tx/=6;
	}
	if(tx!=c)return 0;
	REP(i,5){
		BFS(x%6);
		x/=6;
	}
	if(MAP[0][0]==c){
		int t=BFSC();
		if(ans<t){
			//show();
		}
		ans=max(ans,t);

	}
	memcpy(MAP,cpy,sizeof(cpy));
}
int main(){
	for(;cin>>H>>W>>c;){
		if(W==0)break;
		REP(i,H){
			REP(j,W){
				cin>>MAP[j][i];
				MAP[j][i]-=1;
			}
		}


		c-=1;
		ans=0;
		REP(i,7776){
			solve(i);
		}
		cout<<ans<<endl;
	}
	return 0;
}

D問題

割と率直な実装

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <set>
#include <queue>
#include <cmath>
#include <deque>
#define REP(i,x) for(int i=0;i<(int)x;i++)
using namespace std;
bool check(int x1,int y1,int r1,int x2,int y2,int r2){
	if((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)<(r1+r2)*(r1+r2)){
		return true;
	}
	return false;
}
struct Circle{
	int x,y,r,c;
	int can;
};
bool check(const Circle &a,const Circle &b){
	return check(a.x,a.y,a.r,b.x,b.y,b.r);
}

int n;
vector<Circle> datas;
int ans=0;
int preans=0;
set<int> ac;
#define precheck(a,b) (((a)|(b))==(a))
void dfs(int used){
	//cout<<used<<endl;
	if(ac.find(used)!=ac.end())return;
	ac.insert(used);
	ans=max(ans,preans);
	REP(i,n){
		if(((used>>i)&1)==0&&precheck(used,datas[i].can)){
			for(int j=i+1;j<n;j++){
				if(((used>>j)&1)==0){
					if(datas[i].c==datas[j].c&&precheck(used,datas[j].can)){
						preans+=2;
						dfs(used^(1<<j)^(1<<i));
						preans-=2;
					}
				}
			}
		}
	}
}
int main(){
	for(;cin>>n,n;){
		datas=vector<Circle>(n);
		REP(i,n){
			cin>>datas[i].x>>datas[i].y>>datas[i].r>>datas[i].c;
			datas[i].can=0;
		}
		for(int i=0;i<n;i++){
			for(int j=0;j<i;j++){
				if(check(datas[i],datas[j])){
					datas[i].can|=1<<j;
				}
			}
		}
		ac.clear();
		ans=0;
		preans=0;
		dfs(0);
		cout<<ans<<endl;
	}
	return 0;
}

E問題

始めてrepマクロを使いました．

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <set>
#include <queue>
#include <cmath>
#include <deque>
#define REP(i,x) for(int i=0;i<(int)x;i++)
#define rep(i,s,e) for(int i=(s);i<(int)e;i++)
using namespace std;
//x1<=x<x2 , y1<=y<y2
int MAP[32][32];
typedef pair<int,int> P;
const P NA(-1,-1);
const P init(-2,-2);
P DP[33][33][33][33];
int dp[33][33][33][33];
int H,W,s,S;
int SUM(int x1,int y1,int x2,int y2){
	//if(dp[x1][y1][x2][y2]!=-1)return dp[x1][y1][x2][y2];
	int ans=0;
	rep(y,y1,y2){
		rep(x,x1,x2){
			ans+=MAP[x][y];
		}
	}
	return ans;
	//return dp[x1][y1][x2][y2]=ans;
}
P solve(int x1,int y1,int x2,int y2){
	if(S-SUM(x1,y1,x2,y2)>s)return NA;//解無し
	//cout<<"("<<x1<<","<<y1<<")"<<":"<<"("<<x2<<","<<y2<<")"<<endl;
	if(DP[x1][y1][x2][y2]!=init)return DP[x1][y1][x2][y2];
	P res=P(1,s-(S-SUM(x1,y1,x2,y2)));
	//x方向に分ける
	rep(x,x1+1,x2){
		P a,b;
		a=solve(x1,y1,x,y2);
		b=solve(x,y1,x2,y2);
		if(a==NA||b==NA)continue;
		P tmp;
		tmp=P(a.first+b.first,min(a.second,b.second));
		res=max(tmp,res);
	}

	//y方向に分ける
	rep(y,y1+1,y2){
		P a,b;
		a=solve(x1,y1,x2,y);
		b=solve(x1,y,x2,y2);
		if(a==NA||b==NA)continue;
		P tmp;
		tmp=P(a.first+b.first,min(a.second,b.second));
		res=max(tmp,res);
	}
	return DP[x1][y1][x2][y2]=res;
}
int main(){
	for(;cin>>H>>W>>s;){
		if(H==0)break;
		REP(i,H){
			REP(j,W){
				cin>>MAP[j][i];
			}
		}
		S=SUM(0,0,W,H);
		REP(i,33){
			REP(j,33){
				REP(k,33){
					REP(l,33){
						DP[i][j][k][l]=init;
					}
				}
			}
		}
		memset(dp,-1,sizeof(dp));
		P ans=solve(0,0,W,H);

		cout<<ans.first<<" "<<ans.second<<endl;
	}
	return 0;
}