2011年度ICPC模擬国内予選

ICPC

E,Fがどっちも通せそうで通せず、チームの順位は実力を微妙に出し切れなかったものになってしまったなという感じ。


A,D,Fをkohyatohが担当、B,C,Eをおぎえさんが担当。
自分は雑用を担当。Fの解法だけ出したけど、ほとんど貢献してない気がする。


以下個人の復習。

A koukyoukoukokukikou

問題

日本語なので本文参照（http://acm-icpc.aitea.net/index.php?2011%2FPractice%2F%CC%CF%B5%BC%B9%F1%C6%E2%CD%BD%C1%AA）

方針

各文字ごとに、一つ前の文字と担当の手が違うなら、カウント+1

ソースコード
int main()
{
	string in;
	string l="qwertasdfgzxcvb";
	
	while(cin>>in, in!="#"){
		int cnt=0;
		rep(i,in.size()-1){
			if((l.find(in[i])!=l.npos)^(l.find(in[i+1])!=l.npos))cnt++;
		}
		cout<<cnt<<endl;
	}
	return 0;
}

B ブレイブ・フォース・ストーリー

問題

日本語なので本文参照

方針

hex座標で幅優先探索。

ソースコード
int dx[]={-1,-1,0,1,1,0},dy[]={0,-1,-1,0,1,1};

int main()
{
	int t,n;
	
	while(cin>>t>>n,t||n){
		int obj[200][200]={}, sx,sy, x,y;
		int v[200][200]={};
		rep(i,n)cin>>x>>y,obj[y+100][x+100]=1;
		cin>>sx>>sy;
		
		queue<pair<int,pi> > q; q.push(mp(0,mp(sy+100,sx+100)));
		v[sy+100][sx+100]=1;
		
		while(!q.empty()){
			y=q.front().second.first, x=q.front().second.second;
			int ct=q.front().first; q.pop();
			
			if(ct>=t)continue;
			
			rep(d,6){
				int ny=y+dy[d], nx=x+dx[d];
				if(obj[ny][nx]||v[ny][nx])continue;
				q.push(mp(ct+1,mp(ny,nx)));
				v[ny][nx]=1;
			}
		}
		
		int ans=0;
		rep(i,200)rep(j,200)if(v[i][j])ans++;
		cout<<ans<<endl;
	}
	return 0;
}

C 最短ルート

問題

日本語なので本文参照

方針

ビットdp.
すなわちdp[i]をビットであらわされる、ステージの集合iをクリアするときの最短時間として、テーブルを更新する。

ソースコード
int dp[1<<16];

int main()
{
	int n;
	while(cin>>n,n){
		int t[20][20];
		rep(i,n)rep(j,n+1)cin>>t[i][j];
		
		rep(i,1<<n)dp[i]=inf;
		dp[0]=0;
		rep(i,1<<n){
			rep(j,n)if(!(i&1<<j)){
				//k番目のアイテムを使う
				rep(k,n)if(i&1<<k)dp[i|1<<j]=min(dp[i|1<<j],dp[i]+t[j][k+1]);
				//アイテムを使わない
				dp[i|1<<j]=min(dp[i|1<<j],dp[i]+t[j][0]);
			}
		}
		cout<<dp[(1<<n)-1]<<endl;
	}
	return 0;
}

D 6÷2(1+2)

問題

日本語なので本文参照

方針

普通の構文解析のかわりに、答えとして取りうる集合全部を返す。
構文解析の結果はメモ化しておく。

ソースコード
set<int> dp[200][200];
string in;

set<int> rec(int s,int t){
	if(dp[s][t].count(inf))return dp[s][t];
	
	dp[s][t].insert(inf); //探索終了のしるしに適当にinfを入れておく。
	int i=s,d=0,found=0;
	
	for(;i<t;i++){
		if(in[i]=='(')d++;
		if(in[i]==')')d--;
		
		if(d==0&&(in[i]=='+'||in[i]=='-'||in[i]=='*'||in[i]=='/')){
			found=1;
			
			set<int> l=rec(s,i-1), r=rec(i+1,t);
			fr(ii,l)fr(jj,r){
				if(*ii==inf||*jj==inf)continue;
				
				if(in[i]=='+')dp[s][t].insert(*ii + *jj);
				if(in[i]=='-')dp[s][t].insert(*ii - *jj);
				if(in[i]=='*')dp[s][t].insert(*ii * *jj);
				if(in[i]=='/'&&*jj!=0)dp[s][t].insert(*ii / *jj);
			}
		}
	}
	if(!found){
		if(in[s]=='(')return dp[s][t]=rec(s+1,t-1);
		
		stringstream ss(in.substr(s,t-s+1));
		int n; ss>>n;
		dp[s][t].insert(n);
	}
	return dp[s][t];
}
int main()
{
	while(cin>>in,in!="#"){
		rep(i,200)rep(j,200)dp[i][j].clear();
		
		rec(0,in.size()-1);
		cout<<dp[0][in.size()-1].size()-1<<endl;
	}
	return 0;
}