Pythonで理解する蟻本「2-2 Fence Repair（POJ 3253）」(p.49)
この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の
「2-2 Fence Repair（POJ 3253）」(p.49)
のコードをPythonで書き直したものとなっています。
入力
入力例
3
8 5 8
解答
# 入力
N = int(input())
L = list(map(int,input().split()))
ans = 0
# 坂が1本になるまで適用
while N > 1:
# 一番短い板mii1、次に短い板mii2を求める
mii1 = 0
mii2 = 1
if L[mii1] > L[mii2]:
mii1, mii2 = mii2, mii1
for i in range(2, N):
if L[i] < L[mii1]:
mii2 = mii1
mii = i
elif L[i] < L[mii2]:
mii2 = i
# それらを併合
t = L[mii1] + L[mii2]
ans += t
if mii1 == N - 1:
mii1, mii2 = mii2, mii1
L[mii1] = t
L[mii2] = L[N - 1]
N -= 1
print(ans)
で解く別解についても説明しようと思ったのですが、どうやら2-4で説明されているようなのでそこで解説しようと思います。
Pythonで理解する蟻本「2-2 Saruman's Army（POJ 3069）」(p.47)
この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の
「2-2 Saruman's Army（POJ 3069）」(p.47)
のコードをPythonで書き直したものとなっています。
入力
入力例
6 10
1 7 15 20 30 50
解答
N, R = map(int,input().split())
X = list(map(int,input().split()))
X.sort()
i = 0
ans = 0
while i < N:
# sはカバーされていない一番左の点の位置
s = X[i]
i += 1
# sから距離Rを超える点まで進む
while i < N and X[i] <= s + R:
i += 1
# pは新しく印を付ける点の位置
p = X[i - 1]
# pから距離Rを超える点まで進む
while i < N and X[i] <= p + R:
i += 1
ans += 1
print(ans)
Pythonで理解する蟻本「2-2 Best Cow Line（POJ 3617）」(p.45)
この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の
「2-2 Best Cow Line（POJ 3617）」(p.45)
のコードをPythonで書き直したものとなっています。
入力
入力例
蟻本ではputcharで一文字ずつ出力していますが、Pythonで出力するための標準関数であるprintは出力の際に自動的に改行が挟まれてしまいます。 そのため、下のコードでは文字列Tに文字を追加していき、最後に文字列Tを出力しています。
6
ACDBCB
解答
# 入力
N = int(input())
S = input()
# S[a], S[a+1], ..., S[b]が残っている文字列
a = 0
b = N - 1
T = '' # 文字列T
while a <= b:
# 左からみた場合と右から見た場合を比較
left = False
for i in range(b - a + 1): # 0 <= i <= b - a
if S[a + i] < S[b - i]:
left = True
break
elif S[a + i] > S[b - i]:
left = False
break
# 文字列Tに文字を追加する
if left:
T += S[a]
a += 1
else:
T += S[b]
b -= 1
print(T)
Pythonで理解する蟻本「2-2 区間スケジューリング問題」(p.43)
この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の
「2-2 区間スケジューリング問題」(p.43)
のコードをPythonで書き直したものとなっています。
入力
入力例
5
1 2 4 6 8
3 5 7 9 10
解答
MAX_N = 100000
# 入力
N = int(input())
S = list(map(int,input().split()))
T = list(map(int,input().split()))
# 仕事をソートするための配列itv
itv = []
# 終了時間の早い順にしたいため、Tを配列の一つ目に、Sを二つ目に入れる
for i in range(N):
itv.append([T[i], S[i]])
itv.sort()
# tは最後に選んだ仕事の終了時間
ans = 0
t = 0
for i in range(N):
if t < itv[i][1]:
ans += 1
t = itv[i][0]
print(ans)
Pythonで理解する蟻本「2-2 硬貨の問題」(p.42)
この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の
「2-2 硬貨の問題」(p.42)
のコードをPythonで書き直したものとなっています。
入力
入力例
3 2 1 3 0 2
620
解答
# コインの金額
V = [1, 5, 10, 50, 100, 500]
# 入力
C = list(map(int,input().split())) # C[0] = C_1, C[1] = C_5, ...
A = int(input())
ans = 0
for i in range(5, -1, -1):
t = min(A // V[i], C[i]) # コインiを使う枚数
A -= t * V[i]
ans += t
print(ans)
Pythonで理解する蟻本「2-1 特殊な状態の列挙」(p.39)
この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の
「2-1 特殊な状態の列挙」(p.39)
のコードをPythonで書き直したものとなっています。
PythonとC++の違い
C++ではnext_permutationという関数を使って順列を生成していますが、Pythonではitertoolsモジュールのpermutations関数を使うことで順列を要素としたイテレータを生成できます。
Pythonで組み合わせを扱いたいときは、とりあえずitertoolsを使うことを考えてみるとよいでしょう。
コード
MAX_N = 10 ** 8 used = [0] * MAX_N perm = [0] * MAX_N # {0,1,2,3,4, ... ,n - 1}の並び替えn!通りを生成する def permutation1(pos, n): if pos == n: ''' permに対する操作 ''' return # permのpos番目を0～n-1のどれにするかのループ for i in range(n): if not used[i]: perm[pos] = i # iを使ったのでフラグをTrueにしておく used[i] = True permutation1(pos + 1, n) # 戻ってきたらフラグを戻しておく used[i] = False return from itertools import permutations def permutation2(n): perm2 = list(range(n)) for tmp_perm in permutations(perm2, n): ''' tmp_permに対する操作 ''' return
具体的な実行例も下に載せておきます。
実行例
サンプルコード
MAX_N = 10 ** 8 used = [0] * MAX_N perm = [0] * MAX_N # {0,1,2,3,4, ... ,n - 1}の並び替えn!通りを生成する def permutation1(pos, n): if pos == n: print(perm[:n]) return # permのpos番目を0～n-1のどれにするかのループ for i in range(n): if not used[i]: perm[pos] = i # iを使ったのでフラグをTrueにしておく used[i] = True permutation1(pos + 1, n) # 戻ってきたらフラグを戻しておく used[i] = False return from itertools import permutations def permutation2(n): perm2 = list(range(n)) for tmp_perm in permutations(perm2, n): print(tmp_perm) return permutation1(0, 3) print() permutation2(3)
実行結果
[0, 1, 2] [0, 2, 1] [1, 0, 2] [1, 2, 0] [2, 0, 1] [2, 1, 0] (0, 1, 2) (0, 2, 1) (1, 0, 2) (1, 2, 0) (2, 0, 1) (2, 1, 0)
Pythonで理解する蟻本「2-1 Lake Counting（POJ No.2386）」(p.35)
この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の
「2-1 Lake Counting（POJ No.2386）」(p.35)
のコードをPythonで書き直したものとなっています。
入力
入力例
10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.
解答
# 入力
N, M = map(int,input().split())
field = [list(input()) for _ in range(N)] # 庭
# 現在位置(x,y)
def dfs(x, y):
# 今いるところを.に置き換える
field[x][y] = '.'
# 移動する8方向をループ
for dx in range(-1, 2):
for dy in range(-1, 2):
# x方向にdx y方向にdy 移動した場所を(nx, ny)とする
nx = x + dx
ny = y + dy
# nxとnyが庭の範囲内かどうかとfield[nx][ny]が水溜りかどうかを判定
if 0 <= nx < N and 0 <= ny < M and field[nx][ny] == 'W':
dfs(nx, ny)
return
res = 0
for i in range(N):
for j in range(M):
if field[i][j] == 'W':
# Wが残っているならそこからdfsをはじめる
dfs(i, j)
res += 1
print(res)
