TopCoder SRM 563 Div1 Easy FoxAndHandle

久々のSRM、Easyでミスした上にチャレンジをしくじってスコアマイナス、ひどい目にあった…。
昼間にWUPC2がそこそこの出来だっただけに残念。

落ち着いて復習していきます。
http://community.topcoder.com/stat?c=problem_statement&pm=12331

ある文字列と、その文字列を並べ替えた文字列を混ぜた文字列が与えられるので、条件を満たせる元の文字列のうち、辞書順で最初のものを求める。

本番中は、各文字について元の文字列について採用する・しないでDPを組んだが、その後Mediumに進んだ後TLEすることに気が付いて修正、しかも結局それでもTLEした…。
ということでDPでない手法でリトライ。

答えの文字列の末尾を１文字ずつa～zで探索して追加し、条件を満たすかチェックしていけばよい。
条件とは、問題の文字列を端から１文字ずつ見ていって下記を満たすこと。

• 問題に文字列に、作成中の文字列が含まれる
• 作成中文字列が出終わる前に、問題の文字列に半分より多い文字が登場しない

結局、文字列長がN、文字種別がMだと、O((N^2)*M)程度なので計算量は問題なし。

class FoxAndHandle {
	public:
	int L;
	int al[256];
	int bl[256];
	char str[256];
	char res[256];
	
	int ok() {
		int i,j,k;
		int cl[256],dl[256];
		int ng=1;
		char c;
		FOR(i,256) cl[i]=dl[i]=bl[i];
		int cp=0;
		
		FOR(i,L) {
			c = str[i];
			if(c==res[cp]) {
				if(--dl[c]<0) return 0;
				cp++;
				if(cp==strlen(res)) break;
			}
			else {
				if(--cl[c]<0) return 0;
			}
		}
		return 1;
		
	}
	
	
	string lexSmallestName(string S) {
		L=S.size();
		strcpy(str,S.c_str());
		ZERO(al);
		int i;
		FOR(i,S.size()) al[S[i]]++;
		FOR(i,256) bl[i]=al[i]/2;
		ZERO(res);
		
		char c;
		FOR(i,L/2) {
			for(c='a';c<='z';c++) {
				res[i]=c;
				if(ok()) break;
			}
		}
		
		return string(res);
	}
};

まとめ

Easyが300ptだったので難しく考えすぎた。
あと、チャレンジはEasy自信ないときは無茶しないようにしよう…。
今回Easyも正答率低かったので、0ptならまだ被害は抑えられたがマイナスなのでひどいことになｔった。