第3回まで無料

競技プログラミング入門コース

入出力と計算量の見積もりから、全探索・ビット全探索・二分探索・累積和・動的計画法・グラフ応用まで。全30レッスンで「制約を見て解法を決め、時間内に書き切る」ところまで進みます。全回が「問題 → 実装手順 → 回答例 → 発展課題」の演習形式で、コードと実行時間はすべて Python 3.14.2 で実際に動かしたものです。

カリキュラム

全30レッスンを6つの章に分けています。第1章から順に進めるのがおすすめですが、 気になるところだけ拾い読みしてもかまいません。 ※ 全30レッスンに「問題 → 実装手順 → 回答例 → 発展課題」の演習が入っています。解説だけの回はありません。 ※ サンプルはブラウザ内でそのまま実行できます(標準ライブラリだけを使っています)。件数の大きい計測は、手元の python3 で試してください。

Chapter 1 — 土台(第1〜5回)

入力の受け取り方と、制約から計算量を逆算する考え方をそろえます。最後は桁あふれ・浮動小数・提出前チェックまで、落ちる前に自分で気づけるところまで進みます。

Chapter 2 — 全探索(第6〜10回)

まず全部数える解法を書けるようにします。二重ループ・ビット全探索・順列・再帰、そして枝刈りで N クイーンを 65 倍速くするところまで。

Chapter 3 — 二分探索と累積和(第11〜15回)

答えを二分探索する・右端を戻さない・前処理して何度も使う、の 3 つを身につけます。しゃくとり法で 1,358 倍、累積和で秒単位の差がつくことを実測で確かめます。

Chapter 4 — 動的計画法(第16〜22回)

「dp に何を置くか」を決める練習を 7 回かけて行います。ナップサック・二次元 DP・区間 DP・bitDP まで、毎回素朴な解法と突き合わせて進めます。

16

DP の立て方:状態を決めて、遷移を書く

「何を dp に置くか」を先に日本語で書く。配る DP ともらう DP の書き分けと、素朴な再帰との 40 万倍の差を実測する。

🔒 ベーシック
17

0-1 ナップサック:選ぶ/選ばないの表

容量ごとの最大価値を 1 次元配列で持ち、後ろから回す。全探索 2^n との差は品物 22 個で 26,549 倍。

🔒 ベーシック
18

部分和と個数無制限ナップサック

ループの向きを変えるだけで「何個でも使える」に変わる。部分和は整数 1 個をビット列として使うと 1,111 倍速くなる。

🔒 ベーシック
19

二次元 DP:最長共通部分列と編集距離

2 つの文字列を突き合わせる表。素朴な再帰は長さ 13 で 118 ミリ秒、DP なら 500 文字同士でも 24 ミリ秒で終わる。

🔒 ベーシック
20

区間 DP:短い区間から長い区間へ

区間の長さの小さい順に埋める。分け目をどこに置くかを全部試す形で、素朴な再帰との差は行列 15 個で 12,027 倍。

🔒 ベーシック
21

bitDP:訪問済みの集合を添字にする

「どこを訪れたか」を整数 1 個で表して DP の添字にする。全順列 n! が 2^n × n^2 になり、都市 18 個まで届く。

🔒 ベーシック
22

【実践】遷移を自分で設計する(最長増加部分列)

O(n^2) の素直な DP を書いてから、持つ値を変えて O(n log n) にする。同じ問題で 1,442 倍の差を作る。

🔒 ベーシック

Chapter 5 — グラフ応用(第23〜27回)

隣接リストから始めて、最短経路の 4 つの道具・Union-Find・最小全域木・トポロジカルソートへ。どれも「正しい順番で処理する」という一点でつながっています。

Chapter 6 — 実戦(第28〜30回)

制約から解法を決める手順を 1 問通しでやり、典型 3 問を続けて解きます。最後は反例を自動で見つけて縮める道具を作って締めます。

全30レッスンを終えたら、次はこの道具を別の角度から固める番です。アルゴリズム基礎 入門コース で実務のコードの計算量を測り、プログラミングのための数学 入門コース で式を読む力を足し、Python 入門コース で書き方そのものを固める——どれもこのコースの続きになります。メンバーシップで全コースが解放されます。