第135回【Python】銀行

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

はじめに

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

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

いろいろと策を講じていて、問題が起こらないようにルール作りをして、大きな改革を続けてきましたが、それでもミスは発生するものです。そんなときは、誠実さをもってお詫びし、新たな再発防止策を考える必要があります。それをいかにスピード感を持って実行するかが、今、求められていることだと思っています。

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

銀行

2xxx年に paiza が設立した paiza 中央銀行に勤務する pai沢直樹は、故障した ATM の対応として、お金を引き出したい会社と電話をして、会社名が銀行の名簿に登録されており、かつ、会社側が会社の口座の暗証番号を正しく言えた場合にのみ現金を支払い、それを記帳するという業務を任されていました。

銀行に登録されている会社名とその口座の暗証番号と残高についての情報、また、直樹の電話の情報が与えられるので、全ての取引が終了した後の全ての会社の残高を出力してください。

N K
C_1 P_1 D_1
...
C_N P_N D_N
G_1 M_1 W_1
...
G_K M_K W_K

・1 行目では、銀行に登録されている会社の数 N と行った取引の数 K が与えられます。
・続く N 行のうち、i 行目では、i 番目に登録されている会社名 C_i とその口座の暗証番号 P_i と残高 D_i が与えられます。
・続く K 行のうち、i 行目では、i 回目の取引を行おうとした会社の名前 G_i と、その人が言った暗証番号 M_i , 引出そうとした金額 W_i が与えられます。

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

・1 ≦ N ≦ 100,000
・1 ≦ K ≦ 100,000
・C_i は 20 文字以下の文字列 (1 ≦ i ≦ N)
・P_i , M_j は 0000 〜 9999 のいずれかの数値列 (1 ≦ i ≦ N , 1 ≦ j ≦ K)
・1 ≦ D_i ≦ 1,000,000,000 (1 ≦ i ≦ N)
・G_i は C_j のいずれか (1 ≦ i ≦ K , 1 ≦ j ≦ N)
・1 ≦ W_i ≦ 1,000,000 (1 ≦ i ≦ K)
・C_i ≠ C_j (i ≠ j)
・取引の結果、全ての会社の残高が負にならないことが保証されている。

入力例

3 5
A 0000 10000
B 1234 23456
C 5678 98765
A 0101 1000
B 1234 1000
C 5678 90000
A 0000 200
B 1233 10000

出力例

A 9800
B 22456
C 8765

pai 沢直樹すげーよ。10 万社におよぶ会社の暗証番号と口座に入っている金額の管理を行うのか。最大 10 万回実施してミスなくできたら、そりゃ超有能なんだろうけれど、それ以前に、この銀行とは取引したくねぇなぁ。

Python
N,K = map(int,input().split())
banks = {}

for _ in range(N):
    bank,idnum,money = input().split()
    banks[(bank,idnum)] = int(money)
    
for _ in range(K):
    bank,idnum,money = input().split()
    money = int(money)
    
    if (bank,idnum) in banks.keys():
        banks[(bank,idnum)] -= money
        
for k,v in banks.items():
    print(k[0],v)

模範解答では、銀行名を key に、暗証番号と残高をタプルとして value に設定していた。ただ、調べたところ、辞書型での in 演算子の計算量は O(1) のようなので、これでも良いと思います。なお、paiza の用意してくれている境界値データでのテストでは、模範解答とほぼ同じ速度が得られました。

VBA
Sub query_primer__bank()

    NK = Split(Cells(1, 1), " ")
    N = Val(NK(0))
    k = Val(NK(1))

    Dim dic As Object
    Set dic = CreateObject("Scripting.Dictionary")
    
    For i = 1 To N
        CPM = Split(Cells(i + 1, 1), " ")
        c = CPM(0)
        p = CPM(1)
        m = Val(CPM(2))
        dic.Add c, Array(p, m)
    Next
    
    For i = 1 To k
        CPM = Split(Cells(i + N + 1, 1), " ")
        c = CPM(0)
        p = CPM(1)
        m = Val(CPM(2))
        If dic(c)(0) = p Then
            arr = Array(p, dic(c)(1) - m)
            dic(c) = arr
        End If
    Next
    
    For Each c In dic
        Debug.Print c & " " & dic(c)(1)
    Next
    
End Sub

いつもの如く、境界値データテストで全データ出力まで行って、約 52 秒。出力しなければ、約 1.3 秒。

最後に

Python の辞書型の in 演算子の計算量は O(1) であるということを覚えておいて損はなさそう。ちなみに、リスト、タプルは O(N)、集合は O(1) のようです。

VBA の場合は、連想配列の Value に配列を置くことができることが判明。最初は Python 同様に Key に配列をセットしようとしたのだけれど、ダメでした。しかし、Value に設定した配列の中身を書き換えることが出来ず、配列ごと入れ替えるという力業で解決するに至りました。これで良いのかどうか。速度的には十分実用レベルとは思うのだけれど。

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

Pythonpaiza,学習,Python

Posted by LeoSaki