12月になり今年もアドベントカレンダーの季節がやってきたということで
今年も頑張ってアウトプットしていこうと思う。
今年のアドベントカレンダーは「モチベーション維持」を目標にしている。
- 詳しくは記事後半で書くので見たい人だけどうぞ
早速本題のテンプレート紹介に移る
概要
競プロ用のテンプレートは、ざっくり次の2種類に分けられると考えている。
- 毎回使う雛形コード
- 必要なときに引き出すスニペットコード
前者は main.py にあらかじめ書いておく基本セット で、
入力処理や標準モジュールのインポートといった“毎回触る部分”を先にまとめておくもの。
後者は、問題ごとで必要になる典型アルゴリズムのコード集。
エラトステネスの篩、BFS、UnionFind などがその代表で、必要になったとき VSCode の snippet 機能やメモアプリからコピペして使う。
以降の項では、筆者が日常的に使っている main.py の内容や、VSCode のスニペット（一部）を紹介する。
main.pyの記述
この項では筆者がmain.pyに最初から書いてある内容を紹介する。
友人にこのコードを見せたときの反応とその回答を記事にまとめる予定
→12/24公開予定
コード全体
main.py
from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, Counter, deque
from functools import reduce, lru_cache
from itertools import product, accumulate, groupby, combinations
import sys
import os
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
IS_LOCAL = int(os.getenv("ATCODER", "0"))==0
err = (lambda *args, **kwargs: print(*args, **kwargs, file=sys.stderr)) if IS_LOCAL else (lambda *args, **kwargs: None)
def main():
# N = rI()
# N, M = rLI()
# H, W = rLI()
# N, M, K = rLI()
# X, Y = rLI()
# A, B = rLI()
# N, X, Y = rLI()
# N, A, B = rLI()
# A, B, C, D = rLI()
# E, F, G, H = rLI()
# A = rLI()
# B = rLI()
# S = rS()
# for _ in range():
# for i in range(N):
# for i,a in enumerate(A,start=1):
# for i,a in enumerate(A):
# S = rS()
# X, Y = rLI()
# A, B = rLI()
# if True:
# print("Yes")
# print("No")
# else:
# print("Yes")
# print("No")
# ans =
# print(ans)
# print(*ans)
# print('Yes' if ans else 'No')
if __name__ == '__main__':
main()
目次:
- モジュールインポート
- 入力関数
- デバッグ用エラー出力
- メイン関数
- 変数の入力
- ループ処理
- YesNo出力
モジュールインポート
main.py
from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, Counter, deque
from functools import reduce, lru_cache
from itertools import product, accumulate, groupby, combinations
import sys
import os
よく使うモジュールはインポートをあらかじめ済ませておき簡略化
- bisect: 二分探索
- collections: データ構造系
- defaultdict: 初期値付きdict(連想配列)
- Counter: リスト等の値をカウントしてdictにまとめてくれる
- 例:
[2,2,2,0]→{2:3, 0:1}
- 例:
- deque:
appendLeftpopLeftができるリスト- スタックとかキューに使えるやつ
- functools: 関数処理
- reduce: 部分適用するやつ(あまり使わない)
- lru_chace: キャッシュ作ってメモ化再帰できるデコレーター
- sys: 入出力高速化のために色々使う(よくわからない)
- os: 環境変数の値参照するために使用
入力関数
main.py
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
Pythonは標準入力から変数に代入する処理が冗長的なので、
名前が短い関数にまとめてタイプ数を減らす狙い。
input()の代わりにsys.stdin.readline().rstrip()だと処理が速いらしいのでそちらを採用(詳細不明)
-
rI(): 整数単体 -
rLI(): 空白区切りの整数複数 -
rI1(),rLI1(): 上記2つの入力値から1減らす- リストは0-indexだが、AtCoderの入力は1-indexのため、変換を省略したいときに時々使う
-
rS(): 文字列単体 -
rLS(): 空白区切りの文字列複数
デバッグ用エラー出力
main.py
IS_LOCAL = int(os.getenv("ATCODER", "0"))==0
err = (lambda *args, **kwargs: print(*args, **kwargs, file=sys.stderr)) if IS_LOCAL else (lambda *args, **kwargs: None)
実行テスト時、デバッグ用途で標準エラー出力にする関数
- AtCoder上では
ATCODER=1の環境変数があるようなので、その値を参照して提出時に出力する動作はしないように細工
メイン関数
main.py
def main():
#省略
if __name__ == '__main__':
main()
直接モジュールに処理を書くと処理が遅いらしい(これも詳細不明)のと
また、別途サブ関数やclassを定義する事があるために
モジュール分けを意識してメイン関数を定義している
if __name__ == '__main__': プログラム実行時にこのファイルを読み込んだ場合しか処理しないようにするif文
変数の入力
main.py
# N = rI()
# N, M = rLI()
# H, W = rLI()
# N, M, K = rLI()
# X, Y = rLI()
# A, B = rLI()
# N, X, Y = rLI()
# N, A, B = rLI()
# A, B, C, D = rLI()
# E, F, G, H = rLI()
# A = rLI()
# B = rLI()
# S = rS()
AtCoderでありがちな変数の名前を事前に決め打ちで書いておく
- 使うときにコメントアウト解除、他は削除
ループ処理
main.py
# for _ in range():
# for i in range(N):
# for i,a in enumerate(A,start=1):
# for i,a in enumerate(A):
# S = rS()
# X, Y = rLI()
# A, B = rLI()
# if True:
# print("Yes")
# print("No")
# else:
# print("Yes")
# print("No")
forループ1回程度で完了できる問題用に、
ループ処理を決め打ちで記述している。
コメントアウト解除の変更だけでYesNoのとりわけを変更できる方に両方記述している
回答出力
main.py
# ans =
# print(ans)
# print(*ans)
# print('Yes' if ans else 'No')
コメントアウト解除するだけで回答できるようにここも決め打ちで記述。
YesorNoで回答する問題が結構出るため、それも決め打ちで記述してある。
VSCodeのスニペット(一部)
この項では筆者が競プロで使うVSCodeのスニペットを一部紹介する。
- defaultdict
- Counter
- gridBFS
- UnionFind
- segtree
- Minheapq, Maxheapq
defaultdict
from collections import defaultdict
# カウント用途
cnts = defaultdict(lambda: 0)
# リスト積み上げ用途（グラフの隣接リストなど）
g = defaultdict(list)
# 集合で重複排除しながら集める用途
groups = defaultdict(set)
使用頻度No.1
個数カウント、隣接リスト、集合など、キーにアクセスしたタイミングで自動に 0 / [] / set() を用意してほしいときに使う
-
if k in d:みたいな前置きチェックを省略できて便利
VS Code スニペット定義
"Python defaultdict 0": {
"prefix": "::dd0",
"body": [
"${1:d} = defaultdict(lambda: 0)\n$0"
],
"description": "defaultdictを使用して変数を定義"
},
"Python defaultdict": {
"prefix": "::ddL",
"body": [
"${1:d} = defaultdict(list)\n$0"
],
"description": "defaultdictを使用して変数を定義"
},
Counter
from collections import Counter
# リストの頻度カウント
A = [1, 2, 2, 3, 3, 3]
cA = Counter(A)
# → cA[1] = 1, cA[2] = 2, cA[3] = 3
# 文字列の文字カウント
s = "abacaba"
cs = Counter(s)
# → cs['a'] = 4, cs['b'] = 2, cs['c'] = 1
使用頻度No.2
配列・文字列の要素数を一気に集計したいとき、これを使うとdict で手書きするより読みやすくてミスも減る。
VS Code スニペット定義
"Python Counter": {
"prefix": "::cnt",
"body": [
"${1:c} = Counter(${2})\n$0"
],
"description": "Counterを使用して変数を定義"
},
gridBFS
from collections import deque
dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]
def out_of_bounds(y, x, h, w):
return y < 0 or y >= h or x < 0 or x >= w
def bfs(i, j, h, w, grid):
q = deque([(i, j)])
dist = [[-1] * w for _ in range(h)]
visited = [[False] * w for _ in range(h)]
dist[i][j] = 0
visited[i][j] = True
while q:
y, x = q.popleft()
for di in range(4):
ny, nx = y + dy[di], x + dx[di]
if not out_of_bounds(ny, nx, h, w) and grid[ny][nx] == 0 and not visited[ny][nx]:
dist[ny][nx] = dist[y][x] + 1
visited[ny][nx] = True
q.append((ny, nx))
return dist
グリッド系の最短距離・到達判定で毎回書くことになる BFS を、まとめてテンプレ化したもの。
- 書くの面倒だけどスニペット化すればとっても楽
VS Code スニペット定義
"grid BFS": {
"prefix": "::grid_bfs",
"body": [
"",
"dy = [-1, 0, 1, 0]",
"dx = [0, 1, 0, -1]",
"",
"def out_of_bounds(y, x, h, w):",
" return y < 0 or y >= h or x < 0 or x >= w",
"",
"def bfs(i, j, h, w, grid):",
" q = deque([(i, j)])",
" dist = [[-1] * w for _ in range(h)]",
" visited = [[False] * w for _ in range(h)]",
" dist[i][j] = 0",
" visited[i][j] = True",
" ",
" while q:",
" y, x = q.popleft()",
" for di in range(4):",
" ny, nx = y + dy[di], x + dx[di]",
" if not out_of_bounds(ny, nx, h, w) and grid[ny][nx] == 0 and not visited[ny][nx]:",
" dist[ny][nx] = dist[y][x] + 1",
" visited[ny][nx] = True",
" q.append((ny, nx))",
"",
" return dist"
],
"description": "グリッドの上で幅優先探索（BFS）を行うコードスニペット"
}
UnionFind
class UnionFind:
def __init__(self, n):
self.parent = [-1] * -~n
self.rank = [1] * -~n
self.count = n
def root(self, x):
while (p:=self.parent[x]) != -1:
x = p
return x
def union(self, x, y):
xr = self.root(x)
yr = self.root(y)
if xr == yr: return
elif (rx:=self.rank[xr]) < (ry:=self.rank[yr]):
self.parent[xr] = yr
self.rank[yr] += rx
else:
self.parent[yr] = xr
self.rank[xr] += ry
self.count -= 1
def same(self,x,y):
# err(self.root(x), self.root(y))
return self.root(x) == self.root(y)
典型アルゴリズムの一つ。
グラフの連結判定やグループ分けをやるときに使う
-
union(x, y)でグループをまとめて、same(x, y)で同じグループかどうかを調べる
VS Code スニペット定義
"Union-Find": {
"prefix": "::unionfind",
"body": [
"class UnionFind:",
" def __init__(self, n):",
" self.parent = [-1] * -~n",
" self.rank = [1] * -~n",
" self.count = n",
" def root(self, x):",
" while (p:=self.parent[x]) != -1:",
" x = p",
" return x",
" def union(self, x, y):",
" xr = self.root(x)",
" yr = self.root(y)",
" if xr == yr: return",
" elif (rx:=self.rank[xr]) < (ry:=self.rank[yr]):",
" self.parent[xr] = yr",
" self.rank[yr] += rx",
" else:",
" self.parent[yr] = xr",
" self.rank[xr] += ry",
" self.count -= 1",
" def same(self,x,y):",
" # err(self.root(x), self.root(y))",
" return self.root(x) == self.root(y)"
],
"description": "Union-Findアルゴリズムを実装"
}
segtree
区間和・区間最小値などのクエリを高速に処理するためのデータ構造
op（結合関数）と e（単位元）を渡して初期化して、和・最小値・最大値などを同じクラスで使い回せる
- 正直筆者はまだ完璧に使いこなせてない😅
- GPT5.1曰く「区間和と区間最小値あたりから触ると入りやすい」そうです。
具体的な使い道をGPT5.1に聞いてみた
用途イメージ：
-
配列
Aに対して- 区間
[l, r)の和を素早く求めたい - あるインデックス
iの値を更新したい
- 区間
# 区間和クエリを行うセグメント木の例
# 初期配列
A = [5, 1, 4, 3, 7]
# 結合関数（op）と単位元（E）を用意する
def op(a, b):
return a + b # 区間和なので足し算
E = 0 # 足し算における単位元（0）
# セグメント木を構築
st = segtree(A, op, E)
# 区間 [l, r) の和を取得（ここでは A[1] + A[2] + A[3]）
l, r = 1, 4
print(st.prod(l, r)) # 1 + 4 + 3 = 8
# 要素 A[2] を 10 に書き換え
st.set(2, 10)
# 再度、同じ区間の和を取得
print(st.prod(l, r)) # 1 + 10 + 3 = 14
# 配列全体の和が欲しいとき
print(st.all_prod()) # 5 + 1 + 10 + 3 + 7 = 26
ポイント
segtree(V, OP, E)で
V: 元の配列OP: 結合関数（例：min, max, +）E: 単位元（例：INF, -INF, 0）
prod(l, r)は 0-index, 右端 r は非含
セグ木を「区間最小値」にするバリエーション
INF = 10**18
A = [5, 1, 4, 3, 7]
def op(a, b):
return min(a, b)
st = segtree(A, op, INF)
# 区間 [1, 4) の最小値 → min(1, 4, 3) = 1
print(st.prod(1, 4))
# A[2] を -5 に更新
st.set(2, -5)
# 再度同じ区間の最小値 → min(1, -5, 3) = -5
print(st.prod(1, 4))
セグ木の実装は以下を使用している。
VS Code スニペット定義
"セグメント木":{
"prefix": "::segtree",
"body": [
"class segtree():",
" n=1",
" size=1",
" log=2",
" d=[0]",
" op=None",
" e=10**15",
" def __init__(self,V,OP,E):",
" self.n=len(V)",
" self.op=OP",
" self.e=E",
" self.log=(self.n-1).bit_length()",
" self.size=1<<self.log",
" self.d=[E for i in range(2*self.size)]",
" for i in range(self.n):",
" self.d[self.size+i]=V[i]",
" for i in range(self.size-1,0,-1):",
" self.update(i)",
" def set(self,p,x):",
" assert 0<=p and p<self.n",
" p+=self.size",
" self.d[p]=x",
" for i in range(1,self.log+1):",
" self.update(p>>i)",
" def get(self,p):",
" assert 0<=p and p<self.n",
" return self.d[p+self.size]",
" def prod(self,l,r):",
" assert 0<=l and l<=r and r<=self.n",
" sml=self.e",
" smr=self.e",
" l+=self.size",
" r+=self.size",
" while(l<r):",
" if (l&1):",
" sml=self.op(sml,self.d[l])",
" l+=1",
" if (r&1):",
" smr=self.op(self.d[r-1],smr)",
" r-=1",
" l>>=1",
" r>>=1",
" return self.op(sml,smr)",
" def all_prod(self):",
" return self.d[1]",
" def max_right(self,l,f):",
" assert 0<=l and l<=self.n",
" assert f(self.e)",
" if l==self.n:",
" return self.n",
" l+=self.size",
" sm=self.e",
" while(1):",
" while(l%2==0):",
" l>>=1",
" if not(f(self.op(sm,self.d[l]))):",
" while(l<self.size):",
" l=2*l",
" if f(self.op(sm,self.d[l])):",
" sm=self.op(sm,self.d[l])",
" l+=1",
" return l-self.size",
" sm=self.op(sm,self.d[l])",
" l+=1",
" if (l&-l)==l:",
" break",
" return self.n",
" def min_left(self,r,f):",
" assert 0<=r and r<=self.n",
" assert f(self.e)",
" if r==0:",
" return 0",
" r+=self.size",
" sm=self.e",
" while(1):",
" r-=1",
" while(r>1 and (r%2)):",
" r>>=1",
" if not(f(self.op(self.d[r],sm))):",
" while(r<self.size):",
" r=(2*r+1)",
" if f(self.op(self.d[r],sm)):",
" sm=self.op(self.d[r],sm)",
" r-=1",
" return r+1-self.size",
" sm=self.op(self.d[r],sm)",
" if (r& -r)==r:",
" break",
" return 0",
" def update(self,k):",
" self.d[k]=self.op(self.d[2*k],self.d[2*k+1])",
" def __str__(self):",
" return str([self.get(i) for i in range(self.n)])"
],
"description": "セグメント木を実装します",
}
Minheapq, Maxheapq
import heapq
class Minheapq(object):
def __init__(self):
self.q = []
def push(self, v):
heapq.heappush(self.q, v)
def pop(self):
return heapq.heappop(self.q)
def get(self):
return self.q[0]
def values(self):
for _q in self.q:
yield _q
class Maxheapq:
def __init__(self):
self.q = []
def push(self, v):
heapq.heappush(self.q, v * -1)
def pop(self):
return heapq.heappop(self.q) * -1
def get(self):
return self.q[0] * -1
def values(self):
for _q in self.q:
yield -_q
標準ライブラリ heapq は最小ヒープしか持っていないので、
最大値を取りたいときは毎回「値にマイナスを掛ける」実装を書く必要がある。
そこで、Minheapq / Maxheapq というラッパークラスをスニペット化しておき、
-
push(v)/pop()/get()/values()などの API を共通化 - 最大ヒープ側だけ内部で符号反転する
という方針にしている。
::minheapq / ::maxheapq を展開しておくと、
実装中に「やっぱり最小じゃなくて最大を見たい」となったときでも、クラス名を差し替えるだけで済んで楽。
-
Minheapq: Dijkstra法など、「距離が小さい順」に頂点を取り出したいときに使用 -
Maxheapq: 優先度が高い順・スコアが高い順に処理したいときに使用
VS Code スニペット定義
"MaxHeapq Class": {
"prefix": "::maxheapq",
"body": [
"import heapq",
"",
"class Maxheapq:",
" def __init__(self):",
" self.q = []",
"",
" def push(self, v):",
" heapq.heappush(self.q, v * -1)",
"",
" def pop(self):",
" return heapq.heappop(self.q) * -1",
"",
" def get(self):",
" return self.q[0] * -1",
"",
" def values(self):",
" for _q in self.q:",
" yield -_q"
],
"description": "最大ヒープの実装。Pythonの組み込みモジュールheapqを使用"
},
"Minheapq Class": {
"prefix": "::minheapq",
"body": [
"import heapq",
"",
"class Minheapq(object):",
" def __init__(self):",
" self.q = []",
"",
" def push(self, v):",
" heapq.heappush(self.q, v)",
"",
" def pop(self):",
" return heapq.heappop(self.q)",
"",
" def get(self):",
" return self.q[0]",
"",
" def values(self):",
" for _q in self.q:",
" yield _q"
],
"description": "最小ヒープの実装。Pythonの組み込みモジュールheapqを使用"
}
テンプレートのまとめ
この2つをうまく組み合わせられれば、実装スピードは上がるはず。
さらに、自分だけのテンプレートを育てていくほど作業効率が伸びていき、
その積み重ねが成長の実感にもつながるはず。
おまけ：アドベントカレンダーについて
今年もアドベントカレンダーの季節が来たが、冒頭にも書いた通り今年の目標は「モチベーションの維持」と設定した。
ここ数ヶ月で関東から近畿へ引っ越したこともあって、競プロに割ける時間が減り、時間内に問題を解けず、コンテストも rated で参加する頻度が落ちてしまっている。
それでもアウトプット自体は続けていて、週1のペースで D 問題前後を解き、その内容を記事にまとめて投稿する習慣は維持している。せっかくのイベントなので、この問題解く系の記事を中心に投稿を続けつつ、久々に ABC をrated で参加したいとも思っている。都合が合わずABCに参加できなかった場合は同様に問題を解く。
また、main.py を紹介した項でも触れたように、このテンプレートを友人に見せてみた反応をまとめた企画も用意している。
今年は環境の変化が大きかったものの、少しずつでも積み上げていけば、また以前のように競プロを楽しめるはずだ。アドベントカレンダーをきっかけに日々のアウトプットを継続しながら、自分のペースで進んでいきたい。