SRM554 Div1 Easy - TheBrickTowerEasyDivOne
問題
高さrhの赤いブロックがrc個、高さbhの青いブロックがbc個ある
これらのブロックを1個以上使い、同じ色のブロックが隣接しないように積み上げてタワーを作る
タワーの高さとしてあり得るものの個数を求めよ
1 <= rh, rc, bh, bc <= 5*10^8くらい
解法
(rh=bhのとき)
rc=bcのとき) 答えは明らかにrc*2通り
rc≠bcのとき) 個数が多い方の色のブロックを底にして交互に積むとmin(rc,bc)*2+1通り作れる
(rh≠bhのとき)
赤と青のブロック1個ずつのセットを何個積むかをベースにして考える
セットは最小0個、最大min(rc,bc)個積める
0個積むとき) 赤か青のどっちかを1個積めるから2通り
k (1 <= k <= min(rc,bc)-1) 個積むとき) 何も積まないか赤or青を1個積めるから3通り
min(rc,bc)個積むとき) 何も積まないのが1通り、rc≠bcなら余ってる方のブロックをもう1個積めるからもう1通り
class TheBrickTowerEasyDivOne { public: int find(int rc, int rh, int bc, int bh) { if (rh==bh) return min(rc,bc)*2 + (rc!=bc); return min(rc,bc)*3 + (rc!=bc); } };