Google Code Jam 2016 Qualification Round : A. Counting Sheep、B. Revenge of the Pancakes

今年もGCJ開幕。まずは予選は満点突破で快調。
https://code.google.com/codejam/contest/6254486/dashboard#s=p0
https://code.google.com/codejam/contest/6254486/dashboard#s=p1

A. Counting Sheep

整数Nに対しN,2N,3N...と数えていったとき、0～9の全整数が１回以上登場するのはいつか。

100N程度まで愚直にシミュレートすればよい。

int getmask(ll v) {
	int mask = 0;
	while(v) {
		mask |= 1<<(v%10);
		v/=10;
	}
	return mask;
}

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	ll N;
	
	cin>>N;
	
	if(N==0) return _P("Case #%d: INSOMNIA\n",_loop);
	int mask = 0;
	for(i=1;mask<1023;i++) mask |= getmask(N*i);
	
	_P("Case #%d: %lld\n",_loop,N*(i-1));
}

B. Revenge of the Pancakes

• • のみで構成された文字列Sが与えられる。

以下の操作を繰り返し、Sを+のみにするには最小何回の操作が必要か。

• Sのprefixに対し、+-を逆にした上で順序を反転する。

以下をSがすべて+になるまで貪欲に行えばよい。

• 先頭が+なら、先頭から+が続く範囲を選択し、処理を行うことで先頭を-にする。
• 先頭が-なら、先頭から一番後ろの-までを選択し、処理を行う。

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	string S;
	
	cin>>S;
	FORR(r,S) r=r=='-';
	while(S.size() && S.back()==0) S.pop_back();
	int ret;
	for(ret=0;S.size();ret++) {
		if(S[0]==1) {
			reverse(ALL(S));
			FORR(r,S) r^=1;
		}
		else {
			FORR(r,S) {
				if(r==1) break;
				r=1;
			}
		}
		
		while(S.size() && S.back()==0) S.pop_back();
	}
	
	
	_P("Case #%d: %d\n",_loop,ret);
}

まとめ

Bは最初DP解考えたけど、貪欲でよかったのね。