SRM 699 div2 easy UpDownHiking
問題概要
n日間で山を登ります。1日で最大登れる高度はA、1日で最大下れる高度はBである。このときに、N日間で山を登り、元の場所に戻ってくる場合で、最大高度はいくつまでいけるか。
解法
全探索ぽいことしました。nの制約は小さく、Aの制約も小さいので、N=50、A=50の場合でも、最大で行ける高度は、50*25=1250が限界なので、高さを決めて、その高さにN日間で到達して、帰ってこれるかを確かめることにした。
高度iまで行くのに何日間かかるかは、iをAで割り切ることができれば、i/A日、割り切ることができなければ、i/A + 1日になる。これを同様に下りの場合も計算して、登りと下りの合計日数がN日以下であれば条件を満たすので答えとなる。それの最大を求めればよい。
ミス
思いつくまでに時間かかったよね。すぐ解けないと。
コード
class UpDownHiking { public: int ans = 0; int maxHeight(int N, int A, int B){ for (int i = 0; i <= 3000; ++i){ int iki, kaeri; if(i % A == 0) iki = i / A; else iki = i / A + 1; if(i % B == 0) kaeri = i / B; else kaeri = i / B + 1; if(iki + kaeri <= N){ ans = max(ans, i); } } return ans; } };