ABC281(C問題) 感想

本日はABC281のC問題について。 以下が私が最初に書いたコード。まずこれはセグフォで通らなかった。理由としては、ベクトルの要素数を定義していないのに関わらずA[i]のようにベクトル要素にアクセスしてしまっているからである。そこでstd::vector<int> A(N)のように要素数を決めてしまうのが良い。ただ、今回は新しく配列に要素を追加するというようなことがないので、ただの配列を用いるだけの方がスマートだった気がする。

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int N, T;
    cin >> N >> T;
    std::vector<int> A;
    int total_time = 0;
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }
    for (int i = 0; i < N; ++i) {
        total_time += A[i];
    }
    cout << A[0] << endl;
    int tmp = total_time % T;
    int song_num = 0;
    int time_from_start = 0;
    for (int i = 1; i <= N; ++i) {
        if (A[i-1] > tmp) {
            song_num = i;
            time_from_start = tmp;
            break;
        }
        tmp -= A[i-1];
    }
    cout << song_num << " " << time_from_start << endl;
    return 0;
}

ただベクトルの要素数を決めただけだと通らなかった。そこでこの似たような間違いをした人がどのように修正してACしたかを教えてくれる素晴らしいサイト(https://atcoder-companions.kakira.dev/)を用いて自分の解答を分析した。するとどうやら型の問題で、intとしているのがおかしいみたい。実際問題のそれぞれの整数の範囲を確認する。すると1≤A[i]≤10⁹, 1≤T≤10¹⁸ という条件を確認することができる。int型は32bitで、大体2*10⁹程度までを符号付きで表せるだけであるので、オーバーフローしてしまう。そこで、Tを64 bitのlong long型にしてあげる必要がある。そうして見事以下のコードでACした（以下ではA[i]もlong long型にしているが本来そうする必要ない）。

#include <iostream>
#include <vector>

using namespace std;
using ll = long long;

int main() {
    ll N, T;
    cin >> N >> T;
    std::vector<ll> A(N);
    ll total_time = 0;
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
        total_time += A[i];
    }
    ll tmp = T % total_time;
    ll song_num = 0;
    ll time_from_start = 0;
    for (int i = 1; i <= N; ++i) {
        if (A[i-1] > tmp) {
            song_num = i;
            time_from_start = tmp;
            break;
        }
        tmp -= A[i-1];
    }
    cout << song_num << " " << time_from_start << endl;
    return 0;
}