Hatena::Grouptopcoder

agwの日記 RSSフィード

 | 

2012-09-19SRM 554 Div II

TheBrickTowerMediumDivTwo

16:32 |  TheBrickTowerMediumDivTwo - agwの日記 を含むブックマーク はてなブックマーク -  TheBrickTowerMediumDivTwo - agwの日記  TheBrickTowerMediumDivTwo - agwの日記 のブックマークコメント

http://community.topcoder.com/stat?c=problem_statement&pm=12162&rd=15176

10分。445.36点。

  • まず図を書いた

f:id:agw:20120919001659p:image

  • 問題分に記載されているように、隣り合ったタワーの高さの高いほう分間隔を開ければよいようだ
    • ならば、全順列を試せばよいのではないか?
    • 例題の場合、3P3なので6通り

f:id:agw:20120919001700p:image

  • 試算してみよう
    • 問題の条件、7本のタワーの順番の順列の総数は高々5040

f:id:agw:20120919001658p:image

  • 余裕で全探索できそうだ

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

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での列挙不足等にはならないはずだ
  • 競技プログラミングの成果が実感できた、嬉しい問題であった
 |