Hatena::Grouptopcoder

agwの日記 RSSフィード

 | 

2013-05-17SRM 340 Div II

ProblemsToSolve

14:59 |  ProblemsToSolve - agwの日記 を含むブックマーク はてなブックマーク -  ProblemsToSolve - agwの日記  ProblemsToSolve - agwの日記 のブックマークコメント

http://community.topcoder.com/stat?c=problem_statement&pm=7504&rd=10664

  • DP強化週間だけに、まずDPでの実装を考えた
    • 以下のようなDPテーブルを考えた
    • DPの計算量とメモリ量は、O(N3)
dp[i番目][i番目の頂点までの最小の値][i番目の頂点までの最大の値] = 経由した頂点数
  • 制約は以下

f:id:agw:20130516221444p:image

  • 概算すると、50 × 103 × 103 = 50 × 106 = 5 × 107
    • DPテーブルにはintを用いたい
    • SRMでのメモリ制限は64Mバイトである。intが4バイトであるので、16M要素 = 1.6 × 107要素が上限
    • 納まらない...
  • 双対な関係のDPを用いるのではないか?
    • 自分の実力では思いつかない...
  • 仕方がないのでDFSで考えてみる
    • 関数プロトタイプは以下とした
dfs(i番目, i番目の頂点までの最小の値, i番目の頂点までの最大の値) -> 経由した頂点数を返す
  • これもO(N3)だ
    • だが、(i番目の頂点までの最小の値, i番目の頂点までの最大の値)の組み合わせは高々50 × 50 = 2,500通りであるはず
    • (i番目, i番目の頂点までの最小の値, i番目の頂点までの最大の値)としても、その組み合わせ数は高々50 × 50 × 50 = 125,000 = 1.25 × 105
    • メモ化で十分間に合うはず
  • メモ化再帰で実装を開始した
    • なんだかんだで20分ほどかかってしまったが、テストも通ったので投稿した
  • システムテストを落とす。TLEであった
    • メモ化の実装を間違えていた
    • dfs関数の最後を「return r;」としていた orz

以下は訂正した実装(システムテストを通る)。

class ProblemsToSolve {
public:
  int minNumber(std::vector<int> pleasantness, int variety) {
    pleasantness_ = pleasantness;
    variety_      = variety;

    size_         = pleasantness.size();

    memo_.clear();

    return std::min(std::min(dfs(1, pleasantness[0], pleasantness[0]) + 1,
                             dfs(2, pleasantness[0], pleasantness[0]) + 1),
                    size_);
  };

private:
  int dfs(int i, int j, int k) {
    int key = ((i * 1024 + j) * 1024) + k;

    if (memo_.count(key))
      return memo_[key];

    j = std::min(pleasantness_[i], j);
    k = std::max(pleasantness_[i], k);

    if (std::abs(j - k) >= variety_)
      return memo_[key] = 1;

    int r = INF;

    if (i + 1 < size_)
      r = std::min(dfs(i + 1, j, k) + 1, r);

    if (i + 2 < size_)
      r = std::min(dfs(i + 2, j, k) + 1, r);

    return memo_[key] = r;
  };

private:
  std::vector<int> pleasantness_;
  int              variety_;

  int size_;

  std::map<int, int> memo_;
};

  • 信じられないくらい簡潔な実装が掲載されていた
  • {|pi - pj| | i < j}が与えられた閾値よりも大きいペアを先に全探索している
  • 類似問題でもあるし、しっかり考察することにした

  • じっくり読んでいない今の段階で、エディトリアルのアイデアを実装してみる
  • まずは全探索について考えてみる
    • 以下を満たすiとjのペアを考える

f:id:agw:20130516221445p:image

  • これらのペアを含む経路は条件を必ず満たす
    • i < jとしているので、頂点0、i、jを通ればやはり条件を満たす
    • 条件を満たす経路の中で訪れる頂点の数が最小のものを探せばいい
  • 図示しよう

f:id:agw:20130516221448p:image

  • 閾値を6とすると、2と8の頂点を通る必要がある

f:id:agw:20130516221449p:image

  • 任意の頂点iとjの間の最短距離をδ(i, j)とする
    • 頂点4と2、8を通る最短経路は以下のように表すことができる

f:id:agw:20130516221455p:image

  • 任意の頂点のペアの最短経路の距離が分かれば、これを計算できる

f:id:agw:20130516224555p:image

  • ならば、Warshall-Folyd法だ
  • そのために、隣接行列を用意する。アスタリスクは接続されていないことを表し、実際の行列での値は無限大だ

f:id:agw:20130516221453p:image


Warshall-Floyd法を用いた実装(システムテストを通る)。

#define INF 1000000000


class ProblemsToSolve {
public:
  int minNumber(std::vector<int> pleasantness, int variety) {
    int size = pleasantness.size();

    std::vector<std::vector<bool> > valid(size, std::vector<bool>(size));

    for (int i = 0; i < size; i ++)
      for (int j = i + 1; j < size; j ++)
        valid[i][j] = (std::abs(pleasantness[i] - pleasantness[j]) >= variety);

    std::vector<std::vector<int> > m(size, std::vector<int>(size, INF));

    for (int i = 0; i < size; i ++) {
      if (i + 1 < size)
        m[i][i+1] = 1;

      if (i + 2 < size)
        m[i][i+2] = 1;
    }

    for (int k = 0; k < size; k ++)
      for (int i = 0; i < size; i ++)
        for (int j = 0; j < size; j ++)
          m[i][j] = std::min(m[i][j], m[i][k] + m[k][j]);

    m[0][0] = 0;

    int cp = INF;

    for (int i = 0; i < size; i ++)
      for (int j = 0; j < size; j ++)
        if (valid[i][j])
          cp = std::min(1 + m[0][i] + m[i][j], cp);

    return std::min(cp, size);
  };
};
  • Warshall-Floydを適用した結果、隣接行列は以下のようになる

f:id:agw:20130516221456p:image

  • 経路の辺の数がはδ(0, 2) + δ(2, 5)を計算すればいい(1 + 2 = 3)
  • 辺の数が3であるため、頂点の数は3 + 1 = 4
  • 例外があった
    • 通らなければならない初め頂点が0のとき、最短経路はδ(0, 0) + δ(0, j)として計算する
    • しかしδ(0, 0)は無限大が収められているので、誤動作する
    • 便宜上δ(0, 0)を0としておけばこれを実現できる

f:id:agw:20130516221457p:image

  • グラフの問題としても解くことが出来た

  • 頂点iからjまでにn個の頂点がある場合、最短経路の辺の数は以下の式で計算出来る

f:id:agw:20130516221447p:image

  • 頂点0からiのグラフを見てみよう。この場合nは3。確かにそうなっている

f:id:agw:20130516221450p:image

  • 頂点iからjへのグラフには最短経路が2種類ある。nは4。最短経路は双方ともに2だ

f:id:agw:20130516221451p:image

f:id:agw:20130516221452p:image

  • これを実装してみよう

エディトリアルを熟読してからの実装(システムテストを通る)。

class ProblemsToSolve {
public:
  int minNumber(std::vector<int> pleasantness, int variety) {
    int size = pleasantness.size();

    int cp = size;

    for (int i = 0; i < size; i ++)
      for (int j = i + 1; j < size; j ++)
        if (std::abs(pleasantness[i] - pleasantness[j]) >= variety)
          cp = std::min(1 + (i + 1) / 2 + (j - i + 1) / 2, cp);

    return cp;
  };
};

まとめ

  • この問題は本当に楽しかった
  • 巨大なDPテーブルを用意する方法しか思いつかなかったので実装できなかったが、DPについて考察した
  • メモ化再帰で解くことができた。また、DPでのO(N3)とメモ化再帰でのO(N3)の双方の見積もりをきちんと取ることが出来た
  • グラフ理論について学ぶことが出来た
    • グラフの辺の数を算出するのに、経路の頂点数を使うとシンプルに計算できることは意外と多そうだ
  • 恐らく上級者ならば双対な関係のDPを思いつくのではないだろうか
    • ご存知の方は是非ご教授ください
 |