2重ループ回避とかlambdaとか（ABC200C）
こんにちは。もらい物のいわしせんべいが美味しいです。あまりにも美味しいので今度自分で買おうか迷っています。
今回は実際に参加していくつものTREを出して(WAも出してる)終了2分前でなんとかACできました。Cは計算量の関係でTREばっか出るからいつも泣いてます。ちなみに今回の解法は公式とそこまで変わりません。
今回の問題はこちらです。
200という整数が大好きなりんごさんのために、次の問題を解いてください。
N個の正整数からなる数列Aが与えられるので、以下の条件をすべて満たす整数の組（i,j）の個数を求めてください。
1≦i<j≦N
Aj-Aiが200の倍数になる。 （上記サイトより引用）
自分の解法
最初に失敗したやつ。
N=int(input())
A=sorted(map(int,input().split()))
ans=0
for i in range (N-1):
for j in reversed(range(i+1,N)):
if (A[j]-A[i])%200==0:
ans+=1
elif A[j]-A[i]<200:
ans+=A[i:N].count(A[i])-1
break
print(ans)一回確認漏れ防止のために入れてたprint(A[j],A[i])を消し忘れてWAになったのはただのやらかしです。
新知識：
forが in reversed()で逆順から回せる
countはA[x:y].count()にすれば範囲指定してカウントすることができる
差が200以下なら＝0になる事例をcountで数えてからbreakという形をとれば少しは計算量減るかなって思ったけどダメでしたね。そういえばA[j:N]のスライスは計算量普通に大きかったっけ。
AC解法
N=int(input())
A=list(map(int,input().split()))
A=list(map(lambda x:x%200,A))
ans=0
for i in range(0,200):
K=A.count(i)
if K<2:
pass
else:
D=K*(K-1)
D//=2
ans+=D
print(ans)200で割ったあまりが同じ数同士なら差が200の倍数になることに気づいて慌てて組み立てました。forで余りが0～199まで全部愚直に調べたけどもっといい方法あったんですかね？わからん…リストをセットに変換したのを作るとか考えましたが時間がないのでやってません。
当時は焦っていてcombinationの計算のプログラムをwebから引っ張ってきましたが、結局よくよく考えたらK(K-1)/2で十分でした。あとどっちみちK*(K-1)はK(余りがiになる数の個数)が1か0なら0になるからif文要らなかったかもしれないですね。
参考にしたサイト貼っときます。
それから、lambdaの使い方も忘れてたので調べなおしました。
list(map(lambda x:(やりたい処理),(参照元のリスト名)))
でリスト内の数にまとめて処理を行える。
計算量についてやっと少し把握した
いままでずっと計算量に関してはよくわかってなくて、リストを変にいじくるとめっちゃ重くなるって認識しかありませんでした。
ですがコンテスト中にどうやったらTREをなくせるのか、とひたすら検索していたらすごくいいサイトがありました。感謝。
2重ループなど、多重ループはどうしても重くなるみたいですね。あと10の8乗超えるとTREの可能性が高くなることもわかりました。
今日学んだこと
#forも逆順から回せる
for i in reversed(range()):
#スライス使うと指定範囲内でのcount可能
A[a:b].count(x)
#mapとlambda使ってリスト内の要素に処理ができる
A=list(map(lambda x:x 処理,A))この記事が気に入ったらサポートをしてみませんか？