SRM 549 Div II

Single Round Match 549 Round 1

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

250に11分。500に1時間ほどかけ、完成しなかった。チャレンジ3回成功。合計369.38点。レートは1011から1097へ。緑コーダー。

Problem Status Points
250 BallAndHats System Test Passed 219.38
500 PointyWizardHats Opened 0.00
1000 OrderOfTheHats Unopened
  • 250に11分。219.38点
  • 500に1時間ほどかけ、完成しなかった
    • 2部マッチングであることは分かっていた
    • 準備不足でグラフを間違えて構築していたことに気付かなかった
  • 3回のチャレンジを成功
  • 次回の目標
    • 2問通す

BallAndHats

http://community.topcoder.com/stat?c=problem_statement&pm=11964&rd=15171&rm=313673&cr=22827765

11分。243.22点。

  • 題意を理解するのに時間がかかってしまった
    • 当初は確率を考える問題かと思った
  • よく分からなかったので、図を書いた


  • なるほど、周期性がありそうだ
  • 選択肢としてo..と..oがある場合、答えはo..となる
    • つまり..oとして始まらなかったら、..oとなることはない

実装は以下(システムテスト済)。

class BallAndHats {
public:
  int getHat(std::string hats, int numSwaps) {
    if (numSwaps == 0) {
      return (int)hats.find('o');
    }
    else if (hats == ".o.") {
      return 1 - numSwaps % 2;
    }
    else {
      return     numSwaps % 2;
    }
  };
};
  • 提出前に自分のテストケースを追加した
    • o..と0。答えは0(o..)
    • .o.と0。答えは1(.o.)
    • ..oと1。答えは1(.o.)
    • これらがチャレンジフェーズで地味に活躍した
  • 3回のチャレンジを成功
    • 複雑になってしまっている実装を片っ端から写経
    • 赤らさまに間違えている実装も写経し、確認してからチャレンジした
  • 作図をしていて、以下のようにも考えられることに気付いた


  • この考え方は自分にとってとても大事であるのだがなかなか出てこない

PointyWizardHats

http://community.topcoder.com/stat?c=problem_statement&pm=11965&rd=15171&rm=313673&cr=22827765

1時間実装を行った。2部マッチングで解けることは分かっていたが、準備不足のためグラフの構築に誤りがあったことに気付けなかった。

  • 2部マッチング問題であることは分かっていた
  • しかし、どう使ってよいか分からない...
    • 2部マッチング問題は最大フロー問題に還元されるはず
  • この実装では無向グラフとしてグラフを構築するようだ
    • 知っている最大フローの実装は有向グラフのもの
  • ソースとシンクを含まないグラフを構築して答えが合わなかった
    • グラフの構築方法を間違えていることに気付かなかったのが原因。下の帽子の半径が上の帽子の半径より小さい場合にマッチしないことを見逃していた
  • ソースとシンクが必要なのだろうか? と思い、グラフに足した
      • 当たり前だが、これでも答えが合わない
  • そのまま時間切れ

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

#define MAX_V 100

int V;
std::vector<int> G[MAX_V];
int match[MAX_V];
int used[MAX_V];

void add_edge(int u, int v) {
  G[u].push_back(v);
  G[v].push_back(u);
}


bool dfs(int v) {
  used[v] = true;

  for (int i = 0; i < G[v].size(); i ++) {
    int u = G[v][i], w = match[u];

    if (w < 0 || ! used[w] && dfs(w)) {
      match[v] = u;
      match[u] = v;

      return true;
    }
  }

  return false;
}

int bipartite_matching() {
  int res = 0;

  memset(match, -1, sizeof(match));

  for (int v = 0; v < V; v ++) {
    if (match[v] < 0) {
      memset(used, 0, sizeof(used));

      if (dfs(v))
	res ++;
    }
  }
  return res;
}

class PointyWizardHats {
public:
  int getNumHats(std::vector<int> topHeight, std::vector<int> topRadius, std::vector<int> bottomHeight, std::vector<int> bottomRadius) {
    int top_size    = topHeight.size();
    int bottom_size = bottomHeight.size();

    for (int i = 0; i < MAX_V; i ++)
      G[i].clear();

    for (int i = 0; i < top_size; i ++) {
      for (int j = 0; j < bottom_size; j ++)
	if (check(topHeight[i], topRadius[i], bottomHeight[j], bottomRadius[j]))
	  add_edge(i, j + top_size);
    }

    V = top_size + bottom_size;
    
    return bipartite_matching();
  };

private:
  inline bool check(double th, double tr, double bh, double br) const {
    return th > tr * bh / br;
  };
};
  • 下の帽子の半径が上の帽子の半径より小さい場合にマッチングが成立しないことを加味していなかった
    • 頂点が辺を持つ条件は以下なのであった
  inline bool check(double th, double tr, double bh, double br) const {
    if (tr < br) {
      return th > tr * bh / br;
    }
    else {
      return false;
    }
  };
  • 写経ミスであるのか、ライブラリの使い方が悪いのか判断できず、問題が切り分けられなかった
    • 明らかに準備不足であった
  • 蟻本の2部マッチングの実装を改めて見直してみる
    • 何をしているか全く理解できない
  • 2部マッチングは最大フロー問題に還元できるはず
    • これまでに見たことのある最大フローの実装は有向グラフを使っていた
      • この実装では無向グラフを使っている(隣接リストを用いた双方向の有向グラフ)
    • ソースとシンクを追加するはずだ
      • この実装ではソースとシンクを必要としない
  • 何故だろう...?
    • 今回は蟻本の2部マッチングの実装を理解することを目的としよう
  • 次のような2部グラフを考える


  • 2部マッチング問題を最大フロー問題に還元する
    • ソースとシンクを追加し、有向グラフにする


  • このグラフの最大フロー問題を解く


  • その結果は最大マッチングの結果の一つとなる


  • 実装に関して、蟻本では以下のように説明している

二部マッチングは容量がすべて1であることと二部グラフであることを用いて、よりシンプルに次のように書くこともできます。

  • うーん
    • 全く分からない
  • このままでは埒があかない
    • 実装を追いかけよう
  • 深さ優先探索の動作を追ってみよう


  • をを
    • なるほど、分かったぞ
    • この実装は増大路を探す実装だ
    • 両端の接点がマッチングに含まれていない交互路を増大路という
      • 増大路上の辺を入れ換えるとマッチングの総数が1増える


  • まだ何もマッチしていない
  • 頂点1と連結しているのは頂点AとB
    • まず頂点Aを調べる
    • 頂点Aはマッチングに含まれていない


  • この経路は増大路だ
    • 頂点1とAをマッチングに含めると、マッチングの総数は1つ増える


  • ここまでは簡単
  • 次に頂点3から始まる深さ優先探索を考えてみよう
    • 頂点1とA、頂点2とBがすでにマッチしている


  • 頂点3と連結しているのは頂点BとD
    • まず頂点Bを調べる


  • 頂点Bはマッチングに含まれている
    • また、頂点Bとマッチしているのは頂点2


  • 次に深さ優先探索が訪れるのは、その頂点2だ
    • 頂点2と連結しているのは頂点BとC
    • 頂点Bにはすでに訪れているので、頂点Cを調べる
      • 頂点Cはマッチングに含まれていない


  • この道は頂点3、B、2、Cで構成される交互路だ
    • 頂点3とCはマッチングに含まれていない
    • つまりこの交互路は増大路である
  • マッチングを更新しよう
    • 具体的には増大路上のマッチングを交互に入れ換えればよい


  • 増大路の発見と更新を1回行ったとき、総マッチング数は必ず1つ増える
    • 以下を見れば明かだろう


  • 同様に頂点4から始まる深さ優先探索は頂点4、A、1、B、3、Dからなる増大路を発見し、マッチングを更新する


  • しかし、頂点5から始まる深さ優先探索は増大路を発見しない
  • また、頂点A、B、C、Dはすでにマッチングに含まれているので、増大路として成立しない。そのため、探索する必要もない
  • 大体分かった
    • 分からないこともある
  • 深さ優先探索は増大路が見つからなくなるまで繰り返されるものだと思っていた
  • うーん
    • やっぱりよく分からない
  • 蟻本の著者さん達なら的確に1行で答えるんだろうなぁ...

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?