ICPC2017国内予選参加記

チーム

IS17erのえる氏となたがわ氏と一緒にチームTBDとして出ました。
(わりと急増チームで、チーム名は to be determined の略)
(1年の時はチームtekitoで出てそれなりにいい順位だったので、
チーム名は雑に決めた方がいい成績がとれるというジンクスがありそう？)

結果

7完6位でしたが、学内順位が5位(!?)だったのでなんというかアレ(どうなるんでしょうね)

当日の概要

2限があったので本郷でプラクティスに参加。
2時過ぎに2食に食べにいっていたら、なんやかんやで駒場に着いたのは4時前くらいになってしまった。
Wifiに接続や印刷準備などがぎりぎりになってしまう。

正確な時刻については思い出せないのでスコアボードを参考に。

競技開始

なたがわ氏に印刷しに行ってもらいつつ、える氏と問題について考察したりする。
(というかこの時点でAに走っておくべきだったのだが、「FAとか取れないよね～」とか話していて手をつけていなかったので作戦ミスっぽかった)

A,B,Cはやるだけぽい。Dは簡単そうだが思いつかず。
(こーいう問題は気づくと一瞬なのだろうが思いつくのがつらそうで、僕は思いつきそうにもないのでほっとくことにした)
Eは構文解析。F,Gは不明、Hはどうやら幾何らしそう。
しばらく後にえる氏がAを解き始める。

0:12 Aが通る

同じくBをやってもらう。その間になたがわ氏が帰ってくる。
Fをやりたそうにしていたが、Dが分かんないので聞いてみると、√500≈20なのでmとnの小さい方でべきを回せばいいとのこと。いい話。
なんだかえる氏のBが辛そうな感じになっていたので、Bを印刷してデバッグしてもらうことにして、先にCをじゃっじゃかやっていく。

#include<bits/stdc++.h>

using namespace std;

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

#define reg(i,a,b) for(int i=(a);i<=(b);i++)

int h,w;
int d[15][15];
int main(){
	for(;;){
		scanf("%d%d",&h,&w);
		if(h==0)break;
		rep(y,h){
			rep(x,w)scanf("%d",&d[y][x]);
		}
		
		int ans = 0;
		rep(u,h){
			reg(s,u+2,h-1){
				rep(l,w){
					reg(r,l+2,w-1){
						
						int mw=100;
						int yn=0;
						int mab=0;
						reg(y,u,s){
							reg(x,l,r){
								int p = d[y][x];
								if(y==u || y==s || x==l || x==r){
									mw = min(mw,p);
								}
								else{
									mab = max(mab,p);
									yn += p;
								}
							}
						}
						
						//printf("%d %d %d %d : %d %d %d\n",u,s,l,r,mw,yn,mab);
						if(mab>=mw)continue;
						ans = max(ans,(s-u-1)*(r-l-1)*mw-yn);
					}
				}
			}
		}
		
		printf("%d\n",ans);
	}
	return 0;
}

0:41 Cが通る。

Bのバグがとれたそうな。めでたい。

0:47 Bが通る。

Dをエイヤと書く。

#include<bits/stdc++.h>

using namespace std;

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

#define reg(i,a,b) for(int i=(a);i<=(b);i++)


int h,w;

char s[505][505];

int bd[505];


int dp[2][1<<23];

int nb[505];
int main(){
	for(;;){
		scanf("%d%d",&h,&w);
		if(h==0)break;
		rep(y,h){
			scanf("%s",s[y]);
			int nb=0,t=1;
			rep(x,w){
				if(s[y][x]=='1')nb+=t;
				t*=2;
			}
			bd[y]=nb;
		}
		if(h>w){
			memset(dp,-1,sizeof(dp));
			dp[0][0]=0;
			int p = 0;
			rep(y,h){
				int b = bd[y];
				rep(i,1<<w){
					dp[1-p][i]=dp[p][i];
					int f = dp[p][i^b];
					if(f<0)continue;
					dp[1-p][i]=max(dp[1-p][i],f+1);
				}
				p = 1-p;
			}
			
			printf("%d\n",dp[p][0]);
		}
		else{
			int ans=0;
			rep(i,1<<h){
				memset(bd,0,sizeof(bd));
				int ns=0;
				rep(y,h){
					if(i&(1<<y)){
						ns++;
						rep(x,w){
							bd[x] ^= ((s[y][x]=='1')?1:0);
						}
					}
				}
				
				int ok=0;
				rep(x,w){
					ok+=bd[x];
				}
				if(!ok){
					ans=max(ans,ns);
				}
			}
			printf("%d\n",ans);
						
		}
	}
	return 0;
}

途中、dp配列を[505][1<<26] くらいで取ろうとすると.bssに収まらないと怒られたりした。

1:06 Dが通る。

書いている間になたがわ氏がFの考察をめっちゃ進めている。
どうやら各ビットについて独立にみればよいそうな。
なたがわ氏にFを書いてもらっているうちに、GとEについて考える。

える氏と考えてみるが、Gはどうやら貪欲に右手法をやればよさそうという結論に落ち着く。
(G問題にしてはやるだけでは??と思うが２人ともいけそうと思っているので、嘘解法ではないっぽそう)
マスを通る際に進んだ向きを保存しておけば自動的に経路復元できるっぽいと思いついて実装のめどが立つ。

Eは、構文解析は気合だが、最小論理式の生成がすぐには思いつかない。
なんか小さい方から生成してくんだろうけど計算量が見当もつかず。

なたがわ氏がFを書いたが、なんかバグってるっぽいので印刷してもらって、そのうちにGをやっていく。
適宜なたがわ氏のFと交代しつつGをセイヤとやる。

#include<bits/stdc++.h>

using namespace std;

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

#define reg(i,a,b) for(int i=(a);i<=(b);i++)


int h,w;


char dat[55][55];
 

int dy[4]={0,1,0,-1};
int dx[4]={-1,0,1,0};


int dir[55][55];


int gone[55][55];

int main(){
	for(;;){
		scanf("%d%d",&h,&w);
		if(h==0)break;
		rep(y,h){
			scanf("%s",dat[y]);
		}
		
		memset(dir,-1,sizeof(dir));
		int y=0,x=0,d=1;
		for(;;){
			int ok=0;
			reg(i,-1,2){
				int td = (d+i+4)%4;
				int ty=y+dy[td];
				int tx = x + dx[td];
				if(ty<0 || ty>=h || tx<0 || tx>=w)continue;
				if(dat[ty][tx]=='#')continue;
				dir[y][x]=td;
				x = tx; y=ty; d=td;
				ok=1;
				break;
			}
			if((!ok) || (x==0 && y==0))break;
			
		}
		/*
		rep(y,h){
			rep(x,w){
				printf("%2d%c",dir[y][x],x+1==w?'\n':' ');
			}
		}*/
		memset(gone,0,sizeof(gone));
		
		bool ans = true;
		y=x=0;
		d=dir[0][0];
		for(;;){
			gone[y][x]=1;
			//printf("%d %d %d\n",y,x,d);
			if(d<0){
				ans=false;
				break;
			}
			int ty=y+dy[d];
			int tx = x+dx[d];
			if(ty==0 && tx==0)break;
			if(gone[ty][tx]){
				ans=false;
				break;
			}
			x = tx; y = ty;
			d = dir[ty][tx];
		}
		//printf("%d\n",ans);
		rep(y,2)rep(x,2){
			if(!gone[y*(h-1)][x*(w-1)])ans=false;
		}
		
		puts(ans?"YES":"NO");
	}
	return 0;
}

1:44 Gが通る

なたがわ氏がバグを直したぽい。めでたい。

1:52 Fが通る。

Eの方針が固まる。
論理式の値のとりかたは2^16パターンなので、
各パターンに対して必要な項の長さを小さい方から求めておけばいいぽい。
で、各項をパターンに落とし込んだ後、パターンに対応する長さを返せばよさそう。気合で書く。
(このへん、なたがわ氏もえる氏も幾何は苦手で、Eのコーディングでも見てるか～
といった感じだったのだが、結果的にはHの考察を進めておいた方がよかったですね...)

書いてる途中、xorやandの遷移で2^16かかりそうに思ってぞっとしたが、
まあ枝刈りされるし大丈夫やろと思って書くと存外しゅっと動く。
サンプルが合っているので出す。が、WAる。
テストケースを見てみると、明らかに元の式より長いのが出力されている。
(一見テストケースが強そうに見えたので確認しなかったのだが、 ここで確認しておけば1200変わっていたのかと思うと非常に悔やまれる)

ダイクストラで、突っ込む前に距離を更新してるのに、取り出すときに距離チェックをしすぎるやつをやっていたので修正。

#include<bits/stdc++.h>

using namespace std;

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

#define reg(i,a,b) for(int i=(a);i<=(b);i++)

typedef string::iterator sta;


int dat[6][2]={
	{'0',0},
	{'1',(1<<16)-1},
	{'a',-1},
	{'b',-1},
	{'c',-1},
	{'d',-1}};
	

int expr(sta& s){
	//printf("%c ",*s);
	rep(i,6){
		if(*s==dat[i][0]){
			s++;
			return dat[i][1];
		}
	}
	
	if(*s=='-'){
		s++;
		return ((1<<16)-1)^expr(s);
	}
	else{
		s++;
		int a = expr(s);
		char c = *s;
		s++;
		int b = expr(s);
		s++;
		
		if(c=='^')return a ^ b;
		else return a & b;
	}
}

int dp[1<<16]={};


typedef pair<int,int> mp;

int main(){
	rep(i,4){
		int b = 1,nb=0;
		rep(j,1<<4){
			if((1<<i)&j){
				nb += b;
			}
			b*=2;
		}
		dat[i+2][1]=nb;
	}
	
	 int dpn=0;
	 
	 priority_queue<mp,vector<mp>,greater<mp> > que;
	 
	 rep(i,6){
	 	que.push(mp(1,dat[i][1]));
	 }
	 
	 while(!que.empty()){
	 	mp pa = que.top();
	 	que.pop();
	 	int ls = pa.first;
	 	if(ls>17)break;
	 	int t = pa.second;
	 	if(dp[t]>0 && dp[t]<ls)continue;
	 	dp[t]=ls;
	 	//printf("%d %d\n",t,ls);
	 	//dpn++;
	 	//if(dpn>(1<<16))break;
	 	
	 	int t1 = ((1<<16)-1)^t;
	 	if(dp[t1]>0 && dp[t1]<=ls+1){
	 	}
	 	else{
	 		dp[t1]=ls+1;
	 		que.push(mp(ls+1,t1));
	 	}
	 	rep(i,1<<16){
	 		if(dp[i]==0)continue;
	 		//printf("ni %d ",i);
	 		int tls = ls + dp[i] + 3;
	 		int ts[2];
	 		ts[0]=t^i;
	 		ts[1]=t&i;
	 		rep(j,2){
	 			int& f = dp[ts[j]];
	 			if(f==0 || f>tls){
	 				f=tls;
	 				que.push(mp(tls,ts[j]));
	 			}
	 		}
	 	}
	}
	
	//puts("init");
	
	for(;;){
		string s;
		cin >> s;
		if(s[0]=='.')break;
		sta sa = s.begin();
		int x = expr(sa);
		//printf("%d\n",x);
		printf("%d\n",dp[x]);
	}
	
	return 0;

}

2:20 Eが通る

このへんで、7完したのでどうにかやったやろという気持ちが強くなっていたが、どうやらそうでもないっぽいのでHをやっていく。
(というか当初は幾何までもつれ込むとは思っていなかった)

Hの方針は全部試せばいいらしくて、平行や線分交差とかをできればよいとのこと。
しかし、へたにライブラリを半写しの状態で書こうとしたり、ほかにも途中に微妙に嘘解法であることが分かったりして、結局書ききれなかった。

コンテスト終了

後半ずっとコーディングをしていたので、戦況がどういう状況かが分かっていなかったのだが、順位表を見ると全体6位にもかかわらず東大内5位とのこと。
(聞くところによると、終了4分前(!!)くらいにshurikenがGを通したらしく抜かれたぽい。 あと、catsatmatとは42秒差(!!)だったらしく)

他のチームのHを見せてもらったのだが、ライブラリ部分がとても短かったので、もっと幾何ライブラリを写しやすさに特化させるべきという気持ちになる。
(自分のものは、コピペで使えるなら便利なのだがとても冗長だった)

急造チームにもかかわらずわりとメンバーの能力がマッチしていて望外の順位を取ることができた。
が、なんというかさまざまな面で作戦ミスがあったのでやはりICPCは難しいですね。

アジア地区予選に出てみたいな～