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

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

Pythonで理解する蟻本「3-1 平均最大化」(p.132)

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

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

入力


n\,k\\w_1\,v_1\\:\\w_n\,v_n

入力例



3 2
2 2
5 3
2 1


解答

INF = 10 ** 6 + 1

# 入力
n, k = map(int,input().split())
w = [None] * n
v = [None] * n
for i in range(n):
    w[i], v[i] = map(int,input().split())

y = [None] * n    # v - x * w

# 条件を満たすか判定
def C(x):
    for i in range(n):
        y[i] = v[i] - x * w[i]
    y.sort()
    
    # yの大きいほうからk個の和を計算
    sum = 0
    for i in range(k):
        sum += y[n - i - 1]
    
    return sum >= 0

lb = 0
ub = INF
for i in range(100):
    mid = (lb + ub) / 2
    if C(mid):
        lb = mid
    else:
        ub = mid
    
print(ub)

Pythonで理解する蟻本「3-1 Aggressive cows（POJ No.2456）」(p.131)

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

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

入力


N\,M\\x_1\,…\,x_N

入力例



5 3
1 2 8 4 9


解答

INF = 10 ** 9 + 1

# 入力
N, M = map(int,input().split())
x = list(map(int,input().split()))

# 条件を満たすか判定
def C(d):
    last = 0
    for i in range(1, M):
        crt = last + 1
        while crt < N and x[crt] - x[last] < d:
            crt += 1
        if crt == N:
            return False
        last = crt
    return True

# はじめにxをソートしておく
x.sort()

# 解の存在範囲を初期化
lb = 0
ub = INF

while ub - lb > 1:
    mid = (lb + ub) // 2
    if C(mid):
        lb = mid
    else:
        ub = mid

print(lb)

Pythonで理解する蟻本「3-1 Cable master（POJ No.1064）」(p.129)

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

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

入力


N\,K\\L_1\,…\,L_N

入力例



4 11
8.02 7.43 4.57 5.39


解答

import math

INF = 10 ** 5 + 1

# 入力

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

# 条件を満たすか判定
def C(x):
    num = 0
    for i in range(N):
        num += L[i] // x
    return num >= K

# 解の存在範囲を初期化
lb = 0
ub = INF

# 解の存在範囲が十分狭くなるまで繰り返す
for i in range(100):
    mid = (lb + ub) / 2
    if C(mid):
        lb = mid
    else:
        ub = mid

print(math.floor(ub * 100) / 100)

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

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

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

入力


n\,k\\a_0\,…\,a_{n-1}

入力例



5 3
2 3 3 5 6


蟻本のコード

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

# 解の存在範囲を初期化
lb = -1
ub = n

# 解の存在範囲が1より大きい間、繰り返す
while ub - lb > 1:
    mid = (lb + ub) // 2
    if a[mid] >= k:
        # midが条件を満たせば、解の存在範囲は(lb, mid]
        ub = mid
    else:
        # midが条件を満たさなければ、解の存在範囲は(mid, ub]
        lb = mid

# この時点で、lb + 1 = ubとなっている
print(ub)

bisect_leftを使ったコード


Pythonにはbisect_leftという関数として、bisectモジュールに含まれています。

from bisect import bisect_left

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

i = bisect_left(a, k)
print(i)

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

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

この記事は「プログラミングコンテストチャレンジブック第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)

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

この記事は「プログラミングコンテストチャレンジブック第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)

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

この記事は「プログラミングコンテストチャレンジブック第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)