Hatena::Grouptopcoder

agwの日記 RSSフィード

 | 

2012-09-19SRM 554 Div II

Single Round Match 554 Round 1

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

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
250TheBrickTowerEasyDivTwo System Test Passed215.04
550TheBrickTowerMediumDivTwoSystem Test Passed445.36
1000TheBrickTowerHardDivTwo Opened
  • 250に12分。215.04点
  • 500に10分。445.36点
  • 残り時間を1000に費やすも、間に合わず
    • 後ほど検証。SRM中の実装方針ではTLEとなることが分かった
  • 写経撃墜で50点獲得
  • 合計710.40点
    • 久しぶりに2完できたので嬉しい
  • レート1199点
    • 念願の青コーダーにはなれなかった
  • 次回の目標
    • 2問通す
    • 青コーダーになる

TheBrickTowerEasyDivTwo

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

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

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

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;
  };
};
  • うーん
    • 数式としては納得できるのだが、ぼんやり納得している感が否めない

f:id:agw:20120919002555p:image

  • 条件を視覚化してみよう

f:id:agw:20120919002556p:image

  • うーん
    • やっぱりぼんやりしている
    • 理由がよく分からない...

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

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/agw/20120919
リンク元
 |