1-1: はじめに

ようこそ、思考をコードに変える世界へ

本書を手に取っていただき、ありがとうございます。
この教材は、「プログラミングに初めて挑戦するけれど、どうせなら実践的な力を身につけたい」という方から、「Pythonの基本的な書き方は覚えたけれど、もっと難しい問題を解けるようになりたい」という方まで、全ての「問題解決能力」を鍛えたい人のための戦略的な教科書です。

最終的なゴールは、PaizaのSランクやAtCoderの難問を自力で解き明かす「論理的思考力」と「実装力」を身につけること。それは、単に文法を暗記するのではなく、目の前の課題を解決するための最適な手順を自分で考え、プログラムとして形にする力です。この力は、どんなIT分野に進んでも、あなたの最も信頼できる武器になるでしょう。

なぜ、学ぶ言語がPythonだと最高なのか？

世の中にはたくさんのプログラミング言語がありますが、私たちがPythonを選ぶのには明確な理由があります。

• 書き方がシンプル： まるで英語のように直感的に書けるため、文法で悩む時間が短く、問題の「解き方」を考える本質的な部分に集中できます。
• 便利な道具箱が標準装備： Pythonには、複雑な処理を短いコードで実現できる強力な「道具（標準ライブラリ）」が最初からたくさん用意されています。

本書は、このPythonの強みを最大限に活かし、あなたの学習を力強くサポートします。

さあ、冒険の準備を始めましょう！

1-2: 問題解決という冒険

プログラミングは「魔法の杖」である

これから私たちが学んでいくプログラミングは、それ自体が目的ではありません。それは、あなたが思い描いたことを実現するための「魔法の杖」です。

例えば、あなたが「毎日の献立を考えるのが面倒だ」という問題を抱えているとします。プログラミングという魔法を使えば、「冷蔵庫の中身リスト」と「作りたい料理の気分」を唱えるだけで、「おすすめレシピと買い物リスト」を自動で作り出す杖を創造できるのです。

競技プログラミングは、この「魔法の杖の作り方」を、パズルを解くような感覚で楽しくトレーニングできる、最高の訓練場なのです。

「見立てる」力

複雑な問題を解決するための第一歩は、目の前の問題を、私たちがよく知っているシンプルな形に「見立てる」ことです。

• 「電車の乗り換え」は、駅を「点」、線路を「線」で結んだ「すごろくのマップ」に見立てることができます。
• 「クラスの名簿」は、名前が順番に並んだ「整理されたカードの束」に見立てることができます。
• 「複数の予定が重なっていないか」を調べるのは、数直線の上に「時間の帯」を置いて、それが重なるか調べる問題に見立てられます。

このように問題を身近な形に置き換えることができれば、先人たちが「こういうすごろくは、こうすれば一番早くゴールできるよ」と見つけてくれた、たくさんの攻略法（＝アルゴリズム）を使えるようになります。

この教材で学ぶのは、まさにこの「問題を簡単な形に見立てて、効率的な手順で解く力」なのです。

1-3: 開発環境の準備

魔法の杖を振るう場所

プログラミングを始めるには、コードを書いたり実行したりするための「作業場」が必要です。料理に台所が必要なのと同じですね。この作業場を「開発環境」と呼びます。

競技プログラミングの問題を解くサイト（オンラインジャッジ）でもコードは書けますが、それは「キャンプ場のコンロ」のようなものです。手軽ですが、本格的な料理には向きません。

私たちは、この教材を通じて本格的なスキルを身につけることを目指します。そのため、自分のPCにプロ仕様の「システムキッチン」を構築することを強く推奨します。一度作ってしまえば、今後の学習効率が何倍にもなります。

ローカル開発環境を整えよう

これから、あなたのPCにPythonと、最強のコード編集ツール「Visual Studio Code (VSCode)」を導入します。以下の手順に従って、一歩ずつ進めましょう。

1. Python本体のインストール

まず、魔法の杖の本体であるPythonをPCに入れます。

1. 公式サイト python.org/downloads/ にアクセスします。
2. 「Download Python 3.x.x」のような黄色いボタンをクリックして、インストーラーをダウンロードします。
3. ダウンロードしたファイルを開きます。ここで非常に重要な設定があります。ウィンドウ下部にある「Add Python.exe to PATH」というチェックボックスに、必ずチェックを入れてください。これにチェックを入れると、「どこからでもPythonの魔法を唱えられる」ようになります。
4. 「Install Now」をクリックし、インストールが完了するのを待ちます。

2. VSCodeのインストール

次に、杖を快適に振るうための作業台、VSCodeを導入します。

1. 公式サイト code.visualstudio.com/download にアクセスします。
2. あなたのPCのOS（Windows, Macなど）に合ったボタンをクリックして、インストーラーをダウンロードします。
3. ダウンロードしたファイルを開き、画面の指示に従ってインストールを進めます。（基本的には全て「はい」や「次へ」でOKです）

3. VSCodeを最強のPythonエディタにする

最後に、VSCodeに「Python専用の拡張機能」を入れて、最強の作業場を完成させます。

1. VSCodeを起動します。
2. 画面左側にある、四角が4つ並んだようなアイコン（拡張機能ビュー）をクリックします。
3. 上部の検索ボックスに「Python」と入力します。
4. 一番上に出てくる、発行元が「Microsoft」となっているものをクリックし、「インストール」ボタンを押します。これで、コードを書きながらヒントが出たり、間違いを指摘してくれたりするようになります。
5. 同様に、検索ボックスに「Japanese Language Pack」と入力し、Microsoft製の日本語化パックをインストールすると、メニューなどが日本語になって安心です。

これで、冒険の準備は全て整いました！次の第2部から、いよいよ最初の呪文print()を唱えてみましょう！

2-1: `print()`による出力

コンピュータに話しかける最初の呪文

プログラミングの世界へようこそ！ここから、あなたがコンピュータに命令を出し、その結果を画面に表示させるための、最初の、そして最も基本的な魔法print()を学びます。

print()は、カッコの中に入れたものを画面に表示する、という非常にシンプルな機能を持っています。

文字列の出力

まず、文字や文章（これを文字列と呼びます）を表示させてみましょう。文字列を表示させるには、" "（ダブルクォーテーション）または' '（シングルクォーテーション）で囲む、というルールがあります。

print("Hello, World!")

上のコードを実行すると、画面に `Hello, World!` と表示されます。

数値の出力

print()は、文字列だけでなく数値も表示できます。数値の場合は、文字列と違ってクォーテーションで囲む必要はありません。

print(123)
print(3.14)

これを実行すると、画面に `123` と `3.14` がそれぞれ改行されて表示されます。

やってみよう！知識を固める小問題

【小問題1】最初の挨拶

print()を使って、画面に "Hello Python" という文字列を表示してください。

print("Hello Python")

【小問題2】数値の表示

print()を使って、数値の 100 を表示してください。

print(100)

【小問題3】2行の出力

print()を2回使って、1行目に "ようこそ", 2行目に "冒険の世界へ" と表示してください。

print("ようこそ")
print("冒険の世界へ")

2-2: 四則演算

コンピュータを電卓にする

プログラミングの強力な機能の一つは、複雑な計算を一瞬で実行できることです。基本的な「四則演算」と、競技プログラミングで頻出する演算子を学びましょう。計算結果は、print()を使ってそのまま表示できます。

# 足し算
print(10 + 5) # 15

# 引き算
print(10 - 3) # 7

# 掛け算
print(5 * 3) # 15

# 割り算
print(10 / 3) # 3.333...

# べき乗（2の3乗）
print(2 ** 3) # 8

競プロでよく使う特殊な割り算

通常の割り算 / に加えて、競技プログラミングでは以下の2つの割り算を頻繁に使います。

• 切り捨て除算 //: 割り算の商の「整数部分」だけを求めます。
• 剰余（余り） %: 割り算の「余り」を求めます。

# 10を3で割った商の整数部分
print(10 // 3) # 3

# 10を3で割った余り
print(10 % 3) # 1

やってみよう！知識を固める小問題

【小問題1】消費税の計算

1000円の商品に消費税10%がかかると、支払う金額はいくらになりますか？ 1000 × 1.1 の計算結果を表示してください。

print(1000 * 1.1) # 1100.0

【小問題2】正方形の面積

一辺の長さが8の正方形の面積を、べき乗演算子**を使って計算してください。

print(8 ** 2) # 64

【小問題3】あまりの活用

20人の生徒を3人ずつのグループに分けると、何グループできて、何人余りますか？ 切り捨て除算//と剰余%を使って、それぞれ計算してください。

# グループ数
print(20 // 3) # 6

# 余りの人数
print(20 % 3) # 2

2-3: コメント

プログラムにメモを残す方法

プログラムが長くなったり複雑になったりすると、「この部分は何をする処理だっけ？」と後から見返したときに分からなくなることがあります。また、他の人があなたのコードを読むときにも、処理の意図が伝わりにくいかもしれません。

そんなときのために、プログラムの中に人間用の「メモ」を残す機能があります。それがコメントです。

1行のコメント

Pythonでは、シャープ記号 # を書くと、その行の # 以降の部分はプログラムとして実行されなくなります。

# この行はコメントなので、コンピュータには無視されます。
print(10 + 5) # 足し算の結果を表示。ここもコメントです。

複数行のコメント（範囲コメント）

複数行にわたってコメントを書きたい場合は、各行の先頭に # を置くか、あるいは文字列を作るための三重クォーテーション """ または ''' で全体を囲む方法がよく使われます。

"""
ここは複数行のコメントです。
関数の説明や、一時的にコードの広い範囲を
無効化したいときなどに便利です。
"""
print("この行は実行されます")

'''
こちらも同じように
複数行のコメントとして
使うことができます。
'''

（厳密には、これは「複数行の文字列」を作っているだけですが、どこにも代入されていないため、事実上のコメントとして機能します）

やってみよう！知識を固める小問題

【小問題1】処理内容のメモ

# 自分の名前を表示します というコメントを書き、その次の行で、実際に自分の名前を表示するprint()文を書いてください。

# 自分の名前を表示します
print("Taro Yamada")

【小問題2】一時的に無効化

以下の2行のコードのうち、引き算の行だけを1行コメントを使って実行されないようにしてください。

print(100 + 20)
print(100 - 20)

print(100 + 20)
# print(100 - 20)

【小問題3】複数行の無効化

以下の3行のコードを、三重クォーテーションを使ってすべて実行されないようにしてください。

print("りんご")
print("ばなな")
print("みかん")

"""
print("りんご")
print("ばなな")
print("みかん")
"""

2-4: 変数

データに名前をつける箱

プログラミングでは、計算結果や文字列などのデータを、後で再利用するために一時的に保管しておくことがよくあります。そのデータを保管する「箱」に名前を付けたものが「変数」です。

変数名 = 値 のように書くことで、値をその名前の変数に「代入」できます。

# priceという名前の変数に、150という数値を入れる
apple_price = 150

# 3個分の値段を計算して表示
print(apple_price * 3)

# priceの値を200に変更（上書き）する
apple_price = 200

# 再度、3個分の値段を計算
print(apple_price * 3)

このように、一度代入した後でも、変数の値は自由に変更（上書き）できます。

やってみよう！知識を固める小問題

【小問題1】自己紹介

nameという変数にあなたの名前（文字列）、ageという変数にあなたの年齢（整数）を代入し、それぞれの変数をprint()で表示してください。

name = "Taro Yamada"
age = 25

print(name)
print(age)

【小問題2】値の更新

変数xに10を代入します。次の行で、xの値を今の値の2倍に更新してください。最後にxの値を表示してください。

x = 10
x = x * 2 # または x *= 2
print(x) # 20

2-5: 文字列の操作

文字を連結・反復する

変数と+, *演算子を組み合わせることで、文字列を柔軟に操作できます。

文字列の連結

+演算子を使うと、文字列同士を連結できます。

last_name = "山田"
first_name = "太郎"

full_name = last_name + first_name
print(full_name) # 山田太郎

文字列の繰り返し

*演算子を使うと、文字列を好きな回数だけ繰り返すことができます。

bar = "=" * 10
print(bar) # ==========

やってみよう！知識を固める小問題

【小問題1】挨拶文の作成

変数nameに好きな名前を代入し、「こんにちは、〇〇さん！」という文章を作成して表示してください。

name = "サトシ"
message = "こんにちは、" + name + "さん！"
print(message)

【小問題2】区切り線の作成

-（ハイフン）を20回繰り返した区切り線を表示してください。

print("-" * 20)

2-6: `input()`による入力

ユーザーから情報を受け取る

これまではプログラムに直接値を書いていましたが、実行するたびに違う値で計算したいことがあります。input()関数を使うと、ユーザーがキーボードで入力した値を受け取ることができます。

print("あなたのお名前は？")
name = input()
print(name + "さん、はじめまして！")

上のコードを実行すると、プログラムはinput()の行で一時停止し、あなたの入力を待ちます。入力してEnterキーを押すと、その内容が変数nameに代入され、次の行が実行されます。

重要：input()は常に文字列を返す

ここで絶対に覚えてほしいルールがあります。それは「input()で受け取ったデータは、たとえ123のような数字を入力したとしても、すべて文字列(str)型になる」ということです。

print("好きな数字を入力してください。")
num_str = input()
print("あなたが入力したのは文字列の「" + num_str + "」です。")
print(type(num_str)) #  と表示される

このままでは計算に使えません。次の章で、これを数値に変換する方法を学びます。

やってみよう！知識を固める小問題

【小問題1】オウム返し

ユーザーが入力した文字列を、そのまま次の行に表示するプログラムを作成してください。

s = input()
print(s)

2-7: 型と型変換

文字と数字は違う！

コンピュータの世界では、同じ「10」でも、文字列の"10"と、数値の10は全くの別物として扱われます。このデータの種類のことをデータ型（または単に型）と呼びます。

• str (string): 文字列型
• int (integer): 整数型

input()で受け取った文字列型の数字を、計算に使える整数型に変換するには、int()関数を使います。

num_str = input("数字を入力してください: ") # 例として "100" と入力
x = int(num_str) # 文字列 "100" を 数値 100 に変換
y = x + 50
print(y) # 150

数値を文字列に変換する `str()`

逆に、数値と文字列を+で連結したい場合は、数値をstr()関数で文字列に変換する必要があります。

age = 20
# print("年齢は" + age + "歳です") # ← これはエラーになる！
print("年齢は" + str(age) + "歳です") # 正しい

やってみよう！知識を固める小問題

【小問題1】2つの数の足し算

1行目で整数A、2行目で整数Bをそれぞれ入力として受け取り、その和を計算して表示してください。

A_str = input()
B_str = input()
A_int = int(A_str)
B_int = int(B_str)
print(A_int + B_int)

【小問題2】来年の年齢

あなたの今の年齢を入力すると、「来年は〇〇歳ですね。」と表示するプログラムを作成してください。

age_str = input()
age_int = int(age_str)
next_age = age_int + 1
print("来年は" + str(next_age) + "歳ですね。")

2-E: 部末演習

コンピュータとの対話の総仕上げ

第2部、お疲れ様でした！出力、計算、変数、入力、型変換という、プログラミングの第一歩を学びました。 ここでは、その知識を組み合わせて、少しだけ複雑な問題を解いてみましょう。

【演習問題1】長方形の面積

1行目に長方形の縦の長さ、2行目に横の長さが、それぞれ整数で与えられます。この長方形の面積を計算して表示してください。

height_str = input()
width_str = input()

height = int(height_str)
width = int(width_str)

area = height * width
print(area)

【演習問題2】自己紹介ジェネレーター

1行目にあなたの名前、2行目にあなたの出身地、3行目にあなたの年齢が入力されます。これらを使って、「私は〇〇です。△△から来ました。年齢は□□歳です。」という一文を完成させて表示してください。

name = input()
hometown = input()
age = input() # str型のままでOK

# 文字列を連結して文章を作る
sentence = "私は" + name + "です。" + hometown + "から来ました。年齢は" + age + "歳です。"
print(sentence)

3-1: if文による条件分岐

プログラムに「判断」させる

これまでのプログラムは、上から下へ一本道をただ進むだけでした。しかし、実際のプログラムは「もしAだったらこうする、そうでなければこうする」というように、状況に応じた「判断」が必要です。

この「もし〜なら」を実現するのがif文です。

age = 15

if age >= 20:
    print("あなたは大人です。")
else:
    print("あなたは未成年です。")

上の例では、変数ageが20以上かどうかを判定し、条件が正しい（真: True）場合はifの直後の処理を、正しくない（偽: False）場合はelseの直後の処理を実行します。

インデントの重要性

ifやelseの行の最後には必ずコロン:を付けます。そして、その条件のときに実行したい処理の行頭には、インデント（半角スペース4つ分の字下げ）を入れます。このインデントによって、Pythonはどこからどこまでがifの処理範囲なのかを判断します。

やってみよう！知識を固める小問題

【小問題1】正の数の判定

入力された整数Nが0より大きい場合のみ、"positive"と表示するプログラムを書いてください。（0や負の場合は何も表示しなくてOKです）

N = int(input())
if N > 0:
    print("positive")

【小問題2】パスワードの一致

正しいパスワードが"pass123"だとします。ユーザーに入力を求め、もし入力が正しいパスワードと一致したら"ログイン成功"、間違っていたら"ログイン失敗"と表示してください。

password = input()
if password == "pass123":
    print("ログイン成功")
else:
    print("ログイン失敗")

3-2: 比較・論理演算子

複雑な条件を作るための道具

if文の条件式を、より複雑で柔軟にするための道具が「比較演算子」と「論理演算子」です。

比較演算子

2つの値の関係を比較し、結果をTrueかFalseで返します。

• A > B : AはBより大きい
• A < B : AはBより小さい
• A >= B: AはB以上（A > B または A == B）
• A <= B: AはB以下（A < B または A==B）
• A == B: AとBは等しい
• A != B: AとBは等しくない

論理演算子

複数の条件式を組み合わせるために使います。

• A and B: 条件Aと条件Bが、両方ともTrueのときだけTrueになる。
• A or B : 条件Aと条件Bの、どちらか一方でもTrueならTrueになる。
• not A : 条件Aの結果を反転させる（TrueならFalseに、FalseならTrueに）。

score = 85
attendance_rate = 0.9

# and: スコアが80以上「かつ」出席率が0.8以上
if score >= 80 and attendance_rate >= 0.8:
    print("成績は優です")

# or: スコアが90以上「または」出席率が1.0
if score >= 90 or attendance_rate == 1.0:
    print("特別賞です")

やってみよう！知識を固める小問題

【小問題1】範囲の判定

入力された整数Nが、10以上かつ50以下である場合に"OK"と表示するプログラムを書いてください。

N = int(input())
if N >= 10 and N <= 50:
    print("OK")

【小問題2】範囲外の判定

入力された整数Nが、0未満または100より大きい場合に"範囲外です"と表示するプログラムを書いてください。

N = int(input())
if N < 0 or N > 100:
    print("範囲外です")

3-3: elifを使った複数条件

3つ以上の選択肢を作る

「もしAなら…、そうではなくてもしBなら…、どちらでもなければ…」のように、3つ以上の選択肢から1つを選びたい場合があります。そんなときに使うのがelif（エルスイフと読みます）です。

score = 75

if score >= 80:
    print("優")
elif score >= 60:
    print("良")
elif score >= 40:
    print("可")
else:
    print("不可")
# 出力: 良

ifから始まり、条件は上から順番に判定されます。一度いずれかの条件が真になると、その中の処理が実行され、残りのelifやelseはすべて無視されます。

やってみよう！知識を固める小問題

【小問題1】信号機

信号の色が文字列で入力されます。もし"green"なら"進め"、"yellow"なら"注意"、"red"なら"止まれ"、それ以外なら"無効な色です"と表示してください。

color = input()

if color == "green":
    print("進め")
elif color == "yellow":
    print("注意")
elif color == "red":
    print("止まれ")
else:
    print("無効な色です")

3-4: forループとrange()

決まった回数だけ繰り返す魔法

「同じ処理を100回繰り返したい」とき、同じコードを100行書くのは大変です。そんな時に使うのが「ループ」です。特に、繰り返す回数が決まっている場合に使うのがforループです。

forループは、range()関数と組み合わせて使うのが基本です。

# 0から4まで、5回繰り返す
for i in range(5):
    print(i, "回目のハロー！")

# 出力:
# 0 回目のハロー！
# 1 回目のハロー！
# 2 回目のハロー！
# 3 回目のハロー！
# 4 回目のハロー！

range(N)は0, 1, 2, ..., N-1という数の列を生成します。変数iには、その数が順番に代入されながら、ブロック内の処理が実行されていきます。

やってみよう！知識を固める小問題

【小問題1】九九の表（3の段）

forループを使って、九九の「3の段」の結果（3, 6, 9, ..., 27）を1行ずつ表示してください。

for i in range(1, 10):
    print(3 * i)

3-5: whileループと制御

条件が満たされる限り繰り返す

forループが回数を指定するのに対し、whileループは「ある条件が真である限り、ずっと繰り返す」という処理です。

# カウントダウン
n = 5
while n > 0:
    print(n)
    n = n - 1 # nを1減らす。これをしないと無限ループになる！
print("発射！")

whileは意図せず無限にループしてしまう危険性があるため、条件を変える処理を忘れないよう注意が必要です。

ループの制御：`break` と `continue`

ループの途中で、処理を中断したり、スキップしたりできます。

• break: ループを完全に中断し、ループの外に脱出します。
• continue: その回の処理だけを中断し、次の回に進みます。

# 1から10までで、5を見つけたら中断
for i in range(1, 11):
    if i == 5:
        print("5を発見！ループを中断します。")
        break
    print(i) # 1, 2, 3, 4 が表示される

# 1から10までで、偶数だけをスキップ
for i in range(1, 11):
    if i % 2 == 0:
        continue
    print(i) # 1, 3, 5, 7, 9 が表示される

やってみよう！知識を固める小問題

【小問題1】無限ループからの脱出

while True:を使って無限ループを作り、ユーザーが "exit" と入力したらbreakでループを抜けるプログラムを作成してください。

while True:
    command = input("コマンドを入力してください: ")
    if command == "exit":
        print("終了します。")
        break
    print(command + " を実行しました。")

3-E: 部末演習

流れを操る総力戦

第3部、お疲れ様でした！ifによる条件分岐と、for, whileによる繰り返し処理は、どんなプログラムにも登場する基本中の基本です。この演習で、それらを自在に組み合わせる練習をしましょう。

【演習問題1】FizzBuzz

1から30までの整数を順番に表示します。ただし、その数が3の倍数なら数の代わりに"Fizz"を、5の倍数なら"Buzz"を、3と5の両方の倍数なら"FizzBuzz"を表示してください。

for i in range(1, 31):
    if i % 15 == 0:
        print("FizzBuzz")
    elif i % 3 == 0:
        print("Fizz")
    elif i % 5 == 0:
        print("Buzz")
    else:
        print(i)

4-1: リストの基本と応用（スライシング）

たくさんのデータをいれる箱

これまでは1つの変数に1つのデータしか入れられませんでした。しかし、クラス全員のテストの点数のように、たくさんのデータをまとめて扱いたい場面は頻繁にあります。そんなときに使うのが「リスト」です。

リストは [] （角括弧）で作り、各データは , （カンマ）で区切ります。

scores = [85, 92, 78, 65, 100]

要素へのアクセス (0-indexed)

リストの中の個々のデータ（要素）には、インデックス（番号）でアクセスできます。超重要：インデックスは0から始まります！

scores = [85, 92, 78, 65, 100]

# 0番目（最初の要素）にアクセス
print(scores[0]) # 85

# 2番目（3番目の要素）にアクセス
print(scores[2]) # 78

リストの基本操作

• len(リスト): リストの要素数を取得します。len(scores) は 5 です。
• リスト.append(値): リストの末尾に新しい要素を追加します。

numbers = [10, 20]
print(len(numbers)) # 2

numbers.append(30)
print(numbers) # [10, 20, 30]

リストを自在に切り分ける（スライシング）

リストの中から、特定の「一部分」だけを効率的に取り出したい場面はよくあります。例えば、「前から3つの要素」や「2番目から5番目まで」といった操作です。これを実現するのがスライシングです。

スライシングは リスト[開始:終了] のようにコロン:を使って範囲を指定します。

letters = ['a', 'b', 'c', 'd', 'e', 'f']

# 1番目から3番目の手前まで（インデックス1, 2）
print(letters[1:3]) # ['b', 'c']

# 最初から3番目の手前まで（インデックス0, 1, 2）
print(letters[:3]) # ['a', 'b', 'c']

# 3番目から最後まで
print(letters[3:]) # ['d', 'e', 'f']

重要ルール: 「開始」は含まれ、「終了」は含まれない（その手前まで）と覚えるのがポイントです。

ステップ数を指定する

[開始:終了:ステップ] のように3つ目の値を指定すると、何個おきに要素を取り出すかを指定できます。

numbers = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

# 1番目から8番目の手前まで、2つおきに
print(numbers[1:8:2]) # [1, 3, 5, 7]

# 全体を逆順にする（ステップに-1を指定）
print(numbers[::-1]) # [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

特に[::-1]でリストを簡単に逆順にできるのは、非常に便利なテクニックです。

やってみよう！知識を固める小問題

【小問題1】リストの作成と表示

あなたの好きな食べ物を3つ入れたリストfoodsを作成し、そのリスト全体をprint()で表示してください。

foods = ["ラーメン", "寿司", "焼肉"]
print(foods)

【小問題2】リストの逆順

colors = ["red", "green", "blue"]というリストがあります。スライシングを使って、このリストを逆順にした `["blue", "green", "red"]` を表示してください。

colors = ["red", "green", "blue"]
print(colors[::-1])

【小問題3】リストの先頭と末尾

numbers = [1, 2, 3, 4, 5] というリストがあります。スライシングを使って、先頭の要素を除いたリスト `[2, 3, 4, 5]` と、末尾の要素を除いたリスト `[1, 2, 3, 4]` をそれぞれ表示してください。

numbers = [1, 2, 3, 4, 5]
# 先頭を除外
print(numbers[1:])
# 末尾を除外
print(numbers[:-1])

4-2: リストとループ

リストの全要素を自動で処理する

リストの真の力は、ループと組み合わせることで発揮されます。リストの全要素に対して、同じ処理を自動的に行うことができます。

scores = [85, 92, 78]
total = 0

for s in scores:
    print(s, "点を加算します")
    total += s

print("合計点:", total)

for 変数 in リスト:という構文を使うと、リストの要素が先頭から順番に変数に代入され、その数だけループが実行されます。

やってみよう！知識を固める小問題

【小問題1】リストの全要素を表示

items = ["剣", "盾", "薬草"]というリストがあります。forループを使って、各アイテムを1行ずつ表示してください。

items = ["剣", "盾", "薬草"]
for item in items:
    print(item)

【小問題2】条件に合うものだけ表示

scores = [55, 80, 62, 95, 48]という点数リストがあります。この中から、60点以上の「合格点」だけを表示してください。

scores = [55, 80, 62, 95, 48]
for score in scores:
    if score >= 60:
        print(score)

4-3: 複数データの入力

スペース区切りの入力をリストへ

競技プログラミングでは、「N個の整数が1行にスペース区切りで与えられます」という形式の入力が非常に多いです。これを効率よくリストに変換する魔法の呪文を覚えましょう。

# 入力例: 10 20 30 40 50

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

print(A) # [10, 20, 30, 40, 50]

呪文の分解

1. input(): まずは一行 "10 20 30 40 50" を文字列として受け取ります。
2. .split(): その文字列をスペースで分割し、文字列のリスト ['10', '20', '30', '40', '50'] を作ります。
3. map(int, ...): リストの各要素（'10'や'20'）すべてにint()関数を適用（写像）し、数値に変換する準備をします。
4. list(...): 最後にmapの結果をリストに変換します。

この list(map(int, input().split())) は、息をするように書けるようになりたい頻出テクニックです。

やってみよう！知識を固める小問題

【小問題1】入力された数値の合計

スペースで区切られた複数の整数が1行で与えられます。これらの整数の合計値を計算して表示してください。

A = list(map(int, input().split()))
print(sum(A))

4-4: 辞書

キーと値のペアでデータを管理する

リストはインデックス（番号）でデータを探しましたが、辞書（dict）はキー（Key）と呼ばれる名前でデータ（値: Value）を探します。電話帳で名前（キー）から電話番号（値）を探すのに似ています。

辞書は {}（波括弧）で作り、キー: 値のペアを,で区切ります。

# 辞書の作成
fruits_prices = {"apple": 150, "banana": 100}

# キーを使って値を取得
print(fruits_prices["apple"]) # 150

# 新しいペアを追加
fruits_prices["orange"] = 120

# 値を更新
fruits_prices["apple"] = 140

print(fruits_prices)
# {'apple': 140, 'banana': 100, 'orange': 120}

辞書は、何かの出現回数を数えるときや、名前とパラメータを紐づけて管理したいときに非常に便利です。

やってみよう！知識を固める小問題

【小問題1】テストの点数

"Tanaka"が80点、"Suzuki"が92点のテスト結果を辞書scoresに格納し、Suzukiさんの点数を表示してください。

scores = {"Tanaka": 80, "Suzuki": 92}
print(scores["Suzuki"])

4-5: セットとタプル

リストの特殊な仲間たち

リストや辞書の他に、特定の状況で役立つ特殊なデータ構造があります。

セット (set): 重複しない要素の集まり

「セット」は、重複する値を持たず、順序のないデータの集まりです。自動的に重複を消してくれる性質と、「ある要素が含まれているか」のチェックがリストよりずっと高速である、という特徴があります。

# リストからセットを作成すると重複が消える
numbers = [1, 2, 2, 3, 1, 4]
unique_numbers = set(numbers)
print(unique_numbers) # {1, 2, 3, 4} （順序は保証されない）

# 高速な存在チェック
print(3 in unique_numbers) # True

タプル (tuple): 変更できないリスト

「タプル」は、基本的な性質はリストと似ていますが、一度作成したら中身を変更できない（イミュータブル）という大きな特徴があります。()（丸括弧）で作ります。

point = (10, 20)
print(point[0]) # 10

# point[0] = 30 # これはエラーになる！

プログラムの中で「この値は絶対に変わらない」ということを明示したい場合や、辞書のキーとして使いたい場合（リストはキーにできない）などに使います。

4-6: 文字列の応用と正規表現

複雑な文字列パターンを扱う魔法

「この文字列は、メールアドレスの形式になっているか？」「大量のテキストから、電話番号だけをすべて抜き出したい」——このような、単純な文字列検索では対応できない「パターンの検索」を行うための超強力なツールが正規表現です。

Pythonでは、reモジュールをインポートして使います。

基本的な使い方

• re.search(パターン, 文字列): 文字列の中からパターンに一致する最初の場所を探す。
• re.findall(パターン, 文字列): パターンに一致する全ての箇所をリストとして返す。
• re.sub(パターン, 置換後, 文字列): パターンに一致する箇所を別の文字列に置換する。

メタ文字：特別な意味を持つ文字

正規表現の強力さは、以下の「メタ文字」を組み合わせることで発揮されます。

• . : 任意の一文字
• * : 直前の文字の0回以上の繰り返し
• + : 直前の文字の1回以上の繰り返し
• \d: 任意の数字 ([0-9]と同じ)
• \w: 任意の英数字とアンダースコア ([a-zA-Z0-9_]と同じ)
• []: `[abc]`はaかbかcのいずれか1文字
• ^: 行の先頭 (re.MULTILINEがない場合は文字列の先頭)
• $: 行の末尾 (re.MULTILINEがない場合は文字列の末尾)

import re

text = "私の電話番号は012-345-6789で、メールはtest@example.comです。"

# 3桁-3桁-4桁の数字のパターン
# r'' はエスケープシーケンスを無効化するraw文字列。正規表現で推奨される
phone_pattern = r'\d{3}-\d{4}-\d{4}' # \d{n}は直前の\dがn回繰り返す意味
match = re.search(phone_pattern, text)
if match:
    print("電話番号が見つかりました:", match.group(0))

# メールアドレスの簡易的なパターン
email_pattern = r'\w+@\w+\.\w+'
all_emails = re.findall(email_pattern, text)
print("メールアドレスのリスト:", all_emails)

正規表現は非常に奥が深いですが、基本的なパターンを知っているだけで、特定の文字列処理問題で無類の強さを発揮します。

やってみよう！知識を固める小問題

【小問題1】YYYY-MM-DD形式

文字列 `text = "Today is 2023-10-26."` から、正規表現を使って日付の部分だけを抜き出してください。

import re
text = "Today is 2023-10-26."
pattern = r'\d{4}-\d{2}-\d{2}'
match = re.search(pattern, text)
if match:
    print(match.group(0))

【小問題2】不要な文字の削除

文字列 `price_text = "定価: 1,980円 (税込)"` から、数字以外の文字をすべて削除して、"1980" という文字列を得てください。

import re
price_text = "定価: 1,980円 (税込)"
pattern = r'\D' # 数字以外
result = re.sub(pattern, '', price_text)
print(result) # 1980

4-7: 問題の読み解き方

プログラムを作る前の「設計図」

いよいよ基本的な部品が揃ってきました。ここからは、部品を組み合わせて「プログラム」という家を建てるフェーズに入ります。その前に、家の設計図にあたる「問題文」を正確に読み解くトレーニングをしましょう。

どんなに複雑な問題でも、以下の4つの要素に分解して考える癖をつけることが重要です。

1. 入力 (Input): プログラムは何を情報として受け取る必要があるか？（個数、数値、文字列など）
2. 出力 (Output): プログラムは何を計算して、最終的に何を表示すればよいか？（"Yes/No", 数値, 文字列など）
3. 制約 (Constraints): 入力される数値の範囲はどれくらいか？（これが後の計算量考察で重要になる）
4. サンプル (Sample): なぜこの入力でこの出力になるのか？問題のルールを具体的に理解する最大のヒント。

この4つの要素を、問題文を読むたびに頭の中で整理することで、自分が何を作るべきかが明確になります。これは、競技プログラミングだけでなく、あらゆるプログラミングにおいて最も重要なスキルの一つです。

4-E: 部末演習

データ構造を使いこなす

第4部、お疲れ様でした！リスト、辞書、セットといったデータ構造と、それらを操作する応用技術を学びましたね。この演習では、問題の性質に合わせて、どのデータ構造を使えば効率的に解けるかを考える練習をします。

【演習問題1】カードの枚数

N枚のカードがあり、それぞれのカードには整数A_iが書かれています。数字が書かれたカードがそれぞれ何枚ずつあるか、数字の小さい順に表示してください。

入力例:
7
3 1 4 1 5 9 2

出力例:
1: 2枚
2: 1枚
3: 1枚
4: 1枚
5: 1枚
9: 1枚

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

counts = {}
for num in A:
    counts[num] = counts.get(num, 0) + 1

# キーでソートして出力
for num in sorted(counts.keys()):
    print(f"{num}: {counts[num]}枚")

挑戦：Dランク問題

おめでとうございます！あなたは、プログラミングの基本的な読み書きと、複数のデータを扱うための道具を手に入れました。 これは、Paizaスキルチェックの「Dランク」相当の問題に挑戦できるレベルです。

Dランク問題は、まさにこの第4部までに学んだ「リストへの入出力」や「ループ」「条件分岐」を正確に実装できるかを問う問題が多く出題されます。 ぜひ、力試しに挑戦してみてください！

• 挑戦のリンク: Paiza Dランクレベルアップ問題集
• ヒント：第2部、第4部の知識が特に役立ちます。

また、AtCoderのA問題も、このレベルの知識で解けるものがたくさんあります。

• 挑戦のリンク: AtCoder ABC081 A - Placing Marbles
• ヒント：第2部で学んだ文字列の扱い方が鍵です。

5-1: 計算量とオーダー記法

なぜ「速いコード」が必要なのか？

あなたは宝の地図を手に入れました。宝箱は100万個の部屋のどこかに隠されています。

• 凡人の探し方: 1号室から順に、100万号室までドアを一つずつ開けて探す。最悪の場合、100万回ドアを開ける必要があります。
• 賢者の探し方: 地図には「宝は50万号室より大きい部屋にある」といったヒントが書かれています。まず50万号室を調べ、そこから範囲を半分に絞り…と繰り返します。この方法なら、たった20回ほどで宝を見つけられます。

競技プログラミングの「制限時間」は、まさにこの状況と同じです。「凡人の探し方」をするコードは時間切れ（Time Limit Exceeded, TLE）になり、「賢者の探し方」をするコードだけが正解（Accepted, AC）を得られます。この「コードの効率の良さ」を示す指標が「計算量」です。

オーダー記法：コードの戦闘力

計算量とは、入力サイズNが大きくなったときに、計算回数がどれくらいの勢いで増えるかを示すものです。これをざっくりと表現する方法が「オーダー記法（O記法）」です。

一般的な競技プログラミングサイトの制限時間は2秒で、1秒あたり約10⁸回の計算が目安です。問題の制約を見て、どの計算量まで許されるかを見積もるのが、アルゴリズム選定の第一歩です。

5-2: 高速な入出力 (sys.stdin.readline)

入力がボトルネックになる時

Nが10⁵のように非常に大きい問題では、input()でN行のデータを読み込むだけで、かなりの時間がかかってしまうことがあります。これは、input()が毎回丁寧に行の読み込みと解釈を行うためです。

このような入力がボトルネックになるケースで威力を発揮するのが、sysモジュールのstdin.readlineです。これは、より低レベルで高速な入力読み込み機能を提供します。

使い方：おまじないのコード

競技プログラミングでは、以下のコードをプログラムの冒頭に書くのが定石です。これにより、input()と同じ感覚で高速な入力が使えるようになります。

import sys
input = sys.stdin.readline

# あとはいつも通り input() を使うだけ
N = int(input())
S = input().strip() # ← strip() が重要！

超重要： sys.stdin.readline()は、行末の改行文字(\n)をそのまま含んで読み込みます。そのため、文字列として使う場合は必ず.strip()を付けて改行文字を削除する癖をつけましょう。int()で変換する場合は不要です。

やってみよう！知識を固める小問題

【小問題1】大量の数値入力

1行目にNが与えられ、続くN行に整数A_iが与えられます。高速な入力を使って、これらの数値をすべてリストに格納してください。

import sys
input = sys.stdin.readline

N = int(input())
A = []
for _ in range(N):
    A.append(int(input()))

# print(A) # 確認用

5-3: リスト内包表記

Pythonらしいエレガントなリスト作成

forループを使って、ある条件を満たす要素や、各要素を加工した結果を新しいリストに格納することは頻繁にあります。

# 0から9までの2乗の数をリストにしたい
squares = []
for i in range(10):
    squares.append(i**2)

この処理を、より簡潔に、そして多くの場合でより高速に記述できるのがリスト内包表記です。

# 上の4行が、この1行になる
squares = [i**2 for i in range(10)]
print(squares) # [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

ifを使ったフィルタリング

リスト内包表記には、if文を組み合わせて、条件を満たす要素だけをリストに含めることもできます。

# 1から20までの偶数だけをリストにしたい
evens = [i for i in range(1, 21) if i % 2 == 0]
print(evens) # [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]

リスト内包表記は、Pythonのコードを劇的に読みやすく、かつ効率的にするための非常に重要な機能です。積極的に使っていきましょう。

やってみよう！知識を固める小問題

【小問題1】文字列リストの作成

リスト `words = ["apple", "banana", "cherry"]` があります。リスト内包表記を使って、各単語の長さを要素とする新しいリスト `lengths` を作成してください。期待する出力: `[5, 6, 6]`

words = ["apple", "banana", "cherry"]
lengths = [len(w) for w in words]
print(lengths)

【小問題2】条件付き加工

リスト `numbers = [1, 2, 3, 4, 5, 6]` があります。このリストの要素のうち、奇数だけを2倍した新しいリストを作成してください。期待する出力: `[2, 6, 10]`

numbers = [1, 2, 3, 4, 5, 6]
result = [n * 2 for n in numbers if n % 2 != 0]
print(result)

5-4: deque (高速な両端キュー)

リストの弱点を克服する

Pythonのリストは、末尾への追加 (append) や取り出し (pop) は高速(O(1))です。しかし、先頭への追加 (insert(0, ...)) や取り出し (pop(0)) は、全要素をずらす必要があるため非常に遅い(O(N))という弱点があります。

この弱点を克服したのが collections.deque (デックと読みます) です。dequeは「両端が開いた筒」のようなイメージで、先頭からも末尾からも、高速 (O(1)) に要素を追加・削除できます。

from collections import deque

d = deque([1, 2, 3])
print(d)

d.append(4)     # 末尾に追加
print(d)        # deque([1, 2, 3, 4])

d.appendleft(0) # 先頭に追加
print(d)        # deque([0, 1, 2, 3, 4])

d.pop()         # 末尾から取り出し
print(d)        # deque([0, 1, 2, 3])

d.popleft()     # 先頭から取り出し
print(d)        # deque([1, 2, 3])

後の章で学ぶ「幅優先探索(BFS)」など、キュー（先入れ先出しのデータ構造）を扱う場面で絶大な威力を発揮します。

5-5: Counter (自動集計ツール)

数え上げのスペシャリスト

「リストや文字列の中に、各要素が何個ずつあるか数えたい」
これを自力でやると辞書を用意してループを回す必要がありますが、そんな「数え上げ」作業を一瞬で終わらせてくれるのが collections.Counter です。

from collections import Counter

S = "abracadabra"
C = Counter(S)

print(C)
# 出力: Counter({'a': 5, 'b': 2, 'r': 2, 'c': 1, 'd': 1})

# 特定の要素の数も簡単に取り出せる
print(C['a']) # 5
print(C['z']) # 存在しないキーでもエラーにならず0が返る

# most_common(k)で出現頻度上位k個を(要素, 回数)のリストで取得
print(C.most_common(2)) # [('a', 5), ('b', 2)]

集計系の問題では、まず Counter が使えないか考えてみましょう。

5-6: itertools (順列・組み合わせの達人)

全探索をシンプルに書く

「リストの要素から3つ選ぶ全ての組み合わせを試したい…」
これを多重ループで書くのは大変ですが、 itertools を使えば、組み合わせや順列を簡単に生成できます。

• permutations(リスト, 個数): 順列（順番を考慮する）を列挙
• combinations(リスト, 個数): 組み合わせ（順番を考慮しない）を列挙

import itertools
my_list = [1, 2, 3]

# 3つの要素から2つを選ぶ「順列」
print("--- 順列 ---")
for p in itertools.permutations(my_list, 2):
    print(p, end=" ") # (1, 2) (1, 3) (2, 1) (2, 3) (3, 1) (3, 2) 

print("\n")

# 3つの要素から2つを選ぶ「組み合わせ」
print("--- 組み合わせ ---")
for c in itertools.combinations(my_list, 2):
    print(c, end=" ") # (1, 2) (1, 3) (2, 3)

後の章で学ぶ「全探索」系の問題で絶大な威力を発揮します。

5-E: 部末演習

作法と武器を手に、実践へ

第5部、お疲れ様でした！コードの効率を測る「計算量」という視点と、それを改善するためのPythonの強力な武器を学びました。この演習で、それらを使いこなす感覚を養いましょう。

【演習問題】アナグラム判定

2つの文字列SとTが与えられます。TがSのアナグラム（文字の種類と数が同じで、並びだけが違う）になっているかどうかを判定してください。

from collections import Counter

S = input()
T = input()

# Counterオブジェクトをそれぞれ作成
s_counts = Counter(S)
t_counts = Counter(T)

# Counterオブジェクト同士を比較するだけ！
if s_counts == t_counts:
    print("Yes")
else:
    print("No")

# 別解：ソートして比較する (O(N log N))
# if sorted(S) == sorted(T):
#     print("Yes")
# else:
#     print("No")

挑戦：Cランク & AtCoder(B)

おめでとうございます！計算量という概念を学び、Pythonの便利なライブラリという武器を手に入れたあなたは、Paizaスキルチェックの「Cランク」やAtCoderのB問題に挑戦する準備が整いました。

このレベルの問題は、単純なループでは時間切れになるような制約が設定されていることが多く、「いかに効率的なデータ構造を選ぶか」「便利なライブラリを知っているか」が問われます。

• 挑戦のリンク: Paiza Cランクレベルアップ問題集（文字列処理）
• ヒント：第4部、第5部で学んだデータ構造やライブラリが役立ちます。

• 挑戦のリンク: AtCoder ABC081 C - Not so Diverse
• ヒント：第5-5章 `Counter`の知識が鍵を握ります。種類を減らすには、出現回数が少ないものから取り除いていくのが最適です。

6-1: 全探索

アルゴリズムの原点にして頂点

全探索とは、その名の通り「考えられるすべてのパターンを、文字通り全部試す」という、最もシンプルで最も強力なアルゴリズムの考え方です。

複雑なアルゴリズムを知らなくても、全探索で解ける問題は非常に多いです。まずは「全部試せば答えは出るんじゃないか？」と考えるのが、問題解決の第一歩です。

どんな時に使える？

全探索が使えるのは、試すべきパターンの総数が、計算量の限界（だいたい10⁷〜10⁸回程度）に収まるときです。問題の制約を見て、全探索で間に合うかを見極めるのが重要です。

• Nが10〜20程度 → O(N²)やO(N³)のループでも間に合うかも？
• Nが20前後 → O(2^N) のbit全探索が使えるかも？
• Nが100以上 → 単純な全探索はほぼ無理。別のアルゴリズムを考える。

bit全探索：選ぶか、選ばないか

「N個の品物それぞれについて、選ぶか選ばないかの2択をすべて試す」ような場面で使います。選び方は2^N通りあり、これを2進数で表現して全探索します。

N = 3
items = ["A", "B", "C"]

# 0から7 (2**3 - 1) までループ
for i in range(1 << N): # 1 << N は 2**N と同じ
    selected = []
    for j in range(N):
        # i の jビット目が1かどうかをチェック
        if (i >> j) & 1:
            selected.append(items[j])
    print(i, ":", selected)

やってみよう！知識を固める小問題

【小問題1】3つのサイコロ

3つの6面サイコロを振ったとき、出目の合計が10になる組み合わせは何通りありますか？三重ループを使って全探索で求めてください。

count = 0
for i in range(1, 7):
    for j in range(1, 7):
        for k in range(1, 7):
            if i + j + k == 10:
                count += 1
print(count)

6-2: 二分探索

「賢い絞り込み」の技術

本棚にアルファベット順に並んだ1000冊の本があります。この中から「Python」というタイトルの本を探してください。

まさか先頭から1冊ずつ探したりはしませんよね？
普通は、まず真ん中あたりを手に取り、例えば「Java」だったら、探している「Python」はもっと後ろにあるはずなので、棚の後半部分に的を絞ります。そしてまたその真ん中を手に取り…と繰り返すはずです。

この「探索範囲を毎回半分に絞っていく」賢い方法が二分探索（Binary Search）です。

絶対条件：データがソート済みであること

二分探索が使えるのは、データが必ずソート済み（小さい順 or 大きい順に並んでいる）の場合に限られます。計算量は驚異的な O(log N) になります。

実装：`bisect`ライブラリ

Pythonには二分探索を簡単に行うためのbisectという便利なライブラリがあります。

import bisect
sorted_list = [10, 20, 30, 40, 50]
idx = bisect.bisect_left(sorted_list, 35)
print(idx) # 3

やってみよう！知識を固める小問題

【小問題1】特定のマシンの検索

性能値がソートされたリスト machines = [100, 150, 200, 250, 300] があります。性能値が200のマシンがリストの何番目（0-indexed）にあるか、bisect_leftを使って調べてください。

import bisect
machines = [100, 150, 200, 250, 300]
idx = bisect.bisect_left(machines, 200)
print(idx) # 2

6-3: 再帰関数

自分を呼び出す、不思議な関数

再帰関数とは、マトリョーシカ人形のように、「関数の中で自分自身の関数を呼び出す」構造を持った関数です。大きな問題を、同じ構造を持つ小さな問題に分解して解いていく、というアプローチで非常に強力です。

例：階乗の計算

5の階乗 (5!) は 5 * (4の階乗) と考えられます。

def factorial(n):
    # ベースケース（一番小さい問題の答え）
    if n == 0:
        return 1
    # 再帰的ステップ（より小さい問題に分解）
    else:
        return n * factorial(n - 1)

print(factorial(5)) # 120

絶対に忘れてはいけない「ベースケース」

再帰関数には、必ず「これ以上分解できない最小の問題の答え」であるベースケース（終了条件）が必要です。これがないと無限に自分を呼び出し続け、エラーになってしまいます。

6-4: 深さ優先探索(DFS)

「行けるところまで行く」迷路探索

深さ優先探索（Depth First Search, DFS）は、「まず一つの道を深く、行けるところまで進み、行き止まったら戻って別の道を試す」という探索方法です。

実装には、前章で学んだ再帰関数を使うのが非常に直感的です。

# graph[i] は、地点iから行ける地点のリスト
graph = { 'A': ['B', 'C'], 'B': ['D', 'E'], 'C': ['F'], 'D': [], 'E': ['F'], 'F': [] }
visited = set()

def dfs(node):
    visited.add(node)
    print(node, end=' ')
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(neighbor)

dfs('A') # A B D E F C 

DFSは、グラフの連結判定や、全ての経路の列挙といった問題で威力を発揮します。

6-5: 幅優先探索(BFS)

「近い順に調べる」波紋の探索

幅優先探索（Breadth First Search, BFS）は、池の波紋のように、「スタート地点から近い順に、全方位をくまなく探索していく」手法です。

BFSの最大の特徴は、「辺の重みが全て同じグラフ」において、ゴールにたどり着いたとき、その経路が必ず最短経路（最小手数）になることです。「迷路の最短歩数」を求める問題はBFSの典型例です。

実装には「次に行くべき場所リスト」を管理するキュー（collections.deque）を使います。

from collections import deque
# (4-6章のBFSコードと同様のため省略)

6-E: 部末演習

探索戦略を使い分ける

第6部、お疲れ様でした！全探索、二分探索、DFS、BFSという、アルゴリズムの基本となる探索戦略を学びました。この演習では、問題の性質に応じて適切な戦略を選ぶ訓練をします。

【演習問題】部分和問題の応用

N個の整数からなるリストAと、整数Kが与えられます。Aの要素をいくつか（0個でも可）選んで、その和をKにすることはできますか？

入力例:
4 13
1 2 4 8

出力例:
Yes （1+4+8=13）

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

found = False
for i in range(1 << N):
    current_sum = 0
    for j in range(N):
        if (i >> j) & 1:
            current_sum += A[j]
    if current_sum == K:
        found = True
        break

if found:
    print("Yes")
else:
    print("No")

7-1: DPの心：メモ化再帰

「賢いサボり方」の技術

第4部で学んだフィボナッチ数を計算する再帰関数を思い出してください。fib(5)を計算するのに、fib(3)が2回、fib(2)が3回も呼ばれるなど、非常に無駄が多い処理でした。

「一度計算した答えは、メモしておいて二度と計算しない」——この、プログラミングにおける「賢いサボり方」が、動的計画法(DP)の第一歩、メモ化再帰です。

# メモ用の配列（-1は未計算を表す）
memo = [-1] * 51 

def fib(n):
    # ベースケース
    if n == 0: return 0
    if n == 1: return 1
    
    # すでに計算済みなら、メモした値を返す
    if memo[n] != -1:
        return memo[n]
    
    # 未計算なら、計算してメモしてから返す
    memo[n] = fib(n - 1) + fib(n - 2)
    return memo[n]

print(fib(50))

ただこれだけで、計算量は爆発的なO(2^N)から、驚異的なO(N)にまで削減されます。各fib(n)が、高々1回しか計算されなくなるからです。

この「テーブル（配列や辞書）を用意して、計算結果を記録する」という考え方が、あらゆるDPの基本になります。

7-2: 配るDPと貰うDP

DPの2つの実装スタイル

メモ化再帰はトップダウン（大きな問題から小さな問題へ）のアプローチでしたが、DPはボトムアップ（小さな問題から大きな問題へ）に実装することもできます。これには主に2つのスタイルがあります。

問題設定：N個の足場があり、足場iからはi+1かi+2にジャンプできます。足場iにたどり着く方法の総数を求めてください。

貰うDP (pull-style)

「今いるマスには、どこから来られるか？」を考えるスタイルです。

# dp[i]: 足場iへの到達方法の数
dp = [0] * N
dp[0] = 1 # スタート

for i in range(1, N):
    # 足場i-1から貰う
    if i - 1 >= 0:
        dp[i] += dp[i-1]
    # 足場i-2から貰う
    if i - 2 >= 0:
        dp[i] += dp[i-2]

配るDP (push-style)

「今いるマスから、どこへ行けるか？」を考えるスタイルです。

# dp[i]: 足場iへの到達方法の数
dp = [0] * N
dp[0] = 1 # スタート

for i in range(N):
    # 足場i+1へ配る
    if i + 1 < N:
        dp[i+1] += dp[i]
    # 足場i+2へ配る
    if i + 2 < N:
        dp[i+2] += dp[i]

どちらのスタイルでも解けますが、問題によって考えやすい方が異なります。両方の視点を持っておくことが重要です。

7-3: DPパターン(ナップサック問題)

価値を最大化する選択

DPには、いくつかの有名な問題の「型」があります。その代表格がナップサック問題です。

N個の品物があり、それぞれ重さw_iと価値v_iが決まっています。重さの合計がWを超えないように品物を選んだとき、価値の合計の最大値はいくらになりますか？

DPテーブルの設計

dp[i][w] を「i番目までの品物の中から、重さの合計がw以下になるように選んだときの、価値の最大値」と定義します。

i番目の品物を考えるとき、選択肢は2つです。

• 選ばない: この場合、価値はi-1番目までの品物で重さwを達成した場合と同じ。→ dp[i-1][w]
• 選ぶ: この場合、価値は「i-1番目までの品物で重さ(w - w_i)を達成した価値」に v_i を足したもの。→ dp[i-1][w - wi] + vi

この2つのうち、大きい方をdp[i][w]の値として採用します。

N, W = ...
items = [(w_1, v_1), (w_2, v_2), ...]

# dp[i][w]: i番目までの品物で重さw以下での最大価値
dp = [[0] * (W + 1) for _ in range(N + 1)]

for i in range(N):
    w_i, v_i = items[i]
    for w in range(W + 1):
        # i番目の品物を選ばない場合
        dp[i+1][w] = max(dp[i+1][w], dp[i][w])
        
        # i番目の品物を選ぶ場合
        if w + w_i <= W:
            dp[i+1][w+w_i] = max(dp[i+1][w+w_i], dp[i][w] + v_i)

print(dp[N][W])

7-E: 部末演習

DPの思考法を体得する

第7部、お疲れ様でした！動的計画法(DP)という、競技プログラミングにおける最重要テクニックの一つの扉を開きましたね。この演習では、DPテーブルの設計と更新式の立案という、DPの核心部分をトレーニングします。

【演習問題】最長増加部分列 (LIS)

N個の整数からなる数列Aが与えられます。Aからいくつかの要素を取り出して作ることができる、単調に増加する部分列のうち、最も長いものの長さを求めてください。

入力例:
5
3 1 4 2 5

出力例:
3 (例えば [1, 2, 5] や [1, 4, 5])

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

# dp[i]: 最後がA[i]であるような最長増加部分列の長さ
dp = [1] * N

for i in range(N):
    for j in range(i):
        if A[j] < A[i]:
            dp[i] = max(dp[i], dp[j] + 1)

print(max(dp))

挑戦：Bランク & AtCoder(C)

おめでとうございます！DPの基本的な考え方をマスターしたあなたは、Paizaスキルチェックの「Bランク」やAtCoderのC問題レベルに挑戦する準備ができました。

このレベルの問題では、「この問題はDPで解けるのではないか？」と気づき、適切なDPテーブルを設計する能力が問われます。

• 挑戦のリンク: Paiza Bランクレベルアップ問題集（動的計画法）
• ヒント：第7部で学んだDPの基本的な型（貰うDP/配るDP）がそのまま使えます。

• 挑戦のリンク: AtCoder ABC040 C - 柱渡り
• ヒント：本章で学んだカエルの足場問題と全く同じ構造です。DPテーブルの定義と更新式を思い出しましょう。

8-1: 優先度付きキュー

ただの行列じゃない、「VIP待遇」のある行列

病院の救急外来を想像してください。患者は到着順に診察されるわけではありませんよね。軽傷の人より、重体の人が優先されます。

このように、単なる「先入れ先出し」ではなく、「最も優先度が高い（値が小さい or 大きい）ものから取り出す」ことができるデータ構造が優先度付きキュー（Priority Queue）です。

実装：`heapq`ライブラリ

Pythonでは、heapqライブラリがこの機能を提供します。これは内部的に「ヒープ」という木構造を使って、効率的に最小値を取り出せるようになっています。

注意：heapqは最小ヒープとして実装されています。つまり、常に一番小さい要素が取り出されます。

import heapq

# 優先度付きキュー（実体はただのリスト）
pq = []

# 要素の追加 (heappush)
heapq.heappush(pq, 30) # [30]
heapq.heappush(pq, 10) # [10, 30]
heapq.heappush(pq, 20) # [10, 30, 20] ※内部はヒープ構造

print("現在のキューの中身（ヒープ構造）:", pq)

# 最小値の取り出し (heappop)
min_val = heapq.heappop(pq)
print("取り出した最小値:", min_val) # 10
print("残りのキュー:", pq)

N個の要素が入っているとき、要素の追加(push)も、最小値の取り出し(pop)も、どちらもO(log N)という驚異的な速さで行えます。

やってみよう！優先度付きキューを使いこなす

【小問題1】最小値の連続取り出し

空の優先度付きキューに、50, 10, 80, 30, 20 をこの順で追加した後、3回連続で最小値を取り出して表示してください。

import heapq
pq = []
data = [50, 10, 80, 30, 20]
for x in data:
    heapq.heappush(pq, x)

for _ in range(3):
    print(heapq.heappop(pq))
# 出力: 10, 20, 30

【小問題2】最大値の取り出し

heapqは最小値しか取り出せませんが、工夫することで最大値を取り出す「最大ヒープ」を実装できます。数値の符号を反転させる方法で、データ[10, 50, 20]から最大値を取り出してください。

import heapq
pq = []
data = [10, 50, 20]
for x in data:
    heapq.heappush(pq, -x) # 符号を反転してpush

max_val = -heapq.heappop(pq) # popして再度反転
print(max_val) # 50

【小問題3】タプルの利用

タスク管理を考えます。(優先度, タスク名) のタプルを優先度付きキューに追加し、最も優先度の高い（数値が小さい）タスクを取り出してください。データ: [(3, "書類整理"), (1, "緊急メール返信"), (2, "会議準備")]

import heapq
tasks = [(3, "書類整理"), (1, "緊急メール返信"), (2, "会議準備")]
pq = []
for task in tasks:
    heapq.heappush(pq, task)

most_urgent_task = heapq.heappop(pq)
print(most_urgent_task) # (1, '緊急メール返信')

8-2: ダイクストラ法

最強の「ナビゲーション」アルゴリズム

あなたがカーナビアプリだとします。スタートからゴールまで、各道路に「通過にかかる時間（コスト）」が設定されているとき、どうやって「最速ルート」を見つけますか？

これがまさにダイクストラ法が解決する問題です。ダイクストラ法は、「辺に重み（コスト）があるグラフにおいて、一つの始点から他の全ての頂点への最短経路を求める」アルゴリズムです。

アルゴリズムの動き

ダイクストラ法は「スタートから近い順に、各都市への最短距離を確定させていく」イメージです。

1. 各都市への最短距離を「未定（無限大）」、スタート地点だけ「0」とする。
2. 「未確定の都市のうち、最も距離が短い都市」を一つ選ぶ。（ここで優先度付きキューが活躍！）
3. その選んだ都市を「距離確定」とする。
4. 確定した都市から行ける隣の都市について、「この都市経由で行ったら、もっと近くなる？」を計算し、もし近くなるなら距離を更新する。
5. 全ての都市が確定するまで2-4を繰り返す。

import heapq
# V:頂点数, E:辺数, r:始点
# graph[u] = [(v, cost), ...]: uからvへコストcostの辺
# (入力処理は省略)
graph = ... 
dist = [float('inf')] * V
dist[r] = 0
pq = [(0, r)] # (距離, 頂点)

while pq:
    d, u = heapq.heappop(pq)
    if d > dist[u]: continue # 更新済みの古い情報なら無視

    for v, cost in graph[u]:
        if dist[u] + cost < dist[v]:
            dist[v] = dist[u] + cost
            heapq.heappush(pq, (dist[v], v))

やってみよう！ダイクストラ法の理解を深める

【小問題1】使えないケース

ダイクストラ法は最短経路を求める万能アルゴリズムに見えますが、一つだけ「使ってはいけない」重大な制約があります。それは何でしょうか？

【小問題2】手でトレース

本章の導入で使ったグラフ{'A': {'B': 1, 'C': 4}, 'B': {'C': 2, 'D': 5}, 'C': {'D': 1}, 'D': {}}で、スタートを'B'にした場合、'D'への最短距離はいくつになりますか？手でアルゴリズムを追ってみましょう。

8-3: Union-Find木

「グループ分け」を爆速で管理する

SNSで、友達の友達はみな友達、というように「友達グループ」を作っていく状況を想像してください。「AさんとBさんが友達になった」「CさんとDさんが友達になった」「BさんとCさんが友達になった」…このとき、AさんとDさんは同じグループでしょうか？

このように、「いくつかの要素を、互いに素な集合（グループ）に分け、2つの要素が同じグループに属するかを高速に判定したり、2つのグループを1つに統合したりする」ためのデータ構造がUnion-Find木です。

提供する主な操作

• unite(x, y): 要素xが属するグループと、要素yが属するグループを統合する。
• same(x, y): xとyが同じグループに属するかを判定する。

Union-Find木はクラスとして実装するのが一般的で、経路圧縮などの工夫を施すことで、各操作をほぼO(1)という驚異的な速度で実行できます。

class UnionFind:
    def __init__(self, n): self.parent = list(range(n))
    def find(self, x):
        if self.parent[x] == x: return x
        self.parent[x] = self.find(self.parent[x]); return self.parent[x]
    def unite(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx != ry: self.parent[ry] = rx
    def same(self, x, y): return self.find(x) == self.find(y)

やってみよう！Union-Findを使いこなす

【小問題1】グループ判定

5人の人がいます(0〜4)。(0,1), (1,2), (3,4)がそれぞれ友達になったとき、(0,2)は同じグループですか？ (0,3)は同じグループですか？

uf = UnionFind(5)
uf.unite(0, 1)
uf.unite(1, 2)
uf.unite(3, 4)
print("0と2は同じ？:", uf.same(0, 2)) # True
print("0と3は同じ？:", uf.same(0, 3)) # False

【小問題2】連結成分の個数

上記の小問題1の状況で、最終的にグループの数（連結成分の数）はいくつですか？

# 上記のufオブジェクトの続き
count = 0
for i in range(5):
    if uf.parent[i] == i:
        count += 1
print("グループの数:", count) # 2

8-4: 最小全域木

全ての拠点を最小コストで繋ぐ

あなたはインフラ技術者です。いくつかの都市（頂点）があり、都市間にケーブルを敷設するコスト（辺の重み）が分かっています。全ての都市を連結させる（どの都市からでも他の都市へ行けるようにする）ために、ケーブルの総敷設コストを最小にしたい。どうすればよいでしょうか？

この問題を解決するのが最小全域木（Minimum Spanning Tree, MST）を求めるアルゴリズムです。

クラスカル法：欲張りなアプローチ

MSTを求める代表的なアルゴリズムがクラスカル法です。

1. 全ての辺を、コストが小さい順にソートします。
2. コストの小さい辺から順番に見ていきます。
3. その辺を追加しても閉路（ループ）ができないなら、その辺を採用します。（ここでUnion-Find木が活躍！）
4. (頂点の数 - 1)本の辺を採用するまで繰り返します。

# UnionFindクラスは前章のものを流用
# edges: (コスト, 頂点u, 頂点v) のリスト
edges.sort() 

uf = UnionFind(N)
total_cost = 0
for cost, u, v in edges:
    if not uf.same(u, v):
        uf.unite(u, v)
        total_cost += cost

やってみよう！最小全域木の考え方

【小問題1】MST vs 最短経路

ある2頂点S, Gを結ぶ最短経路は、最小全域木に含まれる辺だけで構成されるとは限りません。それはなぜですか？

【小問題2】クラスカル法の手順

辺のコストが(A,B,1), (B,C,2), (C,A,3)の3本あるグラフで、クラスカル法を適用した場合、どの辺が選ばれますか？

8-E: 部末演習

応用アルゴリズムの実践

第8部、お疲れ様でした！ダイクストラ法やUnion-Findといった、グラフ問題の強力な武器を学びました。これらは多くの問題の基礎となる重要なアルゴリズムです。

【演習問題】派閥の大きさ

N人の生徒とM個の友好関係（誰と誰が友達か）が与えられます。友達の友達は友達、とみなしたとき、最大の派閥（グループ）の人数は何人ですか？

入力例:
5 3
0 1
1 2
3 4

出力例:
3 (グループ{0,1,2}と{3,4}ができ、大きい方は3人)

# サイズ管理機能付きのUnionFindクラスを流用
N, M = map(int, input().split())
uf = UnionFind(N)

for _ in range(M):
    u, v = map(int, input().split())
    uf.unite(u, v)

max_size = 0
for i in range(N):
    max_size = max(max_size, uf.size(i))

print(max_size)

挑戦：Aランク問題

おめでとうございます！ダイクストラ法やUnion-Findといった応用アルゴリズムを学び、あなたはPaizaスキルチェックの「Aランク」問題に挑戦する準備が整いました。

Aランク問題は、まさにこの部で学んだような典型アルゴリズムの知識を直接問う問題が多く出題されます。「この問題はあのアルゴリズムを使えば解ける！」と見抜く力が試されます。

• 挑戦のリンク: Paiza Aランクレベルアップ問題集（ダイクストラ法）
• ヒント：第8-2章で学んだダイクストラ法のコードがほぼそのまま使えます。

• 挑戦のリンク: AtCoder ATC001 A - Union Find
• ヒント：第8-3章で学んだUnion-Find木そのものです。クラスを正しく実装できるか試しましょう。

9-1: 累積和・いもす法

「区間への操作」を高速化する前処理

これまでに学んだアルゴリズムは、単体のデータや、データ間の関係性を扱うものでした。しかし、問題によっては「ある区間全体に対する操作」が求められることがあります。

例えば、「配列のL番目からR番目までの和を、何度も高速に求めたい」「たくさんの区間に、一様に値を足したい」といった要求です。これらを愚直に行うと計算量が悪化します。この「区間」を効率的に扱うための前処理テクニックが累積和とその応用形であるいもす法です。

累積和：区間の合計クエリをO(1)に

「リストのL番目からR番目までの要素の合計を求めてください」というクエリがQ回与えられる問題を考えます。毎回ループを回すとO(NQ)かかり、TLEの原因になります。

そこで、累積和を使います。「あらかじめ先頭から各インデックスまでの和を計算して、別のリストに保存しておく」という前処理をO(N)で行うことで、その後のクエリにO(1)で答えられるようになります。

A = [10, 20, 30, 40, 50]

# 累積和リストSを作る（元のリストより1つ長くするのがコツ）
S = [0] * (len(A) + 1)
for i in range(len(A)):
    S[i+1] = S[i] + A[i]
# Sは [0, 10, 30, 60, 100, 150] となる

# 例：インデックス1から3までの和（20+30+40）を求める
# S[4]（A[0]~A[3]の和）から S[1]（A[0]の和）を引く
result = S[3+1] - S[1] 
print(result) # 90

いもす法：区間への一括加算をO(1)に

「たくさんの区間 [L, R] に、値xを足してください」という操作を何度も行う場合、毎回ループで足していては間に合いません。 いもす法は、このような「区間への加算」を効率化する驚異的なテクニックです。

アイデア：「区間の始まりで+xし、区間の終わりの次で-xする」という印だけを付けておきます。最後に、全体の累積和を一度だけとれば、各区間にだけxが足された状態が復元できます。

# 10個のマスに、区間[2,5]に+10、区間[4,8]に+20したい
diff = [0] * 11 # 差分を記録する配列

# 区間[2,5]への操作
diff[2] += 10
diff[5+1] -= 10

# 区間[4,8]への操作
diff[4] += 20
diff[8+1] -= 20

# diff: [0, 0, 10, 0, 20, 0, -10, 0, 0, -20, 0]

# 最後に累積和をとる
result = [0] * 10
result[0] = diff[0]
for i in range(1, 10):
    result[i] = result[i-1] + diff[i]

print(result) # [0, 0, 10, 10, 30, 30, 20, 20, 20, 0]

9-2: しゃくとり法

二重ループをO(N)に変える探索術

「配列の中から、条件を満たす『連続した部分配列』を数え上げたい」
このような問題で、開始位置と終了位置を二重ループで全探索すると、計算量はO(N²)になってしまいます。Nが大きいとTLEです。

しかし、扱う区間の性質に「単調性」（区間を広げると条件に近づき、縮めると遠ざかる、など）があれば、しゃくとり法が使えます。これは、区間の右端と左端を上手く動かすことで、探索を線形時間O(N)に抑えるテクニックです。

実装パターン：右端を動かし、左端を縮める

しゃくとり法は、配列の右端を指すポインタrightをforループで動かし、その内側で「条件を満たしている限り」左端を指すポインタleftをwhileループで動かす、という実装が一般的です。

# 問題：和がK以上となる、最短の連続部分配列の長さを求める
A = [1, 4, 2, 7, 3, 5]
K = 10
N = len(A)
min_len = float('inf')
current_sum = 0
left = 0

# 右端 'right' を0からN-1まで動かしていく
for right in range(N):
    current_sum += A[right]

    # 和がK以上になる限り、条件を満たす最短の区間を探す
    while current_sum >= K:
        min_len = min(min_len, right - left + 1)
        current_sum -= A[left] # 左端を縮めて次の探索へ
        left += 1

print(min_len) # 2 (7+3=10)

ポインタrightとleftはそれぞれ一方向にしか進まないため、全体の計算量はO(N)になります。

9-3: 座標圧縮

巨大な座標を小さなインデックスに

「A = [10, 100, 5, 50000] という巨大な値を持つ配列を、DPテーブルの添字に使いたい…でもメモリが足りない！」

このような、値そのものではなく「値の大小関係（順位）」だけが重要な場面で、巨大な値を0から始まる連続した小さな整数に変換するテクニックが座標圧縮です。

実装方法：ソートと辞書マッピング

1. 圧縮したい値の重複を除いてソートする。
2. ソート済みのリストの各値と、そのインデックス（0, 1, 2, ...）を対応付ける辞書を作る。
3. 元の配列の各値を、辞書を使って圧縮後の値に置き換える。

A = [10, 100, 5, 50000, 100]

# 1. 重複を除いてソート
unique_sorted = sorted(list(set(A)))
# -> [5, 10, 100, 50000]

# 2. マッピング辞書を作成
coord_map = {val: i for i, val in enumerate(unique_sorted)}
# -> {5: 0, 10: 1, 100: 2, 50000: 3}

# 3. 圧縮
compressed = [coord_map[x] for x in A]
print(compressed) # [1, 2, 0, 3, 2]

座標圧縮はそれ単体で完結するアルゴリズムではなく、他のデータ構造（セグメント木など）やアルゴリズムと組み合わせることで真価を発揮する、重要な「前処理」のテクニックです。

9-4: セグメント木

区間への問いに光速で答える

第5部で「作法」として学んだデータ構造も、ここで「応用テクニック」として再登場します。 「区間に対する問い合わせ（Range Query）」と「一点の値の更新（Point Update）」の両方を、爆速（O(log N)）で処理できるデータ構造がセグメント木でした。

どんな問題を解決するか？

例えば、「N人の兵士が横一列に並んでおり、それぞれの兵士には強さがある。司令官がQ回命令を出す。命令には『i番目の兵士の強さをxに変更せよ』というものと、『L番目からR番目までの兵士の中で、最も強い者の強さはいくつか？』というものがある。」といった問題です。

愚直にやると、更新はO(1)ですが、区間の最大値クエリにO(N)かかり、全体でO(NQ)となります。セグメント木を使えば、どちらの操作もO(log N)で行え、全体でO(Q log N)にまで高速化できます。

9-E: 部末演習

計算量削減テクニックを使いこなす

第9部、お疲れ様でした！O(N²)をO(N)やO(N log N)に削減する強力なテクニックを学びました。これらはより難しい問題への足がかりとなります。

【演習問題】区間の和

N個の整数からなる数列Aと、Q個のクエリが与えられます。各クエリでは区間の左端Lと右端Rが与えられるので、AのL番目からR番目（0-indexed）までの和を答えてください。

制約: N, Q ≤ 10⁵

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

S = [0] * (N + 1)
for i in range(N):
    S[i+1] = S[i] + A[i]

for _ in range(Q):
    L, R = map(int, input().split())
    ans = S[R + 1] - S[L] # 0-indexedなのでR+1とL
    print(ans)

挑戦：Aランク & AtCoder(D)

おめでとうございます！累積和やしゃくとり法といった、計算量を劇的に改善するテクニックを身につけたあなたは、Paizaスキルチェックの「Aランク」の中でも難易度の高い問題や、AtCoderのD問題に挑戦する力がついてきました。

このレベルの問題は、単純なアルゴリズムの適用だけでは解けず、「前処理」や「計算の工夫」が求められます。

• 挑戦のリンク: Paiza Aランクレベルアップ問題集（いもす法）
• ヒント：第9-1章で学んだ累積和の応用である「いもす法」の考え方が必要になります。

• 挑戦のリンク: AtCoder ABC038 C - 単調増加
• ヒント：第9-2章で学んだ「しゃくとり法」の典型問題です。「単調に増加する」という条件を満たす区間を効率よく数え上げましょう。

10-1: 素数と約数

整数の世界の「原子」

整数論は、一見すると複雑なアルゴリズムの世界とは異質に感じるかもしれません。しかし、多くのアルゴリズムが、この整数が持つ性質の上に成り立っています。特に「素数」は、整数の世界における「原子」のようなもので、全ての整数は素数の積で表すことができます。

素数判定：試し割り法

ある整数Nが素数かどうかを判定する最も基本的な方法は、2からN-1までの数で割り切れるか試すことです。しかし、少し工夫するともっと効率的に判定できます。Nが合成数であれば、必ず√N以下の約数を持つはずです。これを利用したのが以下のコードです。

import math

def is_prime(n):
    if n < 2:
        return False
    # 2から√nまでを試す
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False # 割り切れたら素数ではない
    return True

print(is_prime(17)) # True
print(is_prime(18)) # False

約数列挙

ある整数Nの約数を全て列挙する場合も、√Nまでの探索で十分です。なぜなら、dがNの約数であれば、N/dも必ず約数になるからです。

def get_divisors(n):
    divisors = []
    # 1から√nまでを試す
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            # n/i が i と異なる場合のみ追加（平方数の重複を防ぐ）
            if i*i != n:
                divisors.append(n // i)
    divisors.sort() # 昇順に並べる
    return divisors

print(get_divisors(36)) # [1, 2, 3, 4, 6, 9, 12, 18, 36]

やってみよう！知識を固める小問題

【小問題1】素数判定

入力された整数Nが素数なら "Prime"、そうでなければ "Not Prime" と表示するプログラムを作成してください。

import math

def is_prime(n):
    if n < 2: return False
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0: return False
    return True

N = int(input())
if is_prime(N):
    print("Prime")
else:
    print("Not Prime")

【小問題2】完全数

自分自身を除く約数の和が、自分自身と等しくなる自然数を「完全数」といいます。入力された整数Nが完全数かどうかを判定してください。例えば、6の約数は1,2,3,6で、1+2+3=6なので6は完全数です。

def get_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i*i != n: divisors.append(n // i)
    return divisors

N = int(input())
divs = get_divisors(N)
# 自分自身を除く約数の和
sum_of_divs = sum(divs) - N 

if sum_of_divs == N:
    print("Yes")
else:
    print("No")

【小問題3】エラトステネスのふるい

N以下の素数をすべて列挙するアルゴリズム「エラトステネスのふるい」を実装してください。これは、2から順に、素数を見つけたらその倍数をすべてリストから消していく、という操作を繰り返します。

def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for p in range(2, int(n**0.5) + 1):
        if is_prime[p]:
            for i in range(p*p, n + 1, p):
                is_prime[i] = False
    
    primes = []
    for i in range(n + 1):
        if is_prime[i]:
            primes.append(i)
    return primes

N = int(input())
print(sieve(N))

10-2: 合同式と逆元

巨大な数を「時計の世界」で考える

競技プログラミングでは、「答えを 1,000,000,007 (10⁹+7) で割った余りを出力してください」という問題が頻出します。これは、答えが非常に大きな数になり、通常の変数型では扱いきれないためです。

この「余りの世界」で計算を正しく行うための道具が合同式です。a ≡ b (mod m) は、「aをmで割った余りと、bをmで割った余りが等しい」ことを意味します。

足し算、引き算、掛け算は、途中の計算で余りを取っても最終結果は変わりません。

MOD = 10**9 + 7
a = 10**9
b = 10**9

# (a + b) % MOD は ((a % MOD) + (b % MOD)) % MOD と同じ
print((a + b) % MOD)
# ((a % MOD) + (b % MOD)) % MOD を計算
a_mod = a % MOD
b_mod = b % MOD
print((a_mod + b_mod) % MOD)

割り算はどうする？ → 逆元の登場

割り算 a / b は、単純に余りを取ることができません。そこで登場するのがモジュラ逆元です。 数 b の逆元 b-1 とは、b * b-1 ≡ 1 (mod m) となる数のことです。 これを使うと、割り算を掛け算に変換できます。

a / b (mod m) ≡ a * b-1 (mod m)

mが素数のとき、フェルマーの小定理より bm-2 ≡ b-1 (mod m) となることが知られています。Pythonのpow(b, m-2, m)を使えば、この逆元を高速に計算できます。

MOD = 10**9 + 7
a = 100
b = 5

# 100 / 5 を mod の世界で計算する
# bの逆元を計算
b_inv = pow(b, MOD - 2, MOD)

# a * (bの逆元) を計算
ans = (a * b_inv) % MOD
print(ans) # 20

やってみよう！知識を固める小問題

【小問題1】巨大な掛け算

2つの整数 A, B が与えられます。A * B を 10⁹+7 で割った余りを計算してください。

A, B = map(int, input().split())
MOD = 10**9 + 7
ans = (A % MOD) * (B % MOD) % MOD
print(ans)

【小問題2】巨大なべき乗

2つの整数 A, B が与えられます。A^B を 10⁹+7 で割った余りを計算してください。pow(A, B, MOD)を使うと高速に計算できます。

A, B = map(int, input().split())
MOD = 10**9 + 7
print(pow(A, B, MOD))

【小問題3】割り算の実行

2つの整数 A, B が与えられます。A / B を 10⁹+7 で割った余りを計算してください。

A, B = map(int, input().split())
MOD = 10**9 + 7

# Bの逆元を計算
B_inv = pow(B, MOD - 2, MOD)
ans = (A * B_inv) % MOD
print(ans)

10-3: 組み合わせ(nCr)

選び方の総数を数え上げる

「n個の異なるものから、r個を選ぶ方法は何通りか？」これを計算するのが組み合わせ、通称 nCr です。 公式は n! / (r! * (n-r)!) です。

しかし、これも数が非常に大きくなるため、「余りをとってください」と指示されることがほとんどです。 そこで、前章で学んだ逆元が活躍します。

nCr (mod m) ≡ n! * (r!)-1 * ((n-r)!)-1 (mod m)

この計算を効率的に行うには、あらかじめ1!からn!までの階乗とその逆元をテーブルとして計算しておくのが定石です。

nCr (mod m) の高速計算

MOD = 10**9 + 7
MAX_N = 2 * 10**5 # 問題に応じて設定

# 階乗テーブル
fact = [1] * (MAX_N + 1)
# 逆元階乗テーブル
inv_fact = [1] * (MAX_N + 1)

# 階乗テーブルを作成
for i in range(1, MAX_N + 1):
    fact[i] = (fact[i-1] * i) % MOD

# N! の逆元を計算 (MOD-2乗)
inv_fact[MAX_N] = pow(fact[MAX_N], MOD - 2, MOD)

# 逆元階乗テーブルを逆順に作成
# (i-1)!^-1 = i!^-1 * i を利用
for i in range(MAX_N, 0, -1):
    inv_fact[i-1] = (inv_fact[i] * i) % MOD

# nCr を計算する関数
def nCr_mod(n, r):
    if r < 0 or r > n:
        return 0
    # n! * (r!)^-1 * (n-r)!^-1
    numerator = fact[n]
    denominator = (inv_fact[r] * inv_fact[n-r]) % MOD
    return (numerator * denominator) % MOD

# 例：10C3 を計算
print(nCr_mod(10, 3)) # 120

この前計算を一度O(N)で行っておけば、nCrの問い合わせにO(1)で答えられます。

やってみよう！知識を固める小問題

【小問題1】パスカルの三角形

nCr には nCr = n-1Cr-1 + n-1Cr という性質があります。これを利用して、10C3 を計算してみてください。

N = 10
R = 3
C = [[0] * (N + 1) for _ in range(N + 1)]
for i in range(N + 1):
    C[i][0] = 1
    for j in range(1, i + 1):
        C[i][j] = C[i-1][j-1] + C[i-1][j]
print(C[N][R])

【小問題2】グリッドの最短経路

縦Hマス、横Wマスのグリッドがあります。左上から右下まで、右か下にしか進めないとき、最短経路は何通りありますか？

# 上記の nCr_mod 関数が定義されているとする
H, W = map(int, input().split())
ans = nCr_mod(H + W - 2, H - 1) # (0,0)から(H-1,W-1)までなので
print(ans)

10-E: 部末演習

整数論と組み合わせの総仕上げ

第10部、お疲れ様でした！目に見えない「数の性質」を操るテクニックを学びました。これらは、特に数え上げ問題で絶大な力を発揮します。

【演習問題1】素因数分解

与えられた整数 N を素因数分解し、{素因数: 指数, ...} の形式の辞書として出力してください。

入力例: 72

出力例: {2: 3, 3: 2} (72 = 2³ * 3²)

def prime_factorize(n):
    factors = {}
    temp = n
    for i in range(2, int(n**0.5) + 1):
        if temp % i == 0:
            count = 0
            while temp % i == 0:
                count += 1
                temp //= i
            factors[i] = count
    
    if temp != 1:
        factors[temp] = 1
        
    return factors

N = int(input())
print(prime_factorize(N))

【演習問題2】プレゼントの選び方

N種類のプレゼントが1つずつあります。この中からK個以上を選ぶ方法は何通りありますか？答えを 10⁹+7 で割った余りを求めてください。

# 上記の nCr_mod 関数一式が定義されているとする
N, K = map(int, input().split())
MOD = 10**9 + 7

total_ways = 0
for r in range(K, N + 1):
    total_ways = (total_ways + nCr_mod(N, r)) % MOD

print(total_ways)

挑戦：発展的な組み合わせ問題

おめでとうございます！整数論と組み合わせ計算という、競技プログラミングの強力な武器を手にしました。 これらは、AtCoderのD問題以上で頻出する「数え上げ問題」を解くための必須知識です。

このレベルの問題は、単純にnCrを計算するだけでなく、「どの場面で組み合わせ計算を使うのか」を見抜く洞察力が試されます。

• 挑戦のリンク: AtCoder ABC132 D - Blue and Red Balls
• ヒント：K個の青いボールをまず配置し、その隙間に赤いボールを入れていく、という考え方をします。i回ボールを選ぶ問題では、「N-K+1個の場所からi個を選ぶ組み合わせ」と「K-1個の場所からi-1個を選ぶ組み合わせ」の積で計算できます。

• 挑戦のリンク: Paiza Aランクレベルアップ問題集（組み合わせ）
• ヒント：問題文をよく読むと、組み合わせ(nCr)の計算に帰着させることができます。MODを取ることを忘れないようにしましょう。

11-1: ヒューリスティックとは

「最善の解」ではなく「満足できる解」を探す旅

おめでとうございます！あなたはついに、本書の最終章「ヒューリスティック」にたどり着きました。 これまで私たちが学んできたダイクストラ法や動的計画法は、決められた手順に従えば必ず「唯一の正しい答え（厳密解）」にたどり着くことができる「アルゴリズム」でした。

しかし、世の中には問題が複雑すぎて、厳密解を求めるのにスーパーコンピュータを使っても数百年、数万年かかってしまうような問題が存在します。代表的な例が「巡回セールスマン問題（TSP）」です。全ての都市を一度ずつ訪れて出発点に戻ってくるとき、総移動距離が最短になる経路はどれか、という問題です。都市の数が増えると、組み合わせが爆発的に増え、全探索は不可能になります。

このような「厳密解を求めるのは現実的ではない問題」に対して、「必ずしも最適ではないかもしれないが、実用上十分満足できる『良い解（近似解）』を、現実的な時間内に見つける」ための手法。それがヒューリスティックです。

ヒューリスティックの基本は、「現在の解」を評価する評価関数を定め、その評価値をより良くするための「改善操作（近傍探索）」を繰り返す、というシンプルなものです。

やってみよう！知識を固める小問題

【小問題1】厳密解法 vs ヒューリスティック

「100人の中から最も背の高い人を1人見つける」という問題は、厳密解法とヒューリスティック解法のどちらで解くべきですか？その理由も説明してください。

【小問題2】評価関数を考える

「巡回セールスマン問題」において、ある経路（解）の良し悪しを判断するための「評価関数」は、どのように定義すべきでしょうか？

【小問題3】改善操作を考える

「巡回セールスマン問題」で、現在の経路（解）を少しだけ変更して別の経路を作る「改善操作」には、どのようなものが考えられるでしょうか？

11-2: 貪欲法と山登り法

より良い解へ、一歩ずつ進む

ヒューリスティックの最も基本的な考え方が、この章で学ぶ「貪欲法」と「山登り法」です。

貪欲法：局所的な最善手の積み重ね

貪欲法 (Greedy Algorithm) は、「その場その場で、自分にとって最も利益が大きい選択肢を取り続ける」という戦略です。一度決定した選択は、後から変更しません。非常にシンプルで実装も簡単なのが特徴です。

# 問題：価値が(100, 120, 80)、重さが(10, 30, 20)の品物がある。
# 重さ50のナップサックに、分割可能で詰め込む場合。
items = [(100, 10), (120, 30), (80, 20)] # (価値, 重さ)
# 「価値/重さ」の比率でソートするのが貪欲戦略
# 比率: 10, 4, 4 -> 価値100の品物が一番「お得」
items.sort(key=lambda x: x[0]/x[1], reverse=True)
# ... この後、比率の高いものから順に詰められるだけ詰めていく

山登り法：近傍探索による改善

山登り法 (Hill Climbing) は、現在の解（経路全体など）を少しだけ変更（近傍探索）してみて、もし評価値が改善されるなら、その変更を採用するという動きを繰り返します。

【貪欲法との違い】

貪欲法は、個々の部品を選ぶ際に「局所的」に最適なものを選び、それを積み上げて一つの解を作ります。一度選んだ部品は変更しません。
一方、山登り法は、まず一つの完成した解（例：ランダムな経路）からスタートし、その解全体を少しずつ変化させて、より良い「完成品の解」へと改善していきます。

例えるなら、カレーの具材を選ぶとき、貪欲法は「じゃがいも！」「にんじん！」と一個ずつ決めて鍋に入れていきます。山登り法は、まず適当に具材を入れてカレーを一杯作り、「このカレーからじゃがいもを抜いて、代わりにブロッコリーを入れたらもっと美味しくなるかな？」と、完成品を改良していくイメージです。

しかし、山登り法には「近くの丘（局所最適解）の頂上に着くと、そこから動けなくなり、本当に高い山（大域的最適解）にたどり着けない」という大きな弱点があります。

やってみよう！知識を固める小問題

【小問題1】貪欲法の限界

アメリカの硬貨（1, 5, 10, 25セント）で30セントを支払う場合、貪欲法（額面の大きい硬貨から使う）で支払うと、25セント+5セントの2枚が最適です。しかし、もし「20セント硬貨」が存在し、「1, 5, 10, 20, 25セント」の硬貨で40セントを支払う場合、貪欲法は最適でない解を導きます。それはどのような解で、最適解は何ですか？

【小問題2】山登り法の弱点

あなたが山の頂上を目指す登山家だとします。「常に今いる場所より高い方へしか進めない」という山登り法のルールに従うと、どのような場合に本当の山頂（最も高い場所）にたどり着けなくなりますか？

11-3: 焼きなまし法

局所解の罠から脱出する「勇気」

焼きなまし法 (Simulated Annealing, SA) は、山登り法の「丘を登りきると動けなくなる」という弱点を克服するために考案された、より強力なヒューリスティックです。

その最大の特徴は、解を改善する動きに加えて、「ある確率で、あえて改悪する手も受け入れる」という点にあります。

【山登り法との違い】

山登り法は、評価値が「良くなる」場合にしか移動しませんでした。つまり、絶対に坂道を下ることはありませんでした。
焼きなまし法は、このルールを少し緩めます。良くなる移動は常に受け入れますが、悪くなる移動（改悪）も、ある確率で許容します。

この「改悪を受け入れる確率」は、アルゴリズムの進行状況を示す「温度」というパラメータに依存します。
・探索の序盤（温度が高い）: 改悪を高い確率で受け入れる。これにより、局所最適解の丘から勇気をもって下り、別の高い山を探しに行くことができます。
・探索の終盤（温度が低い）: 改悪をほとんど受け入れなくなる。これにより、最終的に見つけた最も高い山の頂上へと、着実に登り詰めていきます。

この振る舞いが、金属を一度高温に熱してからゆっくり冷やすことで安定した構造を作る「焼きなまし」のプロセスに似ていることから、この名が付きました。

import math
import random

# (中略)
for t in range(TIME_LIMIT):
    # 近傍解を一つ生成
    new_score = ...
    
    # 常に改善する場合は採用
    if new_score > current_score:
        current_score = new_score
    else:
        # 温度に応じて、改悪を確率的に受け入れる
        # 温度は時間と共に下がる (例: temp = 30.0 * (1.0 - t / TIME_LIMIT))
        probability = math.exp((new_score - current_score) / temp)
        if random.random() < probability:
            current_score = new_score

やってみよう！知識を固める小問題

【小問題1】焼きなまし法の利点

山登り法と比較した、焼きなまし法の最大の利点は何ですか？

【小問題2】温度の役割

焼きなまし法において、「温度」が高い状態と低い状態では、アルゴリズムの振る舞いはどのように変わりますか？

11-E: 部末演習

近似解法の世界へ

第11部、お疲れ様でした！厳密解を求めるアルゴリズムとは一味違う、ヒューリスティックの世界を体験しました。特に、AtCoderのAHC(Heuristic)コンテストなどでは、この部の知識が直接スコアに結びつきます。

【演習問題1】ビームサーチ

山登り法は、常に1つの最良の解のみを保持し続けました。しかし、これでは有望そうな別の候補を捨ててしまうことになります。そこで、「常に有望な解をK個保持し続け、そのK個それぞれから近傍を探索し、次の世代の有望なK個を選ぶ」という手法が考えられます。この手法を何と呼びますか？

【演習問題2】巡回セールスマン問題の実装

平面上にN個の都市の座標 (x, y) が与えられます。全ての都市を1度ずつ訪れて出発点に戻る経路のうち、総移動距離ができるだけ短くなるような経路を一つ見つけてください。評価関数と改善操作（近傍探索）を定義し、山登り法または焼きなまし法で実装してみましょう。

import random
import math

def calculate_total_distance(tour, cities):
    dist = 0
    for i in range(len(tour)):
        city1 = cities[tour[i]]
        city2 = cities[tour[(i + 1) % len(tour)]]
        dist += math.sqrt((city1[0] - city2[0])**2 + (city1[1] - city2[1])**2)
    return dist

# (焼きなまし法のメインループは省略)
# 1. 初期解を生成 (例: random.shuffle)
# 2. 制限時間までループ
# 3.   近傍を生成 (ランダムに2点swap)
# 4.   スコアを比較し、焼きなまし法のルールに従って採用/不採用を決定
# 5.   温度を少し下げる

最終問題：Sランク & AtCoder(E)への挑戦

ついに、この長い旅の終着点が見えてきました。あなたは、基本的なプログラミングから始まり、データ構造、各種アルゴリズム、そしてヒューリスティックに至るまで、問題解決のための膨大な知識と武器を身につけました。

今のあなたなら、Paizaスキルチェックの最高峰「Sランク」や、AtCoderのコンテストで多くの人が壁と感じる「E問題」にも、臆することなく立ち向かうことができるはずです。 これらの問題は、単一のアルゴリズムを知っているだけでは解けません。

• 問題の本質を見抜き、どのアルゴリズムが使えるか考察する力
• 複数のアルゴリズムやデータ構造を組み合わせる応用力
• 制約から計算量を正確に見積もり、最適な解法を選択する判断力

これまでに学んだ全ての知識を総動員して、ぜひ挑戦してみてください。ここから先は、知識を学ぶフェーズから、知識を「どう使うか」を磨くフェーズです。数々の難問を解き明かし、本当の「問題解決能力」を手に入れる旅は、まだ始まったばかりです。

健闘を祈ります！

• 挑戦のリンク: Paiza Sランクレベルアップ問題集
• 挑戦のリンク: AtCoder 競プロ典型90問 (D問題以降に、E問題レベルの良問が多数あります)

A: Pythonicな小技集

知っていると少しだけ世界が広がるテクニック

ここでは、教科書本編で紹介しきれなかったものの、知っているとPythonでのプログラミングがもっと楽しく、効率的になる「小ネタ」を集めました。

A-1: Zen of Pythonを味わう (`import this`)

Pythonには、その設計思想や哲学をまとめた「Zen of Python」と呼ばれる19か条の詩があります。Pythonの対話モード（REPL）や、スクリプトで `import this` と実行すると、この詩を読むことができます。

import this

The Zen of Python, by Tim Peters

Beautiful is better than ugly.
Explicit is better than implicit.
Simple is better than complex.
Complex is better than complicated.
...

「醜いより美しいほうがいい」「暗黙的より明示的がいい」「複雑であるよりシンプルなほうがいい」など、簡潔で読みやすいコードを書くための指針が詰まっています。迷ったときに立ち返る原点として、心に留めておくと良いでしょう。

A-2: f-stringの便利なデバッグ術 (`f"{var=}"`)

Python 3.8以降では、f-stringの中で変数名の後に = を付けると、変数名とその値を簡単に出力できるデバッグ用の書式が追加されました。`print`デバッグが非常にはかどります。

user_name = "Taro"
user_age = 25

# 従来のf-string
print(f"user_name: {user_name}, user_age: {user_age}")

# Python 3.8+ のデバッグ術
print(f"{user_name=}, {user_age=}")
# 出力: user_name='Taro', user_age=25

A-3: `assert`でデバッグを効率化する

assert 条件式, "エラーメッセージ" は、開発中に「この変数は絶対にこの条件を満たしているはずだ」という仮定をコードに埋め込むための機能です。もし条件式が `False` になった場合、`AssertionError`を発生させてプログラムを停止させます。これにより、バグの早期発見に繋がります。

def get_discount_rate(age):
    assert age >= 0, "年齢が負の値になっています"
    # ...処理が続く
    
get_discount_rate(-10) # AssertionError: 年齢が負の値になっています

注意：`assert`は本番環境では無効化されることがあるため、ユーザー入力のバリデーションなどには使わず、あくまで開発中のデバッグ補助として使いましょう。

A-4: TruthyとFalsy ～Pythonの柔軟な真偽値判定～

Pythonでは、`if`文の条件式に真偽値(`True`/`False`)以外も使えます。空のコンテナや数値の0は`False`として、中身のあるコンテナや0以外の数値は`True`として扱われます。

• Falsy (Falseと評価される値): `None`, `False`, 数値の `0` や `0.0`, 空の文字列 `""`, 空のリスト `[]`, 空のタプル `()`, 空の辞書 `{}`, 空のセット `set()`
• Truthy (Trueと評価される値): 上記以外のほぼ全て

my_list = []
if my_list: # my_listは空なのでFalseと判定される
    print("リストには中身があります")
else:
    print("リストは空です") # こちらが表示される

この性質を利用することで、`if len(my_list) > 0:` のような冗長な記述を `if my_list:` と簡潔に書くことができます。

A-5: REPLの最終兵器 `_`

Pythonの対話型コンソール(REPL)で作業しているとき、直前の実行結果をもう一度使いたい場面がよくあります。そんな時、アンダースコア `_` を使うと、直前の式の評価結果を呼び出すことができます。

>>> 123 * 456
56088
>>> _ + 12
56100
>>> print(f"答えは {_} です")
答えは 56100 です

B: キャリアパス ～そのスキル、どう活かす？～

あなたが手にした「問題解決能力」の価値

本書を通して身につけた論理的思考力と実装力は、IT業界の様々な分野で高く評価される、非常に価値のあるスキルです。ここでは、そのスキルが具体的にどのようなキャリアに繋がるのかを紹介します。

1. ソフトウェアエンジニア

Webサービスやアプリケーションを開発する専門家です。GoogleやMetaといった巨大IT企業の採用試験では、まさに本書で学んだようなアルゴリズムとデータ構造の知識が直接問われます。なぜなら、数億人が利用するサービスのパフォーマンスは、効率的なアルゴリズムにかかっているからです。

• 活かせるスキル: 計算量を意識したAPI設計、大規模データを効率よく捌くデータ構造の選択、バグの少ないロジカルなコード実装能力。

2. データサイエンティスト / 機械学習エンジニア

膨大なデータから価値ある知見を引き出したり、AIモデルを構築したりする専門家です。数十ギガバイトにもなるデータを処理する際、非効率なコードは致命的です。計算量を意識し、高速なライブラリを使いこなす能力が求められます。

• 活かせるスキル: 大規模データの高速な前処理、アルゴリズムの思考法（モデルの内部構造の理解）、効率的なシミュレーションの実装。

3. クオンツ / 金融エンジニア

金融の世界で、数理モデルやアルゴリズムを駆使して市場分析や自動取引システムを開発する専門家です。1ミリ秒の遅れが莫大な損失に繋がる世界であり、極限まで高速化されたアルゴリズムが求められます。

• 活かせるスキル: 高速なアルゴリズムの実装力、DPやグラフ理論を用いたモデル化能力、正確無比な実装を保証する論理的思考力。

4. 競技プログラマ

問題解決の速度と正確さをスポーツのように競う人々です。本書で学んだ知識は、まさに競技プログラミングの土台そのものです。国内のAtCoderや、世界大会であるICPC、Google Code Jamなどで上位を目指すことで、その能力はさらに磨かれ、上記の専門職への道も大きく開かれます。

• 活かせるスキル: 本書で学んだ全ての知識。

C: AIへの招待 ～次の一歩へ～

アルゴリズムとAIの深い関係

現代技術の中核であるAI（人工知能）や機械学習は、一見すると全く新しい分野に見えるかもしれません。しかし、その根底には、本書で学んできた「問題を数理的にモデル化し、最適な解を探す」というアルゴリズム的思考が流れています。

思考の類似性

例えば、ヒューリスティックの章で学んだ「評価関数を定義し、その値が良くなるように解を更新していく」という山登り法や焼きなまし法の考え方は、機械学習における「損失関数を定義し、勾配降下法によってその値が最小になるようにモデルのパラメータを更新していく」というプロセスと非常によく似ています。

本書で培った「計算量を意識する感覚」や「問題を小さなタスクに分解する能力」は、AIという新しい分野を学ぶ上で、他の人にはない強力なアドバンテージになります。

次に学ぶべきPythonライブラリ

AI・データサイエンスの世界へ足を踏み入れるなら、以下の3つのライブラリは避けて通れません。本書の知識を土台に、ぜひ挑戦してみてください。

• NumPy (ナンパイ): Pythonで高速な数値計算を行うためのライブラリ。ベクトルや行列といった多次元配列を効率的に扱うことができ、科学技術計算やAI開発の基盤となっています。リスト内包表記よりさらに高速なデータ処理が可能です。
• Pandas (パンダス): Excelの表のような、行と列を持つデータを自在に操作するためのライブラリ。データの読み込み、欠損値の処理、集計、結合など、データ分析の前処理に必須のツールです。
• Scikit-learn (サイキット・ラーン): 様々な機械学習アルゴリズムを手軽に利用できるようにしたライブラリ。回帰、分類、クラスタリングといった代表的な機械学習モデルを、統一されたインターフェースで試すことができます。

D: エラー早見表 ～PythonからのSOSを読み解く～

エラーは友達、怖くない！

プログラミング学習中にエラーはつきものです。エラーメッセージはプログラムからの重要なヒント。意味を正しく理解し、迅速にバグを修正できるようになりましょう。

E: バグとの戦い方 ～デバッグの心構え～

探偵のように、バグを追い詰めろ

エラーは出ないのに、なぜかプログラムが思った通りに動かない。「バグ」との戦いはプログラマの宿命です。ここでは、バグを効率的に発見し、修正するための基本的な考え方とテクニック（デバッグ手法）を解説します。

1. `print`デバッグ

最も原始的で、しかし最も強力なデバッグ手法です。怪しい箇所の前後やループの内部にprint文を仕込み、変数の値が意図通りに変化しているか、あるいは特定の処理ブロックが実行されているかを確認します。

total = 0
for i in range(1, 6):
    print(f"ループ開始時: i={i}, total={total}") # printデバッグ
    total += i
    print(f"ループ終了時: i={i}, total={total}") # printデバッグ

2. 具体例で考える（手でデバッグ）

「N=100だと分からないが、N=3ならどう動く？」というように、問題を極端に小さくした入力例を考え、その動きを紙と鉛筆でステップごとに手で追ってみます。これにより、自分の思考の前提がどこで間違っているのかを発見しやすくなります。特に、N=0, 1のような境界値（コーナーケース）を試すことは非常に重要です。

3. 二分探索的デバッグ

バグがどこに潜んでいるか見当もつかない場合、コードの後半半分をコメントアウトして実行してみます。もし、それでもバグが再現するなら、バグは前半部分にあります。再現しないなら、後半部分です。このようにして、バグの潜む範囲を半分に狭めていくアプローチは非常に有効です。

4. ラバーダッキング (Rubber Ducky Debugging)

少し変わった、しかし驚くほど効果的な手法です。机の上にアヒルのおもちゃ（ラバーダック）を置き、そのアヒルに向かって、自分のコードが何をしているのかを一行ずつ、丁寧に声に出して説明します。「まず、この変数Nでループを回して…」と説明しているうちに、「あれ、ここはNじゃなくてN-1までじゃないか？」というように、自分の思考の矛盾や思い込みに気づくことができます。説明する相手は、同僚や友人、あるいは壁でも構いません。