Google Code Jam 2016 Qualification Round : D. Fractiles

あまり迷わなかった。
https://code.google.com/codejam/contest/6254486/dashboard#s=p3

問題

L,Gで構成されたK文字の文字列Tを考える。
このTについて、以下の処理をC回行う。
(各置換は同時に行われる)

• T中にあるLを最初のTで置き換える。
• T中にあるGをK回Gで繰り返したもので置き換える。

最終的なTのうち何文字かを調べることで、元のTに1個でもGがあるかを判定したい。
最大S個の文字を調べられる場合、どの文字を調べればよいか。

解法

0-indexで見たとき、a*(K^(C-1))+b*(K^(C-2))+c*(K^(C-3))...+z文字目を調べたときGであるなら、元の文字のa,b,c,...,z文字目のいずれかがGであることがわかる。
すなわち、1つの文字を調べることで最初のTのうちC文字分を調べることができる。

そのためC*S＜Kなら、調べ着ることはできない。
それ以外の場合、初回はa～zに0～(C-1)、次はC～(2C-1)…を当てはめた位置の文字を順に調べればよい。
同じ文字を複数回調べないよう注意。

int K,C,S;

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>K>>C>>S;
	
	if(C*S<K) {
		_P("Case #%d: IMPOSSIBLE\n",_loop);
	}
	else {
		_P("Case #%d:",_loop);
		x=0;
		FOR(i,S) {
			ll v=0;
			FOR(y,C) v=v*K+(x%K), x++;
			_P(" %lld",v+1);
			if(x>=K) break;
		}
		_P("\n");
	}
}

まとめ

Cよりあっさり。