Codeforces #449 Div1 A. Nephren gives a riddle

semi-ratedはさすがに無茶苦茶すぎる…。
http://codeforces.com/contest/896/problem/A

問題

以下のように文字列を定義する。

• f(0) = "What are you doing at the end of the world? Are you busy? Will you save us?".
• f(i)  =  "What are you doing while sending " + f(i - 1) + "? Are you busy? Will you send " + f(i - 1) + "?"

N,Kが与えられるので、f(N)のK文字目を答えよ。

解法

なんかどこかで見たことある気がするが…。
f(0)=A
f(i)=B+f(i-1)+C+f(i-1)+D
長い文字列を変数としてと置こう。
g(i) = |f(i)|とすると、g(i)は容易に計算できるので先に計算しきってしまおう。
g(i+1)＞g(i)*2より、g(i)はすぐに10^18を超える。

これをもとに、f(N)のK文字目を求める関数h(N,K)を考えよう。

• N=0ならA[K-1]を返すだけ
• K＞g(N)なら文字列からはみ出る
• そうでない場合、K文字目がB.F(i-1),C,f(i-1),Dのどこに相当するかわかるので、K文字目がB,C,Dのいずれかの位置に相当すればそれを返せばよいし、そうでないなら再帰的にh(N-1,*)を求めればよい。

int Q;
string S="What are you doing at the end of the world? Are you busy? Will you save us?";
string A="What are you doing while sending \"";
string B="\"? Are you busy? Will you send \"";
string C="\"?";

ll L[1010101];

char hoge(int N,ll K) {
	if(K>=L[N]) return '.';
	if(N==0) return S[K];
	if(K<A.size()) return A[K];
	K-=A.size();
	if(K<L[N-1]) return hoge(N-1,K);
	K-=L[N-1];
	if(K<B.size()) return B[K];
	K-=B.size();
	if(K<L[N-1]) return hoge(N-1,K);
	K-=L[N-1];
	return C[K];
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>Q;
	
	L[0]=S.size();
	FOR(i,100010) {
		L[i+1]=min(1LL<<60,(ll)(A.size()+B.size()+C.size())+L[i]*2);
	}
	
	FOR(i,Q) {
		int N;
		ll K;
		cin>>N>>K;
		cout<<hoge(N,K-1);
	}
	cout<<endl;
}

まとめ

ダブルクォーテーションを入れるのは勘弁してほしいなぁ。