第132回【Python】ソートと検索、ソートと検索 (query)

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

はじめに

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

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

キャンプ場で急な仕事が入って、慌てて作業をしていたところ、充電が切れました。そういう日に限って電源ケーブルを忘れているわけです。電気屋は遥か遠く、自宅に帰るわけにもいかない。謝り倒して期限を延ばしてもらいましたが、そもそも休日なのに・・・。

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

ソートと検索

paiza 君のクラスには paiza 君を含めて N + 1 人の生徒がいます。paiza 君の身長は P cm です。paiza 君以外の N 人の生徒の身長は A_1, … ,A_N です。
今日、クラスに身長 X cm の転校生が 1 人やってきました。転校生が入ってきた後 N + 2 人のクラス全員で背の順で並んだ時、 paiza 君は前から何番目に並ぶことになるでしょうか。

なお、背の順の先頭の生徒を前から 1 番目の生徒とします。

N X P
A_1
...
A_N

・1 行目では、クラスの paiza 君以外の生徒数 N と転校生の身長 X と paiza君の身長 P が与えられます。
・続く N 行では、N 人の生徒の身長が与えられます。

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

・1 ≦ N ≦ 100,000
・100 ≦ X , P ≦ 200
・100 ≦ A_i ≦ 200 (1 ≦ i ≦ N)
・転校生を含め、クラスの中で身長が P cm の生徒は paiza 君のみであることが保証されている

入力例

3 188 174
181
177
113

出力例

2

最大 10 万人のクラスとか、もうそれは町じゃなかろうか。町民全員で身長を計りっこしているとか、微笑ましい・・・ですかね。

Python
N,X,P = map(int,input().split())
A = [int(input()) for _ in range(N)]
A.append(X)
A.append(P)
print(sorted(A).index(P) + 1)
VBA
Sub query_primer__sort_find_single()

    NXP = Split(Cells(1, 1), " ")
    N = Val(NXP(0))
    x = Val(NXP(1))
    P = Val(NXP(2))
    
    Dim A() As Integer
    ReDim A(N + 1)
    A(0) = x
    A(1) = P
    
    For i = 2 To N + 1
        t = Cells(i, 1)
        A(i) = t
    Next
    
    Call QuickSort(A, LBound(A), UBound(A))
    
    For i = LBound(A) To UBound(A)
        If A(i) = P Then
            Debug.Print i + 1
            Exit For
        End If
    Next
    
End Sub
Private Sub QuickSort(ByRef argAry() As Integer, ByVal lngMin As Long, ByVal lngMax As Long)
 
    Dim i As Long
    Dim j As Long
    Dim vBase As Variant
    Dim vSwap As Variant
    vBase = argAry(Int((lngMin + lngMax) / 2))
    i = lngMin
    j = lngMax
    Do
        Do While argAry(i) < vBase
            i = i + 1
        Loop
        Do While argAry(j) > vBase
            j = j - 1
        Loop
        If i >= j Then Exit Do
        vSwap = argAry(i)
        argAry(i) = argAry(j)
        argAry(j) = vSwap
        i = i + 1
        j = j - 1
    Loop
    If (lngMin < i - 1) Then
        Call QuickSort(argAry, lngMin, i - 1)
    End If
    If (lngMax > j + 1) Then
        Call QuickSort(argAry, j + 1, lngMax)
    End If
     
End Sub

VBA でも境界値データで 1 秒は軽くきることが出来ます。ちょっと感動。

ソートと検索 (query)

paiza 君のクラスには paiza 君を含めて N + 1 人の生徒がいます。paiza 君の身長は P cm で、他の N 人の生徒の身長はそれぞれ A_1 … A_N です。
このクラスには次のようなイベントが合計 K 回起こります。
それぞれのイベントは以下のうちのいずれかです。

・転校生がクラスに加入する
・全員で背の順に並ぶ

全員で背の順で並ぶイベントが起こるたびに、そのとき paiza 君は前から何番目に並ぶことになるかを出力してください。

N K P
A_1
...
A_N
event_1
...
event_K

・1 行目では、paiza 君を除いたクラスの人数 N と起こるイベントの回数 K と paiza君の身長 P が与えられます。
・続く N 行では、初めにクラスにいる N 人の生徒の身長が与えられます。
・続く K 行では、起こるイベントを表す文字列が与えられます。

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

・1 ≦ N , K ≦ 100,000
・100 ≦ P ≦ 200
・100 ≦ A_i ≦ 200 (1 ≦ i ≦ N)
・転校生を含め、クラスの中で P cm の生徒は paiza 君のみであることが保証されている
・event_i (1 ≦ i ≦ K) は以下のいずれかの形式で与えられる。

join num

身長 num(cm) の生徒がクラスに加入したことを表す。

sorting

生徒が背の順に並ぶことを表す
この入力が与えられるたび、paiza 君が背の順で前から何番目に並ぶことになるかを出力してください。

入力例

3 3 176
118
174
133
join 137
join 177
sorting

出力例

5

100 cm ～ 200 cm という狭い範囲で最大 10 万人いても、paiza 君は唯一無二の身長を持っているなんて凄いじゃないですか！

Python
N,K,P = map(int,input().split())
A = [int(input()) for _ in range(N)]
A.append(P)
ans = sorted(A).index(P) + 1

for _ in range(K):
    s = input().split()
    event = s[0]
    if event == 'sorting':
        print(ans)
    else:
        t = int(s[1])
        if P > t:
            ans += 1
VBA
Sub query_primer__sort_find_multi()

    NKP = Split(Cells(1, 1), " ")
    N = Val(NKP(0))
    K = Val(NKP(1))
    P = Val(NKP(2))
    
    Dim A() As Integer
    ReDim A(N)
    A(0) = P
    
    For i = 1 To N
        t = Cells(i + 1, 1)
        A(i) = t
    Next
    
    Call QuickSort(A, LBound(A), UBound(A))
    
    ans = 0
    For i = LBound(A) To UBound(A)
        If A(i) = P Then
            ans = i + 1
            Exit For
        End If
    Next
    
    For i = 1 To K
        s = Split(Cells(i + N + 1, 1), " ")
        eve = s(0)
        If eve = "sorting" Then
            Debug.Print ans
        Else
            t = Val(s(1))
            If P > t Then
                ans = ans + 1
            End If
        End If
    Next
    
End Sub
Private Sub QuickSort(ByRef argAry() As Integer, ByVal lngMin As Long, ByVal lngMax As Long)
 
    Dim i As Long
    Dim j As Long
    Dim vBase As Variant
    Dim vSwap As Variant
    vBase = argAry(Int((lngMin + lngMax) / 2))
    i = lngMin
    j = lngMax
    Do
        Do While argAry(i) < vBase
            i = i + 1
        Loop
        Do While argAry(j) > vBase
            j = j - 1
        Loop
        If i >= j Then Exit Do
        vSwap = argAry(i)
        argAry(i) = argAry(j)
        argAry(j) = vSwap
        i = i + 1
        j = j - 1
    Loop
    If (lngMin < i - 1) Then
        Call QuickSort(argAry, lngMin, i - 1)
    End If
    If (lngMax > j + 1) Then
        Call QuickSort(argAry, j + 1, lngMax)
    End If
     
End Sub

このやり方で回した VBA は、境界値データで約 1.2 秒（Python は 0.25 秒）。試しに、1 回ごとに並べ替えを行う 1 問目の方法を試したところ、約 62 秒。

最後に

データの持ち方を工夫することで速度が大幅に変わる。これに気づくかどうかは別問題。問題を一生懸命読んで、馬鹿正直に解いて、タイムアウトを喰らったのは誰か。LeoSaki（旦那）です。

どうしても、この後にどんな作業をするか、を考えたときに、それならば並べ替えられてないとダメじゃないだろうか、って思ってしまいます。問われていることにだけ答えればいいんだ、と割り切るのに時間がかかる。正直者だから。

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

PythonPython,paiza,学習

Posted by LeoSaki