今日プロって国語力
今日も今日とて、プログラミング。最近は大学の課題が忙しくなってきて、テキパキやっていきたい。
今日やったのは、AtCoder -ABC202- のC問題 【Made up】
「ふむふむ、これなら解けそうか?」
と考えて、とりあえずコードを書いてみることに。
「む」
for文の中にfor文を入れてしまうコードに。その結果案の定、【TLE(時間かかりすぎ)】
だよね\(^o^)/
ということで、いつもどおり、調べます。
復習
本日の参考記事はこちら
この方(著者 うにさん)の記事はまじでわかりやすい!!!
記事によると、
さて、(i,j) の組は N2N2 通りあります。200000 ですから、全部試すと、最大 400 億通りになるのでTLEになります。
この問題はC問題で極めて頻出のパターン問題で、『同じ値の要素の数をカウントする』と計算量を O(N)O(N) に落とすことができます。
全ての組み合わせを試すのですから、A,B,CA,B,C の要素がどういう順番で出てくるかはどうでもよくて、どの値が何回出てくるかだけで答えが決まるからです。
要するに、順序関係ないなら、for文を複数回やる必要ないよねっていう話
これまで、計算量の落とし方についての疑問点がやっと解決できました!
ここで、使うライブラリは、 collectionモジュールのCounter
「やっぱりcollectionモジュールのCounterは神ライブラリか!」
ということで、記事の内容を参考にコードを書いてみると
from collections import Counter
n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
count_A = Counter(A) # Counter()の()内のリスト内の要素が何回出てくるか表す
# Counter({2: 2, 1: 1}) みたいに出てくる
ans = 0
for i in C: # Cの要素をiに代入し、Bcjを表している
y = i - 1
k = B[y] # B_{C_j} の値です
ans += count_A[k] # A に k が出現する回数だけ答えに足します
print(ans)
ほぼ、同じコードですね笑
そーすると、無事成功!!!ひゃっほー!!!
本当にうにさん(参考記事の著者)の記事はどれも丁寧かつ、読みやすく、python初学者には超おすすめ!!
(勝手にurlとか貼っていいのかわからなかったので、今回はうにさんのtwitterのアカウントは貼ってないので、各自で調べてみてください)
これからも、過去問を中心に計算量のお勉強してまいります!!!
大事なのは、読解力
AtCoderは文章を読み解く力、読み替える力が必須
自分で変換する力が足りない・・・・
ただ与えられた情報だけで手を動かすと詰む。。。。
こればっかりは、量をこなすしかないか・・・
がんばります。同志の方や、先駆者の方いらっしゃいましたら、連絡お待ちしています。
最後に
読んでくださり、ありがとうございます!よろしければtwitterフォローよろしくお願いいたします!!
この記事が気に入ったらサポートをしてみませんか?