hogloidのブログ

へなちょこ

KUPC 2011

感想:
難しい!!!
正直5問は解けるだろうとタカをくくっていましたが見事に打ち砕かれました
10位目指すって言ってたのが懐かしいです

Problem A

やるだけです。KUPCの文字をそれぞれカウント

int main(){
	char s[305];scanf("%s",s);
	int len=strlen(s);
	int k=0,u=0,p=0,c=0;
	REP(i,len){
		if(s[i]=='K') ++k;
		else if(s[i]=='U') ++u;
		else if(s[i]=='P') ++p;
		else if(s[i]=='C') ++c;
	}
	printf("%d\n",min(min(k,u),min(p,c)));
	return 0;
}

Problem B

DPです。

int main(){
	int h,w;scanf("%d%d",&h,&w);
	vvi buf(h,vi(w)),dp(h,vi(w,INF));
	REP(i,h) REP(j,w){
		char t;scanf("\n%c",&t);
		buf[i][j]=t-'0';
	}
	dp[0][0]=buf[0][0];
	REP(i,h) REP(j,w){
		if(i+j==0) continue;
		if(i) dp[i][j]=min(dp[i][j],buf[i][j]+dp[i-1][j]);
		if(j) dp[i][j]=min(dp[i][j],buf[i][j]+dp[i][j-1]);
	}
	printf("%d\n",dp[h-1][w-1]);

	return 0;
}

Problem C

斬新なかんじの問題(自分にとっては)
相手は2文字までしか使ってこないので最後の文字を決定してしまえば
相手は26+1通りしか出せない
自分が同じのを出さないように注意

int main(){
	char begin='c';
	string ans="bcdefghi",get;
	vi begincnt(250);
	set<string> got;
	while(1){
		begincnt[begin]++;
		if(begincnt[begin]>1){
			cout<<'?'+(begin+ans.substr(0,begincnt[begin])+'a')<<endl;
		}else
			cout<<'?'+(begin+ans+'a')<<endl;
		cin>>get;
		if(get[0]!='a'){
			printf("!OUT\n");fflush(stdout);
			break;
		}
		if(EXIST(got,get)){
			printf("!OUT\n");fflush(stdout);
			break;
		}
		got.insert(get);
		begin=*get.rbegin();
	}
	return 0;
}

Problem D

難しそう。しばらく(3時間)別の問題を考えてたけど分からなかったので
やけくそ状態で考える。
なんか貪欲でできそう(証明なし)
バリバリ。3完ではいかん
通った!やったねたえちゃん

int main(){
	int n,k;scanf("%d%d",&n,&k);
	vp sum(n);
	vi inc(k);
	vvi seq(k,vi(n/2));
	REP(i,n) sum[i].sc=i;
	REP(i,k){
		REP(j,n/2){
			int t;scanf("%d",&t);--t;
			seq[i][j]=t;
			sum[t].fr++;
		}
	}
	sort(ALL(sum),greater<pi>());
	vi res(n);
	REP(i,sum.size()){
		res[sum[i].sc]=1;
		int f=0;
		REP(j,k){
			if(binary_search(ALL(seq[j]),sum[i].sc)){
				++inc[j];
				if(inc[j]>=n/8*3){
					f=1;break;
				}
			}
		}
		if(f) --res[sum[i].sc];
	}
	REP(i,res.size()) putchar('0'+res[i]);
	putchar('\n');
	return 0;
}

そういえばこれ
failフラグ(f)が1になっても増やしたカウンタ減らしていないというひどいプログラムです

else

なんかむずかしい
FOXの問題は普通にやってTLEだったので、FOXでない数が少なそうだとみて
頑張って探索やるけど結局だめ
ボ〜ルが解けそうで解けない。O(N^2*K)しか書けない
山のタイトルがツボったので頑張る。同じ列・行の数は変わらないなと思う
おわり☆

感想:
難しい!!!やっぱりDomesticなコンテストでも一桁順位は遠い!!
精進!!