AtCoder Beginner Contest (ABC) １９４ C問題解いてみた
こんにちは。
メリーです。
バイトで手首を酷使したせいか、手首が痛いです。
バイトが終わってもブログの更新で手首を使うので腱鞘炎になるのでしょうか。
腱鞘炎になったことが無いのでどれだけ辛いかとかはわからないんですけどね。
今日は昨日の続きのC問題編やってきます。
言語はPythonで、ｐypyで提出してます。
A,B問題は以下の記事で。
目次
C問題 問題編
問題文
とりあえずNが10^5程度なので、問題文通りに実装してみよう！！
ってことで実装したのが以下のコード
n = int(input())
a = list(map(int,input().split()))
ans = []
for i in range(1,n):
for j in range(i):
ans += (a[i]-a[j])**2
print(ans)
問題分に載っているΣの式そのまんまですね。
テストケースもACになったのでこれでいけるっしょ、と思い提出。
まあ、案の定TLEになりました。
まぁ、ループ回数結構あるもんね・・・。
解決方法が一向にわからなかったので、素直に検索して答えを見ました。
これがdifficulty400超えて無いんですもんね。
こんな感じの問題を解けるようにならないと茶色になれないのか・・・（TT）
C問題 解決編
というわけで解決編です。
図らずとも推理小説のような編分けになってしまった・・・
公式解説を見てみると、２通りの解説がありました。
まずは制約、
│A│ ＜＝ 200
を利用する方法です。
Aの種類を全探索すれば計算量に引っかからないよね！！
という理論ですね。はい。
というわけで実際のコードです。
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
cnt = Counter(a)
ans = 0
for x in range(-200, 201):
for y in range(x + 1, 201):
cx = cnt[x]
cy = cnt[y]
ans += cx * cy * (x - y) ** 2
print(ans)
cntというリストに各数の要素の個数を入れてます。
cntの中に無い数を指定すると0を返すので、エラーしないです。便利。
そして二重ループを回します。
ただし、x < y にしないと二重に計算することになるので注意です。
また、x = y の場合は０になるので、数えなくてOKです。
cxには要素xの個数が、cyには要素yの個数が入ります。
存在しない要素の個数は０が入ります。(よってその後のansに追加する値が何をかけても０になる。)
最後にansに
（x-y）^2 * (cx * cy)
↑差の２乗 ↑要素の組み合わせの個数
を追加します。
そして最後にansを表示して終わり！
ということですね。
そしてもう一つの方法は、式変形をする方法です。
問題文にあるΣの式を式変形していくと
(n) n
ｎ ∑ ( Ai^2 - ( ∑ Ai^2 ) )
(i = 1) (i = 1)
となるようです。
この式は計算量O（N）で計算できるらしいです。
算数つよつよの民はこの方式でできるみたいですね。（ハナホジ）
僕は算数よわよわなので無理です。
おとなしく１番めの方法でやります。
ということでした！！
ではまた！！
