競プロ練習記録（ABC189、ABC190など）

ABC190に参加した。その前に練習で ABC189もやっておいた。ABCトーナメントに参加するのが主要な動機。練習自体には、多少慣れた以上はあまり意味がなかったが、python のTLE対策に関してはいくらか知見を得た。

コードテストについて

実行時間的に間に合うかどうか微妙な時は高速化する必要がある。その場合、

闇雲に高速化する。
コードテストでパフォーマンスをチェックしながら確認する。

の二通りの選択肢がある。最悪ケースが簡単に作れる場合は迷わずに 2. の選択肢を選ぶが、そうでない場合は 2. ができるように入力を作るのが億劫で 1. で無理やり何とかしてみようとすることが多かった。

しかし、そんなに億劫がる必要はない気もする。

例えば、今回最初にTLEした

Submission #19812154 - AtCoder Beginner Contest 190

の場合、入力部分は

N,M = map(int, input().split())
edges = [[] for _ in range(N)]
for _ in range(M):
    a,b = map(int,input().split())
    a-=1
    b-=1
    edges[a].append(b)
    edges[b].append(a)
K = int(input())
cs = [int(s)-1 for s in input().split()]

となる。これを大きな入力についてテストしようとすると、例えば

if 0:
    N,M = map(int, input().split())
    edges = [[] for _ in range(N)]
    for _ in range(M):
        a,b = map(int,input().split())
        a-=1
        b-=1
        edges[a].append(b)
        edges[b].append(a)
    K = int(input())
    cs = [int(s)-1 for s in input().split()]


if 1:
    N,M = 10**5, 10**5
    edges = [[] for _ in range(N)]
    for i in range(M):
        a,b = i,(i+1)%N
        edges[a].append(b)
        edges[b].append(a)
    K = 17
    cs = [s**3 for s in range(K)]

となるが、コピーペーストで被る部分の多さを考えると、実は大した労力ではなさそうだ(５分もあれば十分？)。

結論：TLEチェック用の入力を自作するのは実はそこまで手間がかからない。闇雲に高速化を試みるより、はるかにまし。

入出力について

import sys
input = lambda: sys.stdin.readline().rstrip()

とするだけで爆速になる。早速、atcoder-toolsの「# Failed to predict input format」部分に追加した。

PyPy3で提出

atcodertools/common/language/.py の PYTHON部分で該当箇所を、 submission_lang_pattern=re.compile("^PyPy3.*"),

に書き換えた。これで、atcoder-tools submit したときにPyPy3で提出してくれるようになった。

消費時間

全体では６〜８時間ぐらい使ったように思う。しかし、今回のABC練習は基本的にABCトーナメントをより楽しむためのもので、レート向上を目指したものではない。TLE原因の調査などはレート向上を目的としたものなので、だいたい３時間ぐらいをレート向上のための消費時間として計上するのが妥当か。このあたりはルール曖昧だが。

今回の消費時間：3時間

今年の消費時間：17時間