はじめに
alumiと申します。初投稿です。
ABC351で入緑したので振り返りも兼ねて色変記事を書かせていただきます。
乱筆乱文ですが、誰かの助けやモチベーションになれば嬉しいです。
誰？
- 非エンジニア（法務系のお仕事）
- プログラミング歴は1年ちょい（業務でズルするときに使うくらい）
- 競プロではPythonだけ使用（C++なにもわからない）
入緑までの経過
灰→茶
業務でPythonを触るようになったので、Python力向上のため去年の9月頃に初コンテスト参加しました（ABC319）。
ビビリ用心深い性格なのでAtCoder ProblemsさんのBoot camp for BeginnersのEasyを半分くらい埋めてからの参戦だったのですが、結果は2完...
悔しさで自分をモチベートしながら過去問で経験値を上げたらだんだん解けるようになり、8回目のコンテストで入茶できました（途中の大陸棚みたいな所は1完で爆死したとこです）。
茶→緑
入茶してしばらくはレート下げるの怖くて修行のため2回コンテスト参加を見送りました。
入茶後初のコンテストで水Perf出して調子に乗ったら、その後レートの伸びがなだらかになり、800に漸近しはじめました。
もう少しで入緑なのに～><となりしびれを切らしARCに初参加したら0完大爆死（蟻地獄の巣みたいな所）。
レート戻るまでTwitter（現X）やめよ...と思って精進したら次の週で2回目の水Perf出してレート戻りました。
そしてABC351で4完緑perf出して晴れて入緑できました。やったぜ。
入緑までにやったこと
過去問
クソビビリ用心深い性格なので、入茶時点でAは全埋め、Bも半分くらい埋めていました。
入緑時点でAcceptedは1620なので、多分人よりも要領が悪いと思います。
過去の自分（あとこれから入緑しようと頑張っている人）にアドバイスできるなら、次の順番の過去問精進を勧めます。
- Boot camp for BeginnersのEasy・Medium
- E869120様の記事の精選100問
この辺を網羅すれば入緑は堅いと思います。
A問題などの低diffは精進における最初のスターターとして使うのがいいでしょう。
もしくは低diffに逃げないようにA・Bを先に埋めておくのもアリです（下図のように）。
多分この日競プロしかしてない。
本から学ぶ
体系的な理解には本からの学びが不可欠です。基本として要求される水準をインストールするためにも、以下の有名本の目次に書いてあるアルゴリズムがなにかわかる程度には知っておいたほうがいいと思います。
-
競技プログラミングの鉄則 aka 鉄則本
- 一番血肉になった気がします。AtCoder上でテストもできるので、精進のしやすさも高いです。
-
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 aka 階段本
- 入緑時点で半分くらいまで読みました。この本に記載の問題もAIZU ONLINE JUDGE上でテストできるため精進しやすいですが、鉄則本に比べれば難易度は高めです。ただ鉄則本と合わせればほとんどの基礎的なアルゴリズムは網羅できると思います。
-
プログラミングコンテストチャレンジブック aka 蟻本
- 個人的にはまだ難しすぎました。緑以上で要求される知識のほうが多いです。ただ上位レートで要求される問題の難易度に触れられたので、モチベーションアップに繋がりました。
-
問題解決力を鍛える!アルゴリズムとデータ構造
- 鉄則本と内容は似ていますが、上の3つに比べて小さいので持ち運びに便利で電車で読んでも顰蹙を買いません（路線による）。
-
競技プログラマーハンドブック
- 海外の本の和訳です。無料で読めるのに罪悪感を感じるほど内容が充実しています。他の本にも共通しますが、海外本は日本のとは違うアルゴリズムや典型問題が取り上げられていてとても面白いです。この本は特に脚注が充実しているので、アルゴリズムの歴史や考案者にも詳しくなれます。うれしい。
-
OpenDataStructures.jp
- 海外の本の和訳です。無料で読めるのに罪悪感を感じるほど内容が充実しています（2回目）。データ構造の体系的な知識が学べます。正直入緑までに寄与する知識は少ないですが、標準ライブラリでカプセルされているデータ構造の実装を学ぶことで、時間・空間計算量の理解や実装アイデアの問題への流用ができるかもしれません。
Twitter（現X）で同レート帯をフォローする
同じレート帯だと同じような問題で悩み、コンテスト終了後に悩んだ問題についての考え方などをツイート（ポスト）してくれます。
また問題が解けなくてレートが冷えても、同じ問題で冷えている人が多いとメンタルが回復します（それでいいのか？）。
何より他の人のいいね🧡はめちゃくちゃモチベーションになりますね。いつもありがとう。
自作ライブラリの構築・整理
自作ライブラリはObsidian上で管理し、使うときに都度コピペしています。あまり効率的ではないですが、一番自分の感じる負荷が少なく運用できるスタイルなので、この方針でしばらく行きます。
分類は以下のように、中分類に問題、小分類にアルゴリズムを置いています（List of algorithms - Wikipediaを参考にしました）。
スニペットの構築・整理
私はVSCodeでコーディングしているので、VSCodeのユーザースニペット機能を使ってスニペット管理をしています。
基本的に必要最低限の要素だけをコードに乗せたいタチなので、時間ロスが多少あっても共通テンプレにマクロをたくさん乗せるのではなく、スニペットから使うものだけを入力するようにしています。
まあ入緑までならそこまで問題にならない程度のロスだと思います。
スニペット作成で参考にしたもの
- python-liblary/.vscode/plainpython.code-snippets at main · rararapi/python-liblary
- vscode-python/snippets/python.json at 2020.12.424452561 · microsoft/vscode-python
- 【AtCoder】普通の人である私が緑になるまでにしたこと - Qiita
- 提出 #47801411 - 競技プログラミングの鉄則 演習問題集
よく使うデータ構造（Union-Find・セグ木など）はスニペットに埋め込んでいるのですが、VSCodeのユーザースニペットは各行をダブルクオートで囲ってカンマで区切る必要があるので、そこら辺の整形をChatGPTなどにまかせています。
スニペット変換用のプロンプト例
以下のコードを次のフォーマットに変換してください。
# フォーマット
- 入力コードの各行の先頭と末尾にダブルクオート（"）をつける
- 末尾のダブルクオートのあとにコンマ（,）と半角スペースをつける
- 空白行はダブルクオート2つとコンマ・半角スペースのみで構成される（"", ）
- 行にインデントがある場合はそれを含めてダブルクオートをつける
- ダブルクオートをつける前の行内にダブルクオートがある場合エスケープ記号（\）を付与する
# 入力例
!```
G = [[] for _ in range(n + 1)]
for _ in range(n + 1):
a, b = getIntMap()
G[a].append(b)
G[b].append(a)
print("Yes")
!```
# 出力例
!```
"G = [[] for _ in range(n + 1)]",
"for _ in range(n + 1):",
" a, b = getIntMap()",
" G[a].append(b)",
" G[b].append(a)"],
"",
"print(\"Yes\")"
!```
# 入力
!```
!```
スニペット例（長いです）
python.json
{
"def main": {
"prefix": ":main",
"body": [
"def main() -> None:",
" import sys",
" input = sys.stdin.readline",
"",
" $0",
"",
"if __name__ == \"__main__\":",
" main()"
]
},
// 入力get
"getString": {
"prefix": ":gs",
"body": [": str = input()"]
},
"getInt": {
"prefix": ":gi",
"body": [": int = int(input())"]
},
"getFloat": {
"prefix": ":gf",
"body": [": float = float(input())"]
},
"getStringMap": {
"prefix": ":gsm",
"body": ["= input().split()"]
},
"getIntMap": {
"prefix": ":gim",
"body": ["= map(int, input().split())"]
},
"getIntTuple": {
"prefix": ":git",
"body": [" = tuple(map(int, input().split()))"]
},
"getFloatMap": {
"prefix": ":gfm",
"body": ["= map(float, input().split())"]
},
"getStringList": {
"prefix": ":gsl",
"body": [" = list(input().split())"]
},
"getIntList": {
"prefix": ":gil",
"body": [" = list(map(int, input().split()))"]
},
"getFloatList": {
"prefix": ":gfl",
"body": [" = list(map(float, input().split()))"]
},
"getStringRow": {
"prefix": ":gsr",
"body": [" = [input() for _ in range(N)]"]
},
"getIntRow": {
"prefix": ":gir",
"body": [" = [int(input()) for _ in range(N)]"]
},
"getFloatRow": {
"prefix": ":gfr",
"body": [" = [float(input()) for _ in range(N)]"]
},
"getStringListRow": {
"prefix": ":gslr",
"body": [" = [list(input().split()) for _ in range(N)]"]
},
"getIntListRow": {
"prefix": ":gilr",
"body": [" = [list(map(int, input().split())) for _ in range(N)]"]
},
"getFloatListRow": {
"prefix": ":gflr",
"body": [" = [list(map(float, input().split())) for _ in range(N)]"]
},
// 頻出入力
"int n": {
"prefix": "n=",
"body": "N: int = int(input())\n",
},
"int n,m": {
"prefix": "nm=",
"body": "N, M = map(int, input().split())\n",
},
"int x,y": {
"prefix": "xy=",
"body": "X, Y = map(int, input().split())\n",
},
"int n,x": {
"prefix": "nx=",
"body": "N, X = map(int, input().split())\n",
},
"int n,k": {
"prefix": "nk=",
"body": "N, K = map(int, input().split())\n",
},
"int n,q": {
"prefix": "nq=",
"body": "N, Q = map(int, input().split())\n",
},
"int l,r": {
"prefix": "lr=",
"body": "L, R = map(int, input().split())\n",
},
"int a,b": {
"prefix": "ab=",
"body": "A, B = map(int, input().split())\n",
},
"int a,b,c": {
"prefix": "abc=",
"body": "A, B, C = map(int, input().split())\n",
},
"int a,b,c,d": {
"prefix": "abcd=",
"body": "A, B, C, D = map(int, input().split())\n",
},
"int h,w": {
"prefix": "hw=",
"body": [
"H, W = map(int, input().split())",
"S = [input() for _ in range(H)]\n"
]
},
"int list A": {
"prefix": "A=",
"body": "A = list(map(int, input().split()))\n",
},
"int list AB": {
"prefix": "AB=",
"body": [
"A = list(map(int, input().split()))",
"B = list(map(int, input().split()))\n",
]
},
"int list ABC": {
"prefix": "ABC=",
"body": [
"A = list(map(int, input().split()))",
"B = list(map(int, input().split()))",
"C = list(map(int, input().split()))\n",
]
},
"int list L": {
"prefix": "L=",
"body": "L = list(map(int, input().split()))\n",
},
"str S": {
"prefix": "S=",
"body": "S: str = input()\n",
},
"str ST": {
"prefix": "ST=",
"body": "S: str = input()\nT: str = input()\n",
},
// 頻出変数
"cnt": {
"prefix": "cnt",
"body": "cnt: int = 0",
},
"pritn cnt": {
"prefix": "pcnt",
"body": "print(cnt)",
},
"ans": {
"prefix": "ans",
"body": "ans: int = 0",
},
"pritn ans": {
"prefix": "pans",
"body": "print(ans)",
},
"Graph G": {
"prefix": "G=",
"body": [
"G = [[] for _ in range(N)]",
"for _ in range(M):",
" a, b = map(int, input().split())",
" G[a].append(b)",
" G[b].append(a)"
],
},
// 高橋さんと青木さん
"高橋": {
"prefix": "ta",
"body": "'Takahashi'",
},
"青木": {
"prefix": "ao",
"body": "'Aoki'",
},
"fori": {
"prefix": "fori",
"body": "for i in range(N):"
},
"forj": {
"prefix": "forj",
"body": "for j in range(N):"
},
"fork": {
"prefix": "fork",
"body": "for k in range(N):"
},
"forij": {
"prefix": "forij",
"body": [
"for i in range(N):",
" for j in range(N):",
]
},
"forijk": {
"prefix": "forijk",
"body": [
"for i in range(N):",
" for j in range(N):",
" for k in range(N):"
]
},
"forhw": {
"prefix": "forhw",
"body": ["for i in range(H):"," for j in range(W):"]
},
"for _": {
"prefix": "for_",
"body": "for _ in range(N):",
},
"defaultdict": {
"prefix": "ded",
"body": ["from collections import defaultdict", "cnt = defaultdict(int)"]
},
"deque": {
"prefix": "deque",
"body": ["from collections import deque", "que = deque()"]
},
"heapq": {
"prefix": "heapq",
"body": ["from heapq import heappush, heappop"]
},
"Counter":{
"prefix": "counter",
"body": ["from collections import Counter", " cnt = Counter(A)"]
},
"math":{
"prefix": "math",
"body": ["import math"]
},
"numpy":{
"prefix": "np",
"body": ["import numpy as np"]
},
"gcd": {
"prefix": "gcd",
"body": [
"from math import gcd",
"",
"g: int = gcd(a, b)"
]
},
"lcm": {
"prefix": "lcm",
"body": [
"from math import gcd",
"",
"def lcm(a: int, b: int) -> int:",
" return a // gcd(a, b) * b",
"",
"g :int = gcd(a, b)",
"m :int = lcm(a, b)",
]
},
"bisect": {
"prefix": "bislr",
"body": [
"from bisect import bisect_left, bisect_right",
"i: int = bisect_left(A, x)",
"i: int = bisect_right(A, x)",
]
},
"めぐる式にぶたん": {
"prefix": "nib",
"body": [
"def f(x: int) -> int:",
" return x",
"",
"ok = 0",
"ng = 2 * 10**18",
"while abs(ok - ng) > 1:",
" mid = (ok + ng) // 2",
" if f(mid):",
" ok = mid",
" else:",
" ng = mid",
"",
"print(ok)"
]
},
"メモ化": {
"prefix": "memo",
"body": [
"from functools import lru_cache",
"@lru_cache()",
]
},
"yes": {
"prefix": "yes",
"body": "print(\"Yes\")"
},
"no": {
"prefix": "no",
"body": "print(\"No\")"
},
"debug print": {
"prefix": "pf",
"body": "print(f\"{$0 = }\")"
},
"abc": {
"prefix": "abc",
"body": "abc: str = 'abcdefghijklmnopqrstuvwxyz'"
},
"ABC": {
"prefix": "ABC",
"body": "ABC: str = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'"
},
"INF":{
"prefix": "INF",
"body": "INF: int = 1<<60",
},
"mod":{
"prefix": "mod",
"body": "mod: int = 998244353",
},
"MOD":{
"prefix": "MOD",
"body": "MOD: int = 1000000007",
},
"sys.set": {
"prefix": "sys",
"body": "import sys\nsys.setrecursionlimit(10**6)",
},
"dxdy": {
"prefix": "dxdy",
"body": [
"dx = [-1, 0, 1, 0, 1, 1, -1, -1]",
"dy = [0, 1, 0, -1, 1, -1, 1, -1]",
"d: int = 0 # 0123→上右下左",
"d = {\"U\": 0, \"R\": 1, \"D\": 2, \"L\": 3}",
"d = {\"U\": (-1, 0), \"R\": (0, 1), \"D\": (1, 0), \"L\": (0, -1)}",
"for i in range(4):",
" nx, ny = cx + dx[i], cy + dy[i]",
" if not (0 <= nx < h and 0 <= ny < w):",
" continue"
],
"description": "後半4つ消すと四方"
},
"coords 2D": {
"prefix": "coords2",
"body": [
"def dist(coord1, coord2):",
" return sum((p - q) ** 2 for p, q in zip(coord1, coord2)) ** 0.5",
"",
"dist(X[i], Y[i], X[j], Y[j])",
"",
"X, Y = [], []",
"for _ in range(N):",
" x, y = map(int, input().split())",
" X.append(x)",
" Y.append(y)"
],
},
"coords 3D": {
"prefix": "coords3",
"body": [
"def dist(coord1, coord2):",
" return sum((p - q) ** 2 for p, q in zip(coord1, coord2)) ** 0.5",
"",
"dist(X[i], Y[i], Z[i], X[j], Y[j], Z[j])",
"",
"X, Y, Z = [], [], []",
"for _ in range(N):",
" x, y, z = map(int, input().split())",
" X.append(x)",
" Y.append(y)",
" Z.append(z)"
],
},
"no yes": {
"prefix": "yn",
"body": ["print(\"Yes\" if f$0 else \"No\")"],
"description": "後の括弧には条件式入れる"
},
"NO YES": {
"prefix": "YN",
"body": ["print(\"YES\" if f$0 else \"NO\")"],
"description": "後の括弧には条件式入れる"
},
"if else": {
"prefix": "if2",
"body": [
"if $0:",
" print(\"Yes\")",
" ans = 0",
"else:",
" print(\"No\")",
" ans = 0",
]
},
"if elif else": {
"prefix": "if3",
"body": [
"if $1:",
" print(\"Takahashi\")",
" ans = 0",
"elif $2:",
" print(\"Aoki\")",
" ans = 0",
"else:",
" print(\"Draw\")",
" ans = 0",
]
},
"time deco": {
"prefix": "time",
"body": [
"import time",
"",
"def func_speed(func):",
" def _wrapper(*args, **keywargs):",
" start_time = time.time()",
" result = func(*args, **keywargs)",
" print(f\"Time: {time.time() - start_time:.9f} [sec], Func: {func.__name__}\")",
" return result",
" return _wrapper",
"",
"@func_speed",
"def func():",
" time.sleep(0.1)",
"",
"func()",
],
"description": "時間計測用デコレータ"
},
// Library ------------------------------------------------------
"Union-Find": {
"prefix": ":uf",
"body": [
"class UnionFind:",
"",
" __slots__ = \"par\"",
"",
" def __init__(self, n: int):",
" self.par = [-1] * n",
"",
" def root(self, x: int) -> int:",
" y = x",
" while self.par[y] >= 0:",
" y = self.par[y]",
" while self.par[x] >= 0:",
" z = self.par[x]",
" self.par[x] = y",
" x = z",
" return y",
"",
" def issame(self, x: int, y: int) -> bool:",
" return self.root(x) == self.root(y)",
"",
" def unite(self, x: int, y: int) -> bool:",
" rx = self.root(x)",
" ry = self.root(y)",
" if rx == ry:",
" return False",
" if -self.par[rx] > -self.par[ry]:",
" self.par[rx] += self.par[ry]",
" self.par[ry] = rx",
" else:",
" self.par[ry] += self.par[rx]",
" self.par[rx] = ry",
" return True",
"",
" def get_size(self, x: int) -> int:",
" return -self.par[self.root(x)]",
"",
" def members(self, x: int) -> \"list[int]\":",
" rx = self.root(x)",
" n = len(self.par)",
" return [i for i in range(n) if self.root(i) == rx]",
"",
" def roots(self) -> \"list[int]\":",
" return [i for i, x in enumerate(self.par) if x < 0]"
],
},
"Weighted Union-Find": {
"prefix": ":wuf",
"body": [
"class WeightedUnionFind:",
" __slots__ = [\"par\", \"rank\", \"siz\", \"diff_weight\"]",
"",
" def __init__(self, n):",
" self.par = [-1] * n",
" self.rank = [0] * n",
" self.siz = [1] * n",
" self.diff_weight = [0] * n",
"",
" def root(self, x):",
" if self.par[x] == -1:",
" return x",
" r = self.root(self.par[x])",
" self.diff_weight[x] += self.diff_weight[self.par[x]]",
" self.par[x] = r",
" return r",
"",
" def weight(self, x):",
" self.root(x)",
" return self.diff_weight[x]",
"",
" def diff(self, x, y):",
" if self.issame(x, y):",
" return self.weight(y) - self.weight(x)",
" return f\"{x} and {y} are not in the same group.\"",
"",
" def issame(self, x, y):",
" return self.root(x) == self.root(y)",
"",
" def unite(self, x, y, w):",
" w += self.weight(x)",
" w -= self.weight(y)",
" rx = self.root(x)",
" ry = self.root(y)",
" if rx == ry:",
" return False",
" if self.rank[rx] < self.rank[ry]:",
" rx, ry = ry, rx",
" w = -w",
" if self.rank[rx] == self.rank[ry]:",
" self.rank[rx] += 1",
" self.par[ry] = rx",
" self.diff_weight[ry] = w",
" self.siz[rx] += self.siz[ry]",
" return True",
"",
" def size(self, x):",
" return self.siz[self.root(x)]",
"",
"uf = WeightedUnionFind(n)",
],
},
"is Prime (Miller–Rabin primality test)": {
"prefix": ":isp",
"body": [
"def is_prime(n: int) -> bool:",
" if n == 2:",
" return True",
" if n < 2 or n % 2 == 0:",
" return False",
"",
" def check_composite(a: int, d: int, n: int, s: int) -> bool:",
" x = pow(a, d, n)",
" if x == 1 or x == n - 1:",
" return False",
" for _ in range(s - 1):",
" x = pow(x, 2, n)",
" if x == n - 1:",
" return False",
" return True",
"",
" s, d = 0, n - 1",
" while d % 2 == 0:",
" d //= 2",
" s += 1",
"",
" bases = (2, 7, 61) if n < 2**32 else (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37)",
"",
" for a in bases:",
" if a >= n:",
" break",
" if check_composite(a, d, n, s):",
" return False",
" return True"
],
},
"segment tree": {
"prefix": ":seg",
"body": [
"class SegmentTree:",
"",
" __slots__ = [\"n\", \"segfunc\", \"ide_ele\", \"num\", \"tree\"]",
"",
" def __init__(self, init_val, segfunc, ide_ele):",
" self.n = n = len(init_val)",
" self.segfunc = segfunc",
" self.ide_ele = ide_ele",
" self.num = 1 << (n - 1).bit_length()",
" self.tree = [ide_ele] * 2 * self.num",
"",
" for i in range(n):",
" self.tree[self.num + i] = init_val[i]",
"",
" for i in range(self.num - 1, 0, -1):",
" self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])",
"",
" def update(self, i, x):",
" i += self.num",
" self.tree[i] = x",
" while i > 1:",
" self.tree[i >> 1] = self.segfunc(self.tree[i], self.tree[i ^ 1])",
" i >>= 1",
"",
" def add(self, i, x):",
" i += self.num",
" self.tree[i] += x",
" while i > 1:",
" self.tree[i >> 1] = self.segfunc(self.tree[i], self.tree[i ^ 1])",
" i >>= 1",
"",
" def query(self, l, r):",
" res = self.ide_ele",
"",
" l += self.num",
" r += self.num",
" while l < r:",
" if l & 1:",
" res = self.segfunc(res, self.tree[l])",
" l += 1",
" if r & 1:",
" r -= 1",
" res = self.segfunc(res, self.tree[r])",
" l >>= 1",
" r >>= 1",
" return res",
"",
" def __getitem__(self, i):",
" return self.tree[self.num + i]",
"",
" def __str__(self):",
" return '[' + ', '.join(str(self[i]) for i in range(self.n)) + ']'",
"",
"st = SegmentTree(A, lambda a, b: a + b, 0)",
"min 1<<60",
"max -1<<60",
"lambda a, b: a+b 0",
"lambda a, b: a*b 1",
"math.gcd 0",
],
},
}
これからやること
階段本を進めながら典型90問やEDCPをやろうと考えています。
先のコンテストの問題でも痛感したのですが、問題を解くスピードは、類似の問題にぶつかった回数に比例すると思うので、コンテスト前に典型的な発想や言い換えに出会えるように数をこなそうと思います（似た話）。つまり今までとあんまり変わりませんね。
言語は今後もPythonで行こうと考えています。もともと始めた動機が業務でよく使うPythonのスキルアップなので、業務であまり使わないC++などの言語を覚えてもうまみが少ないからです。
ただこのような事情がないのであれば、C++で始めたほうがいいと思います。
上で挙げた本のサンプルコードは全てC++で書かれていますし、AtCoder以外のコンテストサイト（AOJやLeetCode）などでは、そもPythonを想定していない制約の問題もあるからです。
実装合ってるのに言語のせいでTLEになるのムカつくよね。
今後も趣味の一環として、ストレスを溜め込まない程度にゆる～く付き合っていければいいなと思います。
ここまで読んでくださった方はありがとうございました！
次は入水記事かあなたの色変記事で会いましょう。それでは楽しいゴールデンウィークと競プロ生活を！