Hatena::Grouptopcoder

cafelier@SRM

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

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

 | 

2010-10-06

SRM484 550

| 13:15 | はてなブックマーク -  SRM484 550 - cafelier@SRM

  • だいたいあってた。
    • A[端!a]::=U[端!a] U U U ... U U U U[端!a]
  • これが間違いで
    • A[端!a]::=U[端!a]*
  • こうすべきだった。でないと結局aがくっついて消えちゃう
  • 自分で "端" とかいう微妙な概念を作ってしまってセルフメダパニしてしまった
static const LL MODVAL = 1000000007;

class PuyoPuyo { public:
   int theCount(int L, int N) 
   {
      vector<LL>           A4(N+1), A3(N+1);
      vector< vector<LL> > U(L, vector<LL>(N+1));

      A4[0] = A3[0] = U[L-1][1] = 1;
      for(int n=1; n<=N; ++n) {
         for(int k=L-2; k>=0; --k)
            for(int z=0; n-z-1>=1; z+=L)
               U[k][n] = (U[k][n] + A3[z]*U[k+1][n-z-1]) % MODVAL;
         for(int i=L; i<=n; i+=L)
            A4[n] = (A4[n] + 4*U[0][i]*A4[n-i]) % MODVAL;
         for(int i=L; i<=n; i+=L)
            A3[n] = (A3[n] + 3*U[0][i]*A3[n-i]) % MODVAL;
      }
      return int(A4[N]);
   }
};

文脈自由文法を定義する。簡単のためL=3、ぷよはabcの3色という例で。

  • A =「全消しできる配ぷよ列」
  • U =「最初のぷよが最後まで残るけど結局全消しできる配ぷよ列」
A ::= U*
U ::= a A[端!a] a A[端!a] a | b A[端!b] b A[端!b] b | c A[端!c] c A[端!c] c
A[端!a] ::= U[端!a]*
A[端!b] ::= U[端!b]*
A[端!c] ::= U[端!c]*
U[端!a] ::= b A[端!b] b A[端!b] b | c A[端!c] c A[端!c] c
U[端!b] ::= a A[端!c] a A[端!c] a | a A[端!a] a A[端!a] a
U[端!c] ::= c A[端!a] c A[端!a] c | b A[端!b] b A[端!b] b

これにマッチする長さNの文字列の個数、が求める物。

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

presented by cafelier/k.inaba under CC0