第143回【Python】’I’ の数

現在取り組んでいるのは、paiza ラーニング問題集「クエリメニュー」になります。

はじめに

猫とキャンプと野球観戦と AWS が大好きな旦那、LeoSaki です。モフモフしたい。

Python をゼロから勉強してみよう、のコーナー 143 回目です。

お客様環境で作業させていただく際には、細心の注意が必要となります。慣れている作業であっても精神をすり減らします。リモート作業は便利な反面、ネットワークの遮断や電源の切断など、どうにもならない状況が発生する可能性もあるからです。

それでは、今日も頑張ってみようと思います。

'I’ の数

英語の授業中に暇だった paiza 君は、N ページの教科書を使った次のようなゲームを思いつきました。

「2人のプレイヤーがそれぞれ教科書の 1 箇所を適当に掴んで、掴んだ範囲のページに含まれる 'I’ の合計数が多い方が勝ち、少ない方が負け、同じだったら引き分け！」
「ただし、 N/3 ページ以上掴んだ人は反則負けで、 2 人とも反則したら引き分け！」
(ここでの N/3 は整数であるとは限りません)

審判を任されたあなたは、各ページに含まれる 'I’ の数を記録しておくことで、掴んだページの両端の番号を確認するだけで、掴んだ範囲のページに含まれる 'I’ の合計数を求めることができることに気付きました。

教科書のページ数 N と試合の数 K , 各ページの 'I’ の数 I_1 … I_N と、
i 番目の試合で対戦した A と B の 2 人が掴んだページの両端のページ番号 A_l_i, A_r_i , B_l_i, B_r_iが与えられるので、各試合のジャッジしてください。

N K
A_1
...
A_N
A_l_1 A_r_1 B_l_1 B_r_1
...
A_l_K A_r_K B_l_K B_r_K

・1 行目では、教科書のページ数 N とおこなわれる試合数 K が与えられます。
・続く N 行のうち、 i 行目では、教科書の i ページ目に含まれる 'I’ の数が与えられます。
・続く K 行のうち、 i 行目では、i 試合目のプレイヤー A が掴んだページの両端のページ番号 A_l_i , A_r_i とプレイヤー B が掴んだページの両端のページ番号 B_l_i , B_r_i が与えられます。

期待する出力

ans_1
...
ans_K

・i 行目に i 試合目の結果を出力してください。
A の勝ちの場合は 'A’, B の勝ちの場合は 'B’ , 引き分けの場合は 'DRAW’ と出力してください。
・また、出力の末尾には改行を入れてください。

すべてのテストケースにおいて、以下の条件をみたします。

・1 ≦ N ≦ 100,000
・1 ≦ K ≦ 100,000
・0 ≦ A_i ≦ 100 (1 ≦ i ≦ N)
・1 ≦ A_l_i ≦ A_r_i ≦ N (1 ≦ i ≦ K)
・1 ≦ B_l_i ≦ B_r_i ≦ N (1 ≦ i ≦ K)

入力例

3 3
0
1
2
1 1 2 2
2 2 3 3
3 3 3 3

出力例

DRAW
DRAW
DRAW

いったい誰が I の数を数えたんだろう。大変な労力だったに違いない！

Python
N,K = map(int,input().split())
A = [int(input()) for _ in range(N)]

ans = [0] + A[:]
for i in range(1,N+1):
    ans[i] += ans[i-1]

bound = N / 3
for _ in range(K):
    al,ar,bl,br = map(int,input().split())
    
    a = ans[ar] - ans[al-1]
    b = ans[br] - ans[bl-1]
    
    if (ar-al+1) >= bound:
        a = -1
    if (br-bl+1) >= bound:
        b = -1

    if a > b:
        print('A')
    elif a < b:
        print('B')
    else:
        print('DRAW')
VBA
Sub query_primer__word_count()

    NK = Split(Cells(1, 1), " ")
    N = Val(NK(0))
    k = Val(NK(1))
    
    Dim ans() As Long
    ReDim ans(N)
    
    For i = 1 To N
        ans(i) = Cells(i + 1, 1)
    Next
    
    For i = 1 To N
        ans(i) = ans(i) + ans(i - 1)
    Next
    
    bound = N / 3

    For i = 1 To k
    
        AB = Split(Cells(i + N + 1, 1), " ")
        al = Val(AB(0))
        ar = Val(AB(1))
        bl = Val(AB(2))
        br = Val(AB(3))
        
        mrA = ans(ar) - ans(al - 1)
        mrB = ans(ar) - ans(al - 1)
        
        If (ar - al + 1) >= bound Then
            mrA = -1
        End If
        If (br - bl + 1) >= bound Then
            mrB = -1
        End If
        
        If mrA > mrB Then
            Debug.Print "A"
        ElseIf mrA < mrB Then
            Debug.Print "B"
        Else
            Debug.Print "DRAW"
        End If
        
    Next
    
End Sub

いつもの如く、paiza の境界値データテストで、約 36 秒。

最後に

累積和、区間和の応用問題。VBA でも、想像以上に早かった。累積和、区間和は何回も書くことで身体に覚えさせるが吉。LeoSaki（旦那）は頭で覚えるだけよりは、何回も書いて身体で覚える派です。

掴んだページが 3 分の 1 以上だったら、という条件で、-1 を入れておくところに行きつかず、if 文をだらだら書いた後で、何か方法があるはず、と頭を捻りました。まぁ、手を動かすことで新しい発想に繋がると信じて手を動かし続けます。

引き続き、よろしくお願いいたします！

Pythonpaiza,学習,Python

Posted by LeoSaki