ICPC2016国内予選

こんばんは．chigichan24です．

ICPCにわたし，@otama_jaccy，@Pelkiraとでて，3完でした．
正直，みんな受験でチームとしての練習はおろか，わたしはたまーにSRMとかARCとかに出てましたが，他二人は競技でC++触るの何時ぶりだっけ？みたいな感じでした．個人的にはその割にチームとして動けてて面白かったです．

なんとなく時系列っぽく振り返りたいと思います．

作戦

どう考えても諸々が衰えていると思い，2人で1問を解いていく作戦でいく．

A

・わたしとPelkiraで読む．sortして，idxとidx+1の差の最小を取れば良さそう．
・Pelkiraくんがコードをカキカキ(^O^)／
・この間にBとCを印刷してotamaになげる．
・sample通ったし，提出作業をわたしが担当する．

A->WA

・ﾜｧﾂ！？
・inputはEOFが来るまでと思っていたら，0が来るらしい．
・Pelkiraくんとそこら辺の勘が消えているなどと言いながら訂正して提出．
・わりと戦犯らしき行為を決めてしまった(while(~scanf("%d",&N)){}などと書いた記憶．)

A->AC

・まさかここでこんなハンデを負ってしまうなんて...

B

・otamaが不等式を満たすまでforをぶん回せばよいと完結に方針を固めていたので，Pelkiraとotamaの2人で解く．
・わたしはCの考察に入る．約数とかで頑張りそう．
・BのコーディングはPelkiraが最初やっていたが，わたしの考察を聞いてもらうために，otamaに替わる(よく見てないがそんな感じだった気がする．)
・Cは始まりと試行回数の条件付きエラトステネスのふるいで間違いないと判断されたため，紙コーディング開始．
・BがI/Oでバグっているらしい．
・紙コーディングが終わったので，一旦変わってもらう．

C

・コーディングする．楽しい．
・sampleが合わない．かつBがI/Oでダメなところを見つけたらしいので，Bに交代．
・修正するも，ダメらしいので再度Cに交代．
・false と trueを間違っていただけだったので，訂正したら，sample通ったので，提出．

C->AC

B

・PelkiraくんにD,Eを読んでもらう間に，わたしがotamaとバグ潰しに行く．
・一番目と二番目に多く票を獲得しているとこの処理がバグってたうえで，なんか私にはよくわからない処理をしてたので，毎回vectorにぶち込んでsortするという荒業を使って回避するコードを書く．
・sample通る．提出．

B->AC

この時点で1hくらい消費してて""やばい""ってなってた．

D,E

・幾何の鬼のPelkiraくんがEが幾何だったのでそっちを詰める．
・残りのインテリアのわたしとotamaでDを考える．
・otamaがDPの息吹を感じるなどと言っていた．
・嘘貪欲でいけるかと思ったけど絶対行けない．
・区間を運びながらメモ化すれば行けそうという発想になるが，区間の運び方がよくわからんってなって，vectorのまま運んでmapで保存すれば行けるんちゃうか(大嘘)という方針がたったので，わたしが書き始める．
・EをotamaとPelkiraくんで詰めていく(自分がコーディングしてた時に若干の歓喜の声が上がっていた)
・D書き上げてsampleは通ったが，やっぱり実行時間がヤバ過ぎるので，一旦Eに交代．

E

・考察を聞くと，結局パスとサイクルしかできないので，その条件でdfsしてやれば良いらしい．
・幾何パートはいい感じに処理が終了してたが，探索パートでつまる．
・何度かDと交代してコーディングしたが，Dはこれ以上いけそうになかったので，Eに託す．
・頑張って書き上げたが，sampleの値が惜しいかんじで通らない．

終了

・Ω＼ζ°)ﾁｰﾝ

まとめ

・D,Eともに大幅なブランクによって解けなかった(ということにしたい．)
・競技中は結構楽しい感じだったので，Asiaに行きたかった．
・チームとしての練習をしてなかったけど，チームとしてかなり機能していて草だった．今日otamaと話したら，それぞれがお互いに競技力の低下を危惧していたので，不信の目によってみんなで助け合えたのではという話になって納得した．
・大学に編入した先でAsiaにいけるようなチームに入れるとは思えないけど，競技熱が復活したので，受験をとっとと終わらせて，競技したい．
・ちなみに，ICPCの悲しみをどうにかこうにかするためにSRMにでたら1年ぶりくらいに青に戻った．
・来年はらて，うぃんじー，っこの3人だろうし普通にAsiaは余裕で行くんだろうな．頑張って．
・まぁいろいろあったけど楽しかったです．

コード(A)

Pelira,chigiで書いた．

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	while(true){
		cin >> n;
		if(n == 0)break;
		int a[100000];
		for(int i = 0;i < n;i++){
			cin>>a[i];
		}
		sort(a,a+n);
		int mi = 10000000;
		for(int i = 0;i < n-1;i++){
			a[i] -= a[i+1];
			if(a[i]<0)a[i] *= -1;
			mi = min(mi,a[i]);
		}
		cout << mi << endl;
	}
	return 0;
}

コード(B)

Pelkira,otama,chigiで書いた．

#include<bits/stdc++.h>
using namespace std;
#define reps(i,j,k) for(int i=j;i<k;++i)
#define rep(i,j) reps(i,0,j)
typedef pair<int,int> P;
int main(){
	int n;
	while(true){
		//puts("a");
		cin >> n;
		if(n == 0)break;
		int cnt[100]={0};
		char input[1000];
		for(int i=0;i<n;i++){
			scanf(" %c",input+i);
		}
		bool flg = false;
		for(int i = 0;i < n;i++){
			//printf("char:%c\n",input[i]);
			cnt[(int)input[i] - 'A']++;
			
			vector < P > a;
			rep(j,26){
				a.push_back(P(cnt[j],j));
			}

			sort(a.rbegin(),a.rend());

			int fi = a[0].second;
			int se = a[1].second;

			//printf("i:%d  cnt:%d %d\n",i,cnt[fi],cnt[se]);
			if(cnt[se] + n - i - 1 < cnt[fi] || n==1){
				flg = true;
				printf("%c %d\n",(char)fi + 'A',i+1);
				break;
			}
		}
		if(!flg){
			cout<<"TIE"<<endl;
		}

	}
	return 0;
}

コード(C)

chigiが書いた．

#include <bits/stdc++.h>
using namespace std;
#define reps(i,j,k) for(int i=j;i<k;++i)
#define rep(i,j) reps(i,0,j)
#define MAX_N 7400000
bool used[MAX_N];
int main(){
	int m,n;
	while(true){
		scanf("%d%d",&m,&n);
		if(m == 0 && n == 0){
			break;
		}
		memset(used,false,sizeof(used));
		int cnt = 0;
		reps(i,m,MAX_N){
			if(used[i] == false){
				cnt++;
				for(int j = i; j <= MAX_N; j+=i){
					used[j] = true;
				}
				if(cnt == n){
					goto skip;
				}
			}
		}
		skip:;

		reps(i,m,MAX_N){
			if(used[i] == false){
				printf("%d\n",i);
				break;
			}
		}



	}
	return 0;
}

コード(D)

chigiが書いた．
普通に実行時間に間に合わない．

#include <bits/stdc++.h>
using namespace std;
#define reps(i,j,k) for(int i=j;i<k;++i)
#define rep(i,j) reps(i,0,j)
typedef vector<int> vi;
typedef pair<vi,int> P;

map<P,int> memo;

int solve(int depth, vi input){

	P p = P(input,depth);

	if(memo[p]){
		return memo[p];
	}

	vi attack; //打つべきindexを持つvector
	int prev = -1;
	int previdx = -1;
	int cnt = 0;
	rep(i,input.size()){
		++cnt;
		if(prev == -1){
			prev = input[i];
			previdx = i;
		}
		else{
			if(abs(prev - input[i]) <= 1){
				attack.push_back(previdx);
			}
			prev = input[i];
			previdx = i;
		}
	}

	/*rep(i,attack.size()){
		printf("%d ",attack[i]);
	}
	puts("");*/

	if(attack.size() == 0){
		P p = P(input,depth);
		if(memo[p] == 0){
			memo[p] = 1;
		}
		//return 0;
		return memo[p];
	} 


	int ans = 1;
	rep(i,attack.size()){
		vi tmp;
		rep(j,input.size()){
			if(!(j == attack[i] || j == attack[i]+1)){
				tmp.push_back(input[j]);
			}
		}
		ans = max(ans,solve(depth+1,tmp)+1);
	}
	P x = P(input,depth);
	return memo[x] = ans;
}

int main(){

	int N;
	while(true){
		memo.clear();
		scanf("%d",&N);

		if(N == 0){
			break;
		}

		vi input;
		rep(i,N){
			int tmp;
			scanf("%d",&tmp);
			input.push_back(tmp);
		}

		printf("%d\n",2*(solve(0,input)-1));

	}

	return 0;
}

コード(E)

あったけど，sampleも通らないので割愛．

それではまた(勉強せんとあかん)．