Hatena::Grouptopcoder

agwの日記 RSSフィード

 | 

2012-09-19SRM 554 Div II

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

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