Hatena::Grouptopcoder

cou929のTopCoder日記

2009-12-05

SRM448 div2 (過去問)

22:13

Hard - TheCardLineDivTwo

最大16枚のトランプが与えられるので, 数字か色が同じものどおしを隣り合わせながら並べる. 並べ方は何通りあるか. 答えは mod 1234567891 を返す.

一枚のカードをノード, 隣り合うことのできるカード同士をエッジとしたグラフを探索すればいいなじゃないかと考え実装しましたが, 大きいケースでTLEになります. 確かに最悪のケースは, 16枚すべてが隣り合うことが出来る場合で, 16! = 20922789888000 通りの並べ方ができてしまうので, とても間に合いません. 基本である計算量の見積ができていない証拠です.

Forumをみてみると, 自分の実装にあとメモ化を追加すれば間に合いそうだということが分かりました. そこで, 探索はqueueとwhileで行っていたのでこれを再起関数で行うよう変更し, メモを追加, 無事に高速化に成功しました.

また, Editorialでdpでの解が紹介されていました. あとで目を通しておこうと思います.

TopCoder - Error


class TheCardLineDivTwo {
public:
  int size;
  long long memo[16][1<<16];
  int graph[16][16];

  long long r(int pos, int flg) {
    long long ret = 0;
    if (memo[pos][flg] != -1)
      return memo[pos][flg];

    if (flg == (1 << size)-1)
      return 1;

    for (int i=0; i<size; i++)
      if (graph[pos][i] == 1 && !(flg & (1 << i))) {
        int next_flg = (flg | (1 << i));
        ret += r(i, next_flg);
      }

    return memo[pos][flg] = ret % 1234567891;
  }

  int count(vector <string> cards) {
    int ret = 0;
    size = cards.size();
    memset(memo, -1, sizeof(memo));
    memset(graph, 0, sizeof(graph));

    for (int i=0; i<cards.size(); i++)
      if (cards[i][1] == 'S' || cards[i][1] == 'C')
        cards[i][1] = 'B';
      else
        cards[i][1] = 'R';

    for (int i=0; i<cards.size(); i++)
      for (int j=0; j<cards.size(); j++)
        if (i != j && (cards[i][0] == cards[j][0] || cards[i][1] == cards[j][1]))
          graph[i][j] = 1;

    for (int i=0; i<cards.size(); i++)
      ret = (ret + r(i, (1 << i))) % 1234567891;

    return ret;
  }
};