abc168

NISHIO Hirokazu [Translate]
ABC168
AtCoder Beginner Contest 168 #Atcoder
https://atcoder.jp/contests/abc168

初挑戦の結果。なんでかBが解けなかった。Eはサンプルコードには正しい答えを出せたけど「2**20000 mod P」の計算を残り5分でできそうになかったから諦めた。提出して途中まで行けるのを確認したほうが良かったかな

コンテスト終了後はどんな入力でこけたのか確認できる
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) で良かった

ちょっと直せば通るかと思ったがなかなか
鉛直などの特殊なケースでエラーになってたので、提出前に手元でコーナーケースをテストした方が良さそう
最後まで残ったバグは、Python3で割り算が整除でなくなったのを忘れてて浮動小数点数の精度でコケるタイプ