SRM 554 Div II - agwの日記

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

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

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点。

まず図を書いた

問題分に記載されているように、隣り合ったタワーの高さの高いほう分間隔を開ければよいようだ
- ならば、全順列を試せばよいのではないか?
- 例題の場合、₃P₃なので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;
  };
};