Codeforces #778 : F. Minimal String Xoration

コードは短い。
https://codeforces.com/contest/1654/problem/F

問題

長さが2^Nである文字列Sが与えられる。
ある整数jに対し、T[i]=S[i xor j]であるような文字列Tを考える。これをSをシャッフルしたものと呼ぶことにする。
こうして作成できる文字列のうち辞書順最小のものは何か。

解法

jの下のビットから決めていく。
jをd bit目まで定めた状態で、Sを2^d文字ずつのブロックに分けたとき、jに対するシャッフルを考える。
愚直に文字列を2^d文字ずつ持つと重いが、ここで重要なのは相対的な大小だけである。
よって、各シャッフルしたものが2^N通りの文字列のうち何通り目かを持つようにすれば、2^d文字全部の情報を持つことなく文字列の大小を比較できる。

こうして下から1bitずつ定めていこう。

int N;
string S;
ll from[1<<18];
ll to[1<<18];
ll cand[1<<18];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S;
	FOR(i,1<<N) {
		from[i]=S[i];
	}
	
	FOR(i,N) {
		FOR(j,1<<N) cand[j]=to[j]=(from[j]<<30)|from[j^(1<<i)];
		sort(cand,cand+(1<<N));
		FOR(j,1<<N) from[j]=lower_bound(cand,cand+(1<<N),to[j])-cand;
	}
	
	FOR(i,1<<N) if(from[i]==0) break;
	FOR(j,1<<N) cout<<S[i^j];
	cout<<endl;
}

まとめ

他で出ててもおかしくない問題かも。