トップ > AtCoder > AtCoder - 解法パターンの整理

AtCoder - 解法パターンの整理

AtCoder Python

よく出る思考パターン・覚えておきたいアイディアをメモしておきます．
問題の分類にもなっています．参考になるコードのリンクをメモしている問題もあります．

【2022.01追記】最近は，このページではなく，タグで分類するようにしています．

入力

import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))

A, B = map(int, input().split())

区切り文字を指定する：

# 1/9
m, d = map(int, input().split('/'))

【参考】

【例】


2つのリストを区別できるようにした上で，混ぜてソート．

A = list(map(lambda x: (int(x), 0), input().split()))
B = list(map(lambda x: (int(x), 1), input().split()))
C = sorted(A + B)

【例】

出力

改行して出力

ans = [1, 2, 3]

if ans:
  print(*ans, sep = '\n')

if ans:
  print('\n'.join(map(str, ans)))
  
# 1
# 2
# 3

bool

False, True

  • Falseとなるもの：None, False, 整数型の0, 空の文字列・リスト・タプル・辞書
  • Trueとなるもの：上記以外

比較演算子

  • イコールが常に右側（<=, >=, !=）
  • 演算子を連鎖させて判定可能（x > y >=z）

all, any

【参考】

切り捨て・切り上げ（床関数・天井関数）

ABCのA・B問題でよく出る．慣れないうちはmath.ceil()，math.floor()を使うと間違えない（慣れてくるとimport mathが面倒になる）．

以下，$x$を実数，$N$を正整数とするとき，

  • $x \div N$の小数点以下切り捨て = math.floor(x / N) = x // N
  • $x \div N$の小数点以下切り上げ = math.ceil(x / N) = (x + N - 1) // N
となる．慣れないと最後の表式が難しいが，$x \div N$の余りが$1,...,N-1$（$0$でない）場合だけ商が+1されることからわかる（詳細は参考記事）．

【参考】

【例】

四捨五入

from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
x = 11.55
print(Decimal(x).quantize(Decimal('0.0'), rounding=ROUND_HALF_UP))  # 11.6

x = 11.55
print((100 * x + 5) // 10 / 10)  # 11.6

x = 11.54
print((100 * x + 5) // 10 / 10)  # 11.5

注：Python3の組み込み関数round()は四捨五入でなく，偶数への丸め．
【参考】

【例】


ソート

  • リストにはsort()かsorted()：sortは上書き（インプレース）なのでイミュータブルには出来なさそう，ということから直感的に理解できる．
  • 文字列・タプルはsorted()：iterable の要素を並べ替えた新たなリストを返す．
  • いずれも，reverse=True で降順ソートできる．
  • いずれも，ソートに使う関数（Key 関数）を指定できる→ex.) key=lambda x: x[1]とすれば，2次元配列の第2要素でソートできる．
  • functools.cmp_to_key(functools --- 高階関数と呼び出し可能オブジェクトの操作 — Python 3.7.17 ドキュメント)を使うことで，比較関数を定義できる（例題：C - Standings/解答例）．

# 注：返り値はNone．l = sorted(l) と同じ．
l.sort()

【参考】

本当にソートが必要？→ソートだと間に合わず，heapqでの代用が必要な例：E - Sorting Queries


反転（逆順）

ソートと似ている．
  • s.reverse()：ミュータブルなシーケンスをインプレースに逆転（上書き）
  • reversed()：要素を逆順に取り出すイテレータを返す．

for を逆順で回すとき，range(start, stop, step)でstep < 0とするよりも

reversed(range(start, stop, step))

としたほうが（考えなくて良いので）ラク．

【参考】
Pythonでリストや文字列を逆順に並べ替え（reverse, reversed） | note.nkmk.me
組み込み関数 — Python 3.11.4 ドキュメント

スライス

後ろから指定

# [0, 1, 2, 3, 4]
A = [i for i in range(5)]
print(A)

for i in range(5):
  print(A[- i - 1:])
  
"""
[4]
[3, 4]
[2, 3, 4]
[1, 2, 3, 4]
[0, 1, 2, 3, 4]
"""

【参考】
Pythonのスライスによるリストや文字列の部分選択・代入 | note.nkmk.me

文字列操作

文字列型 (string) は
  • シーケンス型（インデックスを使ってデータにアクセスできる）だが，
  • イミュータブル（変更できない）
なので，文字列操作ではミュータブルな型（例えばlist）に変換する必要がある．

置換

s = 'ABCABC'
s = s.replace('BC', 'D')  # ADAD

【参考】

【例】

リストの結合

l = ['a', 'b', 'c']
print(''.join(l))
# abc

文字列でない場合は，文字列に変換する必要がある．

l = [0, 1, 2, 3]
print(''.join(map(str, l)))
# 0123

【参考】

deque - 先頭・末尾への追加・削除

deque というデータ構造で高速処理できる（listが$O(n)$に対し，dequeは$O(1)$）．

01-BFSも参照．

from collections import deque

que = deque()
que.append(i)
i = que.popleft()

【参考】


【例】

アルファベット⇔数字

print(ord('A'))  # 65
print(ord('Z'))  # 90
print(ord('a'))  # 97
print(ord('z'))  # 122
print(chr(122))  # z

【Python】文字列と数値（asciiコード）の変換まとめ - Qiita

文字列の位置（左端，右端）

S = 'ab0ab0'
print(S.find('a'))  # 0
print(S.rfind('a')) # 3

print(S.find('ab'))  # 0
print(S.rfind('ab')) # 3

print(S.find('c'))  # -1
print(S.rfind('c')) # -1

S = ''
print(S.find('a'))  # -1
print(S.rfind('a')) # -1

【参考】

【例】


正規表現

あまり使わないかも．

【参考】

【例】

リスト操作

注意

l = [[0, 1] for _ in range(4)]  # [[0, 1], [0, 1], [0, 1], [0, 1]]

を次のように書くのはNG．

l = [[0, 1]] * 4  # [[0, 1], [0, 1], [0, 1], [0, 1]]

なぜなら，以下の操作で全てが書き換わってしまうから．

l[0][1] = 2
print(l)  # [[0, 2], [0, 2], [0, 2], [0, 2]]

ただし，スカラーならOK．

l = [0] * 4  # [0, 0, 0, 0]

l[1] = 2
print(l)  # [0, 2, 0, 0]

2要素の入れ替え

以下で$O(1)$．

l[i], l[j] = l[j], l[i]

【例】

set

生成

{}で生成できる．

s = {'ABC', 'ARC', 'AGC', 'AHC'}

コンストラクタset()で生成

s = set(['ABC', 'ARC', 'AGC', 'AHC'])

空のオブジェクトは

s = set()

とすれば良い．

【参考】

【例】

集合演算

print(set('012'))  # {'0', '1', '2'}

print(set('012') & set('123'))  # {'1', '2'}
print(set('012') | set('123'))  # {'0', '1', '2', '3'}
print(set('012') - set('123'))  # {'0'}

【参考】

【例】

setの中にlistはダメ！

setの中にlistは入れられない（unhashable）．tuple or frozensetはOK．

例えば，ある座標の集合をチェックしたかどうかのメモmemo = set()を作るとき，memoの要素xの扱いは次の2通りが考えられる（編集はミュータブルであるlist, setを使わなければならず，setに入れる前にはhashableなtuple, frozensetに変換する必要がある）．
方法1.
編集するときはlist（x = [(0, 1), (0, 2)]のように，座標はtuple）→確定したらtupleに変更して，if tuple(x) in memo:, memo.add(tuple(x))

方法2.
編集するときはset（x = {(0, 1), (0, 2)}のように，座標はtuple）→確定したらfrozensetに変更して，if frozenset(x) in memo:, memo.add(frozenset(x))

【例】

組み合わせ

出現回数のカウントをとると，上手くいくことが多い．

出現回数 - collections.Counter

from collections import Counter

【参考】

【例】

同じ値になる組み合わせ

リスト$l$で$l[i]=l[j]\,(i\neq j)$となる組み合わせを数える．

①個数をカウントしてから，2個選ぶ組み合わせを計算する

from collections import defaultdict

cnt = defaultdict(int)
for li in l:
  cnt[li] += 1
 
ans = 0  
for k in cnt.keys():
  ans += cnt[k] * (cnt[k] - 1) // 2

②新しい要素が出るたびに，古いの要素との組み合わせを加算する．

from collections import defaultdict

cnt = defaultdict(int)
ans = 0
for li in l:
  ans += cnt[li]
  cnt[li] += 1

【例】

二項係数

\begin{aligned}
\binom{n}{k}
&=\frac{n!}{(n-k)! k!} \\
&=\frac{n(n-1)\cdots (n-k+1)}{k(k-1)\cdots 1} \\
&=\frac{n}{1} \frac{n-1}{2}\cdots \frac{n-k+1}{k}
\end{aligned}

from functools import reduce
def ncr(n, r):
    r = min(r, n - r)
    numer = reduce(lambda x, y: x * y, range(n, n - r, -1), 1)
    denom = reduce(lambda x, y: x * y, range(1, r + 1), 1)
    return numer // denom

functools.reduce(function, iterable[, initializer])は，例えばreduce(lambda x, y: x+y, [1, 2, 3, 4, 5])に対して((((1+2)+3)+4)+5)を返す．
【参考】

二項係数（mod 10**9+7）

よく（？）出くわす．背景はmodのセクションを参照．

from functools import reduce
M = 10**9 + 7

def ncr(n, r):
    r = min(r, n - r)
    numer = reduce(lambda x, y: x * y % M, range(n, n - r, -1), 1)
    denom = reduce(lambda x, y: x * y % M, range(1, r + 1), 1)
    return numer * pow(denom, M - 2, M) % M

【例】

mod

mod 10**9+7, mod 998244353

  • $10^{9} + 7, 998244353$は素数．
  • 素数$p$に対し，$X/ Y \pmod p=$(X * pow(Y, p - 2, p)) % p

【背景】
$p$を素数，$a$を$p$の倍数でない整数とすると

\begin{aligned}
a^{p-1} \equiv 1 \pmod p
\end{aligned}
が成り立つ（フェルマーの小定理）．よって，
\begin{aligned}
a^{-1} \equiv a^{p-2}\pmod p
\end{aligned}
である．

pow(base, exp[, mod])で，pow(base, exp) % modが効率よく計算できる．あるいは「繰り返し二乗法」で高速に計算できる（繰り返し二乗法 - 競プロはじめました）．


【参考】

【例】

自分で決める

大きなべきを計算するときに，modを自分で適切に決めなくてはならない場合がある．
【例】


式変形

考察するときは
\begin{aligned}
& a\equiv b \pmod p \\
&\Leftrightarrow a = b + kp\quad (\exist k \in \mathbb{Z})
\end{aligned}
とするとよい（かも）．参考：Editorial - AtCoder Beginner Contest 210

最大公約数・最小公倍数（gcd, lcm）

  • $\gcd(a, b, c) = \gcd( \gcd(a, b), c)$
  • $\mathrm{lcm} (a, b, c) = \mathrm{lcm} ( \mathrm{lcm} (a, b), c)$
  • $ab = \gcd(a, b) \cdot \mathrm{lcm} (a, b)$：$\mathrm{lcm} (a, b) = a\cdot b/\gcd(a, b)$と考えればわかる．

【例】

dict

出現回数のカウントなどで使用する．

from collections import defaultdict
count = defaultdict(int)  # {種類:出現数}
for key in name:
  count[key] += 1

for key in count.keys():
  # count[key] を使った処理

小さい値で更新したいときは，初期値を大きく取りたいことがある（メモ：B - RGB Matching）．

tmp = defaultdict(lambda: 10 ** 18)
for l1, l2 in zip(l, l[1:]):
  tmp[key] = min(tmp[key], abs(l1 - l2))


keyでループさせたい場合：

for k in d.keys():
  #

または

for k in d:
  #

値でループさせたい場合：

for v in d.values():
  #

keyと値でループさせたい場合：

for k, v in d.items():
  #

【参考】

【例】

約数・倍数・素数

区間[L,R]にあるiの倍数の個数

R // i - (L - 1) // i

\begin{aligned}
& (\text{区間$[L,R]$にある$i$の倍数の個数}) \\
&=(\text{区間$[0,R]$にある・・・}) \\
&\qquad
- (\text{区間$[0,L - 1]$にある・・・}) \\
&=\lfloor R/i \rfloor - \lfloor (L - 1)/i \rfloor
\end{aligned}

【例】

xの倍数の個数をカウント

cnt = [0] * (M + 1)
for a in A:
  cnt[a] += 1

mul = sum(cnt[x::x])  # [start:stop:step]

【参考】


エラトステネスの篩-likeな考え方

ポイント①：約数の問題では，与えられた数の倍数を全列挙することを考える．生成された回数をカウントするなど．

ポイント②：以下の計算量は$O(N\log N)$．
（※二重ループだから$O(N^{2})$と錯覚しがち）
不要な処理はcontinueすることを考える．

for i in range(N):
  for j in range(i, N + 1, i):
    # 処理

同じループは次でも表せる．

for i in range(N):
  j = i
  while j <= N:
    # 処理
    j += i

for i in range(1, N):
  for k in range(1, N // i + 1):
    j = i * k
    # 処理

【参考】

【例】

約数の列挙

N = i * qとなる$i$を$1\leq i \leq \sqrt{N}$の範囲で探せば，$i,q$が約数．q = N // i．

i = 1
while i * i <= N:
  if N % i == 0:
  # 
  i += 1

【参考】

【例】

2で割りきれる限り割り続ける

最下位bitが0なら偶数．

while not (x & 1):
  x  >>= 1

【例】

二分探索

bisect

import bisect
l = [0, 1, 2, 2, 3]
print(bisect.bisect_left(l, 2))  # 2
print(bisect.bisect_right(l, 2))  # 4

【参考】

【例】

二分探索

最大値を問う問題で使うことが多い．

次の形が基本形．

def check(x):
  if xxx:
    return True
  else:
    return False

ok = 2 * 10 **9 + 1
ng = 0
while ok - ng > 1:
  mid = (ok + ng) // 2
  if check(mid):
    ok = mid
  else:
    ng = mid

【参考】

【例】

N状態の全探索

$x$個の変数のそれぞれが$N$通りの状態を取り得るときに，全探索（$x^{N}$通り）する方法．

2状態 (bit全探索)

【例】

3状態以上

2状態ならbitで生成できるが，3状態以上ならどうするか．
【例】

方法1：再帰

再帰に慣れていればこれが簡単で汎用性もありそう．
（ライブラリ覚えている必要もない）

def f(cur):
  if len(str(cur)) == x:
    res.append(cur)
    return
  for s in state:
    f(10 * cur + s)

x = 2
state = [1, 2, 3]
res = []
f(0)
print(res)
# [11, 12, 13, 21, 22, 23, 31, 32, 33]

【参考】https://img.atcoder.jp/abc114/editorial.pdf

【例】

方法2：itertools.product

import itertools

l = list(itertools.product('123', repeat=2))
# [('1', '1'), ('1', '2'), ('1', '3'), ('2', '1'), ('2', '2'), ('2', '3'), ('3', '1'), ('3', '2'), ('3', '3')]

for li in l:
  tmp = int(''.join(li))
  print(tmp)

方法3：N進数

愚直にやる．

def f(x, state):
  l = len(state)
  res = []
  for i in range(l ** x):
    resi = 0
    tmp = i
    for _ in range(x):
      resi = 10 * resi + state[tmp % l]
      tmp //= l
    res.append(resi)
  return res

state = [1, 2, 3]
print(f(2, state))
# [11, 21, 31, 12, 22, 32, 13, 23, 33]

式変形

絶対値

  • $|x|=\max(x, -x)$
  • $\displaystyle \max_{i,j} |x_{i} - x_{j}| = \max_{i}x_{i} - \min_{i}x_{i}$

添字i, jが含まれる問題

式変形して「$i$だけで計算できるもの」「$j$だけで計算できるもの」に分離する．

【例】


再帰関数

再帰回数が多い場合は，上限を上げる必要がある．

import sys
sys.setrecursionlimit(10 ** 6)

以下でメモ化できる．

from functools import lru_cache

@lru_cache(maxsize = None)
def f(x):
  return f(x - 1)

【参考】

bit

ビット演算 (bit 演算) の使い方を総特集！ 〜 マスクビットから bit DP まで 〜 - Qiita

1 << Nは$2^{N}$に相当し，$N$番目のフラグが立つ．$N=0$ならゼロ番目．

次で$N$要素の集合を生成できる（空集合$0$から，$\{1,2,...,N\}$を表す$2^{N} - 1$まで）．$S_{1}\subset S_{2}$なら$S_{1}$より$S_{2}$の方が後に現れる．

for S in range(1 << N):
  # 処理

また，次はよく使われるので，人のコードを読むときはわかっていたほうが良い．

  • 1 << N$=2^{N}$
  • 1 << N | 1$=2^{N}+1$
  • x & 1$=x \% 2$（偶奇の判定）
  • x >>= 1$=x /\!/ 2$

フラグの個数

フラグが何個立っているかは次でわかる．

bin(x).count('1')

bin()はintをstrに変換する．
【参考】

01文字列をbitに変換

int('0b***', 0)

int('0b'+''.join(list(map(str, input().split()))), 0)

【参考】

【例】


グラフ

辺の読み込み

隣接リストとしての読み込み．

g = [[] for i in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

a, bの読み込みはa, b = map(lambda x: int(x) - 1, input().split())とすると一行で書けます．

DFS

【木 （連結・閉路なし）の場合】

def f(cur, par):

  # 葉では実行されない
  for chi in g[cur]:
    if chi != par:
      f(chi, cur)
      # 処理

f(0, -1)

【例】

【非連結・閉路ありの場合】
【例】


【有向グラフ】
頂点$v$から到達可能な頂点数は次でわかる．

def f(cur):
  if visited[cur]:
    return
  visited[cur] = True
  for chi in g[cur]:
     f(chi)

visited = [0] * N
f(v)
print(sum(visited))

【例題】

木

木の場合，任意の頂点を「根」としてBFSが使える．
【例題】

木の場合にDFSは「オイラーツアー」の順に頂点を訪れる．
【例題】

木の場合には，2頂点間の最短経路が一意に定まる．
【例題】


連結成分

連結成分が$X$コのグラフの連結成分を$Y$コにするために必要な辺の数は$Y-X$本．


最小全域木（MST - Minimum Spanning Tree）

全域木：無向グラフの部分グラフで，任意の2頂点が連結である木．
最小全域木：辺のコストの和が最小の全域木．

プリム法：木$T$に，木$T$の頂点と木$T$に含まれない頂点を結ぶ最小コストの辺を貪欲的に追加していく．木$T$の初期状態は1頂点．
クラスカル法：コストの小さい順に辺を見ていき，閉路・二重辺でなければ追加する．UnionFindを使う．バラバラの状態からはじめ，辺の頂点が同じグループに属していないなら追加すれば良い．

【参考】

  • 蟻本p. 99-

【例】

辺を見る

頂点を見る問題が多いが，辺を見ていく問題もある．

【例】


DAG (閉路のない有向グラフ)・トポロジカルソート

  • 閉路検出：トポロジカルソートで検出できる．
  • 「数字を頂点」，「順序関係を辺」と考えてDAGの問題にすれば，トポロジカルソートが使えるかも．
  • 「うまい具合に取り出せ」，「うまい具合に並べろ」という問題は，グラフ化してトポロジカルソートが使えるかも（「閉路があれば解無し」といえないか？）．

【例】

Lowlink - 橋，関節点

橋：ある頂点からDFSを始めて，頂点$v$を訪れた順番（行きがけ順，preorder）pre[v]を記録する．辺$uv$が橋であることと，$v$から深さ方向にたどってpre[u]より小さな値の頂点にたどり着かないことは同値．low[v]を
\begin{aligned}
\mathrm{low}[v]
=\min\{ \mathrm{ord}[w] \mid \substack{\text{$w$は$v$から後退辺を最大1回}\\ \text{まで用いて到達できる頂点}} \}
\end{aligned}
とすれば，
\begin{aligned}
& \text{辺$uv$が橋}\\
&\Leftrightarrow \mathrm{ord}[u] < \mathrm{low}[v]
\end{aligned}
となる．

【参考】

【例】

最短経路 - ダイクストラ法

$X$がスタート地点の場合に，各頂点への最短距離を求める．計算量は$O( (\text{辺数}) \log (\text{頂点数}) )$．

import heapq

INF = 10 ** 18
dist = [INF] * N
dist[X] = 0
que = [[0, X]]
while que:
  d, cur = heapq.heappop(que)  # 最小値は確定→取り出す
  if dist[cur] < d:
    continue  # 古い情報は飛ばす
  for chi, t, k in g[cur]:
    tmp = # 子の距離を計算
    if tmp < dist[chi] :
      dist[chi] = tmp
      heapq.heappush(que, [dist[chi], chi])

【参考】

【例】


辺の長さがすべて同じなら，更新順に距離が最小になるからdequeでよい（heapqより計算量が落ちる）．

from collections import deque
INF = 1000

dist = [INF] * N
prev = [[] for _ in range(N)]  # 経路復元
dist[0] = 0
que = deque([0])
while que:
  cur = que.popleft()
  for chi in G[cur]:
    if dist[cur] + 1 < dist[chi]:
      dist[chi] = dist[cur] + 1
      prev[chi] = cur  # 経路復元
      que.append(chi)

# --- 経路復元 ---
route = set()
cur = N - 1
while cur != 0:
  par = prev[cur]
  route.add((par, cur))
  cur = par

【例】

最短経路 - ワーシャル-フロイド法

全点対最短経路問題（すべての2頂点間の最短路を求める問題）を解くアルゴリズム．計算量は$O((\text{頂点数})^{3})$．中間地点として$k$コの点$\{v\mid v = 0,...,k - 1\}$だけを通るときの，頂点$i$から$j$への最短距離を$\mathrm{d}[k][i][j]$とする．ただし，$\mathrm{d}[-1][i][j]=\mathrm{cost}[i][j]$．遷移は$\mathrm{d}[k][i][j] = \min(\mathrm{d}[k-1][i][j], \mathrm{d}[k-1][i][k] + \mathrm{d}[k-1][k][j])$．$\mathrm{d}[k][k][j] = \mathrm{d}[k-1][k][j]$と$\mathrm{d}[k][i][k] = \mathrm{d}[k-1][i][k]$により，1つめのindexは不要になり，$\mathrm{d}[i][j] = \min(\mathrm{d}[i][j], \mathrm{d}[i][k] + \mathrm{d}[k][j])$と更新すれば良い．

INF = 10 ** 18
d = [[INF] * N for _ in range(N)]
for _ in range(M):
  a, b, c = map(int, input().split())
  d[a - 1][b - 1] = c
  # d[b - 1][a - 1] = c
for i in range(N):
  d[i][i] = 0

for k in range(N):
  for i in range(N):
    for j in range(N):
      # この更新でd[k][i][j]が確定
      d[i][j] = min(d[i][j], d[i][k] + d[k][j])


【例】

【参考】

  • 蟻本p.98

BFS

01-BFS

迷路で進み方が2種類ある場合に使う．普通に進む場合をコスト0，ある範囲でワープする方法をコスト1として，何回ワープしたか（総コスト）を数えるなど．
  • dequeを使い，コスト0を前から入れて，コスト+1の場合を後ろから入れる．
    • コスト0で到達できる範囲がなくなって初めてコスト1を調べることになる
    • コスト1で到達できる範囲がなくなって初めてコスト2を調べることになる
  • dequeに入れるのは，(総コスト, 現在地)．
    • 取り出したとき，すでに見ていたら処理をスキップ（例えば，コスト0で訪れたあとに，コスト1でも訪れた場合）


【例】


データ構造

heapq

ダイクストラ法も参照．

import heapq

h = []
heapq.heappush(h, x)
y = heapq.heappop(h)  # 最小値の取り出し

【参考】

【例】

Union-Find木

UnionFind木 - 競プロはじめました
要素のグループ分けを管理する．

次の操作が可能（注：分割はできない）．

  • 2つの要素を同じグループに併合する
  • 2つの要素が同じグループに属しているか調べる

初期状態では，各要素で1つのグループとなっている（バラバラ）．

【参考】

（なぜか，初期化の要素数を小さく設定してREするというミスを犯しがち）

【例】

セグメント木

集合$S$が二項演算$S\times S \ni (a,b)\mapsto a\cdot b \in S$をもち，①結合則（${}^{\forall} a,b,c\in S$に対し$(a\cdot b) \cdot c = a\cdot (b\cdot c)$）が成立し，②単位元が存在する（${}^{\exist} e\in S \mathrm{\:\,s.t.\:} e\cdot a = a\cdot e = a \, ({}^{\forall}a\in S)$）とき，$(S,\,\cdot, \, e)$をモノイドとよぶ（モノイド - Wikipedia）．

セグメント木は，モノイド$S$の元の列$\{x_{i}\}_{i=0}^{N-1}$に対して

  • $x_{i}$の変更
  • 積$x_{i}\cdot x_{i+1}\cdots x_{j-2}\cdot x_{j-1}$の計算
が効率的にできる．

【参考】

  • Segment Tree のお勉強(1) | maspyのHP（実装：Library Checker）
    • 単位元：X_unit，積：X_f
    • $N$要素で初期化：seg = SegTree(N)
    • データ列の読み込み：seg.build(A)
    • $x_{i}$の変更：seg.set_val(i, x)
    • $\prod_{i=L}^{R-1} x_{i}=$seg.fold(L, R)
    • $x_{i}=$seg.X[seg.N + i]
    • （$\{x_{i}\}_{i=0}^{N-1}$がseg.X[seg.N]〜seg.X[2 * seg.N - 1]に入る）

【例】

積 単位元 例
$\min$ $\infty$
$\max$ $0$ Q - Flowers
$+$ $0$

順序付き集合

Pythonにはないので，工夫が必要．

【例】


累積和

1次元

累積和$S_{0}=0, S_{n}=\sum_{i=0}^{n-1} a_{i}\,(n \geq 1)$から，連続した区間の和を$\sum_{i=m}^{n} a_{i}=S_{n+1} - S_{m}$と計算できる（$S_{n}=\sum_{i\in [0, n)} a_{i}$）．
特に，何度も計算するときには，事前に累積和を求めておくことで計算量を落とせる．

import itertools
l = [1, 2, 3]
acc = list(itertools.accumulate(l))
print(acc)
# [1, 3, 6]

# Σ_{i=0}^{n} l[i] = acc[n+1] - acc[0]としたい
acc = [0] + list(itertools.accumulate(l))
print(acc)
# [0, 1, 3, 6]

【追記】
$S_{-1}=0$としたほうが，$\sum_{i=m}^{n} a_{i}=S_{n} - S_{m-1}$と計算できてわかりやすいかも？（$S_{n}=\sum_{i\in [0, n]} a_{i}$）．

【参考】
Pythonで累積和・累積積（itertools.accumulate） | note.nkmk.me

【例】
A - Zero-Sum Ranges

2次元

その他

l[i]とl[i+1]でループ

リストの隣り合う2要素を取り出してループさせたい場合がある．

for a, b in zip(l, l[1:]):
  # 処理

【例】

4近傍・8近傍

端で配列が参照できなくなるのを回避する方法．

dx = [-1, -1, -1, 0, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 0, 1, -1, 0, 1]

for y in range(H):
  for x in range(W):
    for a, b in zip(dx, dy):
      i, j = x + a, y + b
      if 0 <= i < W and 0 <= j < H:
        # 配列[i][j]を使った処理


【例】

偶奇性

【例】

周期性

数列の取り得る値が有限個（※）なら，周期的にならないか考える．
※：例えば，$M$で割った余りは$0,1,...,M-1$の$M$通りしかない．
【例】

出現位置

出現位置を記憶すると上手くいく場合がある．
【例】

差分（変化したところ）だけ見る

全体の個数をカウンタで管理する．まず，初期状態だけ読み取る．その後は，ある場所（例えば区間の端）だけを変化させ，その場所だけカウンタを更新していく．変更させた場所のカウンタが特定の値になったときだけ，処理をする．


残り1変数を他の変数から求める

例えば変数が3つあるときに，2変数をループさせて残り1変数を関係式から逆算すると，3重ループが2重ループになる．
【例】

区間

  • 2つの閉区間$[a, b], [c,d]$が共通部分をもたない $\Leftrightarrow$ $\min(b,d) < \max(a, c)$
  • 2つの閉区間$[a, b], [c,d]$が共通部分をもつ $\Leftrightarrow$ $\max(a, c) \leq \min(b,d)$
  • 区間の端点が整数なら，$\pm 0.5$をすることで「$[$を$($に」，「$)$を$]$」に置き換え，すべて閉区間として扱えないか考える．


【例】


コピー (deepcopy)

from copy import deepcopy
A = [0, 1, 2, 3]

B = deepcopy(A)

deepcopyを使う理由は，Case. 2 を防ぐため．

from copy import deepcopy
A = [0, 1, 2, 3]

# Case. 1
B = deepcopy(A)
B[0] = 1
print(A)  # [0, 1, 2, 3]

# Case. 2
B = A
B[0] = 1 
print(A)  # [1, 1, 2, 3]

ゲーム

最終状態から考える（後退解析）．
  • 勝ち状態：負け状態に遷移できる（相手に負け状態を押し付けることができる）
  • 負け状態：勝ち状態にしか遷移できない
    • 後退解析で，遷移可能な状態数を管理しておき，勝ち状態への遷移を考えるたびに-1する．
    • 管理していた状態数がゼロなれば（すべて勝ちへの遷移なので）負け状態となる．
    • 管理していた状態数がゼロにならなければ，何もされない（引き分け）．よって，すべての状態は引き分けで初期化しておけばよい．

すでに確定した勝敗を，あとの処理で上書きしないように注意．

必勝法

【例】

勝ち負け判定

【例】

トーナメント

参加者が$2^{k}$人なら，トーナメントの深さは$k$．
【例】

グリッド

反転

2組のグリッド$(i, j)$と$(i^{\prime}, j^{\prime})$の処理をするとき，「$i \leq i^{\prime}$，$j \leq j^{\prime}$に関する処理」が実現できれば，
  • $i \geq i^{\prime}$，$j \leq j^{\prime}$の処理：グリッドを左右反転させることで上の処理に帰着する
  • $i \leq i^{\prime}$，$j \geq j^{\prime}$の処理：グリッドを上下反転させることで上の処理に帰着する
  • $i \geq i^{\prime}$，$j \geq j^{\prime}$の処理：グリッドを上下・左右反転させることで上の処理に帰着する
ことがわかる．

グリッドの反転は，配列の反転で表現する．

# 左右反転1
for i in range(H):
    A[i].reverse()

# 左右反転2
A = [[A[i][-j - 1] for j in range(W)] for i in range(H)]

# 左右反転3
A = [A[i][::-1] for i in range(H)]

【例】

座標圧縮

Xdict = {x:i+1 for i, x in enumerate(sorted(list(set(X))))}
Ydict = {y:i+1 for i, y in enumerate(sorted(list(set(Y))))}

【例】

図形

図形の一致

  • 回転角が$90^{\circ}$の倍数の場合：$90^{\circ}$回転ごとに，端の点を一致させて比較する
  • 回転角が任意の場合：重心（幾何中心）をあわせて，回転させて比較する

【例】

回転

反時計回りに$\theta$回転させる．

import math

N = int(input())
S = [tuple(map(int, input().split())) for _ in range(N)]

def rot(S, theta):
  cos = math.cos(theta)
  sin = math.sin(theta)
  return [(x * cos - y * sin, x * sin + y * cos) for x, y in S]

反時計回りに$90^{\circ}$回転させる．

def rot(S):
  return [(-y, x) for x, y in S]

【参考】回転行列の表式と導出（2次元・3次元） - Notes_JP

偏角

点$(0,r)$を点$(x,y)$に回転させたいとき（$r=\sqrt{x^{2} + y^{2}}$），回転角$\theta$はmath.atan2(y, x)で求められる．

【参考】math --- 数学関数 — Python 3.11.4 ドキュメント

問題になる場合はほとんどなさそうだが，以下のようにゼロの符号で結果が変わることに注意が必要（Pythonで三角関数を計算（sin, cos, tan, arcsin, arccos, arctan） | note.nkmk.me）．多分，点列の極限としてイメージすると間違えない．

print(math.degrees(math.atan2(0.0, 0.0)))  # 0.0
print(math.degrees(math.atan2(-0.0, -0.0)))  #  -180.0

【例】

atan2では計算誤差で上手く行かない場合がある．
【例】

平行移動（重心（幾何中心）を原点に）

座標が整数の場合，座標全体を$N$倍すれば，座標変換後も整数の座標で扱える．

def adjust(S):
  x0 = sum(S[i][0] for i in range(N))
  y0 = sum(S[i][1] for i in range(N))
  return [(N * x - x0, N * y - y0) for x, y in S]

XOR - 排他的論理和

bit

\begin{aligned}
& x \oplus x = 0 \\
& x \oplus y = y \oplus x \\
& (x \oplus y) \oplus z = x \oplus (y \oplus z)
\end{aligned}

上の性質より，$x\oplus y = z \Rightarrow y = x\oplus z$となる（逆演算）．

最下位ビットが$0$か$1$かだけが異なるため，

\begin{aligned}
& 2n \oplus (2n+1) = 1 \quad (n\in\mathbb{N}) \\
\end{aligned}

$x > 0$に対して

\begin{aligned}
& x\oplus (x + 1) \oplus \cdots \oplus (x + n) \\
&= [0 \oplus 1 \oplus \cdots \oplus (x - 1)] \oplus [0 \oplus 1 \oplus \cdots \oplus (x + n)]
\end{aligned}

【例】

エラー

RE

再帰回数の上限は十分か．

MLE

PyPy3→Pythonで提出してみる．
itertoolsを使ったときに起きやすい．
【例】



参考文献

次の書籍が，いろいろなことがコンパクトにまとまっていてよかったです．4章 Pythonの基礎がかなり勉強になります．
科学技術計算のためのPython入門 ――開発基礎、必須ライブラリ、高速化

科学技術計算のためのPython入門 ――開発基礎、必須ライブラリ、高速化

Amazon


【その他】
Pythonで競プロやるときによく書くコードをまとめてみた - Qiita
Python3で競技プログラミングする時に知っておきたいtips（入力編） - Qiita
Pythonで競技プログラミング -ライブラリ編- - Qiita
Python で AtCoder をするあれこれ - Qiita
Python競プロでやりがちなミス | 機械学習エンジニアの技術メモ