Yuulis.log

トンネルを抜けるとそこは参照エラーであった。

【AtCoder】ABC 341 B - Foreign Exchange | 茶コーダーが解くAtCoder

AtCoder ABC 灰Diff Diff: ~99 Easy

実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 163

問題概要

$1$ から $N$ までの番号が付いた $N$ 個の国があり、 $i = 1, 2, ..., N$ について、国 $i$ の通貨を $A_i$ 単位持っている。以下の操作を0回以上繰り返して、最終的に持てる国 $N$ の通貨の単位数としてあり得る最大値を出力せよ。

操作 : 国 $i (i = 1, 2, ..., N - 1)$ の通貨を $S_i$ 単位以上持っているなら、「国 $i$ の通貨を $S_i$ 単位支払い、国 $(i + 1)$ の通貨を $T_i$ 単位得る」という行動を1回行う。

制約

入力はすべて整数
$2 \leq N \leq 2 \times 10^5$
$0 \leq A_i \leq 10^9$
$1 \leq T_i \leq S_i \leq 10^9$

考察

操作を行うことで、番号の小さい国の通貨を番号の大きい国の通貨へ変換できるので、各国に対して操作をできる限り行っていけば、最終的な国 $N$ の通貨の単位数を最大化できる。 $2 \leq N \leq 2 \times 10^5$ なので、操作の結果をシュミレーションしていけばよい。国 $i$ については、 $A_i \geq S_i$ のとき、硬貨の交換を $\lfloor \frac{A_i}{S_i} \rfloor$ 回行うことができる。

コード

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

using ll = long long;

#define rep(i, start, end) for (ll i = (start); i < (ll)(end); i++)

// ======================================== //

int main()
{
    int N;
    cin >> N;
    vector<ll> A(N + 1);
    rep(i, 1, N + 1) cin >> A[i];
    vector<ll> S(N), T(N);
    rep(i, 1, N) cin >> S[i] >> T[i];

    rep(i, 1, N)
    {
        if (A[i] >= S[i])
        {
            A[i + 1] += T[i] * (A[i] / S[i]);
            A[i] %= S[i];
        }
    }

    cout << A[N] << endl;
}

実装時間: 10分