Product Price

2 secs 1024 MB

Ang107

問題

提出

テストケース

解説

Python の input 関数の返り値は str 型であることに注意してください。

一行目の入力を二つの整数として受け取るには map(int,input().split())
二行目以降の入力を整数型の要素を持つリストとして受け取るには list(map(int,input().split()))

を使用することができます。

この問題の肝は、商品番号と代金の関係をどのように管理するか、ということです。
一つ目に、リストのインデックス番号を商品番号として、要素を代金として管理する方法が考えられますが、この問題では適していません。何故なら、商品番号は最大で $10^9$ であり、要素数が $10^9$ のリストを初期化すると、時間計算量・空間計算量共にとても大きくなってしまうからです。（簡単に言うと、処理に時間が長くかかり、必要なメモリサイズも巨大になってしまいます。）
そこで、制約の $N$ の値に注目すると、 $2 \leq N \leq 100$ となっており、扱っている商品の種類は高々 $100$ 種類しか無いことが分かります。そこで、 dict 型の出番です。 list 型では、インデックスは $0$ から順に並べる必要があるのに対し、 dict 型では必要な分だけの key , value の組を管理することができます。
よって、商品番号を key , それに対応する代金を value として dict で管理すればこの問題を解くことができます。また、クエリの処理に関しては、問題に書かれている通りの処理を行えば良いです。

以下は Python の実装例です。

xxxxxxxxxx
 
N, Q = map(int, input().split())
S = list(map(int, input().split()))
P = list(map(int, input().split()))
​
# 商品番号をkey, 代金をvalueとする辞書の初期化
price = {}
for i in range(N):
    price[S[i]] = P[i]
​
# 答えのリストの初期化
ans = []
​
# Q個のクエリを順に受け取る。
for _ in range(Q):
    query = list(map(int, input().split()))
    # 一種類目のクエリが与えれた場合の処理
    if query[0] == 1:
        a, x = query[1:]
        price[a] = x
​
    # 二種類目のクエリが与えれた場合の処理
    elif query[0] == 2:
        a, y = query[1:]
        price[a] -= y
​
    # 三種類目のクエリが与えれた場合の処理
    elif query[0] == 3:
        a, b = query[1:]
        # 代金の比較
        if price[a] > price[b]:
            ans.append(a)
        elif price[a] < price[b]:
            ans.append(b)
        elif price[a] == price[b]:
            ans.append("Equal")
​
# 答えの出力
for i in ans:
    print(i)
​