本を読み終えるまでの日数を求めるC++プログラムの解説

n個の要素を持つ配列Aと整数tが与えられているとします。i日目にはAmalは仕事にA[i]秒を費やし、その空いた時間に本を読みます。本全体を読み終えるのに必要な時間はt秒です。ここで、本を最後まで読み終えるまでに何日かかるかを求めるのがこの問題です。

たとえば、入力がA = [86400, 86398]、t = 2である場合、出力は2になります。1日は86400秒ですが、初日は仕事で丸々埋まってしまい、読書できる時間がありません。2日目には2秒の自由時間が生まれ、そこで本を読み切ることができるためです。

解法のアプローチ

この問題は、各日の自由時間（86400秒から仕事時間を引いた秒数）を順番に読書時間tから差し引いていくことで解けます。具体的な手順は以下の通りです。

1. 経過日数を表すカウンタcntを1で初期化します。
2. 配列Aの各要素xについて、その日の自由時間「86400 − x」をtから引きます。
3. tが0以下になった瞬間に、現在のcntを答えとして返します。
4. まだ読み終わっていなければ、cntを1増やして翌日に進みます。

上記の手順を擬似コードで表すと次のようになります。

cnt := 1
n := size of A
for initialize i := 0, when i < n, update (increase i by 1), do:
    x := A[i]
    t := t - (86400 - x)
    if t <= 0, then:
        return cnt
    (increase cnt by 1)

C++による実装例

理解を深めるために、以下の実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A, int t){
    int cnt = 1;
    int n = A.size();
    for (int i = 0; i < n; i++){
        int x = A[i];
        t -= 86400 - x;
        if (t <= 0){
            return cnt;
        }
        ++cnt;
    }
}
int main(){
    vector<int> A = { 86400, 86398 };
    int t = 2;
    cout << solve(A, t) << endl;
}

入力

{ 86400, 86398 }, 2

出力

2

処理の流れ

この入力における処理の流れを確認してみましょう。

• 1日目： 自由時間は 86400 − 86400 = 0秒。tは2のまま変わりません。
• 2日目： 自由時間は 86400 − 86398 = 2秒。t = 2 − 2 = 0となり条件を満たすので、cnt = 2が返されます。

配列を一度走査するだけなので、計算量はO(n)と非常に効率的です。日ごとの自由時間を単純に減算していくだけで答えが得られる、シンプルながら実用的なシミュレーション問題といえます。