【AtCoder】AtCoderで意外と役立つテンプレ集1

はじめに

競プロerのwhile-true-ifです。久しぶりにAtCoderのまじめな記事を書きます。

テンプレートの良さ

皆さんはテンプレートを使っていますか？テンプレートを使うことで、コードを書く時間を短くすることができます。また、自分なりにカスタマイズすることで、C++のようなわかりにくい言語が書きやすくなります。

自分のPythonで使うテンプレート

def si():
    return input()
def i():
    return int(input())
def m():
    return map(int,input().split())
def l():
    return list(map(int,input().split()))
def o(s):
    print(s)
    return 0
def bin(n):
    return format(n, 'b')
def re(a):
    return list(reversed(a))

se=list("abcdefghijklmnopqrstuvwxyz")
le=list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")

よく使うのは、m()です。AtCoderの半角スペース区切りはよく出てくるのでかなり助かります。AtCoderのAB問題のような簡単なものでは、printをoにするのも案外役に立ちます。

問題によって使うことがあるテンプレート

二次元累積和

def Cumulative_Sum_2D(X):#2次元累積和 Xにグリッド情報
    row=[]
    H=len(X)
    W=len(X[0])
    import itertools
    for i in range(H):
        row.append([0]+list(itertools.accumulate(X[i])))

    col=[list(x) for x in zip(*row)]

    grid1=[]
    grid=[]
    for i in range(W+1):
        grid1.append([0]+list(itertools.accumulate(col[i])))

    grid=[list(x) for x in zip(*grid1)]
    return grid

2次元累積和はたまに使うことがあります。面倒なのでいざという時のために作っておくと役に立つかもしれません。

座標圧縮

# 座標圧縮(0スタート)
def compression0(A:list):
    D = list(set(A))
    D.sort()
    X = dict()
    for i in range(len(D)):
        X[D[i]] = i
    ret = []
    for a in A:
        ret.append(X[a])
    return ret

# 座標圧縮(1スタート)
def compression1(A:list):
    D = list(set(A))
    D.sort()
    X = dict()
    for i in range(len(D)):
        X[D[i]] = i + 1
    ret = []
    for a in A:
        ret.append(X[a])
    return ret

上の座標圧縮は一番小さい値が0スタートで、下の座標圧縮は一番小さい値が1スタートになります。AtCoderでは結構役立ちます。

文字圧縮

def string_compression(s: list):
    a = []
    now = s[0]
    c = 0
    for i in range(len(s)):
        if s[i] == now:
            c += 1
        else:
            a.append([now, c])
            now = s[i]
            c = 1
    a.append([now, c])
    return a

文字列のlistが与えられ、[文字,連続した数]で圧縮するだけ。役立つ場面は少ない。

終わりに

今回の記事で紹介したテンプレートは一部です。次の記事では、特定の問題に特化したテンプレを紹介するつもりです。