Codeforces Round #283(div.2) 496C C. Removing Columns

タイトルアドレス:http://codeforces.com/contest/496/problem/C
テーマ:
n*mの文字マトリクスを与えて、あなたができる操作は毎回1列を削除することで、文字列マトリクスの各行の文字列が上から下まで辞書順になるように最低数列を削除することができます.
方法:
この問題は簡単で、その解法では考えやすいが、書き方が複雑な問題だ.この問題の解法は、各列を巡って、この列を削除する必要があるかどうかを確認すればいいと考えやすい.では、ある列を削除する必要があるかどうかをどのように判定しますか?
これも考えやすいですが、まず、
1.最初の列で、次の文字が前の文字より小さい場合は、この行を削除する必要があります.
2.最初の列が削除されていない場合、最初の列の文字は必ず非減算の配列であり、中間に文字が同じ部分が含まれている可能性があります.これらの文字が同じ部分を同じ文字ブロックと呼びます.同じ文字でないブロックでは、前の列の文字が異なるため、現在の文字はどうしても条件を満たしています.したがって、前のカラムの同じ文字ブロックで、最初のルールを使用してカラムを削除する必要があるかどうかを判断するだけです.
以上の解析により,各列の同じ文字ブロック(左端点と右端点を格納)を1つのvectorで格納し,次のループで前のループで処理した同じ文字ブロックを用いて判断することができる.
コードは次のとおりです.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
#define N 111
char rec[N][N];
vector<pair<int,int> > sam;
vector<pair<int,int> > tmp;
int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        for(int i=0;i<n;i++)
            scanf("%s",rec[i]);
        int ans=0;
        sam.push_back(make_pair(0,n-1));
        for(int i=0;i<m;i++)
        {
            tmp.clear();
            bool allflag=true;
            for(int j=0;j<sam.size() && allflag;j++)
            {
                int l=sam[j].first,r=sam[j].second;
                int curl=l,curr=l;
                bool flag=true;
                for(int k=l+1;k<=r && flag;k++)
                {
                    if(rec[k][i]<rec[k-1][i]) {
                        flag=false;
                    }else if(rec[k][i]>rec[k-1][i]){
                        if(curl!=curr)
                            tmp.push_back(make_pair(curl,curr));
                        curl=k;
                        curr=k;
                    }else if(rec[k][i]==rec[k-1][i]){
                        curr++;
                    }
                    if(k==r){
                        curr=k;
                        if(curl!=curr)
                            tmp.push_back(make_pair(curl,curr));
                    }
                }
                allflag=flag;
            }
            if(allflag)
                sam=tmp;
            else
                ans++;
        }
        cout<<ans<<endl;
    }
    return 0;
}