SRM 553 Div II
Single Round Match 553 Round 1
http://community.topcoder.com/stat?c=round_overview&er=5&rd=15175
250に7分。500も54分で提出したが、システムテストで落ちた。写経ミスでチャレンジ1回失敗。合計210.74点。レートは1123から1111へ。緑コーダー。Room 61。
Problem | Status | Points | |
---|---|---|---|
250 | PlatypusDuckAndBeaver | System Test Passed | 227.00 |
550 | Suminator | Failed System Test | 0.00 |
1000 | SafeRemoval | Unopened |
PlatypusDuckAndBeaver
http://community.topcoder.com/stat?c=problem_statement&pm=12169&rd=15175
7分。235.74点
実装は以下(システムテスト済)。
class PlatypusDuckAndBeaver { public: int minimumAnimals(int webbedFeet, int duckBills, int beaverTails) { int nd = (webbedFeet - beaverTails * 4) / 2; int np = duckBills - nd; int nb = beaverTails - np; return nd + np + nb; }; };
- 今考えれば、全探索してもよかった
実装は以下(システムテスト済)。
class PlatypusDuckAndBeaver { public: int minimumAnimals(int webbedFeet, int duckBills, int beaverTails) { for (int i = 0; i <= 1000; i ++) for (int j = 0; j <= 1000; j ++) for (int k = 0; k <= 1000; k ++) if (i * 4 + j * 2 + k * 4 == webbedFeet && i + j == duckBills && i + k == beaverTails) return i + j + k; return -1; }; };
- なかなか全探索する発想にならない...
- 解析的に解く場合と、全探索で解く場合の両方を考えた上で選択したい
- この問題だと計算量が109であるので少し戸惑うが、nD、nB、nPの範囲が[1, 100]であれば、迷わず全探索を選ぶような気がする
Suminator
http://community.topcoder.com/stat?c=problem_statement&pm=11354&rd=15175
30分ほどで実装終了。20分ほど検証に費やしてから提出。54分。226.44点。システムテストで落ちた。
- まずシミュレータを書いた
- 初めにintを用いて実装したのはまずかった
- 二部探索を用いた実装が出来そうに思った
- しかし、Suminatorが単調増加関数であるかどうか確信が持てなかった
- シミュレータから標本を抽出し、Gnuplotにて描画した
- 範囲を[1, 109]とし、テストケース毎に1024個標本抽出した(図は64個標本抽出した例)
- SRM参戦中にGnuplotを使ったのは初めてだったが、有用であった
- しかし、シミュレータでの計算がオーバーフローしていることに気付かなかった(!)
- 単調増加関数であるか否かのみに注目し、見逃してしまった
- 以下はSRM後にシミュレータを修正し、出力した結果だ
- 大きく2つのパターンに分けられることが分かった
- 線形的に大きくなる
- 定数になる
- またテストケースを試すことで、0を使った場合は特殊であることに気付いた
- まず0を使ってテストし、成立しない場合は探索すればよい
- 二分探索を書いた
- テストはうまく通っている...
- この時点で30分ほど
- コードを見直す
- シミュレータはlong longを用いたほうがよさそうに思えた
- 書き直した
- 提出した
- システムテストで落ちた
- 3つ失敗があった
- シミュレータがlong longに移植しきれていなかった
- std::stack.top()の戻り値をintで受けていた
- check関数の戻り値をintで受けていた
- check関数の戻り値は検証する値との差である
- 途中から、(何らかの負の値、0、何らかの正の値)を取るもの、
- さらに(-1, 0, 1)を取るもの、くらいの認識で進めてしまった
- そのため、ここでオーバーフローとアンダーフローを起こすことは全く予想していなかった
- 整数を扱うのに適した二部探索ではなかった
- 実数を扱うように実装してしまった
- この実装は1,000,000,000を見つけることができない
- l = 999,999,999、r = 1,000,000,000からl = 1,000,000,000、r = 1,000,000,000に遷移しないのだ
int l = 1, r = 1000000000; for (int i = 0; i < 256; i ++) { int m = (l + r) / 2; int c = check(program, wantedResult, m); if (c == 0) { return m; } else if (c < 0) { r = m; } else { l = m; } }
- 今回は整数を扱うのに適した二部探索を考察する
- 以下の実装はアルゴリズムC 第2巻の14章、「初等的な探索法」からの抜粋だ
int binarysearch(int v) { int l = 1; int r = N; int x; while (r >= l) { x = (l+r)/2; if (v < a[x].key) r = x-1; else l = x+1; if (v == a[x].key) return a[x].info; } return -1; }
- いつもながら、アルゴリズムCの実装はかっこいい
- 二分探索は珠玉のプログラミングでも詳しく取り上げられている
- 以下の実装は珠玉のプログラミングのコラム5、「あと少しの事」からの抜粋(57ページ)
int binarysearch(DataType t) { int l, u, m; l = 0; u = n-1; while (l <= u) { m = (l + u) / 2; if (x[m] < t) l = m+1; else if (x[m] == t) return m; else /* x[m] > t */ u = m-1; } return -1; }
- 珠玉のプログラミングの実装も痺れる
- アルゴリズムCの実装も、珠玉のプログラミングの実装も閉区間を扱っていることに注意
- アルゴリズムCでは1から始まる添字を、また珠玉のプログラミングでは0から始まる添字を用いているので、混乱しないようにしたい
- 何れの実装も閉区間を扱っているのがポイント
- また、上限下限の何れを更新する場合にもmを含まない範囲とする
- まとめとして、アルゴリズムCの二分探索の図(図14.2 大きいファイルでの2分探索。10ページ)と珠玉のプログラミングのクイックソートの図(149ページ)を参考に作図する
- 区間を更新する際にmを含まないことをより明確にするために、-1と+1をはっきりと視覚化してみた
では、ここまでの考察を元にリファクタリングする(システムテストをパス)。
class Suminator { public: int findMissing(std::vector<int> program, int wantedResult) { if (compute(program, 0) == wantedResult) return 0; int l = 1, u = 1000000000; while (l <= u) { int m = (l + u) / 2; long long x = compute(program, m); if (x == wantedResult) { return m; } else if (wantedResult < x) { u = m - 1; } else { l = m + 1; } } return -1; }; private: long long compute(std::vector<int> program, long long m) const { std::stack<long long> stack(std::deque<long long>(100, 0)); *std::find(ALL(program), -1) = m; for (int i = 0, size = program.size(); i < size; i ++) { if (program[i] == 0) { long long a = stack.top(); stack.pop(); long long b = stack.top(); stack.pop(); stack.push(a + b); } else { stack.push(program[i]); } } return stack.top(); }; };
- check関数からcompute関数に変更した
- 与えられた数値とシミュレーションの結果の差を返す関数ではなく、シミュレーションの結果の値そのもを返す関数にした
- 関数の戻り値に曖昧さがなくなった
- そのため、実装がより明瞭になったように思う
- 今回は整数の二分探索を考察した
- もう一度ポイントをまとめる
- 二分探索を考察する際に参考にした書籍は以下だ
- 作者: R.セジウィック,Robert Sedgewick,野下浩平,佐藤創,星守,田口東
- 出版社/メーカー: 近代科学社
- 発売日: 1996/09/01
- メディア: 単行本
- 購入: 6人 クリック: 88回
- この商品を含むブログ (11件) を見る
珠玉のプログラミング―本質を見抜いたアルゴリズムとデータ構造
- 作者: ジョンベントリー,Jon Bentley,小林健一郎
- 出版社/メーカー: ピアソンエデュケーション
- 発売日: 2000/10
- メディア: 単行本
- 購入: 30人 クリック: 551回
- この商品を含むブログ (162件) を見る