http://codeforces.com/contest/777/problem/D

与えられる$n$個の文字列が辞書順になるように文字を調整したい.できることは末尾から文字を消していくことで,辞書順にするために消す必要がある文字数を最小にして出力する.

消す文字を最小化したいので,残す文字を最大化する.逆からみて,残せるだけ残していくようにしたらACした.$i+1$番目まで確定していて,$i$番目を決める時,長さの短い方に合わせて文字を見ていき,辞書順で小さい場合は$i$番目はそのまま,辞書順で大きい場合は$i$番目と$i+1$番目の先頭からの共通文字列とする.全て同じ文字だった場合は,$i$番目と$i+1$番目の長さが短い方を優先する.

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define REP(i,k,n) for(int i=k;i<(int)(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define mp make_pair
#define fi first
#define se second

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int main() {
	int n;
	cin >> n;

	vector<string> v(n);
	rep(i, n) cin >> v[i];

	vector<string> ans(n);
	ans[n-1] = v[n-1];

	for(int i = n - 2; i >= 0; i--) {
		if(ans[i+1] == "#") {
			ans[i] =  "#";
			continue;
		}

		string t = "";
		int flag = 0;
		rep(j, min(ans[i+1].size(), v[i].size())) {
			if(v[i][j] == ans[i+1][j]) {
				t += v[i][j];
				continue;
			}
			else if(v[i][j] < ans[i+1][j]) {
				flag = 1;
				break;
			} else {
				flag = 2;
				break;
			}
		}

		if(flag == 0) ans[i] = (v[i].size() <= ans[i+1].size() ? v[i] : ans[i+1]);
		if(flag == 1) ans[i] = v[i];
		if(flag == 2) ans[i] = t;
	}

	rep(i, n) cout << ans[i] << endl;


	return 0;
}