cafelier@SRM

SRM509 500

SRM | 02:06 |

場合分け抹殺計画。

本番に提出し（て撃墜された解を２行足して正しくし）たものがコレ。回文なら左端と右端が合ってないといけないので、両端を見て、合わせ方を全部試す。あとは再帰で。

class PalindromizationDiv1 { public:
   int getMinimumCost(string word, vector <string> operations) 
   {
      for(int i=0; i<word.size(); ++i)
         word[i] -= 'a';

      vector<int> add(26, -1);
      vector<int> del(26, -1);
      vector< vector<int> > rep(26, vector<int>(26, -1));
      map<pair<char,char>,int> change;
      for(int i=0; i<operations.size(); ++i)
      {
         string cmd;
         char letter, to;
         int cost;

         stringstream cin(operations[i]);
         cin >> cmd;
         if( cmd == "add" ) {
            cin >> letter >> cost;
            add[letter-'a'] = cost;
         }
         if( cmd == "erase" ) {
            cin >> letter >> cost;
            del[letter-'a'] = cost;
         }
         if( cmd == "change" ) {
            cin >> letter >> to >> cost;
            rep[letter-'a'][to-'a'] = cost;
         }
      }

      for(int k=0; k<26; ++k)
         for(int i=0; i<26; ++i)
            for(int j=0; j<26; ++j)
               if( rep[i][k]!=-1 && rep[k][j]!=-1 )
                  if( rep[i][j]==-1 || rep[i][j]>rep[i][k]+rep[k][j] )
                     rep[i][j] = rep[i][k]+rep[k][j];

      for(int i=0; i<26; ++i)
         for(int j=0; j<26; ++j)
            if( add[i]!=-1 && rep[i][j]!=-1 )
               if( add[j]==-1 || add[j]>add[i]+rep[i][j] )
                  add[j] = add[i]+rep[i][j];

      for(int i=0; i<26; ++i)
         for(int j=0; j<26; ++j)
            if( rep[i][j]!=-1 && del[j]!=-1 )
               if( del[i]==-1 || del[i]>rep[i][j]+del[j] )
                  del[i] = rep[i][j]+del[j];

      map<int, int> memo;
      int r = rec(memo, word, add, del, rep, 0, word.size()-1);
      return (r>=0x3fffffff ? -1 : r);
   }

   int rec(map<int,int>& memo,
      const string& word,
      const vector<int>& add,
      const vector<int>& del,
      const vector< vector<int> >& rep,
      int s, int e)
   {
      #define REC(ss,ee) rec(memo,word,add,del,rep,(ss),(ee))
      if( s >= e )
         return 0;
      int key = s*100+e;
      if( memo.count(key) )
         return memo[key];

      int result = 0x3fffffff;
      if( word[s] == word[e] )
         result = min(result, REC(s+1,e-1));
      if( del[word[s]]>=0 )
         result = min(result, REC(s+1,e)+del[word[s]]);
      if( del[word[e]]>=0 )
         result = min(result, REC(s,e-1)+del[word[e]]);
      if( add[word[s]]>=0 )
         result = min(result, REC(s+1,e)+add[word[s]]);
      if( add[word[e]]>=0 )
         result = min(result, REC(s,e-1)+add[word[e]]);
      if( rep[word[s]][word[e]]>=0 )
         result = min(result, REC(s+1,e-1)+rep[word[s]][word[e]]);
      if( rep[word[e]][word[s]]>=0 )
         result = min(result, REC(s+1,e-1)+rep[word[e]][word[s]]);
      for(int c=0; c<26; ++c) {
         if( rep[word[s]][c]>=0 && add[c]>=0 )
            result = min(result, REC(s+1,e)+rep[word[s]][c]+add[c]);
         if( rep[word[e]][c]>=0 && add[c]>=0 )
            result = min(result, REC(s,e-1)+rep[word[e]][c]+add[c]);
         if( rep[word[s]][c]>=0 && rep[word[e]][c]>=0 ) // 追加
            result = min(result, REC(s+1,e-1)+rep[word[s]][c]+rep[word[e]][c]); // 追加
      }
      return memo[key] = result;
   }
};

で、これは良くないコードだ、と思う。他の人の解を見て、なるほどなあ、と感心したのが以下のような方針。

class PalindromizationDiv1 { public:
   static const int INF = 0x3fffffff;
   static const int NOLETTER = 26;
   static const int N = 27;

   int getMinimumCost(string word, vector <string> operations) 
   {
      // Cost for changing a character to another
      int cost[N][N];
      for(int a=0; a<N; ++a)
         for(int b=0; b<N; ++b)
            cost[a][b] = (a==b ? 0 : INF);

      for(size_t i=0; i<operations.size(); ++i)
      {
         stringstream cin(operations[i]);
         string cmd; cin >> cmd;

         char a, b; int c;
         if( cmd == "add" )   { cin >> a >> c;      cost[NOLETTER][ a - 'a'] = c; }
         if( cmd == "erase" ) { cin >> a >> c;      cost[ a - 'a'][NOLETTER] = c; }
         if( cmd == "change" ){ cin >> a >> b >> c; cost[ a - 'a'][ b - 'a'] = c; }
      }

      // Warshall-Floyd
      for(int k=0; k<N; ++k)
         for(int i=0; i<N; ++i)
            for(int j=0; j<N; ++j)
               cost[i][j] = min(cost[i][j], cost[i][k]+cost[k][j]);

      // Cost for matching two letters
      int match_cost[N][N];
      for(int i=0; i<N; ++i)
         for(int j=0; j<N; ++j)
         {
            match_cost[i][j] = INF;
            for(int k=0; k<N; ++k)
               match_cost[i][j] = min(match_cost[i][j], cost[i][k]+cost[j][k]);
         }

      // Solve
      memo.clear();
      int r = rec(match_cost, word, 0, word.size()-1);
      return (r>=INF ? -1 : r);
   }

   map<pair<int,int>,int> memo;
   int rec(const int match_cost[N][N], const string& w, int s, int e)
   {
      // Base case
      if( s >= e )
         return 0;

      // Memoizaion
      const pair<int,int> key(s, e);
      if( memo.count(key) )
         return memo[key];

      // take best
      int result = INF;
      result = min(result, rec(match_cost, w, s+1, e-1)+match_cost[w[s]-'a'][w[e]-'a']);
      result = min(result, rec(match_cost, w, s,   e-1)+match_cost[NOLETTER][w[e]-'a']);
      result = min(result, rec(match_cost, w, s+1, e  )+match_cost[w[s]-'a'][NOLETTER]);
      return memo[key] = result;
   }
};

とにかく

• 場合分けはバグの元

というのは言えると思う。分けないで統一的に書ける方法をできる限り探したい。

• addなのかeraseなのかchangeなのか、という分類を消して統一的に扱うために、"文字無し"を意味する特殊ノードを入れる
  • これで入力を読むとき以外に命令種の場合分けは要らない
• "左にadd"と"右をerase"的な左右の分類を消して、"文字無しの左と元々の右を合わせる"というように、"合わせる"コストを計算しておく
  • これで、どの文字を経由するとか左右のどっちを変えるとかの考慮が再帰と分離できる

と、こういうことを、場合分け地獄があらわれた！と思った瞬間に本番中に考えないといかんのですよね。反省。