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

メモ

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

yukicoder No.154 市バス

問題はこちら
No.154 市バス - yukicoder


場合分けが難しい

先頭から順にW,G,Rの数をカウントしていき、W≧G≧Rが常に成り立っていて、かつ
最後まで見た時G=Rかつ、「Rでない文字のうち一番後ろにあるもの」がGであることがpossibleの必要十分条件
(最後の条件は、「Gと対応のないW」が存在しないことと同値)

ということでこれを実装

int main(){
	int n,i,f,w,g,r,t;
	char s[1010];
	scanf("%d\n",&n);
	//\nをつけないと直後のgetsが失敗する
	while(n--){
		gets(s);
		w=g=r=t=0;f=1;
		for(i=0;s[i];i++){
			if(s[i]=='R')r++;
			else{
				t=s[i];
				s[i]=='G'?g++:w++;
			}
			if(w<g||g<r)f=0;
		}
		if(g!=r||t!='G')f=0;
		puts(f?"possible":"impossible");
	}
	return 0;
}

文字列を先頭から見ていくのでgetsしなくてもreadで十分
またW,G,Rもその値ではなくW-G,G-Rを保存すれば変数が1つ減る

int main(){
	int x,f=1,s=0,t=0;
	char z;
	scanf("%*d\n");
	for(;read(0,&z,1);){
		if(z==10){
			if(t!=0||x!='G')f=0;
			puts(f?"possible":"impossible");
			f=1;s=t=0;
			//sがW-G,tがG-R
		}else{
			if(z=='R')t--;
			else{
				x=z;
				z=='G'?s--,t++:s++;
			}
			if(s<0||t<0)f=0;
		}
	}
	return 0;
}

これを縮める
s,tが一度負になったら再び正に戻ることがないようにすれば、フラグfを保存する必要はない
また読み飛ばしをうまくやれば最初のscanfもいらない
zも0で初期化されていればintでよい

こうして

x,z,s,t;
main(i){
	for(;read(0,&z,1);){
		if(z==10){
			s=t=--i&&!puts(t|s<0|x-'G'?"impossible":"possible");
		}else{
			z-'R'?x=z,z-'W'?s--,t>=0&&t++:s>=0&&s++:t--;
		}
	}
}

こうじゃ

x,z,s,t;main(i){for(;read(0,&z,1);)z<11?s=t=--i&&!puts("impossible"+2*!(t|s<0|x-71)):z-82?x=z,z-87?s--,~t&&t++:~s&&s++:t--;}

124B

17/01/12追記
分岐条件を見直して3B短縮。bit演算子は強い

x,z,s,t;main(i){for(;read(0,&z,1);)z&1?x=z,z%3?s--,~t&&t++:~s&&s++:z&8?s=t=--i&&!puts("impossible"+2*!(t|s<0|x-71)):t--;}

121B

17/01/24追記
やはりフラグを使ったほうが短く書けるようだ。
「『Rでない文字のうち一番後ろにあるもの』がGであること」は「Wが登場した以降に必ずGが登場する」と同値であることに注意して次のように書ける

z,g,w,f;main(i){
	for(;read(0,&z,1);){
		if(z=='W')w++,f|=2;
		if(z=='G')g++,f=f&1|--w<0;
		if(z=='R')f|=--g<0;
		if(z=='\n')g=w=f=--i&&!puts("impossible"+!f*!g*2);
	}
}

fの最下位bitに「W≧G≧Rが成立しているか」、その上のbitに「Wが登場した以降にGが登場したか」を保存している
これをぎゅっと縮める

z,g,w,f;main(i){for(;read(0,&z,1);)f=z&1?z%3?g++,f&1|--w<0:(w++,f|2):z&8?g=w=--i&&!puts("impossible"+!f*!g*2):f|--g<0;}

ぐっと睨むと次のようにカッコが外せる

z,g,w,f;main(i){for(;read(0,&z,1);)f=z&1?z%3?g++,f&1|--w<0:f|++w*2:z&8?g=w=--i&&!puts("impossible"+!f*!g*2):f|--g<0;}

117B