■本記事の狙い
❶自分の進捗や学びをリアルタイムで公開しモチベーションを上げること
❷初心者のリアルな学び・過程を残し、同じく初心者コーダーのご参考とすること
■目標と方針
| 時期 | 問題数 | AtCoderランク目標 |
|---|---|---|
| 2023年10月末 | 計50問 | 茶色（3完） |
| 2023年12月末 | 計100問 | 緑色（4完） |
| 2024年 2月末 | 計150問 | 水色（5完） |
⇒BeginnersContestのA~C過去問をメインに解き基本的解法を身につける
■ 問題と学び
８３ ABC336 C Even Digits
✓10進数⇒n進数の変換
def base_n(num_10, n):
str_n = ""
while num_10 > 0:
str_n += str(num_10 % n)
num_10 //= n
return int(str_n[::-1])
✓整数問題でm個の数字ごとに規則性がある場合
⇒m進数を使って考えるとよい。
例）
0, 2, 4, 6, 8を使ったN番目に大きい数字n の工夫
n：0,2,4,6,8,20,22,24,26,28,..
であるが、この単調性を見て、2で割ると
n'：0,1,2,3,4,10,11,12,13,14..
これを5進数で表すと
n''：0,1,2,3,4,10,11,12,13,14..
つまり、N番目の整数を5進数とみなして値を計算するとN-1になる。
８２ ABC336 B CTZ
８１ ABC336 A LongLoong
８０ ATC001 B Union Find
✓Union Find
グループ分けに用いる。2つの要素x, yを同じ集合に結合するunion(x, y)と同じ集合か確認するcheck(x, y)を行う。
その過程で、ある要素xの"親"を見つけるfind(x)を用いる。
７９ 第三回アルゴリズム実技検定 I 行列操作
✓操作対象や操作が特徴的なクエリ処理
特徴的な場合（例えば行列の行・列操作など）は、個々の操作を行わず、そのルールだけを簡潔に処理してシンプルに解くことができる（行列の値まで踏み込まず、そのindexの操作を組み合わせるだけで済むなど）
７８ 第一回アルゴリズム実技検定 K 巨大企業
✓グラフに対するクエリ
独立したクエリを個々に解くのではなく、木・数列などの探索としてまとめて解く場合が多い。
特に「２要素間の関係」（上司・部下など）を解く場合は、片方の情報を持ちながら木や数列を探索して。もう片方の場所に訪れた時にクエリの答えを得る、という作成んがうまくいことが多い。
７７ 第二回アルゴリズム実技毛堰堤 G ストロング・クエリ
✓クエリの計算量
クエリ単体ではなく全体の計算量を見積り、それが効率的になるように、全クエリをまとめて計算したりデータ構造を工夫する。
７６ Educational DP Contest129 H Grid1
✓計算したい値の循環依存
盤面探索では、進む方向が一定であるとき計算したい値の循環依存が生じず、盤面をグラフに見立てるとトポロジカルソートの順になるため、計算方向が一意に決まり動的計画法でスムーズに解ける。
７５ ABC129 C Typical Stairs
✓答えを何か（MOD = 10**9+7 など）で割る問題
答えが足し・引き・割り算で求まる場合、途中で ans %= MODをしておく
pow(a,b,MOD)⇒aのb乗をMODで割ったあまり を用いてもよい
７４ 典型アルゴリズム問題集 F 最小全域木
特になし
７３ 典型アルゴリズム問題集 E 全点対最短路問題
✓二次元配列の初期化
dist = []
for i in range(N):
dist.append([]) #これがないとN*Nの一次元配列としてINFが格納される
for j in range(N):
dist[i].append(INF)
７２ 典型アルゴリズム問題集 D 単一始点最短路問題
✓ダイクストラ法（経路に重み差があるとき）の隣接リスト
(隣接する頂点i, 頂点iまでの移動コストc)をリストに持たせる
✓ダイクストラ法（経路に重み差があるとき）の距離更新
未更新だけでなく、更新済みでも今見ている経路のほうが短いか？を見る
if dist[j] == -1 or dist[j] > dist[i] + x:
７１ ABC068 Cat Snuke and a Voyage
✓移動コストが1の最短路問題
幅優先探索で隣接リスト・dequeを使いdistを更新すればよい。
移動コストが平等に1ではない場合はダイクストラ法・ワーシャル・フロイド法。
７０ ARC050 B 花束
✓二分探索への持ち込み
直接Max/Minを求められないときには、その問題に単調性がある場合、「この値は条件を満たすか？」という判定問題を作ることで二分探索に持ち込める。
６９ ABC146 C Buy an Integer
✓整数Nの桁数
len(str(abs(N)))で求まる。※N // 10 ではただ10分の1されるだけで間違い。
６８ 典型アルゴリズム問題集 A 二分探索の練習問題
✓ソート済み配列の中でK以上になる最小インデックスを求める 二分探索の実装
N, K = map(int, input().split())
A = list(map(int, input().split()))
ok = N #"K以上"なので数値の大きい側がok。K以下であればok, ngは逆。
ng = -1
while abs(ok - ng) > 1:
mid = (ok + ng) // 2
if A[mid] >= K:
ok =mid
else:
ng = mid
print(-1 if ok == N else ok) #題意のindexがなければokが初期値のまま
なお、これはbisectモジュールで完全に代替できる
（bisect_left(A,K)はK以上で、rightはKよりも大きい、になる）
import bisect
N, K = map(int, input().split())
A = list(map(int, input().split()))
ok = bisect.bisect_left(A, K)
print(-1 if ok == N else ok)
６７ 全国統一プログラミング王決定戦予選 C Different Strokes
✓貪欲法 A, Bが交互に意思決定し点を競う場合
AさんがN個の料理の中からiを選ぶとAi, 同様にBさんはBiの幸福度を得て、両者自分の総得点と相手の総得点の差が正に大きくなるよう選択する。
このとき、Aさんは A1-B2 >= B1-A2となる場合に料理2よりも１を選ぶので、A+Bが大きくなるような（つまり自分の得点と相手が潜在的に失う点の和が大きくなるような）料理順にソートすれば貪欲法を用いることができる
６６ 典型アルゴリズム問題集 B 区間スケジューリング問題
✓区間スケジューリング問題の解き方
１．タスク区間を終了日が早い順にソート
２．タスク区間を順番に見て実行可能であれば実行する
⇒[終了日, 開始日]で配列にタスク区間を保持しておく。
６５ 第二回アルゴリズム実技検定 F タスクの消化
６４ ABC333 C Repunit Tri
✓入出力例による簡易化
一見複雑な問題も入出力例を見ると探索範囲の上限など見つかることがある。
例えばNが33以下の制約時に、入出力例でN=33のとき答えが12桁という例があると、探索範囲が12桁以下と分かり全探索でもOKの場合がある。
６３ ARC C Attention
✓累積和
S = "YYNNY"のYを数える累積和は
sum = [0]
for i in range(len(S)):
if S[i] == 'Y':
sum.append(sum[i] + 1)
else:
sum.append(sum[i] + 0) #そのままの数字を要素として要追加
６２ ARC107 A Simple Math
６１ ABC179 C A×B+C
✓計算量を浮かせるアルゴリズムの工夫
★シンプルな実装から始めて計算量ネックを改善していくのが着実なアプローチ
A×B+C = N(given)を満たすA, B, Cの組（2<=A<=B<=1e6））
１．A, B, C総当たり：O(N ** 3)⇒1e18
rep(A)rep(B)rep(C):
if AB+C == N ~~
２．A, B総当たりでCは計算：O（N ** 2）⇒1e12
rep(A)rep(B):
if C = N - AB > 1
ans += 1
３．A, B総当たりでCは計算、Bは早めにbreak ⇒O(NlogN)1e9程度
rep(A)rep(B):
if C = N - A*B > 1:
ans += 1
else:
break #ループ試行回数はA=1でN、A=2でN/2、、なので合計 NlogN
４．A総当たりごとにクリアするBの回数を直接求める
rep(A):
b_count = (N-1)//A
ans += b_count
６０ 第三回アルゴリズム実技検定 C 等比数列
✓扱う数字のサイズ
10 ** 20を超える大きさの数が出てくるようであれば注意。Python以外のC++等はその程度が扱える限界であるため、数字の扱いに何か改善点がいる可能性が高い
例）等比数列AR ** Nを扱うとき、A==1だとNがいくつになっても閾値達しない。
例）順当にAR ** Nを扱うのではなく対数で桁を見積もる。
５９ ARC017 C 無駄なものが嫌いな人
✓全探索が間に合わない場合
半分全探索で簡単に解けないかを試みる。N=30の場合、2 ** 30>1e9だが、2 ** 15<1e5で間に合う
✓リスト内の要素に対する集合
リストAの要素からなる集合は for i in range(1<<len(B)) で表現、探索可能
５８ 典型アルゴリズム問題集 C 巡回セールスマン問題
✓巡回セールスマン問題のDPで用いる状態
cost[n][i]：すでに訪れた都市の集合nであって、最後に訪れた都市がiの時の最小移動コスト
✓DPの計算順序
サイズの小さい部分問題から解く必要があるので要素数の小さい集合から順番を増やすのが基本。ただし、ある集合nについて答えを求めるときには、そこから１つの要素を取り除いた集合に対する答えが計算済みであれば十分。つまり、nを小さい順に見ていけば、各nに対して必要な値は自動的に計算済みの状態となるため、正しい結果が得られる。
例えば、11101を解くには、1つ1の少ない(1か所訪問箇所が少ない)10101や11100が求められている必要があり、これらは元のbit表記集合に対する部分集合であるから元の数字よりも小さい。故に、小さい数字から動的計画法で計算していけば、必然的に必要な（小さな）部分集合から問題を解いていくことができる。
５７ 第一回アルゴリズム実技検定 I 部品調達
✓状態YYNYYNのbit表示
s = input() #"YYNYYN"
s_val = 0
for j in range(N):
if s[j] == 'Y': #Yの箇所のindex特定
s_val = s_val|1<<j #bit列に反映するため和集合をとる
✓動的計画法の基本
状態（cost[i][n]など）、初期条件（cost[0][0]=0など）、遷移（iを買う/買わないなど）
✓bit列の和集合表現
2進数nによって101101のようにi番目の商品があるか否かを表現しているとき、新たにS[i]という同様の2進数表記の商品を購入すると、n|S[i]という2進数表記で商品の有無を表現し直すことができる
５６ 第一回アルゴリズム実技検定 G 組分け
✓重複のないグループ分け
集合を2進数表記で表しグループA, Bをそれぞれ表す数字nA, nBの積が０
さらに３つ目のグループはnC = (2 ** N-1) - (nA|nB) = (2 ** N-1) - nA - nB
※全要素にbitが立った全集合2**N-1から特定の集合を差し引く。
AとBに重複がない場合はnA|nB = nA + nB - nA & nB = nA + nBとなる
✓ビットシフト
2**Nと1<<Nは同じ。※2^Nは２のN乗ではないので注意
^はbit同士のXORを指すので、例えば2^5は010^101=111=7(10)となる
５５ AE DP Contest G Longest Path
✓有向非巡回グラフに対する動的計画法
⇒閉路のない有向グラフでは必ずトポロジカルソートが存在する（辺に沿って進むほど値が大きくなるよう各頂点に番号を割り当てること。単調増加であればとびとびの数字でも問題ない）ことを使う場合が多い。
length[i]：iを始点とするパスのうち最も長いもの、を考えてメモ化再帰で実装
✓有向グラフの入次数・出次数
length[i]を再帰的に定義し、全ての始点に対してlengthを呼び出して最大値を求めるが、実は入次数が非０の始点はlengthを調べる必要がない。
入次数が非０ということは、その接続先の始点からlengthをとった方が長いパスになるからである。故に、辺情報を受け取るときに同時に入次数indeg[]配列で各点iの入次数をカウントしておく。
図の出典ページ：https://www.momoyama-usagi.com/entry/math-risan07
（上記ページ、勉強のため参照させていただきました）
用いる変数：隣接リストedge（どういったグラフの構造で）、入次数リストindeg（どの始点は調べる価値があり）、計算済みフラグリストdone（どの始点は計算済みで）、最大パス長リストlength（各始点からのパス長はいくらか）
５４ ABC026 C 高橋君の給料
✓木に対する動的計画法（木DP）
特に根付き木の構造において、葉から根の方向へ順番に値が決まっていく、またはその逆の場合は、深さ優先探索による実装がうまくいことがおおい。
５３ 第二回アルゴリズム実技検定 H 1-9Grid
✓計算する順番を工夫する動的計画法
N*Mのマス目のうち、1⇒2⇒3..のマス目を移動する最小移動回数を求めるには、1⇒...n-1⇒nに移動する最小コストを求めればよい
⇒group[n][(i1,j1), (i2, j2)..]といった形で番号ごとにグループ化
５２ AE DP Contest D Knapsack 1
✓ナップサック問題
重さwiで価値がviの荷物を組み合わせて、W以下で最大価値を算出する
⇒深さ優先探索だとO(2**N)かかりTLE
⇒合計重さが同じになる選び方の中では価値の高いものだけを考える
⇒多次元配列を用いた動的計画法で解く
⇒状態定義１：value[i][w]：1,.,i個までの荷物で重さwになる価値を最大化
or状態定義２：weight[i][v]：1,..,i個までの荷物で価値vになる重さを最小化
⇒遷移：品物iを選ぶ/選ばない場合で状態を計算しmax/minをとって状態更新
★計算量がそれぞれO(NW)、O(NV)となるので、少ない方を選ぶとよい。
５１ 第三回アルゴリズム実技検定 H ハードル走
✓複数アクションをとれるときのコスト問題
各アクション１～３をとるたびに、cost = min(cost, 別cost)という形で更新し続ければ、各地点での最小costが簡単に求まる
５０ AE DP Contest A Frog１
✓移動の最小コスト
途中地点iまでの最小コストを求める小さな問題を解き、それを用いて一段大きな問題を解く手順を繰り返す動的計画法が有効。
４９ ABC114 C 755
✓整数問題も幅/深さ優先探索が有効
3, 5, 7が含まれるN以下の数字の個数を求める場合、その樹形図を描いてグラフ上の探索問題に持ち込む。深さ優先の場合は、dfs内でNより大きければreturn、そうでなければ3, 5, 7が入っているかを確認し、Trueならばさらに末尾へ3, 5, 7を探索するdfsを再帰呼び出しする
４８ ATC001 深さ優先探索
✓Python実装時の必須対応
Pythonの言語仕様では多くの場合、関数の再帰呼び出し深さに上限がある（1000程度）
多くの問題では足りないため、下記の通り再帰上限を自変更する
import sys
sys.setrecursionlimit(1000000)
４７ ABC007 C 幅優先探索
✓タプルとリスト
(1,1,1)がタプルで[1, 1, 1]がリスト
✓二次元配列の引数
S[sy][sx]が正しい。S[[Sy, Sx]]のようにしない。
✓計算量
BFSはO（N + M）であることに気を付けて、TLEにならないよう見積もる
４６ 第一回アルゴリズム実技検定 H まとめ売り
✓計算量を意識しPythoの1e8以下に抑える
例えば２重ループで計算量がO(Q * N)、Q, Nが最大1e5の場合、Pythonの1e8以下の計算量に抑えられず時間オーバーとなる。故にどちらかのループ処理をO(1)などに抑えられないか？本質的に無駄な計算をさせていないかを見直す。
✓最小値の求め方
一番最初に適当な大きい値を用意しておき、以降は候補との間でminをとる。
４５ 第一回アルゴリズム実技検定 E SNSのログ
✓操作最中の処理は意図せず結果を変えないよう別変数に格納する
例）N人のユーザに対して、Aさんがフォローフォローを行う場合（Aさんがフォローしている人Xiさんがフォローしている人全員をフォローする）
Aさんフォローリスト{1, 3, 10}をフォローしている場合、1のフォローしている人を全員Aさんのフォローリストに追加してしまうと、{1,2,3,4,7,10}のようになる。
すると2のフォローしている人まで深追いしてしまう意図しない実装となる
⇒操作途中の結果は別変数に格納しておけば元のフォローリスト{1,3,10}で処理可能
✓改行しないprint文
print('Test', end='')とすれば改行されない
改行をしたいときはprint()すればよい
４４ 第二回アルゴリズム実技検定 H まとめ売り
４３ 第二回アルゴリズム実技検定 E スプリンクラー
✓無向/有向グラフの扱い
頂点同士をつなぐ辺の有無を隣接行列 or 隣接リストで管理する
例）隣接行列 サイズ3*3の2次元配列
頂点０ 頂点１ 頂点２
頂点０ False True True
頂点１ True False True
頂点２ True True False
graph = [
[False, True, True],
[True, False, True],
[True, True, False]
]
例）隣接リスト サイズ3の1次元配列
graph =[
[1,2],
[0,2],
[0,1]
]
４２ ABC165 A We Love Golf
✓長さ3の任意の文字列
C = 'abcdefghijklmnopqrstuvwxyz'
for c1 in C:
for c2 in C:
for c3 in C:
T = c1 + c2 + c3
✓文字列Sの中で文字列Tのパターンマッチ
Sの途中i+j番目とTのj文字目を比較すればよい
for i in range(0, len(S) - len(T) + 1):
for j in range(0, len(T)):
if S[i+j] == T[j]
４１ ARC046 A ゾロ目数
✓コンピュータの計算速度は1秒間に1億（10**8）回程度
４０ 第二回アルゴリズム実技検定 C 山崩し
✓文字列の変更法
文字列はイミュータブル（変更不可）で書き換えできない
書き換え時は一度リスト（ミュータブル）に変換してから文字列に戻す
list()でリストにして書き換え、''.join()でリスト結合し文字列化
３９ ABC088 C Takahashi's Information
３８ ABC157 B - Bingo
✓N*Mの2次元配列を格納するとき
A = []
for _ in range(0, N):
row = list(map(int, input().split()))#1行分
A.append(row)
✓ビンゴカードの当たり判定
True/Falseの入った専用の2次元配列を用意する
✓aのb乗はa ** b
３７ ABC323（当日参加）C
（作成中）
３６ ABC323（当日参加）B
（作成中）
３５ ABC323（当日参加）A
✓if文の簡略化
print("No" if <条件式> else "Yes")
✓bit演算
入力が100101のように2進数の場合、int(input(), 2)で2進数として受け取れる。
これとbit列の間で&などをとることでbit演算ができる
逆に普通の10進数の数値はbin()によって２進数に変換できる
３４ ABC322（当日参加）C
（作成中）
３３ ABC322（当日参加）B
✓リストの最後のインデックスは-1を使ってスライスできる
L = [1, 2, 3, 4, 5]のときL[-1]など。
３２ ABC322（当日参加）A
３１ ABC317 C
（作成中）
３０ ABC317 B
（作成中）
２９ ABC317 A - Points
２８ ABC318 C - Blue Spring
✓合計N枚買ううちの何枚かをD枚セットに置き換える場合、
for i in range(0, N, D):とすればD枚おきに進んでくれる
（for i in range(0, N):の後にif文かませるよりよい）
２７ ABC318 B - Overlapping sheets
✓x, y平面は SQ =[[0]*Nx for _ in range(Ny)]のように空箱用意可能
そしたら、for x in range(x1, x2):のようにしてSQ[x]にアクセス
２６ ABC318 A - Full Moon
２５ ABC319 C - False Hope
✓マス目の走査
①マス目であっても2次元配列にする必要はなくリストで直線状に格納
例）
for _ in range(3):
list += list(map(int, input().split())) #0..N*M-1まで数字並ぶ
②その中でますを確認する順番は順列で与えればよい
例）
for p in permutations(range(N*M))
③その中で着目する特定のマス番号に着目する
例）
check_nums = [(0,1,2), (3,6,8)]#
for a,b,c in check_nums:
# list[a]#a番目のマスの値 p.index(a)#a番目に確認するマスの値
２４ ABC319 B - Measure
✓リストから文字列への変換
List = ['A', 'B', 'C']のとき、STR = ''.join(List)
でSTR = "ABC" #join()はリスト内の要素を文字列として連結
２３ ABC319 A - Legendary Players
✓辞書型の定義と要素追加
my_dict = {"name": "Alice", "age": 30} #定義
my_dict["city"] = "New York" #新しいキーと値を追加
２２ ABC320 C - Slot Strategy 2 (Easy)
✓十分大きな数はINF=1e9とおく（e9は×10 ** 9の意）
✓if文の短縮 print(A if 条件式 else B)
✓文字列のindexの求め方
S = "ABCD"の場合、S.index("A")で0が返る
✓順列 permutatios と組み合わせcombinations
from itertools import permutationsで使える
permutations_obj = permutations(iterable, r) #rは順列の長さ（略可）
例）リストL = [1,2,3]や文字列S = "ABC"に対して、
perm_obj = permutations(L, 3) #タプル形式
perm_list = list(perm_obj) #リストに格納
print(perm_obj) # [('A', 'B', 'C'), ('A', 'C', 'B')..]
例）0~4のうち2つ選ぶ組み合わせ
for p in permutations(range(5),2):
print(p) #(0,3)や(2,5)など。順列なので(5,2)も入る
⇒同様に組み合わせはcombinations関数
✓少なくとも1つの要素にxxだったら~という条件式
例）if any(d not in S[i] for i in range(3)):
文字列を要素に持つリストSに対して、そのうち1つでもdがなければTrue
２１ ABC320 B - Longest Palindrome
文字列のインデックスは start:stop:step
例）S="ABCD"のときS[1:4]は"BCD"になる（Bが1、Cが2、Dが3のindex）。
例）S="ABCD"のときS[::-1]は"DCBA"になる（start/step省略で逆向き）。
例）S="ABCD"のときS[3:1:-1]は"DC"になる（index3のDから逆向きに進みindex1より1個前index2のCまで見る）
２０ ABC320 A - Leyland Number
✓AのB乗はA ** B
1９ ABC321 C - 321-like Searcher
✓bit全探索
例えば40, 961のように各桁が単調減少の数字を全て格納する場合は、
9 8 7 6 5 4 3 2 1 0 のそれぞれで使うか使わないかをbitで表現し
1 0 1 1 0 0 0 1 1 0 のように対応させればよいので2**10通りある。
各桁に1が入っているかを毎度確認するときは、n >> j & 1(j : 9~0)のようにnを1桁ずつずらして
1と当たるか調べればよい。（n >> 1 は2進数のnを1桁右にずらす操作。1001であれば100になる。）
1８ ABC321 B - Cutoff
✓リストの代入は参照渡し
リストAがあったときに、B = AとしてからB.append(x)をするとAにもxが追加されてしまう。
Bだけに足したい場合には、 B = A[:] + [x]とすると、xだけを要素に持つ[x]とAの結合になる。
あるいは、B = A.copy()としてもよいが、内部の要素が参照型の場合は結局同じ参照先を見るため注意。
A = [1, 2, 3]
B = A.copy() # AとBは異なるメモリ領域を持つが、同じ要素を参照している
print(A is B) # 出力: False
A = [[1, 2], [3, 4]]
B = A.copy() # AとBは異なるメモリ領域を持つが、内部のリストは同じ
print(A is B) # 出力: False
print(A[0] is B[0]) # 出力: True
1７ ABC321 A 321-like Checker
Next
競プロ典型 （★2の問題）
https://atcoder.jp/contests/typical90/tasks
１６ 004 - Cross Sum（★2）
✓2次元配列の作り方（行ごと代入をN列分繰り返す）
A = [list(map(int, input().split())) for _ in range(N)]
✓map関数
map（f, A）はイテラブルAの各要素に関数fを適用し新しいイテラブルを返す
例）map(sum. A)はAの各行の和を取ってリストを返す
✓イテラブル
イテラブル（iterable）は、Pythonで要素を1つずつ反復処理できるオブジェクト
リスト(list）、タプル（tuple）、文字列（string）、辞書（dictionary）、集合（set）
１５ 010 - Score Sum Queries（★2）
✓２重ループ解消による計算時間短縮
１重分のループ結果をあらかじめ保持しておけば2重化を回避できる。
例）Ci(1組or2組), Pi(点数)が入力の時、毎回Ciの値次第でPi和を取ると
for i in range(N):
if(Ci == 1):
sum += Pi
のように、loopになってしまう。もう1ループ回すとN**2の計算量になる。
ここで、Piの和を取った配列を予め作ることで二重ループを解消できる。
for i in range(N):
if Ci = 1:
sum[i+1] = sum[i] + Pi
sum[a:b]のようにスライスすれば、好きな結果を取り出せる。
✓配列のスライス
A[n1:n2+1] # n1からn2までの範囲を含む（n2+1に注意）
１４ 022 - Cubic Cake（★2）
✓最大公約数（gcd）と最小公倍数（lcm）
from math import gcd, lcm で使える
✓割り算の整数値を求める
× int(a/b) ...a/bで小数点計算後にintで切り捨てする
〇a//b ...最初から整数部のみ計算する
⇒前者は小数部の桁丸めで精度が悪くなり得るし、そもそも無駄な計算
１３ 024 - Select +／- One（★2）
１２ 027 - Sign Up Requests （★2）
✓要素の追加方法
listAにはA.append(x)、setAにはA.add(x)を使う
１１ABC086C - Traveling
✓まとめてリストのデータを入れる方法
リストサイズ未指定（d=[]）はappend、指定（d=[None]*N）ならインデックス代入
d = []
for i in range(0, N):
d.append(int(input()))
#または
a, b = [None]*N, [None]*N #ここでa, b = [], []はダメ
for i in range(0, N):
a[i],b[i] = map(int,input().split())
１０ABC049C - 白昼夢
✓可変/不変のデータ構造 メソッドによる変数の変化
・リストは可変（mutabl）のデータ構造であり、リスト内の要素を変更できる
⇒（リスト）.sort() で元のリストが変更される
・文字列は不変（immutable）のデータ構造であり、元の文字列を変更できない
⇒（文字列）=（文字列）.replace() のように新しい文字列を返す
９ABC085C - Otoshidama
✓プログラムを途中で抜ける場合
exit() #プログラムを終了させて良いならflgを持たせるよりも楽
８ABC085B - Kagami Mochi
✓複数入力A1 A2..（縦並び）のリスト格納
d = [int(input()) for _ in range(N)]
または
d = []
for i in range(0, N):
d.append(int(input()))
✓重複の無いリストの採り方
set(d) #list型ではなくset型
list(set(d)) #一旦setにしてからlist型に戻してもOK
７ABC088B - Card Game for Two
６ABC083B - Some Sums
✓数値Nの各桁の和（N=123の場合は6）の求め方
for i in range(1,N+1):
sum(list(map(int,str(i)))) #一旦strにして各桁のlistから和を取る。
#真面目に関数にするなら
def digit_sum(n):
sum = 0
n_str = str(n)
for i in range(0, len(n_str)):
sum += int(n_str[i])
return sum
５ABC087B - Coins
✓for文の開始・終了地点
for i in range(A, N)の場合、A, A+1, ..N-1でNは含まれないことに注意
0~N-1で計N周したい場合はrange(0, N)でよい
４ABC081B - Shift only
✓複数入力A1 A2..（横並び）のリスト格納
A = list(map(int, input().split()))
３ABC081A - Placing Marbles
✓文字のカウント
文字列str aに文字xが含まれる数はa.count("x")でカウントできる
bit列101001に含まれる1をカウントするなら一度strに変換して.count()を計算
２ABC086A - Product
１PracticeA - Welcome to AtCoder
✓複数入力の同時格納
a, b = map(int, input().split())
✓a = input()はstrで代入される
XX その他学び
✓Pythonの早い処理系
"PyPy"を選択した方が早い（特にループの処理がCPythonより早い）
✓変数のスコープ
グローバル変数を関数内で書き換え（再代入）する時はglobal が必要
x = 5
def func():
global x
x += 1
func()
print(x) #6が出力される
✓min, max関数は3個以上採れる MAX = max(a, b, c, d)
✓辞書dictのキーにできるのはイミュータブルのみ
イミュータブル：整数、文字列、タプルなど
dict.keys()、dict.values()でそれぞれリストが取れる
✓ループ内の処理
continue（次ループへ）、break（ループ抜ける）、pass（次行へ）
✓短絡評価のバグリスク
if (条件式1) and (条件式2)
1がTrueのとき2が評価されないため、テスト時に2のバグに気付きにくい
✓配列の要素を出力するsplat演算子 *
a = [1,2,3,4,5]のとき
print(a) だと [1,2,3,4,5]
print(*a) だと 1,2,3,4,5
✓整数の割り算の切り捨て・切り上げ
切り捨て：a//b
切り上げ：(a-1)//b + 1
✓指定した文字でリストを文字列に結合
a = [1,2,3]のとき
","join(a)だと"1,2,3"
"".join(a)だと"123"
✓配列（ミュータブルな変数）は重複設定しない
配列はミュータブルなので、自分自身を変えるメソッドや再代入が効く
文字列等はイミュータブル（変更不可）、コピーしても元変数影響なし
⇒同じ配列を複数の変数に代入すると片方の変更がもう片方にも掛かる
a = [0,1,2]
b = a #参照渡しになる
a[0] = 100 #b[0]も100になる
★配列を指している変数を他の変数に代入しないようにする
（どうしてもしたければ、b=a[:]やb=a.copy()など）
★イミュータブル（変更不可）な数値列を用意したければタプルにする
a = (1,2,3) #配列ならa=[1,2,3]
⇒アルゴリズム面では配列で事足りる。速度・バグ防止にタプル有効
✓計算量を示すOrder "O表記"
O（1）は入力データに依らず、一定の計算時間を要する。例）N＊2の計算
O（N）は入力データのサイズNに比例した計算時間を要する。例）N個の数字の和
O（N+M）はNとMで大きい方が支配的になるO（N）又はO(M)。例）それぞれN/M回のネストになっていないfor文
★TLEにならないためには、処理を108ほどに抑える。
1<=N<=200,000 の場合、O(N2)は厳しい（PyPyでもC++よりかなり遅い）
⇒どうしても必要な処理を残し、オーダーが収まるように軽量な処理に置き換える
✓Falseはbool型
ゆえに"False"などとして文字列扱いしないこと。Trueも勿論同様。
✓空の２次元配列
中に要素があれば下記Aの方法でもいけるが空だとうまくいかない
⇒丁寧にfor文で追加する癖をつけるほうが着実。
A = [[] * 3] #A ： [[]]
B = []
for i in range(3):
B.append([]) #B ： [[], [], []]
✓大きい数字の書き方
INF = 1_000_000_000_000_000_000 のように_を入れても問題ない
✓べき乗のあまり
pow()関数には２つの使い方があり２つ目ではべき数のあまりが一発で求まる
使い方１：pow(2, 3) ⇒2の3乗で8が求まる
使い方２：pow(5, 3, 9) ⇒5の3乗を9で割ったあまり8が求まる
✓答えを整数Mで割った余りを求める問題の途中計算
答えの計算に足し算・引き算・掛け算しか使わない場合、その途中の値をMde割ったあまりに置き換えてもよい。
★割り算に対しても「モジュラ逆数」を用いることで同等の処理が可能。
Mが素数であり、aがMで割り切れない正整数であるときには、aに対してモジュラ逆数が必ず存在し、フェルマの小定理を用いてa**(M-2)をMで割ったあまりとして求められる。
■アルゴリズム（マスター）
幅優先探索、深さ優先探索、動的計画法、メモ化再帰、bit全探索、累積和、貪欲法、二分探索（二分法）、ダイクストラ法、Warshall-Floyd 法、プリム法、クラスカル法、Union-Find（素集合データ構造）
●幅優先探索（BFS：Breadth-First Search）
幅/深さ共にグラフの頂点を探索するアルゴリズムで、グラフ問題以外にも応用可能。幅優先探索では、始点から各頂点に最小で何本の辺を辿り到達できるかが求まる。
✓概要
【入力】頂点数、グラフの隣接リスト、始点の番号
【管理データ】各頂点の訪問済み管理リスト、探索待ち頂点番号のキュー
【手続き】キューに始点を入れて管理リストでTrueを反映
Qが空になるまで（１）先頭取り出し（２）隣接リストからお隣さんを取得、管理リストで未訪問のものがあれば管理リストをTrueにしキューに格納
（→距離０の頂点たち、距離１の頂点たち、距離２の...という内容のキュー）
★辺の重みが等しく０であることに注意（重みが違う場合はダイクストラ法）
✓用いるデータ構造deque
from collections import deque でimportする
追加：Q.append(x)、取り出し：Q.popleft() を用いる
（右から入れて左から出している。逆向きのleftappend(x)、popもある。）
✓計算量
頂点の数Nと辺の数Mどちらかに支配されるためO（N+M）
●深さ優先探索（DFS：Depth-First Search）
深く探索して行き止まりに当たったら、他に進める先がある分かれ道の頂点まで戻りその先を探索する。そのために「再帰」（関数が自分自身を呼び出す仕組み）を用いる。
✓概要
【入力】頂点数、グラフの隣接リスト、始点の番号
【管理データ】各頂点の訪問済み管理リスト
【再帰関数dfs】今見ている頂点を引数に、その訪問済み管理リストをTrueにし、隣接する頂点が未訪問であればdfsを呼び出す。
【手続き】始点を引数にしてdfsを呼び出す。
※BFSは情報をキューに保存して探索していたが、DFSは再帰を行いながら探索する
✓Python実装時の必須対応
Pythonの言語仕様では多くの場合、関数の再帰呼び出し深さに上限がある（1000程度）
多くの問題では足りないため、下記の通り再帰上限を自変更する
import sys
sys.setrecursionlimit(1000000)
●動的計画法
部分的な小さな問題を解き、それを用いて一段大きな問題を解く手順を繰り返すことで所望の問題を解く。「状態定義」と「遷移」が重要。
●メモ化再帰
再帰関数で呼び出し回数が極端に多くなる場合、一度計算した結果はメモ化しておいてその値を返すことで高速化した再帰。
計算済みのフラグ配列done[i]をつくり、関数の中でif done[i]、return cost[i]といったメモ化の値を即座に返すようにする。
●bit（を用いた集合の）全探索
特に集合を扱う際、bitだとset()と比べて動的計画法の状態等にも使いやすい
"AがBの部分集合"⇒"Aを表現した２進数はBを表現した２進数以下"
（※逆は成り立たないので注意）
"Aに要素xが含まれる"⇔"要素xだけを含む{x}とAの積集合が{x}"
"AとBの和集合"⇔"AとBのビットごとのOR演算結果"
"Aの補集合"⇔"2N-1 - Aを表現した2進数" ⇔ "2N-1とAのXOR演算結果"
bit同士の演算はOR：|、AND：&、XOR：^である。
●半分全探索
集合の全探索が間に合わないとき、要素を半分ずつのグループに分けて、それぞれのグループについて部分集合の全列挙を行い、その結果を組み合わせることで答えを求めるアルゴリズム。
例えば30種類の全探索は230 >1e9だが、215 <1e5である（2**10 ~ 1e3の見積もり）
●累積和
数列の配列の先頭からi番目までの和を保存したもので、一度計算した結果を使いまわして高層化するという動的計画法の一種、そのまま利用できる場面が多い。
配列 ：[2, 5, 1]の場合
配列の累積和：[0, 2, 7, 8]となる
つまりsum[i] = A[0]+A[1]..+A[i-1] ※元の配列より要素数が1大きい
sum[0] = 0
for i in range(len(A)):
sum.append(sum[i]+A[i]) #sumは第i+1個目の要素でAはi個目の要素
L番目からR番目の和はsum(R+1)-sum(L)で導出できる
sum(R+1)-sum(L) = (A[0]+..A[L-1]+A[L]+..+A[R]) - (A[0]+..A[L-1])
= A[L]+...+A[R]
●貪欲法
いくつかの選択を順番に行う問題において、各選択において「いま選べるものの中から最も良いものを選ぶ」ことを繰り返すと、それが結果として全体最適になるアルゴリズム。
⇒全探索や動的計画法のような全選択肢を考えるアルゴリズムとは対照的。
⇒「良いものを選び続けると全体最適になる」という非常に相性のいい問題にのみ適用できシンプルに解けるが、その正当性を見極める・証明するのが難しい
⇒照明・見極め方法：「途中で「あえて最良ではないものを選ぶ」ような選び方は、その選び方の一部分を変更することでより良い選び方か同等の選び方に必ず変形できる」ことを確認すればよい
●二分探索（二分法とも）
ソートされている探索対象に対して、その中央を調べることで未確定領域を半分以下に減らすようなアルゴリズム。
単調性「探索対象の数列などが、どこかを境界として条件を満たす/満たさない領域に二分される」を持つ満たしている場合に二分探索の解法が使える
以下のok, ngという２変数を管理することで実装できる。
ok：条件を満たすことが分かっている要素のうち左（右）端の要素のindex
ng：条件を満たさないことが分かっている要素のうち右（左）端の要素のindex
⇒ok, ng間のindex mを調べ条件を満たすならok、満たさないならngに置き換え
（abs(ok-ng) > 1 の限りループを繰り返す）
⇒ok, ngの初期値はi=0~N-1のとき、-1, Nにする
※ok, ngで配列に直接アクセスはしないので配列の範囲外アクセスは心配不要
★非常に大きな対象を探索できるため、探索対象のオーダーもヒント。
●ダイクストラ法
重みが１でない辺が含まれるグラフで、１つの始点から全頂点への最短距離を求めるアルゴリズム。
（重みが１の場合に用いる幅優先探索ではdequeを用いるが）ダイクストラ法ではheapqを用いる。キューではデータを入れた純に取り出すのに対してヒープではデータの小さい順に取り出すため、要素数Xのヒープ操作計算量 O(log X)だけ増えて全体の計算量は O((N+M) log X)となる。
✓一度ヒープから取り出した頂点かをdone[i]で管理すると高速化できる
✓幅優先探索との実装違い①ヒープに追加するときに距離も追加すること②最短距離が更新可能か確認すること（一度探索済みでも、他経路の距離次第で再度更新され得る）
dequeとheapqの実装違い
# deque（幅優先探索で用いる）
from collections import deque
Q = deque()
Q.append(要素)
要素 = Q.popleft()
# heapq（ダイクストラ法で用いる）
import heapq
Q = []
heapq.heappush(Q, (距離d, 頂点i))
距離d, 頂点i= heapq.heappop(Q)
●ワーシャル・フロイド法
重みが１でない辺が含まれるグラフで、全頂点から全頂点への最短距離を求めるアルゴリズム。（始点が１つでなく全てという点がダイクストラ法と異なる）
キューやヒープのようなデータ構造は用いず、多重ループによるシンプルな実装で求まる。全体の計算量はO(N3)となる。全頂点を探索するのであればダイクストラ法よりも早い。ダイクストラ法の計算量((N+M) log X)に頂点数Nをかけ、かつM=N(N+1)/2とするとO(N3 logX) >O(N**3) であるため。
# dist[x][y] に頂点xからyへの最短距離が入るように計算する
# 同じ頂点同士の距離を０とする
for i in range(N):
dist[i][i] = 0
# ワーシャル・フロイド法ですべての頂点同士について最短距離を計算する
for k in range(N): #経由する頂点
for x in range(N): #始点
for y in range(N): #終点
dist[x][y] = min(dist[x][y], dist[x][k] + dist[k][y])
●プリム法
最小全域木問題を解くためのアルゴリズム。
※木：N個の頂点とN-1本の辺を持つ連結したグラフ
※全域木：あるグラフで辺をいくつか選んで作った、全ての頂点が連結する木
※最小全域木：幾つか採り得る全域木のうち辺の重みの合計が最小であるもの
手順① グラフの中から好きな頂点を１つ選びマーク
手順② すべての頂点がマークされるまで次の手順を繰り返す
※ただし閉路ができないことを確認する
a. マークされた頂点とされていない頂点を結ぶ辺のうち重みが最小の辺を１つ選ぶ。
b. 選んだ辺のマークされていない頂点をマーク
c. この時に選んだ辺を最小全域木に使う辺として保持しておく
手順③ 前の手順で選んで保持した辺が最小全域木になっている
⇒重みが最小の頂点を選べるように、頂点iと頂点jを結ぶ重みcの辺があるとして、辺頂点iがマークされたときに（重みc, 選んだ時にマークする頂点j）をヒープに保持しておく。
⇒計算量は、ヒープの操作でO(log M)、さらに頂点を選ぶN回または辺を選ぶ数Mが支配的になるため、O((N+M) log M)となる
●クラスカル法
プリム法と同様に最小全域木問題を解くためのアルゴリズム。
プリム法は先に任意の頂点を決めてからスタートするのに対して、クラスカル法では全ての辺の中から最も低コストであるものでスタートをし、閉路にならないようにしながら低コスト順に辺を確定していく。
即ち、点から決めるのがプリム法で辺から決めるのがクラスカル法。
●Union-Find（素集合データ構造）
数字のグループ分けを管理するアルゴリズム・
「union」と「check」の２つのクエリに対応し、その過程で「find」を用いる
✓クエリ１：union(x, y)
要素x, yを同じ集合にする
def union(x, y):
if find(x) == find(y):
return
else:
parent[x] = y
✓クエリ２：check(x, y)
要素x, yが同じ集合か確認する
def check(x, y):
return find[x] == find[y]
✓find(x)
parent = [i for i in range(N)] で初期化された、各要素が属する集合の”親”を管理しておく。
def find(x):
if parent[x] == x:
return x
else:
parent[x] = find(parent[x])
return parent[x]
■アルゴリズム（未マスター）
高速な素数判定法 冪乗を高速に計算する手法 逆元を計算する手法 グラフ構造 座標圧縮 半分全列挙 エラトステネスの篩 ダブリング Grundy数 Rolling Hash 平方分割 最大流 最小カット 最小費用流 二部グラフ判定 二部マッチング 行列累乗 Binary Indexed Tree セグメント木 強連結成分分解
■参考資料
岩下真也、中村謙弘 著、高橋直大 監修、2022、『アルゴリズム実技検定公式テキスト エントリー～中級編』、第三版、マイナビ出版
Bill Lubanovic 著、鈴木 駿 監訳、2021、『入門 Python３』、第二版、オライリージャパン