2012-12-08

SRM 563 Div1 300 FoxAndHandle

04:57 |

文字列Sが与えられる。H と H のpermutationをそれぞれ順番を変えずに織り交ぜたとき S になるような辞書順最小の H を求める問題
|S|≦50

辞書順最小ということで、なんとか H を 1 文字ずつ後戻りせずに決めていきたい
H の次の文字としてありうる文字集合を小さい順に試すとして...

H の permutation なら順番はどうでもいいので、H が S の中に順番通りに入っていればそれでいい
順番を保証するために、H の次の文字を試す時は S[Si] 以降を見ることにする
S[Si] 以降で H の次の文字候補の出現位置を探す。
その位置以降に H の残り文字集合がすべて含まれていればその候補は OK
予めhi[i][c]にS[i]以降の文字カウントを保存しておいたけど毎回計算してもよかった

fedcbafedcba の場合
H の次の文字候補 abcdef
a を試すとして fedcbafedcba から a を検索 → afedcba
afedcba に abcdef が入るので１文字目は a で確定
H の次の文字候補 bcdef
b を試すとして afedcba から b を検索 → ba
ba には bcdef は入らないので b はだめ
c～eもだめ
fedcba に abcdef が入るので２文字目 f で確定
...

で、Si の進め方が 1 足りなくて failed system test. なんとも.

↓あとで (accepted in practice)

class FoxAndHandle {
	public:
	string lexSmallestName(string S) {
		int N=S.size();
		VVI hi(N+1, VI(256));
		REP(i, N) {
			hi[N-1-i] = hi[N-1-i +1];
			hi[N-1-i][S[N-1-i]]++;
		}
		string Hs;
		{
			VI w(256);
			REP(i, N) w[S[i]]++;
			REP(i, 256) {
				while(w[i]) {
					Hs.PB((char)i);
					w[i]-=2;
				}
			}
		}
		string H;
		int Si = 0;
		while(Hs.size()) {
			VI lhi(256);
			REP(j, Hs.size()) lhi[Hs[j]]++;
			
			REP(k, Hs.size()) {
				int idx=0;
				RANGE(i, Si, N) if(S[i]==Hs[k]) {idx=i;break;}
				
				int ok=1;
				REP(j, 256) if(hi[idx][j]<lhi[j]) ok=0;
				
				if(ok) {
					H.PB(Hs[k]);
					string nHs;
					int removed=0;
					REP(z, Hs.size()) {
						if(!removed && Hs[k]==Hs[z]) removed=1;
						else nHs.PB(Hs[z]);
					}
					Hs=nHs;
					//Si=idx; // だめ
					Si=idx+1; // OK
					break;
				}
			}
		}
		return H;
	}
};

kojingharangの日記

2012-12-08

SRM 563 Div1 300 FoxAndHandle