2020/04/12 atcoderをやっていきます。メールが届いたらやるルール。書くまで時間がかかったのは秘密。計算時間時間についてやったこと。
結果
得点: 300 正解: A,B問題
所感
前回の反省を生かして早めに待機。これはまず良い。(アクシデントによりちょい遅刻したけど)。
A, B, Cまでは「ふふ～ん」みたいな感じで解いていきました。が。Cで計算時間オーバー。「え、計算時間てどうやってどうやって短くするの！？むずっ。」今回はC問題に注目する。
+ 毎回提出して生き恥をさらさなくても「コードテスト」で実験すれば良いらしいということを発見した。
C問題について。
C - Sum of gcd of Tuples (Easy)
(Easy)ってのは煽ってるな。ワイの回答。(python3.8)
- コード長 277 Byte
- 実行時間 2205 ms
- メモリ 9196 KB
import math
K=int(input())+1
sum=0
for a in range(1,K):
for b in range(1,K):
for c in range(1,K):
gcd1 = int(math.gcd(a,b))
gcd2 = int(math.gcd(b,c))
gcd = int(math.gcd(gcd1,gcd2))
sum = sum+gcd
print(sum)無駄無駄無駄無駄！！！という感じ。
すぐ思いつく範囲で計算時間を減らしてみる
gcdは二回で十分だということに気付いた。
from math import gcd
K=int(input())+1
sum=0
for a in range(1,K):
for b in range(1,K):
for c in range(1,K):
AB = gcd(a,b)
ABC = gcd(AB,c)
sum = sum+ABC
print(sum)結果: (input 200)
| 項目 | 元 | 新 |
| 実行時間 [ms] | 5604 | 3131 |
| メモリ [KB] | 2924 | 2912 |
| 出力 | 10813692 | 10813692 |
意外に減る。でもすべてのテストで2000ms以内じゃないといけないらしく、正解の基準を満たせていない。(どんな内容のテスト入力なのかは知らない。)
以降はこのコードを「新」と呼称している。
いろんな人を参考にする
1. あらかじめ
$$a,b,c={1,2,...,K},(1 \leq K \leq 200)$$
上を満たすすべての組み合わせの最大公約数の和をあらかじめ数値で持っておく場合。#11846022、#11854269など、似た回答が複数あった。けど数値で書いてある事に驚いて「暗算で出来るのか...!?要素が同じなら一緒だからinput Kで選べるぞってこと？分からーん。 すげえバケモンか」...と思ったけど。
計算時間がかかることが分かり次第、提出用コードとローカル用コードに分けたのかもしれない。K=1~200ですべて計算してKに対応する表にして、提出用コードではそれを引き渡すだけ。かしこっ。実行時間が40msくらいの人たちも同じ感じだった。すごい。
| 項目 | スコア |
|---|---|
| 実行時間 | 20 ms |
| メモリ | 9372 KB |
| 出力 | 10813692 |
参考: 提出 #11824568 他 (結果はだれでも見れる)
2. 工夫
では (良い意味で) ちゃんと計算していそうな人は何をやっているのか。ということでいくつか見た中で目についたものを (かなり)参考にした新コード。
from math import gcd
K = int(input())
out = 0
count = [0]*K
gcds = [[0]*K for i in range(K)]
for i in range (1,K+1):
for j in range(1,+K+1):
value = gcd(i,j)
gcds[i-1][j-1]=value
count[value-1]+=1
for i in range(1,K+1):
for j in range(1,K+1):
out +=gcds[i-1][j-1]*count[j-1]
print(out)上のループは変数が２個の場合の1~Kまでのすべての組み合わせ最大公約数をgcdsに格納して、gcdごとにその回数をcountに格納している。言い換えればこれは、AとBに関してだけのすべてのgcdと回数の表を作成している。なぜならABでもBCでもCAでも条件は同じで、同じバリエーションしか作れないから。
下のループでは、gcd(A,B)とCの最小公倍数の計算をしているが、このときgcd(A,B)は同じ結果をcount回出すからcount倍している。ちなみにgcdを呼ぶ回数はK=2の時16回から8回に、K=200の時160000回から80000回に減らせる。
この実行時間の変化は驚き。
| 項目 | スコア |
|---|---|
| 実行時間 | 38 ms |
| メモリ | 3292 KB |
| 出力 | 10813692 |
参考: 提出 #11819140 など。ありがとうございました。
3. ユークリッドの互除法
ここで公式の解説を見てみる。ユークリッドの互除法をやりなさいとのこと。そんなもんは言われなくとも、と思いつつ「新」をベースにやってみた。
def mygcd(p,q):
if p % q ==0:
return q
else :
return mygcd(q,p%q)
K=int(input())+1
sum=0
for a in range(1,K):
for b in range(1,K):
for c in range(1,K):
AB = mygcd(a,b)
ABC = mygcd(AB,c)
sum = sum+ABC
print(sum)
#print(count)| 項目 | 新 | mygcd |
| 実行時間 [ms] | 3131 | 6838 |
| メモリ [kB] | 2912 | 2940 |
自分で書いてみた場合、計算時間は減らない。
4. numpy
たしかnumpyはCで実装されていて早いとかなんとか。=>下記参考
ufunc.outer()はuniversal function (配列の各要素に対して行う関数)のメソッドで、引数はベクトル。引数がM次元行ベクトルAとN次元行ベクトルBなら返り値がM*Nのベクトルで、numpy.gcd.outer()なら各要素ごとの最大公約数を対応する位置へ格納する。(というのが私の理解ですが合っているのか)
これを使って全部の場合を「新」のようにやっちゃえという場合のコード下記。
import numpy as np
K = int(input())
x = np.arange(1, K + 1)
nums = np.gcd.outer(np.gcd.outer(x, x), x)
out = nums.sum()
print(out)実行時間やメモリの使用具合を「工夫」「numpy」と比べてみます。
| 項目 | 工夫 | numpy |
|---|---|---|
| 実行時間 [ms] | 38 | 217 |
| メモリ[kB] | 3292 | 76180 |
「工夫」の方が高スコアとはいえ、(知ってれば) 何も考えずにかけそうなnumpyバージョンでもこの速さ。numpyが早いってホントだったんですね。感動。
参考: [AtCoder 参加感想] 2020/04/12:ABC 162 -maspyのHP
まとめ
考えるのがきついならnumpy。お疲れ様でした。