トップページ -> AOJの解答例 -> ITP2_8の解答例

ITP2_8の解答例(Python)

辞書に対して操作を行う問題です．

1. ITP2_8_A: Map: Search

入力に対して辞書の操作を行う問題です．


# ITP2_8_A
n = int(input())
D = {}
for _ in range(n):
    query = input().split(" ")
    # insert
    if query[0] == "0":
        D[query[1]] = query[2]
    # get
    else:
        print(D[query[1]])

2. ITP2_8_B: Map: Delete

Aの操作に加えてdeleteも行います．


# ITP2_8_B
n = int(input())
D = {}
for _ in range(n):
    query = input().split(" ")
    # insert
    if query[0] == "0":
        D[query[1]] = query[2]
    # get
    elif query[0] == "1":
        if query[1] in D.keys():
            print(D[query[1]])
        else:
            print(0)
    # delete
    else:
        if query[1] in D.keys():
            D.pop(query[1])

3. ITP2_8_C: Map: Range Search

Bの操作に加えてdumpも行います．普通にやると時間制限が厳しいのでITP2_6_Dと同じ方法で二分探索を使ってlower bound と upper boundを求めます．ここで使っているbinary_search(n,N)はbisect.bisect_left(N,n)と同じです．【外部サイト】bisect --- 配列二分法アルゴリズム


# ITP2_8_C

# 二分探索の関数 lower_bound
def binary_search(n,N):
    left = 0
    right = len(N)-1
    lower_bound = len(N) # 存在しない場合はNの長さ
    while left <= right:
        half = int((right + left)/2)
        # n が half より左側にある (一致しても同じ数字が左側にあるかもしれないことに注意)
        if N[half] >= n:
            right = half-1
            lower_bound = half # lower_boundを更新
        # n が half より右側にある
        elif N[half] < n:
            left = half+1
            
    return lower_bound

n = int(input())
D = {}
is_sorted = False
for _ in range(n):
    query = input().split(" ")
    # insert
    if query[0] == "0":
        D[query[1]] = query[2]
        is_sorted = False
    # get
    elif query[0] == "1":
        if query[1] in D.keys():
            print(D[query[1]])
        else:
            print(0)
    # delete
    elif query[0] == "2":
        if query[1] in D.keys():
            D.pop(query[1])
            is_sorted = False
    # dump
    else:
        L,R = query[1],query[2]
        if not is_sorted:
            keys_list = list(D.keys())
            keys_list.sort()
            is_sorted = True
        
        lower_bound = binary_search(L,keys_list)
        upper_bound = binary_search(R+"a",keys_list) # 辞書順で1個後ろは a を足せばいい
        
        for i in range(lower_bound,upper_bound):
            key = keys_list[i]
            print(key,D[key])

4. ITP2_8_D: Multi-Map

今までと異なりキーの重複を許す辞書に関してです． Cとほとんど同じですが，重複を許すのでD[key] = [item1, item2, ...] のように管理しました．


# ITP2_8_D
# D[key] = [item1, item2, ...] のように管理する

# 二分探索の関数 lower_bound
def binary_search(n,N):
    left = 0
    right = len(N)-1
    lower_bound = len(N) # 存在しない場合はNの長さ
    while left <= right:
        half = int((right + left)/2)
        # n が half より左側にある (一致しても同じ数字が左側にあるかもしれないことに注意)
        if N[half] >= n:
            right = half-1
            lower_bound = half # lower_boundを更新
        # n が half より右側にある
        elif N[half] < n:
            left = half+1
            
    return lower_bound

n = int(input())
D = {}
is_sorted = False
for _ in range(n):
    query = input().split(" ")
    # insert
    if query[0] == "0":
        # キーが存在しなければ D[key] = [] で初期化
        if query[1] not in D.keys():
            D[query[1]] = []
        D[query[1]].append(query[2])
        is_sorted = False
    # get
    elif query[0] == "1":
        if query[1] in D.keys():
            for item in D[query[1]]:
                print(item)
    # delete
    elif query[0] == "2":
        if query[1] in D.keys():
            D.pop(query[1])
            is_sorted = False
    # dump
    else:
        L,R = query[1],query[2]
        if not is_sorted:
            keys_list = list(D.keys())
            keys_list.sort()
            is_sorted = True
        
        lower_bound = binary_search(L,keys_list)
        upper_bound = binary_search(R+"a",keys_list) # 辞書順で1個後ろは a を足せばいい
        
        for i in range(lower_bound,upper_bound):
            key = keys_list[i]
            for item in D[key]:
                print(key,item)

<- 前へ戻る【目次に戻る】次へ進む ->