| 
反省点
DFSでという方針がそもそもだめだったらしい。撃墜された。。たぶん長いDDDDDDDDDDDDDDDDDDDDDDとかが入力されたのだと思う。
DFSのコードがなんかバグってて、いろいろcoutしまくってたのを submit して、入力が長いと標準出力のせいで実行時間制限にひっかかりそうなのでcoutを消してsubmitしたと思ったら修正してないやつをsubmitしてて、合計３回submitして大幅減点。ぬるい。で、結局撃墜。
他の人のコードをみると、DDDが続くかたまりを見つけて、その中だけで順序を反転させる、という処理だけで良いみたい。美しい...
というわけで Div2 に落ちそうです....
class PermutationSignature { public: int dfs(string& sig, int pos, int start, VI& ans) { //cout<<"pos "<<pos<<endl; //printf("%s %d\n", __FILE__, __LINE__); int sz = sig.SZ; FOR(i, 1, sz+2) { //cout<<"try pos "<<pos<<" i "<<endl; int ok = 1; REP(j, pos) { if(ans[j]==i) {/*cout<<"NG dup "<<ans[j]<<endl;*/ok=0; break;} } if(!ok) continue; if(pos!=0) { if(sig[pos-1]=='I' && i<ans[pos-1]) {/*cout<<"NG "<<sig[pos-1]<<" "<<i<<" "<<ans[pos-1]<<endl;*/ ok=0;continue;} if(sig[pos-1]=='D' && i>ans[pos-1]) {/*cout<<"NG "<<sig[pos-1]<<" "<<i<<" "<<ans[pos-1]<<endl;*/ ok=0;continue;} } //cout<<"pos "<<pos<<" i "<<i<<" ok "<<ok<<endl; //if(!ok) continue; ans[pos] = i; if(pos==sz) { cout<<"FOUND "<<ans<<endl; return 1; } int ret = dfs(sig, pos+1, 0, ans); if(ret) return 1; } return 0; } vector <int> reconstruct(string sig) { printf("%s %d\n", __FILE__, __LINE__); int sz = sig.SZ; VI ans(sz+1); dfs(sig, 0, 1, ans); return ans; }
