ABC168
https://gyazo.com/3151b3beb6dedcdae82ad056d80d5cbd
初挑戦の結果。なんでかBが解けなかった。Eはサンプルコードには正しい答えを出せたけど「2**20000 mod P」の計算を残り5分でできそうになかったから諦めた。提出して途中まで行けるのを確認したほうが良かったかな
コンテスト終了後はどんな入力でこけたのか確認できる
結論、sys.stdin.readlineで読んだせいで行末の改行コードもSに含まれてしまっていた
inputは改行コードを取るのでこっちが良さそう
code::
"read ints": {
"scope": "python",
"prefix": "readints",
},
終了後に「2 ** n mod P」のO(log n)の実装を書いたがタイムアウト
雑に fractions.Fractionを collections.defaultdict に突っ込んでたのだけど、これカウントアップに63us掛かるので20万件で12秒になってタイムアウトするなー
code::
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):
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 countangle += 1 math.gcdしてタプルの場合は1usなので桁違いだね
Eは、見かけよりややこしい。途中で0,0が特別扱いなのに気づいたが、サンプルにはないので、ハマる人多そう。
ハマった
こんなの作ったけど
code::
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)で良かった
ちょっと直せば通るかと思ったがなかなか
https://gyazo.com/f044fcf8bb984abf7d6df572cf73d3e5
鉛直などの特殊なケースでエラーになってたので、提出前に手元でコーナーケースをテストした方が良さそう
最後まで残ったバグは、Python3で割り算が整除でなくなったのを忘れてて浮動小数点数の精度でコケるタイプ