プログラミングコンテスト・チャレンジブックのコードをPythonにしたメモ

マイナビのプログラミングコンテスト チャレンジブックでアルゴリズムを勉強中!

この本は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″のフォントがそっくりで、かなり迷ってしまった..2分探索を使用したアルゴリズム。


# 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():
    #2分探索を行うためにソート
    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の階乗は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
    #板が1本になるまで適応
    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#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)

コメント