LoginSignup
0
0

More than 1 year has passed since last update.

ABC202 C - Made Up を解いてみた

Last updated at Posted at 2021-09-06

abc202_1.png

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

abc202_2.png

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)
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0