HackerRank University CodeSprint 2: Game of Two Stacks

,

https://www.hackerrank.com/contests/university-codesprint-2/challenges/game-of-two-stacks

solution

自然数のstackがふたつと整数$x$が与えられる。 取り出した数の合計が$x$以上になるまで、ふたつのstackから好きに数を取り出してよい。 取り出す数の個数を最大化したとき、それはいくつか。

solution

しゃくとり法。$O(N + M)$ for each game。

implementation

#include <iostream>
#include <vector>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
using ll = long long;
using namespace std;
template <class T> void setmax(T & a, T const & b) { if (a < b) a = b; }
int main() {
    int games; cin >> games;
    while (games --) {
        int na, nb, x; cin >> na >> nb >> x;
        vector<int> a(na); repeat (i,na) cin >> a[i];
        vector<int> b(nb); repeat (j,nb) cin >> b[j];
        int result = 0;
        int i = 0;
        ll acc = 0;
        while (i < na and acc + a[i] <= x) {
            acc += a[i];
            ++ i;
        }
        int j = 0;
        while (true) {
            while (j < nb and acc + b[j] <= x) {
                acc += b[j];
                ++ j;
            }
            setmax(result, i + j);
            if (i == 0) {
                break;
            } else {
                -- i;
                acc -= a[i];
            }
        }
        cout << result << endl;
    }
    return 0;
}