読者です 読者をやめる 読者になる 読者になる

メモ

yukicoderで遊んでいる競プロゆるふわ勢

yukicoder No.349 干支の置き物

問題はこちら
No.349 干支の置き物 - yukicoder

だいたい「過半数を占めるようなやつがあると無理」っぽい感じ
Nが偶数なら確かにそうだが、奇数の時は例えば●○●○●と並べることで(N+1)/2まではセーフ
ここでNが偶数の時floor((N+1)/2)=N/2となることから
floor((N+1)/2)個より多いものが存在しないことを確かめれば良い

各種類がいくつあるか数えるのは、C++だと一瞬だけどCだとちょっと面倒
うまいやり方が思いつかないからif文をずらずらと並べた

int main(){
	int i,n,a[12]={};
	scanf("%d",&n);
	for(i=0;i<n;i++){
		gets(s);
		if(strcmp(s,"ne")==0)a[0]++;
		else if(strcmp(s,"ushi")==0)a[1]++;
		else if(strcmp(s,"tora")==0)a[2]++;
		else if(strcmp(s,"u")==0)a[3]++;
		else if(strcmp(s,"tatsu")==0)a[4]++;
		else if(strcmp(s,"mi")==0)a[5]++;
		else if(strcmp(s,"uma")==0)a[6]++;
		else if(strcmp(s,"hitsuji")==0)a[7]++;
		else if(strcmp(s,"saru")==0)a[8]++;
		else if(strcmp(s,"tori")==0)a[9]++;
		else if(strcmp(s,"inu")==0)a[10]++;
		else if(strcmp(s,"i")==0)a[11]++;
	}
	for(i=0;i<n;i++){
		if(a[i]>(n+1)/2){puts("NO");return 0;}

	}
	puts("YES");
	return 0;
}

文字列をいつもどおりint型に読み込んでいい感じに場合分けしたい

int型に読み込んだ時の値 mod 21
25966 10
1768452981 15
1634889588 3
117 12
1937006964 18
26989 4
6385013 5
1937009000 17
1970430323 8
1769107316 11
7695977 2
105 0


ということでこれでばらけた

a[21],s;
main(i){
	for(gets(&i);gets(&i);i=20)a[i%21]+=2,s++;
	//1回目のgetsは高々2文字なのでiの初期化は不要
	for(;a[i]<=s+1&&i--;);
	s=!puts(~i?"NO":"YES");
}

あとはこれをぎゅっとして、

a[21],i;
main(s){
	for(;gets(&i)?a[i%21]+=2*!!s++,i=21:a[--i]<=s;);
	//終了条件がa[--i]<=sとかいうめちゃくちゃだけど動く
	i=!puts(i<0?"YES":"NO");
}
89B

最初の読み飛ばしはしなくても実はACできる

a[21],i;
main(s){
	for(;gets(&i)?a[i%21]+=2,s++,i=21:a[--i]<=s;);
	i=!puts(i<0?"YES":"NO");
}
//嘘解法:5 tori*3 何か*2 で落とせる

87B