蟻本初級編をpythonで解いてみた

#蟻本をpythonで解いてみた

##2.1 全探索

###再帰関数

#階乗
def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n-1)

#フィボナッチ
def fib(n):
    if n <= 1:
        return n
    else:
        return fib(n-1) + fib(n-2)

#配列をメモ化することで高速化
def fib_memo(n):
    memo = [0] * (n+1)

    def fib_cal(x):
        if x <= 1:
            memo[x] = x
            return x
        elif memo[x] != 0:
            return memo[x]
        else:
            memo[x] = fib_cal(x-2) + fib_cal(x-1)
            return memo[x]

    return fib_cal(n)

print(fib_memo(40))

###スタックとキュー

わかりやすいサイト

from collections import deque

#スタック(LIFO)
s = deque([])
s.append(1)
s.append(2)
s.append(3)
print(s.pop(), s)
print(s.pop(), s)
print(s.pop(), s)

#キュー(FIFO)
q = deque([])
q.append(1)
q.append(2)
q.append(3)
print(q.popleft())
print(q.popleft())
print(q.popleft())

###深さ優先探索（Depth First Search)

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

def dfs(i, sum):
    # nこの状態を決めた後に判定する
    if i == n:
        return sum == k

    if dfs( i+1 , sum):
        return True

    if dfs( i+1, sum+a[i]):
        return True

    return False

if dfs(0,0):
    print("Yes")
else:
    print("No")

###幅優先探索(Breadth-First Search)

参考はこちら

from collections import deque

def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy,sx]])
    visited[sy][sx] = 0
    while queue:
        y, x = queue.popleft()
        if [y, x] == [gy, gx]:
            return visited[y][x]
        for j,k in ([1,0], [-1,0], [0,1], [0,-1]):
            new_y, new_x = y+j, x+k
            if (maze[new_y][new_x] == ".") and (visited[new_y][new_x] == -1):
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])

if __name__ == "__main__":
    R, C = map(int, input().split())
    sy, sx = map(int, input().split())
    gy, gx = map(int, input().split())
    sy, sx, gy, gx = sy - 1, sx - 1, gy - 1, gx - 1
    maze = [input() for i in range(R)]
    visited = [[-1]*C for j in range(R)]
    print(bfs(maze, visited, sy, sx, gy, gx))

##2.2 貪欲法

###硬貨の問題

Input = list(map(int, input().split()))
c_list = Input[:6]
A = Input[6]
c = [1, 5, 10, 50, 100, 500]
num = 0

for i in range(5):
    j = 5 - i
    t = min( A // c[j], c_list[j])
    A -= t * c[j]
    num += t

print(num)

###最適スケジューリング問題

N = int(input())
Start = list(map(int, input().split()))
End = list(map(int, input().split()))

from operator import itemgetter

span = sorted([(Start[i], End[i]) for i in range(N)], key=itemgetter(1))

ans = 0
last = 0

for m in range(N):
    if span[m][0] > last:
        last = span[m][1]
        ans += 1
print(ans)

###辞書順最小問題

N = int(input())
S = input()

T = ""
for i in range(N):
    S_rev = S[::-1]
    if S >= S_rev:
        T += S[-1]
        S = S[:-1]
    else:
        T += S[0]
        S = S[1:]


print(T)

Saruman's Army

N = int(input())
R = int(input())
X = list(map(int, input().split()))

ans = 0
last_posi = 0

while X[last_posi] + R  <= X[-1]:
    k = last_posi
    while X[k] < X[last_posi] + R:
        k += 1
    last_posi = k
    ans += 1

print(ans)

Fence repair

下のコードだと、listを更新するたびに全体をsortしてるから計算量増えそう。
listの末尾だけに着目してうまくsortする方法ないかな

n = int(input())
l = list(map(int, input().split()))

ans = 0
while len(l) > 1:
    l.sort(reverse=True)
    new_l = l.pop() + l.pop()
    ans += new_l
    l.append(new_l)

print(ans)

##2.3 動的計画法

###ナップサック問題01

n = int(input())
w = list(map(int, input().split()))
v = list(map(int, input().split()))
MW = int(input())

#i番目以降の品物、j以下の重さから最適な価値を算出する関数

memo = [[0]*((MW)+1) for k in range(n+1)]

#opt(i,j)は、i番目以降(i+1~)のj以下になるように選んだ時の価値の最大値
def opt(i, j):

    if memo[i][j] != 0:
        return memo[i][j]
    if i == n:
        res = 0
    elif j < w[i]:
        res = opt(i+1, j)
    else:
        res = max(opt(i+1,j) , opt(i+1,j-w[i]) + v[i])
    memo[i][j] = res
    return res

print(opt(0,MW))

通すのにかなり苦労した問題。optが表しているものの意味をよく理解した上のlistのindexを気をつける！！！
dp[i][j]が表しているものが分からなくなった、とりあえずdo[N][W]を考える！！！（つまり、最初と最後のインデックスで辻褄を合わせる。

dp[i][j]の解釈を、"dp[i+1][w]はi番目までの品物の中から重さの総和がw以下になるように選んだ時の最大の価値"とした時、コードは以下。

N, W = map(int, input().split())
V_list = []
W_list = []
for i in range(N):
    w, v = map(int, input().split())
    V_list.append(v)
    W_list.append(w)

'''
1.DPテーブルを作る
2.条件に応じてテーブルを更新
今回の問題での条件は、ナップザックを選択するかしないかの二通り
dp[i+1][w]はi番目までの品物から、重さの総和がw以下となるように選んだ時の最大の価値を表している
'''

'''
DPテーブル作成
'''
dp = [[0]*(W+1) for j in range(N+1)]


for i in range(N):
    for j in range(W+1):
        if (j < W_list[i]):
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i][j-W_list[i]] + V_list[i])

print(dp[N][W])

'''
”入力”
4 5
2 3
1 2
3 4
2 2

"出力"
7
'''

###最長共通部分列問題

n = int(input())
m = int(input())
s = input()
t = input()

#dp[a][b]というのは、(a,b)の長さの文字列の組み合わせでの最大値
dp = [[0]*(m+1) for k in range(n+1)]

def cal_match():
    dp[0][0] = dp[0][1] = dp[1][0] = 0
    for i in range(0,n):
        for j in range(0,m):
            if s[i] == t[j]:
                dp[i+1][j+1] = dp[i][j] + 1
            else:
                dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
    return dp[n][m]

print(cal_match())

２回目

N = int(input())
M = int(input())
s = list(input())
t = list(input())
ls = len(s)
lt = len(t)

dp = [[0]*(lt+1) for x in range((ls+1))]

for i in range(ls):
    for j in range(lt):
        if s[i] == t[j]:
            dp[i+1][j+1] = max(dp[i][j]+1, dp[i+1][j], dp[i][j+1])

        else:
            dp[i+1][j+1] =max(dp[i+1][j], dp[i][j+1])
print(dp[ls][lt])

漸化式立てて、実際に小さい数字で計算して、indexの辻褄を合わせることが大事。

###個数制限なしナップザック問題

これだと計算量がO(n*MW^2)になってしまう

n = int(input())
w = list(map(int, input().split()))
v = list(map(int, input().split()))
MW = int(input())

'''
dp[i+1][j]は、0~i番目までの品物から重さの総和がj以下になるように選んだ時の
価値の最大値を表している
'''

dp = [[0] * ((MW+1)) for t in range(n+1)]
for s in range(MW):
    dp[0][s] = 0

def opt():
    for i in range(0,n):
        for j in range(MW+1):
            for k in range(0, (j // w[i]) + 1):

                dp[i+1][j] = max(dp[i+1][j], dp[i][j - k * w[i]] + k * v[i])
    return dp[n][MW]

print(opt())

計算量を改善したversion（漸化式の変形を行った）（蟻本P.59参照）
計算量O（n*MW)

n = int(input())
w = list(map(int, input().split()))
v = list(map(int, input().split()))
MW = int(input())

'''
dp[i+1][j]は、0~i番目までの品物から重さの総和がj以下になるように選んだ時の
価値の最大値を表している
'''

dp = [[0] * ((MW+1)) for t in range(n+1)]
for s in range(MW):
    dp[0][s] = 0

def opt():
    for i in range(0,n):
        for j in range(MW+1):
            if (j < w[i]):
                dp[i + 1][j] = dp[i][j]
            else:
                dp[i + 1][j] = max(dp[i][j], dp[i + 1][j - w[i]] + v[i])
    return dp[n][MW]

print(opt())

###個数制限付き部分和問題
計算量を考慮して漸化式を立てる必要性あり。

n = int(input())
a = list(map(int, input().split()))
m = list(map(int, input().split()))
K = int(input())

#配列の再利用
dp = [-1] * (K+1)

dp[0] = 0

for i in range(n):
    for j in range(K+1):
        if dp[j] >= 0:
            dp[j] = m[i]
        elif j < a[i] or dp[j-a[i]] <= 0:
            dp[j] = -1
        else:
            dp[j] = dp[j-a[i]] - 1

if dp[K] >= 0:
    print("Yes")
else:
    print("No")

###最長増加部分列問題

n = int(input())
a = list(map(int, input().split()))

dp = [0] * n

for i in range(0,n):
    dp[i] = 1
    for j in range(0,i):
        if a[j] < a[i]:
            dp[i] = max(dp[i], dp[j] + 1)

print(dp[n-1])

###分割数

n = int(input())
m = int(input())
M = int(input())
'''
dp[i][j]はjをi分割する、通り数
'''

dp = [[0] * (n+1) for k in range(m+1)]
dp[0][0] = 1

for i in range(1,m+1):
    for j in range(n+1):
        if j >= i:
            dp[i][j] = (dp[i][j-i] + dp[i-1][j]) % M
        else:
            dp[i][j] = dp[i-1][j]

print(dp[m][n])

##2.4データ構造

###priorityQueとheap

import heapq as hq

a  = [5,3,2,1,6,13,4,12,14,9,10]
hq.heapify(a)
print(a)

hq.heappush(a, 7)
print(a)

hq.heappop(a)
print(a)

'''
pushとpopをまとめて行うメソッドもある（こちらの方が高速）
pushとpopの行う順番に注意
'''

print(hq.heappushpop(a, 11))
print(a)

print(hq.heapreplace(a,1))
print(a)

###Expedition

import heapq as hq

N,L,P = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

ans = 0
pos = 0
tank = P
gas_station = []

#ゴールもリストに追加する
A.append(L)
B.append(0)

for i in range(N):
    dis = A[i] - pos
    while dis > tank:
        if(len(gas_station) == 0):
            ans = -1
            break
        L = [k * -1 for k in gas_station]
        tank += hq.heappop(L) * (-1)
        ans += 1
    if ans == -1:
        break
    pos = A[i]
    tank -= dis
    hq.heappush(gas_station, B[i])

print(ans)

###Fence Repairの計算量を改善

貪欲法のchapterで解いた問題の計算量を、heapQueを用いて改善してみた

import heapq as hq

n = int(input())
l = list(map(int, input().split()))

ans = 0
while len(l) > 1:
    hq.heapify(l)
    new_l = hq.heappop(l) + hq.heappop(l)
    ans += new_l
    l.append(new_l)

print(ans)

###二部探索

このベージがわかりやすい

Union find木

このページがわかりやすい&参考にさせていただきました

#Union Find

#木の根を求める
def find(x,par):
    if par[x] == x:
        return x
    else:
        return find(par[x],par)

#xとyの属する集合の併合
def unite(x,y,par,rank):
    x = find(x,par)
    y = find(y,par)
    
    if x != y:
        #xとyの属している集合が異なる時
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x]==rank[y]:
                rank[x] += 1

#xとyが同じ集合に属するかの判定
def same(x,y,par):
    return find(x,par) == find(y,par)

########################################
n = 7
par = [] #親
rank = [] #木の深さ

#初期化
for i in range(n):
    #par[i]:i rank[i]:0
    par.append(i)
    rank.append(0)

#A(0,1,4) B(2) C(3,5,6)のグループを作成
unite(0,1,par,rank)
unite(0,4,par,rank)
unite(3,5,par,rank)
unite(5,6,par,rank)
#1と2,3と5は同じ集合かの判定
print(same(1,2,par))
print(same(3,5,par))
#AとBの併合
unite(4,2,par,rank)
#1と2は同じ集合かの判定
print(same(1,2,par))

[出力]　コメントは補ったものです。

#A(0,1,4) B(2) C(3,5,6)のグループを作成
#1と2,3と5は同じ集合かの判定
False
True
#AとBの併合
#1と2は同じ集合かの判定
True

2.5グラフの探索

###二部グラフ判定

これは深さ優先探索を用いています。

n, w = map(int, input().split())
g = [[] for i in range(n)]

for k in range(w):
    x, y = map(int, input().split())
    g[x].append(y)
    g[y].append(x)

color = [0] * n

def dfs(v, c):
    color[v] = c
    for j in g[v]:
        if color[j] == c:
            return False
        elif color[j] == 0 and (not dfs(j,-c)):
            return False

    return True

'''
もしかしたら問題で与えられる木が連結ではない可能性もある。
なので、各頂点がすでに塗られているかどうかを順番に見て行く必要性がある。
'''
k = 1
for i in range(n):
    if color[i] == 0:
        if not dfs(i, 1):
            k = -1

if k == 1:
    print('Yes')
else:
    print("No")

###ベルマンフォード法

随時更新していきます。