Codeforces #692 Div1 C. Poman Numbers

一転こっちはコードが短いんだよな。
https://codeforces.com/contest/1464/problem/C

問題

アルファベット小文字で構成される文字列Sに対し、f(S)は以下のように定義される。

• Sが1文字なら、その文字がアルファベットで(0-originで)i番目の場合f(S)=2^iとなる
• Sが2文字以上なら、Sを空でない文字列2つA,Bに分割し、f(S)=-f(A)+f(B)となる。A,Bの分割位置は任意に設定できるので、f(S)は複数の値を取りうる。

文字列Sが与えられるとき、f(S)はTとなりうるか判定せよ。

解法

Sの各文字が、f(S)の計算においてプラスで計上されるかマイナスで計上されるかを考える。
末尾の文字はプラス、その手前はマイナスで固定されるが、それ以外は±を選択できる。
そこで、Sの文字を大きい順に、貪欲にTを0に近づくように±指定していこう。

int N;
ll T;
string S;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>T>>S;

	FORR(a,S) a-='a';
	T-=1<<S.back();
	S.pop_back();
	T+=1<<S.back();
	S.pop_back();

	sort(ALL(S));
	reverse(ALL(S));
	T=abs(T);
	
	FORR(c,S) T=abs(T-(1LL<<c));
	
	if(T) return _P("No\n");
	cout<<"Yes"<<endl;
	
}

まとめ

本番中に思いつかず…。