第145回【Python】点の幅

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

はじめに

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

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

以前に比べて、1 問にかかる時間が伸びていることが分かります。それでも、まずは自力で解くことが大前提だと思っているので、腰を据えて挑戦しています。自ずと勉強時間が伸びています。楽しいからいっか！

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

点の幅

テストの返却中に暇だった paiza 君は、また 2 人で遊ぶゲームを思いつきました。

「2 人はそれぞれ生徒番号 1 〜 N の全校生徒 N 人の中から生徒番号が連続するように好きな人数の生徒を選ぶ。その選んだ生徒達の得点の幅が大きい方、すなわちその生徒たちの (最高点 – 最低点) の値が大きい方が勝ち、同じだったら引き分け！」

「ただし、このルールだと人を多く選ぶ方が有利になってしまうから、選べる生徒の数はお互い N/2 人以下ね！」

また審判を任されたあなたは、全ての生徒の得点を記録しておくことで、選んだ生徒たちの最小・最大の生徒番号を確認するだけで、その生徒たちの中の (最高点 – 最低点) の値をすぐに求めることができることに気付きました。

学校の生徒数 N と試合の数 K , 各生徒の得点 S_1 … S_N と、
i 番目の試合で対戦した A と B の 2 人が選んだ生徒の最小の生徒番号と最大の生徒番号が与えられるので、各試合のジャッジをしてください。

N K
S_1
...
S_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 の生徒のテストの得点 S_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 ≦ 10,000
・N は平方数である(ある整数 x > 0 を用いて N = x^2 と表すことができる)
・1 ≦ K ≦ 100,000
・0 ≦ S_i ≦ 100,000 (1 ≦ i ≦ N)
・1 ≦ Al_i ≦ Ar_i ≦ N (1 ≦ i ≦ K)
・1 ≦ Bl_i ≦ Br_i ≦ N (1 ≦ i ≦ K)
・各ゲームにおいて、プレイヤーの選ぶ生徒の数は N/2 以下であることが保証されている。

入力例

4 2
1
3
2
4
1 2 2 3
1 2 3 4

出力例

A
DRAW

審判を任されてしまった LeoSaki（旦那）は、全員のテストの点数を教えてもらわないといけないらしいです。そんなまさか、教えてくれるのか？

Python
def comparison(X,max_range,min_range,sqrt,left,right):
    max_now = 0
    min_now = 100000
    div = left // sqrt
    while left <= right:
        if left % sqrt == 0 and left + sqrt - 1 <= right:
            max_now = max(max_now,max_range[div])
            min_now = min(min_now,min_range[div])
            left += sqrt
        else:
            max_now = max(max_now,X[left])
            min_now = min(min_now,X[left])
            left += 1
    return max_now,min_now

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

sqrt = int(pow(N,0.5))
if sqrt ** 2 < N:
    sqrt += 1

temp = N // sqrt
max_range = [None] * (temp)
min_range = [None] * (temp)

for i in range(temp):
    s,e = sqrt * i,sqrt * (i+1)
    max_range[i] = max(A[s:e])
    min_range[i] = min(A[s:e])

for _ in range(K):
    al,ar,bl,br = map(lambda x:int(x)-1,input().split())
    
    a_max_now,a_min_now = comparison(A,max_range,min_range,sqrt,al,ar)
    b_max_now,b_min_now = comparison(A,max_range,min_range,sqrt,bl,br)
    a_score = a_max_now - a_min_now
    b_score = b_max_now - b_min_now
    
    if a_score > b_score:
        print('A')
    elif a_score < b_score:
        print('B')
    else:
        print('DRAW')
VBA
Sub query_primer__range_of_score()

    NK = Split(Cells(1, 1), " ")
    N = Val(NK(0))
    k = Val(NK(1))
    
    Dim a()
    a = Range(Cells(2, 1), Cells(N + 1, 1))
    
    sqrt = Application.WorksheetFunction.RoundUp(Sqr(N), 0)
    div = Application.WorksheetFunction.RoundUp(N / sqrt, 0)
    
    Dim range_max() As Long
    Dim range_min() As Long
    Dim temp_max() As Long
    Dim temp_min() As Long
    ReDim range_max(1 To div)
    ReDim range_min(1 To div)
    ReDim temp_max(1 To sqrt)
    ReDim temp_min(1 To sqrt)
    
    For i = 1 To div
        s = sqrt * (i - 1) + 1
        e = sqrt * i
        ad = 1
        For j = s To e
            If j > N Then
                temp_max(ad) = 0
                temp_min(ad) = 100000
            Else
                temp_max(ad) = a(j, 1)
                temp_min(ad) = a(j, 1)
            End If
            ad = ad + 1
        Next
        range_max(i) = Application.WorksheetFunction.Max(temp_max)
        range_min(i) = Application.WorksheetFunction.Min(temp_min)
    Next
    
    For i = 1 To k
        in_ = Split(Cells(i + N + 1, 1), " ")
        a_left = Val(in_(0))
        a_right = Val(in_(1))
        b_left = Val(in_(2))
        b_right = Val(in_(3))

        a_now = comparison(a, range_max, range_min, sqrt, a_left, a_right)
        b_now = comparison(a, range_max, range_min, sqrt, b_left, b_right)
        a_score = a_now(0) - a_now(1)
        b_score = b_now(0) - b_now(1)
        
        If a_score > b_score Then
            Debug.Print "A"
        ElseIf a_score < b_score Then
            Debug.Print "B"
        Else
            Debug.Print "DRAW"
        End If
        
    Next

End Sub
Private Function comparison(X, range_max, range_min, sqrt, left_, right_)

    max_now = 0
    min_now = 100000
    div = Int(left_ / sqrt) + 1
    Do While left_ <= right_
        If left_ Mod sqrt = 1 And left_ + sqrt - 1 <= right_ Then
            max_now = Application.WorksheetFunction.Max(max_now, range_max(div))
            min_now = Application.WorksheetFunction.Min(min_now, range_min(div))
            left_ = left_ + sqrt
        Else
            max_now = Application.WorksheetFunction.Max(max_now, X(left_, 1))
            min_now = Application.WorksheetFunction.Min(min_now, X(left_, 1))
            left_ = left_ + 1
        End If
    Loop
    
    comparison = Array(max_now, min_now)
    
End Function

いつもの如く、境界値データテストでは（最初から Debug.Print 無し）、約 128 秒。

最後に

Python でも、7 秒程度かかっていた模様なので、最初から Debug.Print 無しで回してみましたが、2 分ちょっとなら悪くないスコアな気がしました。こういうやり方もあるんだなぁ、と大変勉強になりました。

これで「クエリメニュー」が終了です。最後の方は B ランク問題や A ランク問題ばかりになって、なかなか面白かったです。B ランク以上の問題に挑戦していたのに、次は「B ランクレベルアップメニュー」に挑戦してみたいと思います。

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

Python学習,Python,paiza

Posted by LeoSaki