AtCoder Beginner Contest 168#atcoder https://atcoder.jp/contests/abc168
コンテスト終了後はどんな入力でこけたのか確認できる
- https://atcoder.jp/posts/20
結論、
sys.stdin.readlineで読んだせいで行末の改行コードもSに含まれてしまっていたinputは改行コードを取るのでこっちが良さそう VsCodeのスニペットのススメ - Qiita :
"read ints": {
"scope": "python",
"prefix": "readints",
"body": ["$1 = [int(x) for x in input().split()]"]
},
終了後に「2 ** n mod P」のO(log n)の実装を書いたがタイムアウト 雑に fractions.Fractionを collections.defaultdict に突っ込んでたのだけど、これカウントアップに63us掛かるので20万件で12秒になってタイムアウトするなー :
Line # Hits Time Per Hit % Time Line Contents
==============================================================
11 @profile
12 def foo():
13 200001 87415.0 0.4 0.6 for i in range(N):
14 200000 549187.0 2.7 3.7 A, B = [int(x) for x in sys.stdin.readline().split()]
15 200000 88256.0 0.4 0.6 if B == 0:
16 angle = "I"
17 else:
18 200000 1450133.0 7.3 9.8 angle = Fraction(A, B)
19 200000 12591985.0 63.0 85.3 count[angle] += 1
pyutils/line_profiler: Line-by-line profiling for Python math.gcdしてタプルの場合は1usなので桁違いだね
Eは、見かけよりややこしい。途中で0,0が特別扱いなのに気づいたが、サンプルにはないので、ハマる人多そう。 https://twitter.com/hamamu_kyopro/status/1262030222716661761 ハマった
こんなの作ったけど :
def pow2(n):
if n < 30:
return 2 ** n
p = pow2(n // 2)
pp = (p * p) % P
if n % 2 == 1:
return (2 * pp) % P
else:
return pp
pow(2, x, P)で良かった
ちょっと直せば通るかと思ったがなかなか
