Codeforces #401 Div2 D. Cloud of Hashtags

最近Codeforces多すぎじゃない？
http://codeforces.com/contest/777/problem/D

問題

N個の文字列S[i]が並んでいる。
各文字の末尾を何文字か削り、全体が辞書順に並んでいるようにしたい。
削る文字列を最小にするとき、最終的なSの状態を求めよ。

解法

後ろから順に処理していく。
今S[i]をどうするか考える場合、S[i]≦S[i+1]であればよいので、以下のように処理していけばよい。

• もともとS[i]≦S[i+1]ならS[i]はいじらない。
• S[i]＞S[i+1]であれば、S[i][j]＞S[i+1][j]となる最小のjが存在するはずなので、S[i]を先頭j文字だけ残す。

int N;
string S[505050];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>S[i];
	for(i=N-2;i>=0;i--) {
		FOR(x,S[i].size()) {
			if(S[i+1].size()<x || S[i][x]>S[i+1][x]) {
				S[i]=S[i].substr(0,x);
				break;
			}
			if(S[i+1].size()>=x && S[i][x]<S[i+1][x]) {
				break;
			}
		}
	}
	FOR(i,N) cout<<S[i]<<endl;
	
}

まとめ

この回はDiv2とはいえ妙にラク。