yukicoder No. 604 誕生日のお小遣い - 今日から始める競プロ日記

はじめに

最近、yukicoderも始めました。

本当は作問してみようと思って登録したのですが、 いざ問題を作ろうと思ったら何も思い浮かばなかったので、 他の方々が作った問題を解いて勉強していきます。

No. 604 誕生日のお小遣い

• 誕生日になるとお小遣いが貰える
• 歳がAの倍数のときはB円
• それ以外では1円
• 1歳からお小遣いをもらい始めたとき、総額がC円を超えるのは何歳か

No.604 誕生日のお小遣い - yukicoder

解いた方針

頑張って計算する方法（1行で書ける）と二分探索を使う方法があるみたいです。

ここでは二分探索のほうで解いてみます。

以下の記事を参考にしました。

c6h4c12takatakamasataka.hatenablog.com qiita.com

この問題の制約が

1 <= A,B,C <= 10^18

とかなり大きいので、計算量がO(N)でもダメです。

歳が増えるごとに、もらえる総額も増えるので二分探索が使えそうです。 二分探索なら計算量は`O(logN)であるため、大丈夫そうです。

計算の流れは以下のようになります。

1. 二分探索の範囲を設定（左端=0, 右端=C）
2. 中央の値を計算中央 = （左端+右端）/ 2
3. 2で求めた中央の値（歳）のときもらえる総額を計算
4. 3で求めた総額がCより大きいか小さいかで、範囲を更新
5. 解が求まるまで2～4をループ

コード

#include <bits/stdc++.h>
using namespace std;

int main()
{
    // 入力
    unsigned long long A, B, C;
    cin >> A >> B >> C;

    // 二分探索
    unsigned long long left  = 0; //左端
    unsigned long long right = C; //右端
    while(right - left > 1)
    {
        unsigned long long mid = (left+right)/2; //中央
        unsigned long long sum = (mid/A)*B + mid-(mid/A);
        if(sum >= C) right = mid;
        else left = mid;
    }

    // 解を出力
    cout << right << endl;
    return 0;
}

おわりに

二分探索をなんとなく理解した。

今日から始める競プロ日記まとめ

kato-robotics.hatenablog.com