Google Code Jam 2017 Qualification Round : A. Oversized Pancake Flipper、B. Tidy Numbers、C. Bathroom Stalls

今年もGCJに参加。時間がなく少ししか参加できなかったこともあり、Dは時間切れ。
https://code.google.com/codejam/contest/3264486/dashboard#s=p0
https://code.google.com/codejam/contest/3264486/dashboard#s=p1
https://code.google.com/codejam/contest/3264486/dashboard#s=p2

A. Oversized Pancake Flipper

"+-"で構成された文字列が与えられる。
連続するK文字を両者反転できるとき、全体を"+"にできるか。

左から見て、"-"があったらそこから右K文字を反転させていけばよい。

string S;
int K;

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>S>>K;
	
	int ret=0;
	FOR(i,S.size()) {
		if(S[i]=='-') {
			if(i+K>S.size()) return _P("Case #%d: IMPOSSIBLE\n",_loop);
			ret++;
			
			FOR(j,K) S[i+j]='+'+'-'-S[i+j];
		}
	}
	
	_P("Case #%d: %d\n",_loop,ret);
}

B. Tidy Numbers

整数Nが与えられる。
N以下の整数のうち、各桁の数値が昇順になっているものの最大値を求めよ。

ある連続する2桁ABが降順になっている場合、その2桁を(A-1)9に置き換えるという処理を繰り返せばよい。
Leading Zeroは消しておくこと。

string S;
int N;

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>S;
	
	while(1) {
		FOR(i,S.size()-1) if(S[i]>S[i+1]) break;
		if(i==S.size()-1) break;
		S[i]--;
		for(j=i+1;j<S.size();j++) S[j]='9';
	}
	
	while(S[0]=='0' && S.size()>1) S=S.substr(1);
	
	_P("Case #%d: %s\n",_loop,S.c_str());
}

C. Bathroom Stalls

N個の一列に並んだ空きマスがある。
これらのうち、K個のマスを以下の手順で埋める。

• そこのマスを埋めた場合、左右の連続する空きマスの数のうち少ない方が最大となる場所を選ぶ。
• 同じ条件のものがあれば、最も左側のマスを選ぶ。

K個目に埋めたマスに関し、左右の連続する空きマス数を求めよ。

この問題はマスの位置はあんまり関係なくて、何マス連続している空きマスのうち中央の1マスを埋める、ということを繰り返す。
処理過程で出てくる連続する空きマスのパターンは同じようなものばかりなので、map等使い同じ長さの空きマス群はまとめて処理しよう。

ll N,K;

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>N>>K;
	map<ll,ll> M;
	M[-N]=1;
	while(1) {
		auto v = *M.begin();
		ll len=-v.first;
		ll num=v.second;
		M.erase(M.begin());
		
		ll L=(len-1)/2;
		ll R=len-1-L;
		if(L>R) swap(L,R);
		
		if(K<=num) {
			_P("Case #%d: %lld %lld\n",_loop,R,L);
			return;
		}
		K-=num;
		if(L) M[-L]+=num;
		if(R) M[-R]+=num;
	}
	
	
}

まとめ

ここまではすんなり。