土下座しながら探索中

主に競技プログラミング

Codeforces 497A : Removing Columns

問題リンク : Problem - A - Codeforces

問題概要 :
長さmの文字列がn個与えられる
自分はこの文字列に対して、ある列を決めn個の文字列の決めた列にある文字を全て削除することができる
n個の文字列が辞書順になるために必要な列の削除の回数をもとめよ

解法 :
列を0から順に最後までみていく
列0の段階では、その列全体が辞書順になっていなければならない
そうでない場合は必ずその列を削除しなければならない
辞書順になっている場合、
ある文字とその次の文字が異なるのであればその先はまったく関係がない
ある文字とその次の文字が同一の場合はその次の列のそれらの場所にある文字次第である
再帰でそれらの範囲を選択し、validでなければその列を消しvalidならばその中で連続して同じ文字が続いている部分に対して再帰する

コード:

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

string a[110];
bool erased[110];
int n,m;
bool update;

void dfs(int x,int top,int bottom){
  if( x >= m ) return;
  if( erased[x] ) {
    dfs(x+1,top,bottom);
    return;
  }

  bool valid = true;
  REP(i,top+1,bottom+1) {
    if( a[i][x] < a[i-1][x] ) { valid = false; break; }
  }
  if( !valid ) {
    erased[x] = true;
    update = true;
    dfs(x+1,top,bottom);
    return;
  }
  REP(i,top,bottom+1) {
    int sp = i, ep = i;
    while( ep+1 <= bottom && a[ep][x] == a[ep+1][x] ) ++ep;
    if( sp == ep ) continue;
    else {
      i = ep;
      dfs(x+1,sp,ep);
    }
  }
}

bool finish[110];
int main(){

  cin >> n >> m;
  rep(i,n) cin >> a[i];
  string s = "";
  rep(i,n) s += a[i][0];
  memset(erased,false,sizeof(erased));
  update = true;
  while(update){
    update=false;
    dfs(0,0,n-1);
  }
  int answer = 0;
  rep(i,m) answer += erased[i];
  cout << answer << endl;
  return 0;
}