Hatena::Grouptopcoder

cou929のTopCoder日記

2010-05-05

SRM 469 div1 (過去問)

13:08

Medium - TheMoviesLevelTwoDivOne

昨日の復習です.

nodchipさんのエントリをみてなるほどと思い実装. 基本dfsで, 今まで通ったところをビットマスクで表現して配列に保存しておきます. 辞書順に若いものが欲しいので, 若い順に探索してあとから見つかったものは探索を打ち切ります. johnがすべての映画を見られない場合は, dfsの結果が見られる映画だけのベクタになるので, のこりの見られない映画をあとから順に詰め込んでいます.

デフォルトの関数名がfind()なので, std::findとバッティングしていて, 気づくのに少し時間がかかってしまいました. これはなんとかして欲しいです.

下のコードの vector <int> path を探索する再帰関数に毎回わたしていたんですが, これが原因でシステムテストではTLEしました. 変数をグローバルに置くことで対応しました. 一応ローカルでも単に要素数が最大のケースを作って試してはいたんですが, TLEで落ちたケースには気付けませんでした. 単にサイズが最大のインプットを用意するんじゃなくて, その内容も最悪のものを考える必要があるというのが今回の反省点です.

class TheMoviesLevelTwoDivOne {
public:
  bool visited[1 << 20];
  int movieNum;
  vector <int> ret;
  vector <int> length;
  vector <int> scary;
  int n;
  vector <int> path;

  bool canWatch(int level, int index) {
    if (level >= length[index] ||
        (level >= scary[index] && level + 47 >= length[index]))
      return true;
    return false;
  }

  int search(int level) {
    int i;
    int mask = 0;

    for (i=0; i<path.size(); i++)
      mask |= 1 << path[i];

    if (visited[mask])
      return 0;
    visited[mask] = true;

    if (path.size() > movieNum) {
      movieNum = path.size();
      ret = path;
    }

    for (i=0; i<n; i++)
      if (!((1 << i) & mask))
        if (canWatch(level, i)) {
          path.push_back(i);
          search(level - length[i] + 47);
          path.erase(path.end()-1);
        }

    return 0;
  }

  vector <int> find(vector <int> _length, vector <int> _scary) {
    int i;
    memset(visited, false, sizeof(visited));
    movieNum = 0;
    ret.clear();
    length = _length;
    scary = _scary;
    n = length.size();
    path.clear();

    search(74);

    for (i=0; i<n; i++)
      if (std::find(ret.begin(), ret.end(), i) == ret.end())
        ret.push_back(i);

    return ret;
  }
};

nodchipnodchip2010/05/05 15:08「vector <int> path を探索する再帰関数に毎回わたしていた」とは引数に「vector<int> path」を入れていたということでしょうか?この場合、関数の呼び出しの度にvectorの動的なメモリ確保と値のコピーが行われ、かなりの時間がかかってしまうと思います。「vector<int>& path」なら動的なメモリ確保とコピーが行われないはずですので、通るかもしれません。

cou929cou9292010/05/05 18:29はい, おっしゃる通り値渡しで vector <int> path をわたしていました. 確かにメモリ確保&コピーで時間がかかっていたらしく, ここを変えただけでだいぶ速くなりました. 参照渡しでもいけそうですね.