コンテンツへスキップ

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]56043131
メモリ [KB]29242912
出力1081369210813692

意外に減る。でもすべてのテストで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)

上のループは変数が2個の場合の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]31316838
メモリ [kB]29122940

自分で書いてみた場合、計算時間は減らない。

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]38217
メモリ[kB]329276180

「工夫」の方が高スコアとはいえ、(知ってれば) 何も考えずにかけそうなnumpyバージョンでもこの速さ。numpyが早いってホントだったんですね。感動。

参考: [AtCoder 参加感想] 2020/04/12:ABC 162 -maspyのHP

まとめ

考えるのがきついならnumpy。お疲れ様でした。

2020/04/04 の日記です。ひどい出来でした。

目的

  • 参加人数が多い為かよく話しを聞きます。とりあえず1回やってみて内容を確認したいと思います。
  • 競プロやってる友達がアルゴリズム~とか言ってたので、アルゴリムについて考える機会になることに期待しています。

AtCoder

AtCoder

問題を解いて点数を競うやつです。

AtCoder Beginner Contest 161の結果と感想

結果: A問題だけ正解。パフォーマンス12、ratig 1。

感想(言い訳):

なんと21:00~22:40のところを20時に参加!一番慣れてるのがpythonなのでpython使うことは決めてましたが、jupyterじゃなくてコマンドプロンプトからやった方がやりやすいんじゃね?とかpcの不調でフォルダが開けないとかしてるうちにあんまり解けず。結果A問題しか回答出来ず。タイムオーバーしたものの、手をつけていたB問題はクリアしたところで第一回は終了。

時間との勝負なんすね。遅刻はダメです

...というのは勿論なんですが。基本的な書き方をググりながら解いたのでその分のタイムロスがあり、それが点数に影響していたのは間違いないです。

というのも、私は「何かをすごくやっている人」ではないので必要に応じて使用言語を変えてまして、どの言語もちょろっとしかやってないため基本的な書き方を忘れてたりするので、条件分岐の書き方あってるかなーとか、こんな関数あったっけなーとかググりながらワサワサやってるわけです。記憶力が無いのがバレてしまいましたが、これは直すべきというのが明らかになりました。

あとは、今回のA問題は並び替えるだけなんですけど、操作を書かずに結論だけ出力すればクリアできます。でもこれってコードに反映されてなくていいのか?とか考えて無駄に迷いました。昔読んだリーダブルコードに、「コンパクトに書くよりも可読性を!」みたいな事が書いてあったのが頭をよぎりまして、「結果だけ出力するより過程も記述するべきなのでは?動作が読めないコードは微妙なのでは?」「いやそれだとただ無駄なコードだし変数もまるっきり無駄なのでは?」とか考えてしまって5分くらい無駄にしたという話です。コメントに書くにもいずれ限界が来ますし。

普段は「半年後の自分が読めて理解できるコード」を書こうという目標を立てていますが、これは競技プログラミングをやる目的と合致するのかしないのか、という問いが発生したのはうれしい誤算でした。

問題を解き始めてからは楽しかったので今後もぼちぼち続けていきたいと思います。お疲れ自分。

シリーズ化について

私は競争とか順位とか点数とかが嫌いなので続くかは分かりません。続けるためにatcoder日記を書きます。ロジックの事は書かないと思いますが、面白いなーと言うのがあったら書くかもしれません。

こんな私的なことをネットに流すのはいかがなものか、というのはありますが許してください。賢くなったら社会に貢献しますので...

プリント基板(PCB)で名刺を作ろうということになったので、作ってみました。出来たものを自慢するのが目的です!

PCBで名刺をつくります。

目次

  • 目的と内容
  • KiCAD
  • 画像の加工
  • 完成
  • 雑記

目的と内容

プリント基板(PCB)で名刺を作ろうということになったので、作ってみました。出来たものを自慢するのが目的です!

KiCAD

KiCADについては以前使用した回をご覧ください。=> KiCADでプリント基板を作ってElecrowさんに注文

使い方は「KiCADことはじめ」を見ればだいたい大丈夫かと思います。

画像の加工

これをKiCAD のビットマップのインポートにロードして、好きなフォルダにアップロードします。

大きさを変更する場合は、元の画像かグレースケールかエクスポートのどこかの段階ですればOKです。

日本語で書けるらしいんですが、うまくいかなかったので今回は日本語も同じように画像を貼り付けます。

完成品

回路図

picの回で使ったものをつけられるようにしました。でもそれだけじゃ寂しかったのでモータードライバをつけてみました。

回路図

データ

下にある大きいRefのCu部分に電源を繋げるつもりです。

PCB data

3D view

3D view

雑記

今回は特に技術的に取り上げるものがありませんので以上です。

回路は一応動くだろうと思うんですが、テストしてないので分かりません。最低限Lチカはできるはず。

参考