マイナビのプログラミングコンテスト チャレンジブックでアルゴリズムを勉強中！
この本はC++でコードが書かれているので、勉強がてらPython3で書き直した時のメモ。
こちらの本とは微妙にアルゴリズムが違っている場合もあるかもしれないですが、悪しからず。
この本はとても勉強になるし、面白いのでぜひ読みましょう！(マイナビのまわし者ですww)
プログラミングコンテスト・チャレンジブック P24
# coding: utf-8
# Your code here!
#入力
L = 10
n = 3
list = [2,6,7]
def func():
minTime = 0
for i in range(0,n):
minTime = max(minTime,min(list[i],L -list[i]))
maxTime = 0
for i in range(0,n):
maxTime = max(maxTime,max(list[i],L -list[i]))
print(maxTime,minTime)
func()
プログラミングコンテスト・チャレンジブック P26
本に書かれているコードの”l”と”1″のフォントがそっくりで、かなり迷ってしまった..２分探索を使用したアルゴリズム。
# coding: utf-8
# Your code here!
#入力
n = 5
m = 9
list = [3,0,5,5,5]
def binary_search(x):
#xの存在し得る範囲はlist[l].list[l + 1],....list[r - 1]
l = 0
r = n
while r - l >= 1:
i = (l + r) / 2
i = int(i)
if list[i] == x:
return True
else:
if list[i] < x:#xは後ろ半分の中にある
l = i + 1
else:#xは前半分のなかににある
r = i
return False
def solve():
#２分探索を行うためにソート
list.sort()
f = False
for a in range(0,n):
for b in range(0,n):
for c in range(0,n):
if binary_search(m - list[a] - list[b] - list[c]):
f = True
if f == True:
print("Yes")
else:
print("No")
solve()
プログラミングコンテスト・チャレンジブック P30 階乗
n! ←nの階乗と言う意味。例えば３の階乗は3*2*1。1の階乗は1と定義されている。
関数の中でその関数を使用する再帰関数を使って階乗を計算する関数↓
# coding: utf-8
# Your code here!
def factorial(n):
if n == 1:return 1
return n*factorial(n-1)
print(factorial(10))
#3628800と出力
プログラミングコンテスト・チャレンジブック P30 フィボナッチ数列
※nが大きいとエラーが出る
def fibonacci(n):
if n <= 1:return n
return fibonacci(n-1) + fibonacci(n -2)
print(fibonacci())
プログラミングコンテスト・チャレンジブック P31 フィボナッチ数列 メモ探索
上記のコードより多少高速処理になるメモ探索。
※nが大きいとエラーが出る
# coding: utf-8
# Your code here!
memo = {}
def fibonacci(n):
if n <= 1: return n
if n not in memo:
memo[n] = fibonacci(n-1) + fibonacci(n-2)
return memo[n]
print(fibonacci(10))
#55と出力
プログラミングコンテスト・チャレンジブック P36 深さ優先探索
# coding: utf-8
# Your code here!
N = 10
M = 12
#空のフィールド(庭)を作成
field = []
for i in range(N):
field.append(i)
field[0] = ["W",".",".",".",".",".",".",".",".","W","W","."]
field[1] = [".","W","W","W",".",".",".",".",".","W","W","W"]
field[2] = [".",".",".",".","W","W",".",".",".","W","W","."]
field[3] = [".",".",".",".",".",".",".",".",".","W","W","."]
field[4] = [".",".",".",".",".",".",".",".",".","W",".","."]
field[5] = [".",".","W",".",".",".",".",".",".","W",".","."]
field[6] = [".","W",".","W",".",".",".",".",".","W","W","."]
field[7] = ["W",".","W",".","W",".",".",".",".",".","W","."]
field[8] = [".","W",".","W",".",".",".",".",".",".","W","."]
field[9] = [".",".","W",".",".",".",".",".",".",".","W","."]
def dfs(x,y):
if field[x][y] == "W":field[x][y] = "."
for dx in range(-1,2):
for dy in range(-1,2):
nx = x + dx
ny = y + dy
if 0 <= nx and nx < N and 0 <= ny and ny < M and field[nx][ny] == "W":dfs(nx,ny)
return
def solve():
res = 0
for i in range(N):
for j in range(M):
if field[i][j] == "W":
dfs(i,j)
res += 1
print(res)
#実行
solve()
#3と出力
プログラミングコンテスト・チャレンジブック P38 幅優先探索
# coding: utf-8
# Your code here!
N = 10
M = 10
INF = 100000000
#スタートの座標
sx = 0
sy = 1
#ゴールの座標
gx = 9
gy = 8
#各点までの最短距離の辞書
d = {}
for i in range(N):
d[i] = {}
#空のフィールド(庭)を作成
maze = []
for i in range(N):
maze.append(i)
#空のキューを作成
que = []
maze[0] = ["#","S","#","#","#","#","#","#",".","#"]
maze[1] = [".",".",".",".",".",".","#",".",".","#"]
maze[2] = [".","#",".","#","#",".","#","#",".","#"]
maze[3] = [".","#",".",".",".",".",".",".",".","."]
maze[4] = ["#","#",".","#","#",".","#","#","#","#"]
maze[5] = [".",".",".",".","#",".",".",".",".","#"]
maze[6] = [".","#","#","#","#","#","#","#",".","#"]
maze[7] = [".",".",".",".","#",".",".",".",".","."]
maze[8] = [".","#","#","#","#",".","#","#","#","."]
maze[9] = [".",".",".",".","#",".",".",".","G","#"]
#移動4方向のベクトル
dx = [1,0,-1,0]
dy = [0,1,0,-1]
#(sx,sy)から(gx,gy)への最短距離を求める
#たどり着けないとINF
def bfs():
#全ての点をINFで初期化
for i in range(N):
for j in range(M):
d[i][j] = INF
que.append([sx,sy])
d[sx][sy] = 0
while len(que):
p = que[0]
que.pop(0)
if p[0] == gx and p[1] == gy:
break
#移動4方向をループ
for i in range(4):
#移動した後の点を(nx,ny)とする
nx = p[0] + dx[i]
ny = p[1] + dy[i]
#移動が可能かの判定と既に訪れたことがあるかの判定
if 0 <= nx < N and 0 <= ny < M and maze[nx][ny] != "#" and d[nx][ny] == INF:
que.append([nx,ny])
d[nx][ny] = d[p[0]][p[1]] + 1
return d[gx][gy]
print(bfs())
#22と出力
プログラミングコンテスト・チャレンジブック P43 貪欲法
# coding: utf-8
# Your code here!
#入力
V = [1,5,10,50,100,500]#硬貨の種類
c1 = 3
c5 = 2
c10 = 1
c50 = 3
c100 = 0
c500 = 2
C = [c1,c5,c10,c50,c100,c500] #硬貨の枚数
A = 620
def solve():
ans = 0#コインの枚数カウント
global A
for i in range(5,-1,-1):
t = min(int(A/V[i]),C[i])
A -= t*V[i]
ans += t
print(ans)
solve()
#6と出力
プログラミングコンテスト・チャレンジブック P44 貪欲法,区間の問題
# coding: utf-8
# Your code here!
n = 5
s = [1,4,2,6,8]
t = [3,7,5,9,10]
#sとtをitvにまとめて終了時刻に早い仕事順に並び替え
itv = []
for i in range(len(s)):
itv.append([t[i],s[i]])
itv = sorted(itv)
def solve():
T = 0
cnt = 0
for i in range(len(itv)):
if T < itv[i][1]:
cnt += 1
T = itv[i][0]
print(cnt)
solve()
#3と出力
プログラミングコンテスト・チャレンジブック P47 辞書順
# coding: utf-8
# Your code here!
N = 6
S = "ABCBCD"
def solve():
a = 0
b = N -1#5
while a <= b:
#左から見た場合と右から見た場合を比較
left = False;
i = 0
while a + i <= b:
if S[a + i] < S[b -i]: left = True break elif S[a + i] > S[b -i]:
left = False
break
i += 1
if left:
print(S[a],end="")
a += 1
else:
print(S[b],end="")
b -= 1
solve()
#ABCBCD
プログラミングコンテスト・チャレンジブック P48
# coding: utf-8
# Your code here!
N = 6
R = 10
X = [1,7,15,20,30,50]
def solve():
global X
X = sorted(X)#Xの順が昇順になっていなかった場合のための並び替え
ans = 0
i = 0
while i < N:
#sはカバーされていない一番左の点の位置
s = X[i]
#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)
solve()
#3と出力
プログラミングコンテスト・チャレンジブック P50 貪欲法 二分木
# coding: utf-8
# Your code here!
L = [1,4,3,5,2]
N = len(L)
def solve():
global N
ans = 0
#板が１本になるまで適応
while N > 1:
#一番短い板mii1,次に短い板mii2を求める
mii1 = 0
mii2 = 1
if L[mii1] > L[mii2]:
L[mii1],L[mii2] = L[mii2],L[mii1]#swap
for i in range(2,N):
if L[i] < L[mii1]:
mii2 = mii1
mii1 = i
elif L[i] < L[mii2]:
mii2 = i
#それらを併合
t = L[mii1] + L[mii2]
ans += t
if mii1 == N -1:
L[mii1],L[mii2] = L[mii2],L[mii1]#swap
L[mii1] = t
L[mii2] = L[N - 1]
N -= 1
print(ans)
solve()
#33と出力
プログラミングコンテスト・チャレンジブック P53 動的計画法
今回はPHPで書いてみました。理由はPythonの辞書の取扱いに慣れていなかったのと、辞書の取扱いも一応参考書を読み直し、できたと思ったのですが、Pythonのエラーの読み方に慣れておらず、諦めてPHPで書くことにしました。
(PHPに訳した後に、Python3で書き直してみました。)
メモ(dp)を使い処理数を減らしています。下の事例では3回減っているようです。
// Your code here!
$n = 4;
$w = [2,1,3,2];
$v = [3,2,4,2];
$W = 5;
//空のリスト(メモ)
for($i = 0;$i < $n +1;++$i){
for($j = 0;$j < $W +1;++$j){
$dp[$i][$j] = -1;
}
}
//$cnt = 0;//再帰処理回数のカウント
//i番目以降の品物から重さの総和がj以下となるよう選ぶ
function rec($i,$j){
global $dp;
global $n;
global $W;
global $w;
global $v;
global $cnt;
if($dp[$i][$j] >= 0){
return $dp[$i][$j];
}
//++$cnt;
//echo $cnt.PHP_EOL;
//echo $i."-".$j.PHP_EOL;
if($i == $n){
#もう品物は残っていない
$res = 0;
}elseif($j < $w[$i]){
#この品物は入らない
$res = rec($i +1,$j);
}else{
#入れない場合と入れる場合を両方試す
$res = max(rec($i +1,$j),rec($i +1,$j - $w[$i]) + $v[$i]);
}
//echo $res.PHP_EOL;
return $dp[$i][$j] = $res;
}
function solve(){
global $W;
print_r(rec(0,$W));
}
solve();
//7と出力
Python仕様↓
# coding: utf-8
# Your code here!
n = 4;
w = [2,1,3,2]
v = [3,2,4,2]
W = 5
dp = {}
#空のリスト(メモ)
for i in range(n +2):
dp[i] = {}
for j in range(W + 2):
dp[i][j] = -1
#cnt = 0#処理回数のカウント
#i番目以降の品物から重さの総和がj以下となるよう選ぶ
def rec(i,j):
if(dp[i][j] >= 0):
return dp[i][j]
#cnt += 1
#print(cnt)
#print('{0}-{1}'.format(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])
#print(res)
dp[i][j] = res
return res
def solve():
global W
print(rec(0,W))
solve()
#7と出力
プログラミングコンテスト・チャレンジブック P57 最長共通部分列
# coding: utf-8
# Your code here!
n = 4
m = 4
s = "abcd"
t = "becd"
dp = {}
for i in range(n +1):
dp[i] = {}
for j in range(m +1):
dp[i][j] = 0
def solve():
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])
solve()
#3と出力
プログラミングコンテスト・チャレンジブック プライオリティキューを用いる問題P73
久しぶりにこの本を開いてpythonの復習、という理由により教科書とは少し違う風にしてしまった。。
Lの値が膨大な数だった場合は計算時間がかかってしまう。
さらにキューの使い方がよろしくないかもしれない、pythonのキューに関しては
参考サイトhttp://n-knuu.hatenablog.jp/entry/2015/05/30/183718
#!/usr/bin/env python
# -#- coding: utf-8 -#-
N = 4 #ガソリンスタンドの数
L = 25 #移動する距離
P = 10 #積まれているガソリンの量 1L/1P
A = [10,14,20,21]#スタートからのガソリンスタンドの位置
B = [10,5,2,4]#各スタンドで行える給油量
now = 0 #現在地
que = []
cnt = 0 #ガソリンスタンドのナンバー
ans = 0 #給油回数
#ゴールするまでループ
while now < L:
now += 1#１距離進む
#スタンド通過したら給油できるガソリン量をキューに入れる
if cnt < N: if now == A[cnt]: que.append(B[cnt]) cnt += 1 que.sort()#昇順に並び替え if P == 0:#ガソリンがなくなった if len(que) > 0:#現在地より以前に給油できるスタンドがあれば
P += que.pop()#1番給油量が多く行えるスタンドで給油したことにする
ans += 1#給油回数をカウント
else:#途中に給油スタンドなし
ans = -1#ゴールにたどり着けなかった場合の解答にしてループを抜ける
break
P -= 1#ガソリンを1消費
#解答
print(ans)
コメント