AtCoder AGC #020 : E - Encoding Subsets

これは落ち着いて解けば解けた…のか？
https://agc020.contest.atcoder.jp/tasks/agc020_e

問題

01で構成される文字列をエンコードすることを考える。

• 文字列0,1はそれぞれ0,1とエンコードされる。
• 文字列A,BがそれぞれP,Qとエンコードされる場合、文字列ABはPQとエンコードできる。
• 文字列AをPとエンコードできる場合、AをK回以上繰り返した文字列は(A*P)とエンコードできる。

文字列が与えられる。
この文字列のSubsetである文字列群に対し、そのエンコード結果としてあり得るものは何通りか。

解法

文字列をエンコードするのではなく、文字列を再現するようなエンコード結果を列挙することを考えよう。
f(S) := 文字列SのSubsetを再現するエンコード列の数
とする。

エンコード結果の先頭文字が01か開き括弧かで分類しよう。

• エンコード結果の先頭が0,1なら、S[0]によって0,1のうち取りえる値が定まる。あとはf(S[1:])を再帰的に処理しよう。
• エンコード結果が(P*K)Qの形とする。|P|とKを総当たりすると、Pとして取りえるのはS[0..|P|-1]、S[|P|..2|P|-1]、…、S[(K-1)|P|..K|P|-1]のandのSubsetを再現するエンコードである。
  • よってS[0..|P|-1]、S[|P|..2|P|-1]、…、S[(K-1)|P|..K|P|-1]のandをTとすると、f(T)*f(S[K|P|:])を足しこんでいく。

後は上記処理をメモ化再帰する。

int N;
string S;
ll mo=998244353;
map<string,ll> memo;

ll hoge(string S) {
	if(S.empty()) return 1;
	if(memo.count(S)) return memo[S];
	ll ret=0;
	
	ret = (1+S[0])*hoge(S.substr(1))%mo;
	for(int rep=1;rep<=S.size()/2;rep++) {
		string C(rep,1);
		for(int num=1;rep*num<=S.size();num++) {
			for(int x=(num-1)*rep;x<rep*num;x++) C[x%rep] &= S[x];
			if(num>1) (ret+=hoge(C)*hoge(S.substr(rep*num)))%=mo;
		}
		
	}
	
	return memo[S]=ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	N=S.size();
	FORR(c,S) c-='0';
	
	cout<<hoge(S)<<endl;
}

まとめ

デコード結果のバリエーションが複数通りあるので、デコード結果から始めるより、エンコード結果から処理する方が楽なのか。
これは思い浮かばなかったな。逆にそこさえ思い浮かべばあとはどうにかなりそう。