SRM 554 Div II
Single Round Match 554 Round 1
http://community.topcoder.com/stat?c=round_overview&er=5&rd=15176
250に12分。500に10分。1000の実装を始めたが、間に合わず。写経撃墜に成功。合計710.40点。レートは1111から1199へ。緑コーダー。Room 82。
Problem | Status | Points | |
---|---|---|---|
250 | TheBrickTowerEasyDivTwo | System Test Passed | 215.04 |
550 | TheBrickTowerMediumDivTwo | System Test Passed | 445.36 |
1000 | TheBrickTowerHardDivTwo | Opened |
TheBrickTowerEasyDivTwo
http://community.topcoder.com/stat?c=problem_statement&pm=12160&rd=15176
12分。215.04点。
実装は以下(システムテストをパス)。
class TheBrickTowerEasyDivTwo { public: int find(int redCount, int redHeight, int blueCount, int blueHeight) { heights_.clear(); red (redCount, redHeight, blueCount, blueHeight, 0); blue(redCount, redHeight, blueCount, blueHeight, 0); return heights_.size(); }; private: void red(int redCount, int redHeight, int blueCount, int blueHeight, int height) { if (redCount == 0) return; int h = height + redHeight; heights_.insert(h); blue(redCount - 1, redHeight, blueCount, blueHeight, h); }; void blue(int redCount, int redHeight, int blueCount, int blueHeight, int height) { if (blueCount == 0) return; int h = height + blueHeight; heights_.insert(h); red(redCount, redHeight, blueCount - 1, blueHeight, h); }; private: std::set<int> heights_; };
- 全探索的な実装はできないものか
- SRM554 Div2 Easy(250) TheBrickTowerEasyDivTwo - 赤コーダーになりたいを読む
- !
- 衝撃を受けた
- 「赤と青が接しないようにブロックを並べられるのは、個数の差が1個以下の場合。」
- 目から鱗
実装は以下(システムテストをパス)。
class TheBrickTowerEasyDivTwo { public: int find(int redCount, int redHeight, int blueCount, int blueHeight) { std::set<int> heights; for (int i = 0; i <= redCount; i ++) for (int j = 0; j <= blueCount; j ++) if (std::abs(i - j) <= 1) heights.insert(redHeight * i + blueHeight * j); return heights.size() - 1; }; };
- うーん
- 数式としては納得できるのだが、ぼんやり納得している感が否めない
- 条件を視覚化してみよう
- うーん
- やっぱりぼんやりしている
- 理由がよく分からない...
TheBrickTowerMediumDivTwo
http://community.topcoder.com/stat?c=problem_statement&pm=12162&rd=15176
10分。445.36点。
- まず図を書いた
- 問題分に記載されているように、隣り合ったタワーの高さの高いほう分間隔を開ければよいようだ
- ならば、全順列を試せばよいのではないか?
- 例題の場合、3P3なので6通り
- 試算してみよう
- 問題の条件、7本のタワーの順番の順列の総数は高々5040
- 余裕で全探索できそうだ
実装は以下(システムテストをパス)。
class TheBrickTowerMediumDivTwo { public: std::vector<int> find(std::vector<int> heights) { std::vector<int> r; int size = heights.size(); std::vector<int> indexes; for (int i = 0; i < size; i ++) indexes.push_back(i); int lm = 999; do { int l = 0; for (int i = 0; i < size - 1; i ++) l += std::max(heights[indexes[i]], heights[indexes[i+1]]); if (l < lm) { lm = l; r = indexes; } } while (std::next_permutation(ALL(indexes))); return r; }; };
- indexesは生成した段階で昇順に整列している
- 整列されていないコンテナによるstd::next_permutationでの列挙不足等にはならないはずだ
- 競技プログラミングの成果が実感できた、嬉しい問題であった