クルトンのプログラミング教室

Pythonの使い方やPythonを使った競技プログラミングの解法などを解説しています。

Pythonで理解する蟻本(プログラミングコンテストチャレンジブック)

 

この記事のコンセプト

プログラミングコンテストチャレンジブック(以下蟻本)は競技プログラミングの参考書として圧倒的な知名度を誇っており、まさに競技プログラマーにとっての必需品といえます。

その一方で、蟻本のコードはすべてC++で書かれており、Python競技プログラミングをしている人にとってはコードの理解が困難になっています。

蟻本を理解するためにC++を学ぶのも一つの手ではありますが、それだけで多大な労力が必要となってしまいます。

そこでこの記事では、Pythonコーダーが蟻本を理解する際の補助となるように、蟻本のコードをできるだけ忠実にPythonで書き直したものを記載しようと思います。

この記事が、Pythonコーダーが蟻本を理解する一助となれば幸いです。


Pythonで理解する蟻本「2-3 lower_bound」(p.65)

この記事は「プログラミングコンテストチャレンジブック第2版」(蟻本)の
「2-3 lower_bound」(p.65)
のコードをPythonで書き直したものとなっています。

bisectモジュール

二分探索をする際にPythonではbisectモジュールを使用します。

lower_boundにはbisectモジュールのbisect_left関数が、upper_boundにはbisectモジュールのbisect_right関数が対応しています。

コラムのコード

# bisect_left関数、bisect_right関数をインポートする
from bisect import bisect_left, bisect_right

bisect_right(a, k) - bisect_left(a, k)

Pythonで理解する蟻本「2-3 最長増加部分列問題」(p.63)

この記事は「プログラミングコンテストチャレンジブック第2版」(蟻本)の
「2-3 最長増加部分列問題」(p.63)
のコードをPythonで書き直したものとなっています。

入力

n\\a_1\,…\,a_n

入力例



5
4 2 3 1 5


解答

O(n^2)の解法

MAX_N = 1000

# 入力
n = int(input())
a = list(map(int,input().split()))

dp = [0] * MAX_N    # DPテーブル
res = 0
for i in range(n):
    dp[i] = 1
    for j in range(i):
        if a[j] < a[i]:
            dp[i] = max(dp[i], dp[j] + 1)
        res = max(res, dp[i])
print(res)

O(n log n)の解法

MAX_N = 1000
INF = float('inf')

# 二分探索するためにbisect_left関数をインポートする
from bisect import bisect_left

# 入力
n = int(input())
a = list(map(int,input().split()))

dp = [INF] * MAX_N    # DPテーブル

for i in range(n):
    dp[bisect_left(dp, a[i])] = a[i]
print(bisect_left(dp, INF))

Pythonで理解する蟻本「2-3 個数制限付き部分和問題」(p.62)

この記事は「プログラミングコンテストチャレンジブック第2版」(蟻本)の
「2-3 個数制限付き部分和問題」(p.62)
のコードをPythonで書き直したものとなっています。

入力

n\\K\\a_1\,a_n\\m_1\,…\,m_n

入力例



3
17
3 5 8
3 2 2


解答

bool値を求めるDP(O(Σmi))

MAX_N = 100
MAX_K = 100000

# 入力
n = int(input())    # 列の長さ
K = int(input())    # 作りたい数
a = list(map(int,input().split()))    # 値
m = list(map(int,input().split()))    # 個数

dp = [[False] * (MAX_K + 1) for _ in range(MAX_N + 1)]    # DPテーブル

dp[0][0] = True
for i in range(n):
    for j in range(K + 1):
        k = 0
        while k <= m[i] and k * a[i] <= j:
            dp[i + 1][j] |= dp[i][j - k * a[i]]
            k += 1
if dp[n][K]:
    print("Yes")
else:
    print("No")

情報量の多いDP(O(nK))

MAX_N = 100
MAX_K = 100000

# 入力
n = int(input())    # 列の長さ
K = int(input())    # 作りたい数
a = list(map(int,input().split()))    # 値
m = list(map(int,input().split()))    # 個数

dp = [-1] * (MAX_K + 1)    # DPテーブル

dp[0] = 0
for i in range(n):
    for j in range(K + 1):
        if dp[j] >= 0:
            dp[j] = m[i]
        elif j < a[i] or dp[j - a[i]] <= 0:
            dp[j] = -1
        else:
            dp[j] = dp[j - a[i]] - 1
if dp[K] >= 0:
    print("Yes")
else:
    print("No")

Pythonで理解する蟻本「2-3 01 ナップサック問題その2」(p.60)

この記事は「プログラミングコンテストチャレンジブック第2版」(蟻本)の
「2-3 01 ナップサック問題その2」(p.60)
のコードをPythonで書き直したものとなっています。

入力

n\,W\\w_1\,…\,w_n\\v_1\,…\,v_n

入力例



4 5
2 1 3 2
3 2 4 2


解答

# 入力
n, W = map(int,input().split())
w = list(map(int,input().split()))
v = list(map(int,input().split()))

MAX_N = 100
MAX_V = 100
INF = float('inf')

dp = [[INF] * (MAX_N * MAX_V + 1) for _ in range(MAX_N + 1)]    # DPテーブル
dp[0][0] = 0

for i in range(n):
    for j in range(MAX_N * MAX_V + 1):
        if j < v[i]:
            dp[i + 1][j] = dp[i][j]
        else:
            dp[i + 1][j] = min(dp[i][j], dp[i][j - v[i]] + w[i])
    res = 0
    for i in range(MAX_N * MAX_V + 1):
        if dp[n][i] <= W:
            res = i
print(res)

Pythonで理解する蟻本「2-3 個数制限なしナップサック問題」(p.58)

この記事は「プログラミングコンテストチャレンジブック第2版」(蟻本)の
「2-3 個数制限なしナップサック問題」(p.58)
のコードをPythonで書き直したものとなっています。

入力

n\,W\\w_1\,…\,w_n\\v_1\,…\,v_n

入力例



3 7
3 4 2
4 5 3


解答

三重ループによる解法(O(nW^2))

MAX_N = 100
MAX_W = 10000

# 入力
n, W = map(int,input().split())
w = list(map(int,input().split()))
v = list(map(int,input().split()))

dp = [[0] * (MAX_W + 1) for _ in range(MAX_N + 1)]    # DPテーブル

for i in range(n):
    for j in range(W + 1):
        k = 0
        while k * w[i] <= j:
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - k * w[i]] + k * v[i])
            k += 1
print(dp[n][W])

二重ループによる解法(O(nW))

MAX_N = 100
MAX_W = 10000

# 入力
n, W = map(int,input().split())
w = list(map(int,input().split()))
v = list(map(int,input().split()))

dp = [[0] * (MAX_W + 1) for _ in range(MAX_N + 1)]    # DPテーブル

for i in range(n):
    for j in range(W + 1):
        if j < w[i]:
            dp[i + 1][j] = dp[i][j]
        else:
            dp[i + 1][j] = max(dp[i][j], dp[i + 1][j - w[i]] + v[i])
print(dp[n][W])

同じ配列を再利用した解法(O(nW))

01ナップサック問題の場合
# 入力
n, W = map(int,input().split())
w = list(map(int,input().split()))
v = list(map(int,input().split()))

MAX_N = 100
MAX_W = 10000
dp = [[0] * (MAX_W + 1) for _ in range(MAX_N + 1)]    # dpテーブル

for i in range(n - 1, -1, -1):
    for j in range(W + 1):
        if j < w[i]:
            dp[i][j] = dp[i + 1][j]
        else:
            dp[i][j] = max(dp[i + 1][j], dp[i + 1][j - w[i]] + v[i])
print(dp[0][W])

iに関するループの向きを順方向に直した動的計画法(O(nW))

# 入力
n, W = map(int,input().split())
w = list(map(int,input().split()))
v = list(map(int,input().split()))

MAX_N = 100
MAX_W = 10000
dp = [[0] * (MAX_W + 1) for _ in range(MAX_N + 1)]    # dpテーブル

for i in range(n):
    for j in range(W + 1):
        if j < w[i]:
            dp[i + 1][j] = dp[i][j]
        else:
            dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i])
print(dp[n][W])
01ナップサック問題の場合
MAX_N = 100
MAX_W = 10000

# 入力
n, W = map(int,input().split())
w = list(map(int,input().split()))
v = list(map(int,input().split()))

dp = [0] * (MAX_W + 1)    # DPテーブル

for i in range(n):
    for j in range(W, w[i] - 1, -1):
        dp[j] = max(dp[j], dp[j - w[i]] + v[i])
print(dp[W])
個数制限なしナップサック問題の場合
MAX_N = 100
MAX_W = 10000

# 入力
n, W = map(int,input().split())
w = list(map(int,input().split()))
v = list(map(int,input().split()))

dp = [0] * (MAX_W + 1)    # DPテーブル

for i in range(n):
    for j in range(w[i], W + 1):
        dp[j] = max(dp[j], dp[j - w[i]] + v[i])
print(dp[W])

Pythonで理解する蟻本「2-3 最長共通部分列問題」(p.56)

この記事は「プログラミングコンテストチャレンジブック第2版」(蟻本)の
「2-3 最長共通部分列問題」(p.56)
のコードをPythonで書き直したものとなっています。

入力

n\,m\\s\\t

入力例



4 4
abcd
becd


解答

MAX_N = 1000
MAX_M = 1000

# 入力
n, m = map(int,input().split())
s = input()
t = input()

dp = [[0] * (MAX_M + 1) for _ in range(MAX_N + 1)]    # DPテーブル

for i in range(n):
    for j in range(m):
        if s[i] == t[j]:
            dp[i + 1][j + 1] = dp[i][j] + 1
        else:
            dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
print(dp[n][m])

Pythonで理解する蟻本「2-3 01 ナップサック問題」(p.52)

この記事は「プログラミングコンテストチャレンジブック第2版」(蟻本)の
「2-3 01 ナップサック問題」(p.52)
のコードをPythonで書き直したものとなっています。

入力

n\,W\\w_1\,…\,w_n\\v_1\,…\,v_n

入力例



4 5
2 1 3 2
3 2 4 2


解答

再帰による愚直解(O(2^N))

# 入力
n, W = map(int,input().split())
w = list(map(int,input().split()))
v = list(map(int,input().split()))

# i番目以降の品物から重さの総和がj以下となるように選ぶ
def rec(i, j):
    if i == n:
        # もう品物は残っていない
        res = 0
    elif j < w[i]:
        # この品物は入らない
        res = rec(i + 1, j)
    else:
        # 入れない場合と入れる場合を両方試す
        res = max(rec(i + 1, j), rec(i + 1, j - w[i]) + v[i])
    return res

print(rec(0, W))

メモ化再帰(O(nW))

# 入力
n, W = map(int,input().split())
w = list(map(int,input().split()))
v = list(map(int,input().split()))

MAX_N = 100
MAX_W = 10000
dp = [[-1] * (MAX_W + 1) for _ in range(MAX_N + 1)]    # メモ化テーブル

def rec(i, j):
    if dp[i][j] >= 0:
        # すでに調べたことがあるならばその結果を再利用
        return dp[i][j]
    if i == n:
        res = 0
    elif j < w[i]:
        res = rec(i + 1, j)
    else:
        res = max(rec(i + 1, j), rec(i + 1, j - w[i]) + v[i])
    # 結果をテーブルに記憶する
    dp[i][j] = res
    return res

print(rec(0, W))

動的計画法(DP)(O(nW))

# 入力
n, W = map(int,input().split())
w = list(map(int,input().split()))
v = list(map(int,input().split()))

MAX_N = 100
MAX_W = 10000
dp = [[0] * (MAX_W + 1) for _ in range(MAX_N + 1)]    # dpテーブル

for i in range(n - 1, -1, -1):
    for j in range(W + 1):
        if j < w[i]:
            dp[i][j] = dp[i + 1][j]
        else:
            dp[i][j] = max(dp[i + 1][j], dp[i + 1][j - w[i]] + v[i])
print(dp[0][W])

iに関するループの向きを順方向に直した動的計画法(O(nW))

# 入力
n, W = map(int,input().split())
w = list(map(int,input().split()))
v = list(map(int,input().split()))

MAX_N = 100
MAX_W = 10000
dp = [[0] * (MAX_W + 1) for _ in range(MAX_N + 1)]    # dpテーブル

for i in range(n):
    for j in range(W + 1):
        if j < w[i]:
            dp[i + 1][j] = dp[i][j]
        else:
            dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i])
print(dp[n][W])

p.56の解法(O(nW))

# 入力
n, W = map(int,input().split())
w = list(map(int,input().split()))
v = list(map(int,input().split()))

MAX_N = 100
MAX_W = 10000
dp = [[0] * (MAX_W + 1) for _ in range(MAX_N + 1)]    # dpテーブル

for i in range(n):
    for j in range(W + 1):
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
        if j + w[i] <= W:
            dp[i + 1][j + w[i]] = max(dp[i + 1][j + w[i]], dp[i][j] + v[i])
print(dp[n][W])