ABC202 C - Made Up を解いてみた

6570 ワード
AtCoder Python AtCoderBeginnerContest Python テキストリンク

いつもの通り i, j をそれぞれ for でネストして全探索したら
TLE で落ちてしまう。とりあえずサンプルを眺める

for 文で B[C[i]-1] について i で回してみよう。
その時にB[C[i]-1] と同じ値が 配列 A の中に何個あるのか数えれば良さそう。
ってことは事前に辞書で A について整理しておけば解決すると思った。

MadeUp.py
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))

#A の中に何の要素が何個ずつ入っているのか管理
dic = {}
for i in range(N):
    if A[i] not in dic:
        dic[A[i]] = 0
    dic[A[i]] += 1

score = 0
for i in range(N):
    try:
        score += dic[B[C[i]-1]]#該当したら、その個数を積み上げる
    except:
        pass#　B[C[i]-1] が辞書内に存在しないと言われたら pass する
print(score)

atcoder problem 灰色〇で半分くらいのレベルだったら C 問題でも何とか。。
ちょっとずつレベルを上げていきたいところですね。

おまけ

間違っても以下のようにしない方がいいと思います。

MadUp_TLE.py
N = int(input())
A = list(map(str,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))

A = "".join(A)
score = 0
#以下のように O(N^2) となるので TLE となります。
for i in range(N): #=> N
    score += A.count(str(B[(C[i])-1])) # => N : 
                                       # count は都度 A の中を要素数(N) だけ探索してカウントするため
                                       # 計算量は N と認識されます。
print(score)