文字列の整形メモ

for i in range(6, 15): print(f'{"geeks" :*<{i}}') で文字埋めできたぞ
print(f'observation: {str(observation): <36} ')　のように　strでないタイプは文字列に変換すれば空白埋めできた

二重ループをbreakできるtipsは初めて知った　確かにbreakしなかった場合は else:continue を通るよなあ

競プロでよく使うけど空で書けないフレーズ https://qiita.com/do_an/items/e5a202cac4fc69fe849d ``` for i in range(10): for j in range(10): for k in range(10): if 25< ijk: ng=(i,j,k) break ok=(i,j,k)
```
 else:continue
 break
```
else:continue break

print(ok) # (1, 3, 8) print(ng) # (1, 3, 9) ```

自分のvisualgo を codepen とかで作れるのではないかと思っている

https://visualgo.net/

segment tree

*　\practicePython\atcoder\segment_tree.py

https://algo-logic.info/segment-tree/より。概念を掴めた。

間違えたことがあるもの

(1,-1)[x]　の9文字を短く表現する方法。
- 結局1-2*vの5文字がベスト。 -1**x の5文字だと常に -1 を返してしまうので間違い。正しい表記は7文字 (-1)**xで長い。

メモ

グラフで木の高さの最小値（木の半径と呼ばれる）は　およそ木の直径の半分下記のコードでいうところの(GetDiam(G)+1)//2
- 木の直径は任意の点から最も遠い点をゲットし、そこを起点として再び最も遠い点までの距離
  - https://algo-method.com/submissions/1276401
nCr のベストな説明

(atcoder では使えなかったもの、、、)

import gmpy2 example : xのn乗根 root(x,n) , is_prime(x) , next_prime(x)

available lib at codewars

import math example : lcm(a,b) , factorial(x)
import collections example : Counter(A)
import numpy example : .base_reprで5進法に変換 , np.zerosにレンジで値を加えるよりも imos法の方が速かったので注意
import re example : re.sub('c|[a-z]?C[a-z]?','',x)
import haslib example : sha256(x.encode()).hexdigest()
import datetime exmaple : (date(2024,1,1)+timedelta(x)).strftime("%B, %-d")
import itertools example : zip_longest with fillvalue=’’ , groupby

100問をやる

77	https://github.com/jamad/jamad.github.io/blob/master/_posts/atcoder/practice100_77.md#a—%E6%97%85%E4%BA%BA

アルゴリズム（12 個）

全探索（bit 全探索、順列全探索を含む）
二分探索
深さ優先探索（DFS）
幅優先探索（BFS）
動的計画法（bitDP などを含む）
ダイクストラ法（最短経路問題）
ワーシャルフロイド法（最短経路問題）
クラスカル法（最小全域木問題）
高速な素数判定法
べき乗を高速に計算するアルゴリズム
逆元を計算するアルゴリズム
累積和

データ構造（3 個）

グラフ（グラフ理論）
木
Union-Find


全探索	二分探索	深さ優先探索 (DFS)	幅優先探索 (BFS)
動的計画法 (DP)	ダイクストラ法	ワーシャルフロイド法	クラスカル法
高速な素数判定法	べき乗を高速に計算する手法	逆元を計算する手法	累積和

2-3. 分野別　初中級者が解くべき過去問精選 100 問

記事へのリンク
AtCoder 水色コーダーを少ない問題数で達成するために、適切な100 問
分野ごとに問題が分けられています。また、アルゴリズムの確認問題から応用問題まで幅広い層の問題がありますので、是非解いてみることをおすすめします。
難しい問題もあるので、水色コーダーを目指す人は 100 問中 70 問正解を目安に頑張ってください。
100 問全部解けたら、水色コーダーどころか青色コーダーくらいの実力

全探索：全列挙

全探索：工夫して通り数を減らす全列挙

7　JOI 2007 本選 3 - 最古の遺跡　面白いです。Python3 だと想定解法が TLE する可能性があります。

全探索：ビット全探索

14　Square869120Contest #4 B - Buildings are Colorful!　工夫も必要で、一筋縄では解けない難問ですが、解けば確実に力がつきます。

全探索：順列全探索

17　ALDS_13_A - 8 クイーン問題　面白いです。

二分探索

21　AtCoder Beginner Contest 023 D - 射撃王　教育的に良いです。
22　AtCoder Regular Contest 054 B - ムーアの法則　微分して二分法をすると解けます。三分探索と話が繋がってくるので、それも調べてみると良いと思います。
23　JOI 2008 本選 3 - ダーツ　工夫して二分探索する、チャレンジ問題です。

深さ優先探索

26　AtCoder Beginner Contest 138 D - Ki　木構造の問題の多くは、深さ優先探索を使います。
27　JOI 2009 予選 4 - 薄氷渡り　深さ優先探索は、木構造だけではありません、ということを教えてくれる問題です。再帰関数を使って解けます。

幅優先探索

31　JOI 2012 予選 5 - イルミネーション　少し実装が重いですが、頑張れば解けます。
32　AOJ 1166 - 迷図と命ず　実装が少し重いです。
33　AtCoder Beginner Contest 088 D - Grid Repainting　これが解ければ、幅優先探索に慣れたと思って良いです。

動的計画法：ナップザック DP

36　DPL_1_C - ナップザック問題　基本問題です。
38　ALDS_10_C - 最長共通部分列　基本問題です。

(ここから先は、どのような DP で解けるのかは書きませんが、全部ナップザック DP またはその亜種で解くことができます。)

40　JOI 2012 予選 4 - パスタ
41　JOI 2013 予選 4 - 暑い日々
42　JOI 2015 予選 4 - シルクロード
43　パ研杯2019 D - パ研軍旗
44　AOJ 1167 - ポロック予想
45　AOJ 2199 - 差分パルス符号変調

動的計画法：区間 DP

46　ALDS_10_B - 連鎖行列積　基本問題です。
47　JOI 2015 本選 2 - ケーキの切り分け 2　 $O (N^{2})$ の区間 DP です。
48　AOJ 1611 ダルマ落とし　 $O (N^{3})$ の区間 DP です。

動的計画法：bit DP

49　DPL_2_A - 巡回セールスマン問題　基本問題です。
50　Square869120Contest #1 G - Revenge of Traveling Salesman Problem　巡回セールスマン問題を少し変えた問題です。
51　JOI 2014 予選 4 - 部活のスケジュール表　bitDP に含まれるか微妙ですが、一応入れておきます。
52　JOI 2017 予選 4 - ぬいぐるみの整理　少し難しいですが、是非挑戦してみてください。

動的計画法：その他

その他の DP として代表的なものは、最長増加部分列問題 (LIS) です。
53　DPL_1_D - 最長増加部分列
54　AtCoder Beginner Contest 006 D - トランプ挿入ソート
55　AtCoder Beginner Contest 134 E - Sequence Decomposing　チャレンジ問題です。

最短経路問題：ダイクストラ法

58　JOI 2016 予選 5 - ゾンビ島　前述の幅優先探索も使います。実装がやや重めです。
59　JOI 2014 予選 5 - タクシー

最短経路問題：ワーシャルフロイド法

60　GRL_1_C - 全点対間最短経路　基本問題です。
61　AtCoder Beginner Contest 012 D - バスと避けられない運命
62　AtCoder Beginner Contest 079 D - Wall
63　AtCoder Beginner Contest 074 D - Restoring Road Network　ちょっと数学的考察が必要で難しいですが、是非解いてみましょう。

最小全域木問題

64　GRL_2_A - 最小全域木　基本問題です。
65　JOI 2010 春合宿 - Finals　(問題pdf) JOI 春合宿の問題ですが、比較的簡単です。
66　AOJ 1127 - Building a Space Station
67　AtCoder Beginner Contest 065 D - Built?　やや難しいです。単純に最小全域木を求めると、 $N$ 頂点 $N^{2}$ 辺になりますが、なんとそれを減らすことができます。

高速な素数判定法

68　NTL_1_A - 素因数分解　基本問題です。
69　AtCoder Beginner Contest 084 D - 2017-like Number

高速なべき乗計算

70　NTL_1_B - べき乗
71　Square869120Contest #1 E - 散歩
※ べき乗だけを使う問題は少ないですが、 $n C r$ などを求める際に、逆元とセットで出てくることが多いです。例えば、 $a x \equiv 1 (m o d p)$ の解は $a^{p - 2} m o d p$ となります。（ $p$ が素数の場合）

逆元を使う問題

72　AtCoder Beginner Contest 034 C - 経路　nCr を求めるだけの基本問題です。
73　AtCoder Beginner Contest 145 D - Knight
74　AtCoder Beginner Contest 021 D - 多重ループ
75　AtCoder Beginner Contest 149 F - Surrounded Nodes　チャレンジ問題です。解けなくても、「そういう特殊な出力形式の問題ってあるんだな」と感じてほしいです。

累積和

76　全国統一プログラミング王決定戦本戦 A - Abundant Resources　基本です。累積和を使わなくても解けますが、是非使って解いてみてください。
77　JOI 2010 本選 1 - 旅人
78　JOI 2011 本選 1 - 惑星探査　二次元累積和です。
79　AtCoder Beginner Contest 106 D - AtCoder Express 2
80　GigaCode 2019 D - 家の建設

(ここから先は、「いもす法」というアルゴリズムを使う場合があります。)

81　AtCoder Beginner Contest 014 C - AtColor　基本問題です。
82　AOJ 2013 - 大崎
83　JOI 2015 本選 1 - 鉄道運賃
84　JOI 2012 本選 4 - 釘　チャレンジ問題です。

Union-Find

85　DSL_1_A - 互いに素な集合　基本問題です。
86　AtCoder Beginner Contest 075 C - Bridge　深さ優先探索による連結成分の個数の数え上げでも解けますが、Union-Find でも解いてみましょう。
87　AtCoder Beginner Contest 120 D - Decayed Bridge　一個の考察ステップがあり、少し難しいですが、解くことで得られる力は大きいと思います。

その他のテクニック

「圧縮」によって解ける問題たちです。

88　JOI 2008 本選 1 - 碁石ならべ
89　JOI 2013 本選 1 - 電飾

「単純な幾何計算」によって解ける問題たちです。標準ライブラリに存在する、2 乗根・三角関数などを使うと解けます。

90　Square869120Contest #5 B - Emblem
91　AtCoder Beginner Contest 144 D - Water Bottle　本記事では触れていませんが、三角関数の逆関数を使って解くことができます。

実装問題

考察に比べて実装がとても重い問題です。練習になると思います。

92　AOJ 1193 - 連鎖消滅パズル
93　Square869120Contest #3 B - 石落としゲーム
94　AOJ 1149 - ケーキカット

数学的な問題

AtCoder の問題の一部では、解くために数学的な考察を必要とします。上級編にも繋げていくために、水色コーダーを目指している人は「数学的考察って何なのか」「数学的考察ってどんな感じで使うのか」くらいは知っておくと良いと思うので、これを感じられる問題の代表例を紹介しておきます。

95　AtCoder Beginner Contest 149 B - Greedy Takahashi　200-300 点問題で出る数学的問題は大体そんな感じです。（貪欲法アルゴリズムに繋がってきます。）
96　AtCoder Beginner Contest 139 D - ModSum　考察一個です。
97　AtCoder Beginner Contest 150 D - Semi Common Multiple
98　三井住友信託銀行プログラミングコンテスト2019 予選 E - Colorful Hats 2
99　DDCC2020 予選 D - Digit Sum Replace　これも考察一個です。
100　Tenka1 Programmer Beginner Contest D - Crossing　やや難しいですが、頑張って解いてください。

これが全部解けたら、自信をもって「水色コーダー相当の実力」があるといってよいです。
--- # 分野別　初中級者が解くべき過去問精選 100 問

文字列の整形メモ

二重ループをbreakできるtipsは初めて知った 確かにbreakしなかった場合は else:continue を通るよなあ

自分のvisualgo を codepen とかで作れるのではないかと思っている

segment tree

間違えたことがあるもの

メモ

(atcoder では使えなかったもの、、、)

available lib at codewars

100問をやる

2-3. 分野別 初中級者が解くべき過去問精選 100 問

全探索：全列挙

全探索：工夫して通り数を減らす全列挙

全探索：ビット全探索

全探索：順列全探索

二分探索

深さ優先探索

幅優先探索

動的計画法：ナップザック DP

動的計画法：区間 DP

動的計画法：bit DP

動的計画法：その他

最短経路問題：ダイクストラ法

最短経路問題：ワーシャルフロイド法

最小全域木問題

高速な素数判定法

高速なべき乗計算

逆元を使う問題

累積和

Union-Find

その他のテクニック

実装問題

数学的な問題

全探索：全列挙

全探索：工夫して通り数を減らす全列挙

全探索：ビット全探索

全探索：順列全探索

二分探索

深さ優先探索

幅優先探索

動的計画法：ナップザック DP

ナップサックDPまたはその亜種

動的計画法：区間 DP

動的計画法：bit DP

動的計画法：その他

最短経路問題：ダイクストラ法

最短経路問題：ワーシャルフロイド法

最小全域木問題

高速な素数判定法

高速なべき乗計算

逆元を使う問題

累積和

いもす法

Union-Find

その他のテクニック

圧縮

単純な幾何計算

実装問題

数学的な問題

二重ループをbreakできるtipsは初めて知った　確かにbreakしなかった場合は else:continue を通るよなあ

2-3. 分野別　初中級者が解くべき過去問精選 100 問