鉄則本 B06 - Lottery (4Q, ★2)

累積和をやって、その次にやる類題として、そりゃこれを出すよね！！　って感じの問題ですね。

• 問題へのリンク

問題概要

回くじびきを引いた。 回目の結果は であった ( のときアタリ、 のときハズレ)。

次の 回のクエリに答えよ。

【クエリ】
が与えられるので、 回目から 回目までの間に、アタリとハズレのどちらの方が多かったかを答えよ。

制約

• 

考えたこと

通常の累積和と同様に、数列 の累積和を考えることで、各区間における「アタリの個数」が求められる。これによって、「ハズレの個数」もわかるので、比較すれば OK。

qiita.com

コード

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

int main() {
    int N, Q;
    cin >> N;
    
    // 配列 A の入力を受け取りながら、累積和も求める
    vector<int> A(N), S(N + 1, 0);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
        S[i + 1] = S[i] + A[i];
    }
    
    // クエリに答える
    cin >> Q;
    for (int iter = 0; iter < Q; ++iter) {
        int L, R;
        cin >> L >> R;
        --L;
        
        // 区間のアタリの個数
        int atari = S[R] - S[L];
        
        // 区間のハズレの個数
        int hazure = (R - L) - atari;
        
        if (atari > hazure) cout << "win" << endl;
        else if (atari < hazure) cout << "lose" << endl;
        else cout << "draw" << endl;
    }
}