Codeforces #283 Div1 A. Removing Columns

CF283に参加。
この回はDが難しかったこともあり、ABC+1Hackで結構良い順位を取れた。
http://codeforces.com/contest/497/problem/A

問題

M文字の文字列がN個順に与えられる。
ここから、全ての文字列からi文字目を削除する、という処理を任意回数行うことができる。
N個が辞書順に並ぶようにするには、最小何回処理を行えばよいか。

解法

１文字目から見ていって、辞書順が満たせないようならその文字位置を削除すればよい。
i文字目を判定するとき、i-1文字目までの時点で２つの文字列が辞書順に並んでいるなら、i文字目はなんでもよい。
i-1文字目までが一致するなら、i文字目は等しいか前者の文字列がが辞書順手前の文字でなければならない。

int H,W;
string S[1010];
int large[1001];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	FOR(y,H) cin>>S[y];
	
	int ret=0;
	FOR(x,W) {
		int ng=0;
		FOR(y,H-1) if(large[y]==0 && S[y][x]>S[y+1][x]) ng++;
		if(ng) {
			ret++;
		}
		else {
			FOR(y,H-1) if(S[y][x]!=S[y+1][x]) large[y]=1;
		}
	}
	
	cout<<ret<<endl;
}

まとめ

ここらへんはまだまだ。500ptでもいいんじゃないかね。