読者です 読者をやめる 読者になる 読者になる

srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

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;
    }
};