AtCoderでPython使うときの小ネタ

はい。
AtcoderでPython使うときに小技、というか小さな注意点が必要になるときがあります。いちいち探すの地味に面倒なのでどこかにまとめておきたいと思ったのでちょいと書いてみます。思いつくたびに、更新して増やしていきたいと考えているんですけど、はてなブログで記事を後から更新しても見にくかったりするんですかね？

1. 入力が多いとき
入力の行がめちゃくちゃ多くなりそうなとき、Pythonデフォルトのinput()は実は結構遅い。入力だけでTLE出るときがごくまれにある。

import sys
input = sys.stdin.readline

を書いておくことで、高速に入力を受け取れる。
実行時間の差についてはこちらの記事が勉強になる。
www.kumilog.net

注意点として、この方法で入力を受け取ると末尾の改行の有無でちょっと処理が必要になる可能性がある。

2. 有効数字
ABC139Dの苦い思い出

n=int(input())
print(int((n-1)*n//2))

これが通って

n=int(input())
print(int((n-1)*n/2))

が通らないでWAの悲しみを味わった人も何人かいるはず。
/ だと演算結果がfloatになって有効数字が10何桁しか保たない。完全に整数になる、したいときは//を使っておきたい。

/2を採用すると、double演算になっちゃって、doubleになった瞬間、有効桁数が64bitではなくなるので、精度が悪くなります＞＜https://t.co/g2HC9d5q9i
— chokudai(高橋直大)🍆🍡 (@chokudai) 2019年9月1日

3. 配列のコピー
Atcoderに限らないけど、Pythonのリストコピーで配列の参照オブジェクトが同じってよくあるアレ。dfsやるときに、すでに通った場所のメモ用の配列を

reached=[[0]*w]*h

で定義して、はまったことがあるので一応メモ

reached=[[0]*w for _ in range(h)]

みたいな感じで定義しよう。

4.itertools
競プロやる上でめちゃくちゃ便利なライブラリ。便利過ぎてまだ全容を把握していない。この記事を参考にしよう。
qiita.com

5.fractions
最大公約数・最小公倍数を求めるときなど、gcdを使いたいときがある。バージョン3.5以降はmathにあるのだがAtcoderではpython3.4.3なので2019/9/29現在、mathは使えない。fractionsモジュールを使おう。これでWA出すと何とも言えない気持ちになる。

6. 再帰の回数
Pythonでの再帰のデフォで回せる最高数は結構少なめなので増やす。

import sys
sys.setrecursionlimit(4100000)

7. for文でelse
他の人の提出コード見ててびっくりしたんだけど、PythonではWhile、forのループにelseを使えるらしい。コレほかの言語ではあまり見ない機能ですよね。
パッと思いつく便利な使い方は、ループの処理でbreakしたときにフラグ変数を使わなくてすむ。

ary=[False,False,True,False]
flag=False
for a in ary:
  if a==True:
    flag=True
    break
if flag:
  print('yes')
else:
  print('no')

と書いていたところを

ary=[False,False,True,False]
for a in ary:
  if a==True:
    print('yes')
    break
else:
  print('no')

と書ける。スマートでいいですね。
使用例:
atcoder.jp
ただほかの言語だと見かけないので、そういう意味ではあまり多用しない方が良いのかもしれない。まだあまり使ってないけど for、if が入り乱れるとめんどくさそう感はある。
それにパッとググってもあまり使うなと書いてるものを結構見かける。

......いやーでもこれ、めっちゃスマートでいいぞ。競プロに関してはどんどん使っていきたい。