SRM 571 Div I

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

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

	Problem	Status	Points
250	FoxAndMp3	System Test Passed	170.76
500	MagicMolecule	Opened	0.00
1000	CandyOnDisk	Unopened

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

FoxAndMp3

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, 10⁹]であった

intで宣言していたiがオーバーフローするであろうことに提出後気付いたが、10⁹ × 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までのものを追加するものであった

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

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

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

TLで「深さ優先探索で解ける」、「枝刈りが必要」...等の情報が流れてくる

@chokudaiさんの実装をコードリーディングする
- ビット演算をうまく使っており、読みどころ満載であった

なんとなく理解できていない部分もあったが、参考にして自分で実装をしようと考えた

まず作図をした。探索木はすぐ大きくなってしまう。6つの頂点を持つ比較的小さいグラフを基調に考えることにした

以下はO(2⁶)の探索木だ

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

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

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

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

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

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

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

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

変形すると

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

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

mは[4, 6]となる

これを言い換えると、頂点を選ばない選択が行える上限は2回である

探索木で言えば、右側のパスを選べるのは2回までということになる

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

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

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

なるほど、これは枝刈りの効果がありそうだ

早速実装してみよう

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

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してしまった(メモ化をしても駄目だった)

確かにこの実装はナイーブすぎる。計算量はO(2ⁿn)である(指数時間アルゴリズム入門を参考にした)

うーん、全く分からなくなってしまった

おにぎりさんの記事を読む

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

@chokudaiさんの実装で理解していなかったこととおにぎりさんの記事がじわじわと繋がってきたので作図した

あー、なるほど...こういうことか...

全ての頂点を選択した状態から、グラフの接続情報を元に、選ぶ、選ばないを繰り返す

選ばない回数の上限はn - m

つまり、最大でもO(2^{n - m})の探索木にしかならない。そのため、計算量は

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

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

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_;
};