久々のSRM、Easyでミスした上にチャレンジをしくじってスコアマイナス、ひどい目にあった…。
昼間にWUPC2がそこそこの出来だっただけに残念。
落ち着いて復習していきます。
http://community.topcoder.com/stat?c=problem_statement&pm=12331
ある文字列と、その文字列を並べ替えた文字列を混ぜた文字列が与えられるので、条件を満たせる元の文字列のうち、辞書順で最初のものを求める。
本番中は、各文字について元の文字列について採用する・しないでDPを組んだが、その後Mediumに進んだ後TLEすることに気が付いて修正、しかも結局それでもTLEした…。
ということでDPでない手法でリトライ。
答えの文字列の末尾を1文字ずつa~zで探索して追加し、条件を満たすかチェックしていけばよい。
条件とは、問題の文字列を端から1文字ずつ見ていって下記を満たすこと。
- 問題に文字列に、作成中の文字列が含まれる
- 作成中文字列が出終わる前に、問題の文字列に半分より多い文字が登場しない
結局、文字列長が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ならまだ被害は抑えられたがマイナスなのでひどいことになtった。