Hatena::Grouptopcoder

agwの日記 RSSフィード

 | 

2013-02-27SRM 571 Div I

MagicMolecule

17:28 |  MagicMolecule - agwの日記 を含むブックマーク はてなブックマーク -  MagicMolecule - agwの日記  MagicMolecule - agwの日記 のブックマークコメント

30分ほど方向性を誤った実装を行い、未提出に終わった。

  • TLで「深さ優先探索で解ける」、「枝刈りが必要」...等の情報が流れてくる
  • @chokudaiさんの実装をコードリーディングする
    • ビット演算をうまく使っており、読みどころ満載であった
  • なんとなく理解できていない部分もあったが、参考にして自分で実装をしようと考えた
  • まず作図をした。探索木はすぐ大きくなってしまう。6つの頂点を持つ比較的小さいグラフを基調に考えることにした
  • 以下はO(26)の探索木だ

f:id:agw:20130226221530p:image

  • それぞれの頂点では頂点を選ぶ、頂点を選ばないという2つの選択肢がある。頂点を選んだ場合は左のパスへ、頂点を選ばなかった場合は右のパスへ行くものとする。図では矢印で表してみよう

f:id:agw:20130226221531p:image

  • この探索木は完全グラフの探索木だ

f:id:agw:20130226221623p:image

  • 枝刈りを考えてみる。まず以下のように頂点0と頂点5が接続していないグラフで考えてみよう

f:id:agw:20130226221624p:image

  • 答えは以下の2つの何れかになることは容易に予想がつく
    • このように完全グラフとなる部分グラフをクリークというそうだ

f:id:agw:20130226221625p:image

  • 例えば頂点0を選んだ場合、頂点5は選べなくなる。また、頂点0を選ばなかった場合は頂点5を選べる(もちろん、選ばないことも出来る)。これを探索木に反映すると以下のようになる

f:id:agw:20130226221532p:image

  • 次に頂点1と接続している頂点2、3、4を外してみよう

f:id:agw:20130226221626p:image

  • このときの探索木は以下となる。頂点1の左側の部分木では頂点2、3、4が選べないことに注意しよう

f:id:agw:20130226221533p:image

  • さてこの問題ではクリークの頂点数に制限が儲けられている

f:id:agw:20130226221627p:image

  • 変形すると

f:id:agw:20130226221628p:image

  • nとmが整数であることを考えると

f:id:agw:20130226221629p:image

  • このグラフの場合、nは6であるので

f:id:agw:20130226221630p:image

  • mは[4, 6]となる

f:id:agw:20130226221631p:image

  • これを言い換えると、頂点を選ばない選択が行える上限は2回である
  • 探索木で言えば、右側のパスを選べるのは2回までということになる

f:id:agw:20130226221534p:image

  • では例2を考えてみよう。頂点5に接続されている辺がさらに減っている

f:id:agw:20130226221632p:image

  • 頂点の和が最大となるクリークは頂点0、2、3、4からなる部分グラフだ(合計は332だ)

f:id:agw:20130226221633p:image

  • 探索木での経路は以下となる。頂点0からパスを追うと、以下のようになる
    • 頂点0を選び
    • 頂点1を選ばず
    • 頂点2を選び
    • 頂点3を選び
    • 頂点4を選び
    • 頂点5は選ばない

f:id:agw:20130226221535p:image

  • なるほど、これは枝刈りの効果がありそうだ
  • 早速実装してみよう

以下はシステムテストを通らない実装。

class MagicMolecule {
public:
  int maxMagicPower(std::vector<int> magicPower, std::vector<std::string> magicBond) {
    magicPower_ = magicPower;

    n_ = magicPower.size();

    m_ = (2 * n_ + 2) / 3;

    adj_.assign(n_, 0);

    for (int i = 0; i < n_; i ++)
      for (int j = 0; j < n_; j ++)
        if (i == j || magicBond[i][j] == 'Y')
          adj_[i] |= 1LL << j;

    return dfs(0, (1LL << n_) - 1);
  };

private:
  int dfs(int i, long long bits) {
    if (i == n_)
      return -1;

    if (bitcount(bits) < m_)
      return -1;

    if (cliques_are_valid(bits))
      return sum(bits);

    if (bits & (1LL << i)) {
      return std::max(dfs(i + 1, bits & adj_[i]),
                      dfs(i + 1, bits - (1LL << i)));
    }
    else {
      return dfs(i + 1, bits);
    }
  };

  int bitcount(long long bits) const {
    int c = 0;

    for (int i = 0; i < n_; i ++)
      if (bits & (1LL << i))
        c ++;

    return c;
  };

  int sum(long long bits) const {
    int s = 0;

    for (int i = 0; i < n_; i ++)
      if (bits & (1LL << i))
        s += magicPower_[i];

    return s;
  };

  bool cliques_are_valid(long long bits) const {
    for (int i = 0; i < n_; i ++)
      if (bits & (1LL << i))
        if ((bits & adj_[i]) != bits)
          return false;

    return true;
  };

private:
  std::vector<int> magicPower_;

  std::vector<long long> adj_;

  int n_;
  int m_;
};
  • システムテストを試す。TLEしてしまった(メモ化をしても駄目だった)
  • うーん、全く分からなくなってしまった

  • 読んだ直後は今ひとつ理解できなかった(おにぎりさんの実装は今だに理解できていない...)

f:id:agw:20130227165117p:image

  • あー、なるほど...こういうことか...
  • 全ての頂点を選択した状態から、グラフの接続情報を元に、選ぶ、選ばないを繰り返す
  • 選ばない回数の上限はn - m
  • つまり、最大でもO(2n - m)の探索木にしかならない。そのため、計算量は

f:id:agw:20130227000840p:image

  • この問題ではnが50を取る。そのときmは16であるので、計算量は最大でもO(216 × 50)となり、メモ化をしなくても間に合う

f:id:agw:20130227000841p:image

ここまでを元に実装した結果は以下(システムテストをパス)。

class MagicMolecule {
public:
  int maxMagicPower(std::vector<int> magicPower, std::vector<std::string> magicBond) {
    magicPower_ = magicPower;
    
    n_ = magicPower.size();
    
    m_ = (2 * n_ + 2) / 3;

    adj_.assign(n_, 0);

    for (int i = 0; i < n_; i ++)
      for (int j = 0; j < n_; j ++)
        if (i == j || magicBond[i][j] == 'Y')
          adj_[i] |= 1LL << j;

    return dfs(0, (1LL << n_) - 1);
  };

private:
  int dfs(int i, long long bits) {
    if (i == n_)
      return -1;

    int r = 0;

    if (bitcount(bits) < m_)
      return r = -1;

    for (int j = i; j < n_; j ++)
      if (bits & (1LL << j))
        if ((bits & adj_[j]) != bits)
          return r = std::max(dfs(j + 1, bits & adj_[j]),
                              dfs(j + 1, bits - (1LL << j)));

    return sum(bits);
  };

  int bitcount(long long bits) const {
    int c = 0;

    for (int i = 0; i < n_; i ++)
      if (bits & (1LL << i))
        c ++;

    return c;
  };

  int sum(long long bits) const {
    int s = 0;

    for (int i = 0; i < n_; i ++)
      if (bits & (1LL << i))
        s += magicPower_[i];

    return s;
  };
  
private:
  std::vector<int> magicPower_;

  std::vector<long long> adj_;

  int n_;
  int m_;
};
  • 想定解は以下であるらしい

  • Easy、Medium共に解法が多岐に渡る面白い問題だなぁと関心した
 |