cafelier@SRM

SRM445 1000

あとで | 11:53 |

6個にグループ分けでメモ化探索という方針はあってた

static const LL MODVAL = 1234567891;

class TheEncryptionDivOne { public:
  map<pair< pair<pair<int,int>, int>, pair<pair<int,int>, int> >, LL> memo;

  int count(string msg, string encMsg) 
  {
    // accumulate unused characters
    char cs[] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
    set<char> ori(cs+0, cs+52), enc(cs+0, cs+52);
    for(int i=0; i<msg.size(); ++i)
      ori.erase(msg[i]), enc.erase(encMsg[i]);

    // obviously-invalid cases
    for(int i=0; i<msg.size(); ++i)
      if( toupper(msg[i]) == toupper(encMsg[i]) )
        return 0;
    if( ori.size() != enc.size() )
      return 0;

    // count
    int t0x=0, tx0=0, t11=0, t12=0, t21=0, t22=0;
    for(char c='a'; c<='z'; ++c) {
      int oc = ori.count(c)+ori.count(c+'A'-'a');
      int ec = enc.count(c)+enc.count(c+'A'-'a');
      if( oc == 0 )      t0x += ec;
      else if( ec == 0 ) tx0 += oc;
      else if(oc==1 && ec==1) t11 ++;
      else if(oc==1 && ec==2) t12 ++;
      else if(oc==2 && ec==1) t21 ++;
      else if(oc==2 && ec==2) t22 ++;
    }
    return rec(tx0, t0x, t11, t12, t21, t22);
  }

  LL rec(int tx0, int t0x, int t11, int t12, int t21, int t22)
  {
    pair< pair<pair<int,int>, int>, pair<pair<int,int>, int> >
      key(make_pair(make_pair(tx0,t0x), t11), make_pair(make_pair(t12,t21), t22));
    if(memo.count(key))
      return memo[key];

    if( t11 )
    {
      LL val = 0;
      if( t0x ) val += t0x *     rec(tx0,   t0x+1-1, t11-1,   t12,   t21,   t22);
      if(t11>1) val += (t11-1) * rec(tx0+1, t0x+1,   t11-1-1, t12,   t21,   t22);
      if( t12 ) val += t12 * 2 * rec(tx0,   t0x+1,   t11-1+1, t12-1, t21,   t22);
      if( t21 ) val += t21 *     rec(tx0+2, t0x+1,   t11-1,   t12,   t21-1, t22);
      if( t22 ) val += t22 * 2 * rec(tx0,   t0x+1,   t11-1,   t12,   t21+1, t22-1);
      return memo[key] = val%MODVAL;
    }
    if( t12 )
    {
      LL val = 0;
      if( t0x ) val += t0x *     rec(tx0,   t0x+2-1, t11,     t12-1,   t21,   t22);
      if( t11 ) val += t11 *     rec(tx0+1, t0x+2,   t11-1,   t12-1,   t21,   t22);
      if(t12>1) val += (t12-1)*2*rec(tx0,   t0x+2,   t11+1,   t12-1-1, t21,   t22);
      if( t21 ) val += t21 *     rec(tx0+2, t0x+2,   t11,     t12-1,   t21-1, t22);
      if( t22 ) val += t22 * 2 * rec(tx0,   t0x+2,   t11,     t12-1,   t21+1, t22-1);
      return memo[key] = val%MODVAL;
    }
    if( t21 )
    {
      LL val = 0;
      if( t0x ) val += t0x *     rec(tx0,   t0x-1, t11+1,   t12,   t21-1,   t22);
      if( t11 ) val += t11 *     rec(tx0+1, t0x,   t11+1-1, t12,   t21-1,   t22);
      if( t12 ) val += t12 * 2 * rec(tx0,   t0x,   t11+1+1, t12-1, t21-1,   t22);
      if(t21>1) val += (t21-1) * rec(tx0+2, t0x,   t11+1,   t12,   t21-1-1, t22);
      if( t22 ) val += t22 * 2 * rec(tx0,   t0x,   t11+1,   t12,   t21-1+1, t22-1);
      return memo[key] = val%MODVAL;
    }
    if( t22 )
    {
      LL val = 0;
      if( t0x ) val += t0x *     rec(tx0,   t0x-1, t11,   t12+1,   t21,   t22-1);
      if( t11 ) val += t11 *     rec(tx0+1, t0x,   t11-1, t12+1,   t21,   t22-1);
      if( t12 ) val += t12 * 2 * rec(tx0,   t0x,   t11+1, t12+1-1, t21,   t22-1);
      if( t21 ) val += t21     * rec(tx0+2, t0x,   t11,   t12+1,   t21-1, t22-1);
      if(t22>1) val += (t22-1)*2*rec(tx0,   t0x,   t11,   t12+1,   t21+1, t22-1-1);
      return memo[key] = val%MODVAL;
    }
    LL f=1;
    for(LL n=1; n<=tx0; ++n)
      f = (f*n)%MODVAL;
    return memo[key] = f;
  }
};

あってたけど、この腐った手作業条件分岐を時間内に正しくデバッグし通せる見込みは全くないなあ。どんだけ時間が切羽詰まっててもちゃんとしたコードを書く習慣を付けなければ…

改訂版

static const LL MODVAL = 1234567891;

class TheEncryptionDivOne { public:
   map<vector<int>, LL> memo;

   int count(string msg, string encMsg) 
   {
      // 平文側(ori)、暗号文側(enc) でそれぞれ
      // 使われてない文字 = これから割り当て決めなきゃいけない文字 を集める
      char cs[] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
      set<char> ori(cs+0, cs+52), enc(cs+0, cs+52);
      for(int i=0; i<msg.size(); ++i)
         ori.erase(msg[i]), enc.erase(encMsg[i]);

      // 探索の前にあきらかにダメなケースをはじく
      for(int i=0; i<msg.size(); ++i)
         if( toupper(msg[i]) == toupper(encMsg[i]) )
            return 0;
      if( ori.size() != enc.size() )
         return 0;

      // メモ化探索
      // - 9元ベクトルsが状態。
      // - sは、アルファベット(A-Z)26種を9パターンに分けて持っている
      // - s[a*3+b] == 平文側にa個、暗号文側にb個、未割当の字が残ってるアルファベットの総数
      //    - たとえば入力が "a"->"W" なら初期状態は
      //        (0,0,0,  0,0,1, 0,1,24) 
      //      となる: 1個-2個 のもの (A,aA) が1種、2個-1個の (wW,w)が1種、その他24種
      vector<int> s(9);
      for(char c='a'; c<='z'; ++c)
      {
         int oc = ori.count(c)+ori.count(c+'A'-'a');
         int ec = enc.count(c)+enc.count(c+'A'-'a');
         s[oc*3+ec] ++;
      }
      return rec(s);
   }

   LL rec( const vector<int>& s )
   {
      if( memo.count(s) )
         return memo[s];

      for(int a=1; a<=2; ++a)
      for(int b=0; b<=2; ++b) if( s[a*3+b] ) // 平文側の未割当のものを順に割り当て
      {
         LL val = 0;
         for(int c=0; c<=2; ++c)
         for(int d=1; d<=2; ++d) if( s[c*3+d] ) // 暗号文側の未割当のものを全通り選ぶ
         {
            vector<int> t = s;
            t[a*3+b] --;
            if( LL choices = t[c*3+d]*d )
            {
               t[(a-1)*3+b] ++;
               t[c*3+d]     --;
               t[c*3+(d-1)] ++;
               val += choices * rec(t); // 再帰
            }
         }
         return memo[s] = val%MODVAL;
      }
      return 1;
   }
};