kmjp's blog

競技プログラミング参加記です

yukicoder : No.653 E869120 and Lucky Numbers

時刻系の問題、ライブラリ使った方がいいんだろうか。Aはさっくり解けたけどBに手間取った。
https://yukicoder.me/problems/no/653

問題

正整数Nが与えられる。
各桁6と7だけで構成された2値の和で表せるか判定せよ。

解法

Nのうち末尾の何桁かは2つの6か7の和(および下の桁から繰り上がり分)で、その上の何桁かは1つの6か7(および下の桁から繰り上がり分)の和となっているはずである。
そこで、下の桁から順に何個の6または7の和で表しうるかを考えていこう。
この数は徐々に減っていかなければならない。

下の桁からの繰り上がり分はまず最初に差し引いておく。

  • 今見ている桁が2,3,4のいずれかなら6+6,6+7,7+7と2値の和で構成される。
  • 今見ている桁が6,7のいずれかなら1値で構成される。
  • 今見ている桁が0なら0値で構成される。

条件に反する桁を検出したら、Noを返す。

int N;
string P;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>P;
	reverse(ALL(P));
	
	int num=2,carry=0,first=1;
	FORR(c,P) {
		x=c-'0'-carry;
		carry=0;
		
		if(num==-1) return _P("No\n");
		
		if(x==0) {
			num=-1;
		}
		else if(x==6||x==7) {
			if(num<1) return _P("No\n");
			num=1;
		}
		else if(x>=2 && x<=4) {
			if(num<2) return _P("No\n");
			carry=1;
		}
		else {
			return _P("No\n");
		}
		if(first&&num!=2) return _P("No\n");
		first=0;
	}
	if(carry) return _P("No\n");
	_P("Yes\n");
}

まとめ

めでたい数字というと7,8のイメージだけど、そうすると7と8+8+1(繰り上がり)=17の下の桁の和が被るからやめたのかな?