今日プロって国語力

今日も今日とて、プログラミング。最近は大学の課題が忙しくなってきて、テキパキやっていきたい。

今日やったのは、AtCoder -ABC202- のC問題 【Made up】

C - Made Up

「ふむふむ、これなら解けそうか？」

と考えて、とりあえずコードを書いてみることに。

「む」

for文の中にfor文を入れてしまうコードに。その結果案の定、【TLE(時間かかりすぎ)】

だよね＼(^o^)／

ということで、いつもどおり、調べます。

復習

本日の参考記事はこちら

【AtCoder解説】PythonでABC202のA,B,C,D問題を制する！ - Qiita

この方（著者 うにさん）の記事はまじでわかりやすい！！！

記事によると、

さて、(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フォローよろしくお願いいたします！！

Tweets by sugiza_k