累積和（１次元）②

問題

くじを $ N $ 回引き、$i$ 回目の結果は $ A_i $ でした。

$ A_i = 1 $ のときアタリ、$ A_i = 1 $ のときハズレを意味します。

$L$ 回目から $R$ 回目までの中では、アタリとハズレのどちらが多いか？という形式の質問が $Q$ 個与えられるので、それぞれの質問に答えて下さい。

解き方・ソースコード

この問題は、アタリとハズレの累積和を求めることで、より少ない計算量で解くことができます。

くじを引いた回数ごとのアタリとハズレの累積回数を比較し、アタリが多い場合は“勝ち”、ハズレが多い場合は“負け”、アタリとハズレの回数が同じ場合は“引き分け”を出力します。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#-------- 入力例１ ---------
N = 10
A = [random.randint(0, 1) for _ in range(N)] 
Q = 5
L = [1,  3, 8, 3, 6]
R = [4, 10, 9, 4, 9]
#---------------------------
print('くじの全結果', A)

# アタリの個数・ハズレの個数の累積和を算出
Atari = [ 0 ] * (N + 1)
Hazre = [ 0 ] * (N + 1)
for i in range(1, N + 1):
    # アタリの計算
    Atari[i] = Atari[i - 1]
    if A[i - 1] == 1:
        Atari[i] += 1
    # ハズレの計算
    Hazre[i] = Hazre[i - 1]
    if A[i - 1] == 0:
        Hazre[i] += 1

# 質問に答える
for i in range(Q):
    NumAtari = Atari[R[i]] - Atari[L[i] - 1]
    NumHazre = Hazre[R[i]] - Hazre[L[i] - 1]
    print('{}回目～{}回目の結果'.format(L[i], R[i]), A[L[i] - 1:R[i]], end=' => ')
    if NumAtari > NumHazre:
        print("勝ち")
    elif NumAtari == NumHazre:
        print("引き分け")
    else:
        print("負け")

[実行結果（入力例１）]

くじの全結果 [1, 1, 1, 1, 1, 1, 0, 0, 0, 0]

1回目～4回目の結果 [1, 1, 1, 1] => 勝ち

3回目～10回目の結果 [1, 1, 1, 1, 0, 0, 0, 0] => 引き分け

8回目～9回目の結果 [0, 0] => 負け

3回目～4回目の結果 [1, 1] => 勝ち

6回目～9回目の結果 [1, 0, 0, 0] => 負け

くじを引いた回数の範囲に応じて、勝ち負けを判定することができました。