Hatena::Grouptopcoder

cafelier@SRM

cafelier のSRM参加記録です。コンテスト中に考えてたことを執拗に全部書き残すとどうなるだろうかという試み本番中にこういうコードが書きたかったなあ、という後で書いた反省コードを書き残す試み

スパムが来たのでしばらくコメント欄をはてなユーザ限定にしています、すみません、

2014-02-26

SRM610 Div1 550

| 20:03 | はてなブックマーク - SRM610 Div1 550 - cafelier@SRM

  • 入力
    • 初期燃料 F
    • タスクの集合 T = (d[0],r[0]), (d[1],r[1]), ... (d[N-1],r[N-1])
  • 求めるもの
    1. 初期値 f = F
    2. Tから d<=f であるような一組(d,r)を取り除き、f=f-d+r とする
    3. ステップ2を繰り返す
    4. できるだけ多くステップ2を繰り返せるように頑張ったら何回できますか

解くときに考えたこと。

  • Tから取り出す順番がフリーダムだとパターンが多すぎて考えにくい。
  • 固定の順番で試してみれば十分ということはないだろうか?
    • たとえば、d が小さいタスクは後の方に回しても実行できるから、必ず d が大きい順に実行する方がお得とか
    • たとえば、d-r が小さい方が燃料の減りがトータルで少なくて後のタスクに差し支えにくいので、こういうのを先にやった方が絶対お得とか
    • なんかそんな感じの。

  • そもそも順番固定したら解けるのかっていうと謎だけど。
  • それは未来の自分が頑張って格好良く解いてくれる!頑張れ未来の自分!

  • ということで試す順序の固定の仕方を考える。
    • タスク T1=(d1,r1) と T2=(d2,r2) があるとき、どっちを先に実行するべきか?
    • 「先にやっても損がない」方を先にやるべき。
      • 先にやると損というのは、"T1をやった後でもT2はできるのに、T2をやった後は燃料不足でT1ができない" みたいな状況。これはT2を先にやるのは損。
      • 逆にいうと「T1を先にやっても損がない」とは
      • 「T2→T1 の順でできるなら T1→T2 の順でもできる」ことと同値。
      • なぜならT1を先にやってもT2ができる可能性を狭めないから損がない。

  • 「T2→T1 の順でできるなら T1→T2 の順でもできる」とは何か。
    • T2→T1の順でやると燃料は (-d2, -d2+r2, -d2+r2-d1, -d2+r2-d1+r1) の順に移り変わる。
    • この時、燃料がもっとも少なくなるのは min(-d2, -d2+r2-d1) のとき。
    • T1→T2 の時の燃料の底は min(-d1, -d1+r1-d2)
    • 燃料が一番少ない瞬間に余裕があるタスク順の方が実行しやすいので
  • 「T2→T1 の順でできるなら T1→T2 の順でもできる」 とはすなわち
  • 後者の方が燃料の底が大ということなので
    • min(-d1, -d1+r1-d2) >= min(-d2, -d2+r2-d1)
    • のことである。

  • 問題は、この謎の条件式が全順序関係になっているかどうか。
  • じゃんけんの勝ち負けみたいに「こっちを先にした方が損がない」関係が輪になっているとソートして先頭から順に試すとかができないので困る。
  • 何とかして全順序になっているかどうかを見抜きたい。わからん。


  • min(-d1, -d1+r1-d2) >= min(-d2, -d2+r2-d1)
    • の何がわからんかというと、dとrが色々混ざっててわからん。
    • 分解しましょう。
    • 「x >= min(y,z)」 は 「x>=y または x>=z」と同値。つまり
  • min(-d1, -d1+r1-d2) >= -d2 または min(-d1, -d1+r1-d2) >= -d2+r2-d1
    • さらに「min(a,b)>=c」は「a>=c かつ b>=c」と同値。つまり
  • 「-d1>=-d2 かつ -d1+r1-d2>=-d2」または「-d1>=-d2+r2-d1 かつ -d1+r1-d2>=-d2+r2-d1

  • さて
    • 問題文の条件で、d>r と書いてある。
    • つまり -d1+r1 < 0
    • つまり2個目の論理式 -d1+r1-d2>=-d2 は絶対に成り立たない
  • 「-d1>=-d2 かつ False」または「-d1>=-d2+r2-d1 かつ -d1+r1-d2>=-d2+r2-d1
    • つまり
  • 「False」または「-d1>=-d2+r2-d1 かつ -d1+r1-d2>=-d2+r2-d1
    • つまり
  • 「-d1>=-d2+r2-d1 かつ -d1+r1-d2>=-d2+r2-d1

  • 同様に
    • -d2+r2 < 0 なので「-d1>=-d2+r2-d1」これは絶対にTrue。
  • 「True かつ -d1+r1-d2>=-d2+r2-d1
    • つまり
  • -d1+r1-d2>=-d2+r2-d1
    • なにか両辺に-d1とか-d2とか同じ物がある。消そう。
  • r1 >= r2。


  • まとめよう。
    • 「T1 を T2 より先にやった方が損がない」iff
    • 「T2→T1 の順でできるなら T1→T2 の順でもできる」iff
    • 「min(-d1, -d1+r1-d2) >= min(-d2, -d2+r2-d1)」iff
    • 「r1 >= r2」
  • つまり r の大きいタスクから先に試すべき。

  • あとは未来の自分が頑張った。
トラックバック - http://topcoder.g.hatena.ne.jp/cafelier/20140226

2012-08-18

SRM552 Div1 900

| 23:01 | はてなブックマーク - SRM552 Div1 900 - cafelier@SRM

問題文を整理すると、

  • 「upTo (≦10^10) 以下の自然数で、次の条件を満たすものの個数は?」
  • 条件:素因数分解 p1^k1 p2^k2 ... pm^km したとき
    • pi ≦ maxmalPrime (≦10^6)
    • ki は奇数

が問われている。計算量が分析できてないので考える。

class HolyNumbers { public:
   long long count(long long upTo, int maximalPrime)
   {
      return rec(eratosthenes(maximalPrime), 0, upTo);
   }

   static vector<LL> eratosthenes(int N)
   {
      vector<LL> ps;
      vector<bool> is_prime(N+1, true);
      for(int p=2; p<=N; ++p)
         if(is_prime[p]) {
            ps.push_back(p);
            for(int q=p+p; q<=N; q+=p)
               is_prime[q] = false;
         }
      return ps;
   }

   static LL rec(const vector<LL>& ps, int i, LL upto)
   {
      if( i==ps.size() || upto<ps[i] )
         return 1;

      // 以下2行が枝刈り
      // ps[i]の2乗より小さかったら高々1回しか割れないのでパターン数は数えればわかる
      if( upto < ps[i]*ps[i] )
         return upper_bound(ps.begin()+i, ps.end(), upto)-ps.begin() - i + 1;

      LL sum = rec(ps, i+1, upto);
      for(LL p=ps[i], pk=p; pk<=upto; pk*=p*p)
         sum += rec(ps, i+1, upto/pk);
      return sum;
   }
};

ほぼナイーブな全探索。

  • upTo を 2, 8, 32, 128, 512, ... で割ってみる
  • その結果を 3, 27, 243, ... で割ってみる
  • その結果を 5, 125, ... で

を再帰で、エラトステネスの篩で求めた素数リストに対してひたすら繰り返し。特にメモ化もしない。

【性質1】途中の2行の枝刈りをしなかった場合、計算時間 = O(recの呼び出し回数) = O(答え)

  • 理由: if(upto<ps[i]) return 1; が入っているので、再帰本体のfor文に到達したときに1回は必ず回る。トーナメント形式の対戦回数がO(チーム数)であるのと同じ理屈で、再帰の時は必ず分岐する再帰の呼び出し回数はO(leafの数)。この場合は再帰のleafでreturn 1してその数を数えて答えているので、これは答えの値に等しい。

以下 upTo は最大値 10^10 固定で考える。上の議論により計算時間は O(upTo) で抑えられたけど、これでは大きすぎる。maximalPrime=200 で答えが1000万くらい。ここらへんまでが特に枝刈りしなくても行ける範囲。

10^7オーダに落とすには、maximalPrime=10^6のケースで1000倍高速化すればよい。枝刈りによってどのくらい速くなるかというと、

if( upto < ps[i]*ps[i] )
   return upper_bound(ps.begin()+i, ps.end(), upto)-ps.begin() - i + 1;

要はまとめて数えることでleafがどれだけ減ったかと考えると、このreturn文が平均でいくつを返すかによって決まる。平均で1000を返すなら1000倍速い(たぶん)。

1000以上を返すのはどういう場合かというと

pの1000個先の素数 <= upto < 素数p^2

の時で、枝刈れるならすぐ刈ってるので割と upto ≒ 素数p^2 っぽいと仮定すると

pの1000個先の素数 < 素数p^2

なら十分で、これは調べてみると p=101 辺りから成り立つようなので、まあだいたいほとんどの素数で成り立っていると言える、のかな?すごく嘘っぽいですね。

トラックバック - http://topcoder.g.hatena.ne.jp/cafelier/20120818

2012-04-11

SRM 540

| 00:07 | はてなブックマーク -  SRM 540 - cafelier@SRM

250

  • A[0] = x とする
  • 例えば B[0] = 100 で op[0]=='+' なら A[1] は 100-x
  • 例えば B[1] = 50 で op[0]=='-' なら A[2] は (100-x)-50
  • という感じでA[1], ..., A[N-1] を全部 x の一次式で求めてそれが正の数になるという不等式
typedef long long LL;
typedef complex<double> CMP;

class ImportantSequence { public:
   int getCount(vector <int> B, string operators)
   {
      vector< pair<LL,LL> > A;
      A.push_back( make_pair(1,0) ); // A[0] = 1x + 0
      for(int i=0; i<B.size(); ++i)
      {
         LL a = A.back().first;
         LL b = A.back().second;
         LL c = B[i];
         if( operators[i] == '+' ) // (ax+b) + A[i] = c  :: A[i] = -ax + c-b
            A.push_back( make_pair(-a, c-b) );
         else // (ax+b) - A[i] = c   :: A[i] = ax + b-c
            A.push_back( make_pair(a, b-c) );
      }

      static const LL INF = (1LL<<62);
      LL xMin = 1;
      LL xMax = INF;
      for(int i=0; i<A.size(); ++i)
      {
         LL a = A[i].first;
         LL b = A[i].second;
         // ax + b > 0  (aは+1か-1)
         if( a == +1 ) // x > -b
            xMin = max(xMin, -b+1);
         else // -x > -b  == x < b
            xMax = min(xMax, b-1);
      }

      return xMax==INF ? -1 : max(0, int(xMax-xMin)+1);
   }
};
  • 問題を見たら探索空間の自由度はどれくらいか?を考える
  • どれとどれを決めれば残りが定まるか?と
  • 今回の場合一個目 A[0] が決まれば全部決まる
    • 案1: じゃあ可能な A[0] を全通り試そう
    • 案2: 可能な A[0] の上限下限を二分探索とか挟み撃ちとかで賢く探そう
    • 案3: じゃあ A[0] を使って記号的に全部の値を決めよう
  • などがあって、現れる演算が + と - しかないことを考えると、「記号的に全部の値を表現」が爆発しないことがわかるのでそれでやってみる、という感じで考えた。

550

  • 基本的に問題の定義通りの確率の漸化式をDPで計算するのだけど
  • 直方体領域の和は累積和っぽくやって包除原理っぽくやるとO(1)
  • コード汚い
class RandomColoring { public:
   double getProbability(int N, int maxR, int maxG, int maxB, int startR, int startG, int startB, int d1, int d2)
   {
      const int dx = d1-1;

      vector< vector< vector<double> > > p(maxR, vector<vector<double> >(maxG, vector<double>(maxB)));
      p[startR][startG][startB] = 1.0;

      for(int i=1; i<N; ++i)
      {
         for(int r=0; r<maxR; ++r)
         for(int g=0; g<maxG; ++g)
         for(int b=0; b<maxB; ++b) {
            int c = cnt(maxR, maxG, maxB, r-d2, r+d2, g-d2, g+d2, b-d2, b+d2)
            - (d1==0 ? 0 : cnt(maxR, maxG, maxB, r-dx, r+dx, g-dx, g+dx, b-dx, b+dx));
            if( c )
               p[r][g][b] /= c;
            else
               p[r][g][b] = 0;
         }

         vector< vector< vector<double> > > low = p;
         for(int rgb=0; rgb<=maxR+maxG+maxB-3; ++rgb)
         for(int r=0; r<maxR; ++r)
         for(int g=0; g<maxG; ++g)
         {
            int b = rgb-r-g;
            if( 0<=b && b<maxB ) {
               low[r][g][b] =
                  p[r][g][b]
                  + (r ? low[r-1][g][b] : 0)
                  + (g ? low[r][g-1][b] : 0)
                  + (b ? low[r][g][b-1] : 0)
                  - (r&&g ? low[r-1][g-1][b] : 0)
                  - (g&&b ? low[r][g-1][b-1] : 0)
                  - (b&&r ? low[r-1][g][b-1] : 0)
                  + (r&&g&&b ? low[r-1][g-1][b-1] : 0);
            }
         }

         vector< vector< vector<double> > > q = p;
         for(int r=0; r<maxR; ++r)
         for(int g=0; g<maxG; ++g)
         for(int b=0; b<maxB; ++b)
         {
            q[r][g][b] =
                 zone(low, r-d2, r+d2, g-d2, g+d2, b-d2, b+d2)
               - (d1==0 ? 0 : zone(low, r-dx, r+dx, g-dx, g+dx, b-dx, b+dx));
         }
         p.swap(q);
      }

      vector< vector< vector<double> > > low = p;
      for(int rgb=0; rgb<=maxR+maxG+maxB-3; ++rgb)
      for(int r=0; r<maxR; ++r)
      for(int g=0; g<maxG; ++g)
      {
         int b = rgb-r-g;
         if( 0<=b && b<maxB ) {
            low[r][g][b] =
               p[r][g][b]
               + (r ? low[r-1][g][b] : 0)
               + (g ? low[r][g-1][b] : 0)
               + (b ? low[r][g][b-1] : 0)
               - (r&&g ? low[r-1][g-1][b] : 0)
               - (g&&b ? low[r][g-1][b-1] : 0)
               - (b&&r ? low[r-1][g][b-1] : 0)
               + (r&&g&&b ? low[r-1][g-1][b-1] : 0);
         }
      }

      return 1.0 - (
         zone(low, startR-d2, startR+d2, startG-d2, startG+d2, startB-d2, startB+d2)
         - (d1==0 ? 0 : zone(low, startR-dx, startR+dx, startG-dx, startG+dx, startB-dx, startB+dx))
      );
   }

   double zone(const vector< vector< vector<double> > >& low,
      int r, int R, int g, int G, int b, int B) {
      r = max(0, min<int>(low.size()-1, r));
      R = max(0, min<int>(low.size()-1, R));
      g = max(0, min<int>(low[0].size()-1, g));
      G = max(0, min<int>(low[0].size()-1, G));
      b = max(0, min<int>(low[0][0].size()-1, b));
      B = max(0, min<int>(low[0][0].size()-1, B));
      return low[R][G][B]
            - (r ? low[r-1][G][B] : 0)
            - (g ? low[R][g-1][B] : 0)
            - (b ? low[R][G][b-1] : 0)
            + (r&&g ? low[r-1][g-1][B] : 0)
            + (g&&b ? low[R][g-1][b-1] : 0)
            + (b&&r ? low[r-1][G][b-1] : 0)
            - (r&&g&&b ? low[r-1][g-1][b-1] : 0);
   }

   int cnt(int maxR, int maxG, int maxB,
      int r, int R, int g, int G, int b, int B) {
      r = max(0, min<int>(maxR-1, r));
      R = max(0, min<int>(maxR-1, R));
      g = max(0, min<int>(maxG-1, g));
      G = max(0, min<int>(maxG-1, G));
      b = max(0, min<int>(maxB-1, b));
      B = max(0, min<int>(maxB-1, B));
      return (R-r+1)*(G-g+1)*(B-b+1);
   }
};
トラックバック - http://topcoder.g.hatena.ne.jp/cafelier/20120411

2011-07-10

TCO11 R3

| 04:42 | はてなブックマーク -  TCO11 R3 - cafelier@SRM

  • oxx でギリギリ通過。500は凡ミス。1000は境界条件2個ほど間違えてた。
  • 以下清書した物

250

int gcd(int x, int y)
{
   while(x)
      swap(x, y%=x);
   return y;
}

int lcm(int x, int y)
{
   return x/gcd(x,y)*y;
}

class ArtShift { public:
   int maxShifts(string sequence) 
   {
      int B=0, W=0;
      for(int i=0; i<sequence.size(); ++i)
         (sequence[i]=='B' ? B : W)++;
      memo.assign(31*31, set<int>());
      for(int b=0; b<=B; ++b) memo[b*31+0].insert(1);
      for(int w=0; w<=W; ++w) memo[0*31+w].insert(1);
      return *rec(B,W).rbegin();
   }

   vector< set<int> > memo;
   const set<int>& rec(int B, int W)
   {
      set<int>& result = memo[B*31+W];
      if( !result.empty() )
         return result;

      result.insert(B+W);
      for(int b=0; b+b<=B; ++b)
      for(int w=!b; w<=W; ++w) {
         const set<int>& x = rec(b,w);
         const set<int>& y = rec(B-b,W-w);
         for(set<int>::const_iterator it=x.begin(); it!=x.end(); ++it)
         for(set<int>::const_iterator jt=y.begin(); jt!=y.end(); ++jt)
            result.insert(lcm(*it,*jt));
      }
      return result;
   }
};
  • 黒B個白W個で作れる周期を全部setで計算、というDP
  • 周期はせいぜい因数分解したら和が30になる数のパターン数くらいしかないはずなのでそんな多くないはず
  • 実際はもっと素直に全探索でよかったらしい

500

class PrefixFreeSuperset { public:
   long long minSumLength(vector <string> cur, long long k) 
   {
      map<int,LL> open; {
         string me("");
         rec(me, cur, open);
      }

      LL totalLen = 0;
      for(int i=0; i<cur.size(); ++i)
         totalLen += cur[i].size();
      k -= cur.size();

      while(k) {
         if( open.empty() )
            return -1;
         map<int,LL>::iterator it = open.begin(); 
         int lll = it->first;
         LL  ccc = it->second;
         open.erase(it);

         if( k <= ccc ) {
            totalLen += lll*k;
            k         = 0;
         }
         else if( k <= ccc + open[lll+1] ) {
            totalLen += lll*ccc;
            k        -= ccc;
         }
         else if( k <= ccc*2 + open[lll+1] ) {
            LL div = k - (ccc+open[lll+1]);
            open[lll+1] += div*2;
            totalLen += (ccc-div)*lll;
            k        -= (ccc-div);
         }
         else
            open[lll+1] += ccc*2;
      }
      return totalLen;
   }

   void rec(string& me, const vector<string>& prefix, map<int,LL>& open)
   {
      bool iamprefix = false;
      for(int i=0; i<prefix.size(); ++i)
         if( me == prefix[i] )
            return;
         else if( is_prefix(me, prefix[i]) )
            iamprefix = true;
      if( iamprefix )
      {
         me += '0';
         rec(me, prefix, open);
         me.resize(me.size()-1);
         me += '1';
         rec(me, prefix, open);
         me.resize(me.size()-1);
      }
      else
      {
         open[me.size()] ++;
      }
   }

   bool is_prefix(const string& s, const string& t)
   {
      return s.size()<=t.size() && s==t.substr(0,s.size());
   }
};
  • 二分木を探索していって先が空いているノードの深さをとりあえず数える
  • あとは浅いところだけで足りそうならそれで、
  • 足りなかったら浅いところは2分割して使う
  • の繰り返し

1000

template<typename T>
struct DP3x
{
   int N1, N2, N3;
   vector<T> data;
   DP3x(int, int N2, int N3, const T& t = T())
      : N1(2), N2(N2), N3(N3), data(N1*N2*N3, t) { assert(data.size()*sizeof(T) < (1<<26)); }
   T& operator()(int i1, int i2, int i3)
      { i1&=1; return data[ ((i1*N2)+i2)*N3+i3 ]; }
};

static const int MODVAL = 1000000007;

class RowOfColors { public:
   int countWays(int w, int h, int k) 
   {
      DP3x<LL> dp(w+1, h+1, k+1);
      for(int i=w; i>=0; --i)
      for(int stack=0; stack<=h; ++stack)
      for(int used =0; used <=k; ++used)
         if( i == w )
            dp(i,stack,used) = (stack==1 && used==k ? 1 : 0);
         else {
            LL cnt = 0;
            if(stack+1<=h && used+1<=k) // push new color
               cnt += dp(i+1,stack+1,used+1);
            if(stack) // continue the same color
               cnt += dp(i+1,stack,used);
            if(stack && used+1<=k) // replace top
               cnt += dp(i+1,stack,used+1);
            if(stack>=2) // pop
               cnt += dp(i+1,stack-1,used);
            dp(i,stack,used) = cnt % MODVAL;
         }
      LL v = dp(0,0,0);
      for(int i=1; i<=k; ++i)
         v = (v*i) % MODVAL;
      return int(v);
   }
};
  • こんな感じに
RGR
RRR

RGBGRYCYR
RGGGRYYYR
RRRRRRRRR
  • 高さhあればh段のネストまでできるので、
  • という感じで(何段ネスト,何色使った,今何桁目まで決めた)をキーにDP
トラックバック - http://topcoder.g.hatena.ne.jp/cafelier/20110710

2011-06-12

SRM509 500

| 02:06 | はてなブックマーク -  SRM509 500 - cafelier@SRM

場合分け抹殺計画。

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

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"的な左右の分類を消して、"文字無しの左と元々の右を合わせる"というように、"合わせる"コストを計算しておく
    • これで、どの文字を経由するとか左右のどっちを変えるとかの考慮が再帰と分離できる

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

トラックバック - http://topcoder.g.hatena.ne.jp/cafelier/20110612

presented by cafelier/k.inaba under CC0