SRM 638 Div2 Medium NarrowPassage2Easy

問題

SRM 638 - TopCoder Wiki

狼が狭い路地に一列に並んでいる. 各狼のサイズがsize[i]で与えられていて, 隣接する狼のサイズの和がmaxSizeSum以下なら,入れ替わることが出来る. 狼の並び方の異なり数を答える問題. また,サイズが同じでも狼同士も区別する事に注意.

解答

  • 狼の数が6!なのですべての並びを考える.
  • もちろん,前の状態がわからないと次の状態が求められないので,全ての状態を保持しておいて, 一度計算した状態は2度計算しないようにする.

解説を見ると,提出率が悪いようなのだがなぜだろう? 問題サイズも小さいし,単純な部類だと思う.

class NarrowPassage2Easy
{
public:
  map<vector<int>, bool> memo;
  int maxSizeSum;
  vector<int> size;
  int calc(vector<int> & id) {
    auto itr = memo.find(id);
    if (itr != memo.end()) return 0;
    memo[id] = true;
    int res = 1;
    for (int i = 1; i < size.size(); i++) {
      if ((size[id[i-1]] + size[id[i]]) <= maxSizeSum) {
        int tmp = id[i-1];
        id[i-1] = id[i];
        id[i] = tmp;
        res += calc(id);
        id[i] = id[i-1];
        id[i-1] = tmp;
      }
    }
    return res;
  }
  int count(vector <int> size, int maxSizeSum)
    {
      this->maxSizeSum = maxSizeSum;
      this->size = size;
      vector<int> id;
      for(int i = 0; i < size.size();i++)id.push_back(i);
      return calc(id);
    }
};