メモ

yukicoderでゆるふわgolf

yukicoder No.653 E869120 and Lucky Numbers

問題はこちら
No.653 E869120 and Lucky Numbers - yukicoder

まずは66……66という形の数を2つ足すことを考えてみる。
同じ桁数のものを足すと133……32に、違う桁数のものを足すと66……66733……32となる。
(ただし、3,6は0個以上。正規表現で言うなら、前者は13*2、後者は6*73*2である)
ラッキーナンバーは、66……66に、それと桁数が等しく各位の数字が0か1である数(leading zeroあり)を足して得られるので、ラッキーナンバー2つの和として考えられるのは
(133……32)+(各位の数字が0~2である数)
(66……66733……32)+(各位の数字が0,1である数)+(各位の数字が0,1である数)となる。
この足し算では繰り上がりが発生しないことに注意しつつ、桁数の条件を考えて足される範囲を見ると、これは結局
1(3,4,5のいずれかの繰り返し)(2か3か4)
(6,7いずれかの繰り返し)(7か8)(3,4,5いずれかの繰り返し)(2か3か4)
という並びになっている数であることがわかる。正規表現でいうなら
1[345]*[234]
[67]*[78][345]*[234]
というもの。

正規表現が扱える言語ならこれで解決だが、Cはそうではないので、文字列がこのようなものであるかどうかを判定しなければならない。
頭から見ても良いが、後ろから見た方が簡単
場合分けについては自然言語で書くより次のプログラムを読んで理解してもらったほうが早いと思う。

int main(){
	char s[20010];
	gets(s);
	int i=strlen(s)-1;
	
	//最後の文字が2,3,4かチェック
	if(s[i]!='2'&&s[i]!='3'&&s[i]!='4'){
		puts("No");
		return 0;
	}

	i--;
	//3,4,5の繰り返しを飛ばす
	while(i>=0&&(s[i]=='3'||s[i]=='4'||s[i]=='5'))i--;

	//先頭まで来てたらダメ
	if(i<0){
		puts("No");
		return 0;
	}
	
	//次が1なら前者のパターン
	if(i==0&&s[i]=='1'){
		puts("Yes");
		return 0;
	}

	//次が7,8なら後者のパターン
	if(s[i]=='7'||s[i]=='8'){
		i--;
		//6,7の繰り返しを飛ばす
		while(i>=0&&(s[i]=='6'||s[i]=='7'))i--;
		//先頭まで来てたらOK
		if(i<0)puts("Yes");
		else puts("No");
		return 0;
	}

	//どちらでもなければだめ
	puts("No");
}

ところで、正規表現ですね。
ということでオートマトンを書きましょう。
状態はこんな感じ

初期状態
2,3,4→状態1

状態1
3,4,5→状態1
7,8→状態2
1→状態3

状態2
6,7→状態2
EOF→終了

状態3
EOF→終了

これをコードにするとこう
(ただし、EOFまわりだけめんどくさかったのでちょっと別の処理をしている)

main(){
	char s[20010];
	gets(s);

	int state=0;
	int i=strlen(s)-1;
	for(;i>=0;i--){
		switch(state){
			case 0:
				if(s[i]=='2'||s[i]=='3'||s[i]=='4')state=1;
				else state=-1;
				break;
			case 1:
				if(s[i]=='3'||s[i]=='4'||s[i]=='5')state=1;
				else if(s[i]=='7'||s[i]=='8')state=2;
				else if(s[i]=='1')state=3;
				else state=-1;
				break;
			case 2:
				if(s[i]=='6'||s[i]=='7')state=2;
				else state=-1;
				break;
			case 3:
				//終了していないとダメ
				state=-1;
				break;
		}
	}
	if(state==2||state==3)puts("Yes");
	else puts("No");
}

これを縮める。後ろから見るときは再帰とは何度も言っているのでそのようにする。
s[i]=='1'の部分はs[i]<='1'としてよい(もしs[i]=='0'なら、その直後かならずcase 3:に到達するので)
さらに、-1という2文字書かなくてよいように、全体に1を足す。

f;
g(c){
	f=read(0,&c,1)?g(),f-1?f-2?f-3?f-4?0
	                                  :c%27<2?4
	                                         :0
	                              :c%11<2?4
	                                     :c%17<3?3
	                                            :49/c*5
	                          :c%10<3?3
	                                 :0
                              :2
                      :1;
}
main(){g();puts(f>3?"Yes":"No");}

129B