cafelier@SRM

deque で DP

21:42 |

Codeforces 129 Div1 D の本質的な部分は、こんな問題でした。（実際にはこれを左右から計算して掛け算などする。）

'B' か 'W' か 'X' の並んだ長さ100000以下の文字列 S と、1以上の整数 K が与えられます。S に含まれる全ての 'X' を 'B' か 'W' に置き換えたときに "BBB....BB" (BのK連続) が含まれるようにする置き換え方は何通りあるか、mod 1,000,000,007 で求めてください。

ただし、Sの長さが1000以下のケースを全て解けたら部分点300点が得られる、という場合、部分点狙いの O( |S|・K ) の DP は比較的簡単です。

// mod 1000000007 は心の目で補うこと。
// 動かしてないので細かいとこは間違ってるかも。

int solve1(const string& S, int K)
{
   // done[i]    = 「S[0..i) の範囲でK連続がもう作れた」パターンの数
   // mada[i]    = 「S[0..i) の範囲でK連続が一度も作れてない」パターンの数
   // kwsk[i][x] = mada[i] のうち「S[0..i) の後半はBがx連続」のパターンの数

   vector<int>           done(S.size()+1);
   vector<int>           mada(S.size()+1);
   vector< vector<int> > kwsk(S.size()+1, vector<int>(K));

   done[0] = 0;
   mada[0] = 1;
   kwsk[0][0] = 1;
   for(int x=1; x<K; ++x)
      kwsk[0][x] = 0;

   for(int i=0; i<S.size(); ++i)
   {
      if( S[i] == 'W' )
      {
         done[i+1] = done[i];
         mada[i+1] = mada[i];
         kwsk[i+1][0] = mada[i];
         for(int x=1; x<K; ++x)
            kwsk[i+1][x] = 0;
      }
      else if( S[i] == 'B' )
      {
         done[i+1] = done[i] + kwsk[i][K-1];
         mada[i+1] = mada[i] - kwsk[i][K-1];
         kwsk[i+1][0] = 0;
         for(int x=1; x<K; ++x)
            kwsk[i+1][x] = kwsk[i][x-1];
      }
      else // if( S[i] == 'X' )
      {
         done[i+1] = done[i] + (done[i] + kwsk[i][K-1]);
         mada[i+1] = mada[i] + (mada[i] - kwsk[i][K-1]);
         kwsk[i+1][0] = mada[i] + 0;
         for(int x=1; x<K; ++x)
            kwsk[i+1][x] = 0 + kwsk[i][x-1];
      }
   }

   // 答え： S[0..$) で K 連続が作れたパターンの数
   return done[S.size()];
}

で、このDPの重要な特徴は、一番計算の重い部分が「値を一つずらす」

         for(int x=1; x<K; ++x)
            kwsk[i+1][x] = kwsk[i][x-1];

か、「ゼロクリアする」

         for(int x=1; x<K; ++x)
            kwsk[i+1][x] = 0;

だけというところ。正直に vector や配列で一つインデックスをずらしてコピーする代わりに、deque で push_front してやると、O(1) で全要素がずらせます。

int solve2(const string& S, int K)
{
   int done = 0;
   int mada = 1;
   deque<int> kwsk(1, 1);

   for(int i=0; i<S.size(); ++i)
   {
      if( S[i] == 'W' )
      {
         kwsk.assign(1, mada);
      }
      else if( S[i] == 'B' )
      {
         kwsk.push_front(0);
         done = done + (kwsk.size()>K ? kwsk[K] : 0);
         mada = mada - (kwsk.size()>K ? kwsk[K] : 0);
         if( kwsk.size() > K )
            kwsk.pop_back();
      }
      else // if( S[i] == 'X' )
      {
         kwsk.push_front(mada);
         done = done + done + (kwsk.size()>K ? kwsk[K] : 0);
         mada = mada + mada - (kwsk.size()>K ? kwsk[K] : 0);
         if( kwsk.size() > K )
            kwsk.pop_back();
      }
   }

   return done;
}

ゼロクリアの部分も未使用に戻すだけなのでO(1)でできますし、そうじゃなくても、今までに積んだ分の長さしか伸びてないので、ならし計算量で考えればO(1)です。

取り出しが反対側からだけなので、deque じゃなくて queue でもいいですし、概念的にこれをやればいいだけなので、配列をうまくずらしながら使っても同じ事ができます。が、deque (≒ push_front が O(1) の vector) を使っちゃうのが楽かなあと。