Codeforces #814 : Div1 B. Fibonacci Strings

悪くはなかった回。
https://codeforces.com/contest/1718/problem/B

問題

文字列Sに含まれる、各文字の文字数が与えられる。
この文字列は、以下のように構成可能か答えよ。

フィボナッチ数列(1,1,2,3,5....)のprefixに対し、それぞれ1種類の文字でその文字数からなる文字列を割り当てたとき、それらの連結でSを構成できるか。

解法

文字列長を見れば、フィボナッチ数列の第何項まで見ればよいかはわかる。
あとは愚直に、登場回数の大きい文字の順にフィボナッチ数列の後ろから割り当てて行けばよい。

int T,K;
ll C[101];
ll F[100],S[100];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	F[0]=F[1]=1;
	S[0]=1;
	S[1]=2;
	for(i=2;i<=60;i++) {
		F[i]=F[i-1]+F[i-2];
		S[i]=S[i-1]+F[i];
	}
	
	cin>>T;
	while(T--) {
		cin>>K;
		ll sum=0;
		set<pair<ll,int>> M;
		FOR(i,K) {
			cin>>C[i];
			sum+=C[i];
			M.insert({C[i],i});
		}
		int tar;
		FOR(tar,60) if(S[tar]==sum) break;
		if(tar==60) {
			cout<<"NO"<<endl;
			continue;
		}
		pair<ll,int> pre={-1,-1};
		while(tar>=0) {
			if(M.empty()) break;
			pair<ll,int> a=*M.rbegin();
			
			if(a.first<F[tar]) break;
			M.erase(a);
			if(pre.first>=0) M.insert(pre);
			pre=a;
			pre.first-=F[tar];
			tar--;
		}
		if(tar==-1) {
			cout<<"YES"<<endl;
		}
		else {
			cout<<"NO"<<endl;
		}
		
	}
}

まとめ

もう少し問題文わかりやすいといいんだけどな。