SRM 554 250pt : TheBrickTowerEasyDivOne

TopCoder

問題概要

赤のブロックと青のブロックがそれぞれいくつかある。それぞれ高さが決まっている。ブロックを積み上げるときは異なる色のブロックを交互に積まなければならない。異なる高さの塔が何種類作れるか求める問題。

考えたこととか

  • (問題誤読したまま書き上げてサンプルが通らなくて初めて誤読に気づいた)
  • 任意の形が(redHeight + blueHeight)*k + (0 or redHeight or blueHeight)の形に書けるわけで。
  • で、kはmin(redCount, blueCount)まで動くけどこのとき余りの部分は個数が一致してると0に限定されてそうでないとき多い方を選べる。
  • ただし、redHeight = blueHeightのときは余りの部分を区別できない。
  • 遅れていたので急いで提出した後撃墜できそうなところを探す。案外サンプル強いので落とし辛い。

後で修正したコード

#include <algorithm>
using namespace std;

struct TheBrickTowerEasyDivOne {

	int find(int redCount, int redHeight, int blueCount, int blueHeight) {
		int ans = 0, mini = min(redCount, blueCount);
		ans += mini * (redHeight == blueHeight ? 2 : 3);
		if (redCount != blueCount) {
			++ans;
		}
		return ans;
	}

};