問題
くじを N 回引き、i 回目の結果は Ai でした。
Ai=1 のときアタリ、Ai=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, 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] => 負け
くじを引いた回数の範囲に応じて、勝ち負けを判定することができました。