yukicoder : No.3290 Encrypt Failed, but Decrypt Succeeded

これは典型かな…。
https://yukicoder.me/problems/no/3290

問題

あるアルファベットからなる文字列Sに対し、a→1、b→2、…、z→26と変換し、再び連結した。
連結の結果、元の文字の境目がわからなくなった。

数字列Tが与えられたとき、その元となりうるアルファベット列のうち、辞書順でK番目のものは通りか。

解法

f(n) := Tのうちn文字目以降で作れるアルファベット列の数

とする。
この時f(n)は以下の和となる。

• T[n+1]が1～9なら、Sの対応する箇所をa～iとでき、その際f(n) += f(n+1)
• T[n+1]・T[n+2]が10～26なら、Sの対応する箇所をj～zとでき、その際f(n) += f(n+2)

あとはこれを用いて、Tのうち先頭から数字1桁または2桁順次アルファベットに置き換えていこう。

int N;
ll K;
string S;
ll pat[303030];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K>>S;
	
	pat[N]=1;
	for(i=N-1;i>=0;i--) {
		if(S[i]=='0') {
			pat[i]=0;
		}
		else {
			pat[i]=pat[i+1];
			if(S[i]=='1'||(S[i]=='2'&&S[i+1]<='6')) pat[i]+=pat[i+2];
			pat[i]=min(pat[i],1LL<<61);
		}
	}
	
	int cur=0;
	while(cur<N) {
		if(K<=pat[cur+1]) {
			cout<<(char)('a'+S[cur]-'1');
			cur++;
		}
		else {
			K-=pat[cur+1];
			cout<<(char)('a'+(S[cur]-'0')*10+S[cur+1]-'1');
			cur+=2;
			
		}
	}
	cout<<endl;
	
}

まとめ

Succeededとはいえ、Kという追加パラメータのヒントもあるしね。