★2.5位の感じ?
http://yukicoder.me/problems/412
問題
N個のアルファベット小文字で構成される文字列S[i]が与えられる。
初期状態で空文字列であるTに対し、S[i]のうち1つを選んで先頭の文字を消し、Tの末尾に追加する、という処理をS[i]がすべて空になるまで繰り返す。
Tとして得られる辞書順最小の文字列を求めよ。
解法
蟻本 p45を見ると類題が出てくる。
まずS[i]の末尾にアルファベットより文字コード順で後の末尾文字を追加しておく。
あとはS[i]のうち辞書順で最小のものを選択する、という処理を貪欲に繰り返せばよい。
int N; string S[60]; string T; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N) cin>>S[i], S[i]+="{"; while(1) { x=-1; FOR(i,N) if(S[i].size()>1) { if(x==-1 || S[x]>S[i]) x=i; } if(x==-1) break; T+=S[x][0]; S[x]=S[x].substr(1); } cout<<T<<endl; }
まとめ
★2にしては難しいし3でもしょうがないね。