CS Academy Recursive String

リンク : https://csacademy.com/contest/archive/task/recursive-string/statement/

問題概要

f(0)="a",f(1)="b",f(2)="c",f(n)=f(n-1)+f(n-2)+f(n-3) であらわされる文字列を返す関数がある。N,Kが入力されるのでf(N)のK番目の値を出力せよ。

解説

N<=35より、全通りできるかなとか思ってしまった。

f(N)のサイズはフィボナッチと同様に線形時間でできる。K番目の文字さえわかればよいため、f(N)の文字列を実際に求める必要はない。もしK>f(N).size なら -1 を出力。そうでない場合は、f(N)のK番目ということは、f(N-1)かf(N-2)かf(N-3)のどこかに属する。それぞれの文字列の大きさのみに注目してf(N)のK番目がf(N-1)かf(N-2)かf(N-3)のどこに属するかわかると、最終的にf(0)かf(1)かf(2)のどこかに属することがわかる。

    
    LL n, k,dp[40];
string str;
int main() {
	cin >> n >> k;
	dp[0] = 1, dp[1] = 1, dp[2] = 1;
	rep(i, n) {
		dp[i + 3] = dp[i] + dp[i + 1] + dp[i + 2];
	}
	if (dp[n] < k) {
		cout << -1 << endl;
		return 0;
	}
	LL i = n;
	while (i > 2) {
		if (k <= dp[i - 1])
			i = i - 1;
		else if (k <= dp[i - 1] + dp[i - 2])
			k -= dp[i - 1], i = i - 2;
		else
			k -= dp[i - 1] + dp[i - 2], i = i - 3;
	}
	if (i == 0) cout << "a" << endl;
	if (i == 1) cout << "b" << endl;
	if (i == 2) cout << "c" << endl;
	return 0;
}