htkb-proconの日記

初心者がPythonで問題解いた記録

AtCoder Beginner Contest 096

C - Grid Repainting 2

Submission #2461512 - AtCoder Beginner Contest 096

番兵で周りを囲む、ループ回しながら隣のマスを調べるなど二次元座標探索の基本をやる問題。制約がゆるいので定数倍を気にする必要は無かったが、pythonのindexingはかなり遅いため全座標に対して毎回二次元indexingしまくるとクソクソ遅い。こういうのはzipなどを駆使しできる限り座標の中身を値で受け取るようにしたい。

改善例→Submission #2472595 - AtCoder Beginner Contest 096

同じような定数倍改善で通らない問題が通せた例

よくpythonはforループが遅いと言われるけど、numpyが速いのでnumpyで完結できることをforでやると当然遅いってのと、indexingや属性アクセスなどの遅いことをループ内でやりがちってだけで、pythonの中でforループ自体が特別に遅いということは無いような気がするけどなぁ。append = a.appendのようにループ外で属性をキャッシュして使うとforと内包表記の速度差はかなり縮まるし。

D - Five, Five Everywhere

Submission #2464170 - AtCoder Beginner Contest 096

まずエラトステネスのふるいで55555以下の素数リストを作る。ふるいは過去に実行時間測定しながら効率良さげな書き方を調べたのを覚えてた。以下のような感じ:

import math
n = 55555
primes = set(range(2, n+1))
for i in range(2, math.sqrt(n)+1):
    primes.difference_update(range(i*2, n+1, i))

set.difference_updateは要するに-=演算子とほぼ同義なんだけど、-=の被演算子setしか取れないのに比べてdifference_updateの引数はiterableなら何でも取れる?のでrangeをそのまま渡すことができ、いちいちsetを作り捨てるよりかなり高速なのがミソだった気がする。

そこまではいいんだけど何をトチ狂ったか「2が入ってれば5つの和は必ず偶数になるんじゃね??」とか勘違いして1WA、しばらく思いつかなくて数が大きくなれば新たな素数はできにくくなるだろうと素数リストの大きい方から指定個数切り出してみて2WA(こういう横着を想定してないわけないよな……)。1の位が全部1なら5つの和は必ず5の倍数になるなとようやく気づいてAC。こういう発想問題は数論系の知識の引き出しが少ないと難しいな。