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

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

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

 

この記事のコンセプト

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

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

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

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

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


記事一覧

1 いざチャレンジ!でもその前に―準備編

1-6 気楽にウォーミングアップ

kuruton.hatenablog.com

kuruton.hatenablog.com

Pythonで理解する蟻本「2-7 Millionaire(2008 APAC local onsites C)」(p.123)

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

入力


M\,X\\P

入力例1



1 500000
0.5

入力例2



3 600000
0.75


解答

MAX_M = 15

# 入力
M, X = map(int,input().split())
P = float(input())

dp = [[0] * ((1 << MAX_M) + 1) for _ in range(2)]

n = 1 << M

prv = dp[0]
nxt = dp[1]
prv[n] = 1

for r in range(M):
    for i in range(n + 1):
        jub = min(i, n - i)
        t = 0
        for j in range(jub + 1):
            t = max(t, P * prv[i + j] + (1 - P) * prv[i - j])
        nxt[i] = t
    prv, nxt = nxt, prv

i = X * n // 1000000
print(prv[i])

Pythonで理解する蟻本「2-7 Bribe the Prisoners(2009 Round 1C C)」(p.121)

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

入力


P\,Q\\A_1\,…\,A_Q

入力例1



8 1
3

入力例2



20 3
3 6 14


解答

MAX_Q = 100
INF = float('inf')

# 入力
P, Q = map(int,input().split())
A = [None] * (MAX_Q)
A[1:Q+1] = list(map(int,input().split()))    # Aには1-indexedでデータが入っている

# dp[i][j] := (i, j)を解放するのに必要な金貨
dp = [[None] * (MAX_Q + 2) for _ in range(MAX_Q + 1)]

# 簡単のため、端をAに追加する
A[0] = 0
A[Q + 1] = P + 1

# 初期化
for q in range(Q + 1):
    dp[q][q + 1] = 0

# 幅が小さい順にdpを埋めていく
for w in range(2, Q + 2):
    for i in range(Q - w + 2):
        # dp[i][j]を計算する
        j = i + w
        t = INF
        
        # 最初に解放する囚人をすべて試し、最小のコストのものを探す
        for k in range(i + 1, j):
            t = min(t, dp[i][k] + dp[k][j])
        
        # 最初の解放では解放する囚人に関わらずA[j] - A{i} - 2の金貨が必要
        dp[i][j] = t + A[j] - A[i] - 2
    
print(dp[0][Q + 1])

Pythonで理解する蟻本「2-7 Crazy Rows(2009 Round2 A)」(p.119)

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

入力


N\\M_{(1,1)}M_{(1,2)}\,…\,M_{(1,N)}\\M_{(2,1)}M_{(2,2)}\,…\,M_{(2,N)}\\:\\M_{(N,1)}M_{(N,2)}\,…\,M_{(N,N)}

入力例1



2
10
11

入力例2



3
001
100
010

入力例3



4
1110
1100
1100
1000


解答

MAX_N = 40

# 入力
N = int(input())
M = [list(map(int,list(input()))) for _ in range(N)]    # 行列

a = [-1] * MAX_N    # a[i]はi行目の最後に現れる1の位置-1~N-1

res = 0
for i in range(N):
    a[i] = -1    # i行目に1がない場合は-1にしておく
    for j in range(N):
        if M[i][j] == 1:
            a[i] = j

for i in range(N):
    pos = -1    # i行目に移動する行
    for j in range(i, N):
        if a[j] <= i:
            pos = j
            break
    
    # 実際にスワップする
    for j in range(pos, i, -1):
        a[j], a[j-1] = a[j-1], a[j]
        res += 1
    
print(res)

Pythonで理解する蟻本「2-7 Minimum Scalar Product(2008 Round1A A)」(p.117)

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

入力


n\\x_1\,…\,x_n\\y_1\,…\,y_n

入力例1



3
1 3 -5
-2 4 1

入力例2



5
1 2 3 4 5
1 0 1 0 1


解答

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

v1.sort()
v2.sort()
ans = 0
for i in range(n):
    ans += v1[i] * v2[n - i - 1]
print(ans)

Pythonで理解する蟻本「2-6 Carmichael Numbers(UVa No.10006)」(p.114)

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

入力


n

入力例1



17

入力例2



561

入力例3



4


2のべき乗の和として表す方法

def mod_pow(x, n, mod):
    res = 1
    while n > 0:
        if n & 1:
            res = res * x % mod    # 最下位ビットが立っているときにx^(2^i)を掛ける
        x = x * x % mod        # xを順次二乗していく
        n >>= 1
    return res

再帰関数を使う方法

def mod_pow(x, n, mod):
    if n == 0:
        return 1
    res = mod_pow(x * x % mod, n // 2, mod)
    if n & 1:
        res = res * x % mod
    return res

組み込み関数powを使う方法(重要!)

実は、pythonにはO(log n)でべき乗の計算を行うことができる、pow関数が存在します。

この関数は組み込み関数であるため、インポートせずに使うことができます。

競技プログラミングでべき乗を計算する際には、迷わずこのpow関数を使いましょう。

pow(x, n, mod)

解答

import sys

# 入力
n = int(input())

# 素数判定O(√n)
def is_prime(n):
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return n != 1    # 1の場合は例外

if is_prime(n):
    print('No')
    sys.exit()    # nが素数であれば、'No'を出力してプログラムを終了する

for x in range(2, n):
    if pow(x, n, n) != x:
        print('No')
        sys.exit()    # x^n≡x(mod n) が成り立たないようなxが存在すれば、'No'を出力してプログラムを終了する

print('Yes')

Pythonで理解する蟻本「2-6 区間内の素数の個数」(p.113)

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

入力


a\,b

入力例



22801763489 22801787297

解答

MAX_L = 10 ** 6
MAX_SQRT_B = 10 ** 6

is_prime = [True] * MAX_L
is_prime_small = [True] * MAX_SQRT_B

# [a,b)の整数に対して篩を行う。is_prime[i - a] = True ⇔ iが素数
def segment_sieve(a, b):
    i = 0
    while i * i < b:
        is_prime_small[i] = True
        i += 1
    i = 0
    for i in range(b - a):
        is_prime[i] = True
    
    i = 2
    while i * i < b:
        if is_prime_small[i]:
            j = 2 * i
            while j * j < b:
                is_prime_small[j] = False    # [2,√b)の篩
                j += i
            j = (a + i - 1) // i * i
            while j < b:
                is_prime[j - a] = False    # [a,b)の篩
                j += i
        i += 1

a, b = map(int,input().split())
segment_sieve(a, b)
ans = sum(is_prime[:b - a])
print(ans)

Pythonで理解する蟻本「2-6 素数の個数」(p.111)

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

入力


n

入力例1



11

入力例2



1000000


解答

MAX_N = 10 ** 6

prime = [None] * MAX_N    # i番目の素数
is_prime = [True] * (MAX_N + 1)    # is_prime[i]がTrueならiは素数

# n以下の素数の数を返す
def sieve(n):
    p = 0
    for i in range(n + 1):
        is_prime[i] = True
    is_prime[0] = is_prime[1] = False
    for i in range(2, n + 1):
        if is_prime[i]:
            prime[p] = i
            p += 1
            for j in range(2 * i, n + 1, i):
                is_prime[j] = False
    return p

n = int(input())
ans = sieve(n)
print(ans)