Hatena::Grouptopcoder

agwの日記 RSSフィード

 | 

2013-02-27SRM 571 Div I

SRM 571 Div I

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

http://community.topcoder.com/stat?c=round_overview&er=5&rd=15491

250に21分。チャレンジ1回成功。220.76点。レートは1335から1440へ。Room 39

Problem Status Points
250FoxAndMp3 System Test Passed170.76
500MagicMoleculeOpened 0.00
1000CandyOnDisk Unopened
  • 250に21分
    • 提出した実装を検証するのに15分ほど時間を費やした
  • 500は見当違いの方向性を元に実装し、徒労に終わった
  • チャレンジに1回成功した
  • 今回は怪しい実装を行ってしまった。レートは上がったが、目標は不達成
  • 次回はTCOだ。TCOはペース配分が分からないが、Easyを確実に通すようにしたい

FoxAndMp3

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

http://community.topcoder.com/stat?c=problem_statement&pm=12436&rd=15491

21分。

  • 1からnまでに収まる、1、10、100、...からの50個ずつの数値を文字列として用意。整列して先頭の50個の要素を得る戦略とした

以下は提出した実装(システムテストをパス)。

class FoxAndMp3 {
public:
  std::vector<std::string> playList(int n) {
    std::set<int> set;

    for (int i = 1; i <= n; i *= 10)
      for (int j = 0; j < 50; j ++)
        if (i + j <= n)
          set.insert(i + j);

    std::vector<std::string> filenames;

    EACH (it, set)
      filenames.push_back(filename(*it));

    std::sort(ALL(filenames));

    if (filenames.size() > 50)
      filenames.resize(50);

    return filenames;
  };

private:
  std::string filename(int i) const {
    std::ostringstream os;
    // XXX
    os << i << ".mp3";

    return os.str();
  };
};
  • std::ostringstreamを後で確認しようと思いコメントを入れていたが、記入していたことすら忘れていて恥ずかしい
  • 制約から、nの取りうる範囲は[1, 109]であった

f:id:agw:20130226221434p:image

  • intで宣言していたiがオーバーフローするであろうことに提出後気付いたが、109 × 10は1,410,065,408となり、命拾いした
  • SRM直後のTLやコードリーディングで目から鱗の発想を幾つか見つけた

  • すごい。無駄なくまとめている

これを参考にした実装は以下(システムテスト済)。

class FoxAndMp3 {
public:
  std::vector<std::string> playList(int n) {
    std::vector<std::string> filenames;

    for (int i = 1; i < 100; i ++)
      if (i <= n)
        filenames.push_back(filename(i));

    for (long long i = 100; i <= n; i *= 10)
      for (int j = 0; j < 50; j ++)
        if (i + j <= n)
          filenames.push_back(filename(i + j));

    std::sort(ALL(filenames));

    if (filenames.size() > 50)
      filenames.resize(50);

    return filenames;
  };

private:
  std::string filename(int i) const {
    std::ostringstream os;

    os << i << ".mp3";

    return os.str();
  };
};
  • コードリーディングでは内側の反復の範囲を工夫した実装を見つけた
  • iから始まる数値を50個、ただし10iまでのものを追加するものであった

f:id:agw:20130226221435p:image

これを参考にした実装は以下(システムテスト済)。

class FoxAndMp3 {
public:
  std::vector<std::string> playList(int n) {
    std::vector<std::string> filenames;

    for (long long i = 1; i <= n; i *= 10)
      for (int j = i; j < std::min(i + 50, i * 10); j ++)
        if (j <= n)
          filenames.push_back(filename(j));

    std::sort(ALL(filenames));

    if (filenames.size() > 50)
      filenames.resize(50);

    return filenames;
  };

private:
  std::string filename(int i) const {
    std::ostringstream os;

    os << i << ".mp3";

    return os.str();
  };
};
  • すっきりしている。この実装が一番好きだ
  • これ以外にも深さ優先探索を使った実装や、ジェネレータを使った実装があったようだ
  • std::vector::resize()を初めて使った。嬉しい

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共に解法が多岐に渡る面白い問題だなぁと関心した
 |