「AtCoder 版！蟻本 (初級編)」をPythonで解く！

AtCoder 版！蟻本 (初級編)を細々と__Python__で解いていきます。

1 すべての基本 "全探索"

1-1　bit全探索

ABC 045 C - たくさんの数式

【解答】

S = list(input())

ans = 0
for i in range(2**(len(S)-1)):
    plus = [""]*(len(S))
    fomula = ""
    for j in range(len(S)-1):
        if(i>>j & 1):
            plus[j] = "+"
    
    for i in range(len(S)):
        fomula += S[i] + plus[i]
    ans += eval(fomula)
    
print(ans)

ABC 104 C - All Green

【解説】
ボーナスを取る取らないをbit全探索する。
ボーナスを取って、残りの足りない点数を点数の高いものから選んでいく。

【解答】

D,G = map(int,input().split())
l = list(list(map(int, input().split())) for _ in range(D))

# 得点の大きい順に並び替えておく
l = l[::-1]

ans = float("inf")
for i in range(2**D):
    total = 0
    cnt = 0
    for j in range(D):
        if (i>>j)&1:
            total += 100*(D-j)*l[j][0] + l[j][1]
            cnt += l[j][0]
    if total >= G:
        ans = min(ans,cnt)
        continue
    for j in range(D):
        if (i>>j)&1 == False:
            for k in range(l[j][0]):
                total += 100*(D-j)
                cnt+=1
                if total >= G:
                    ans = min(ans,cnt)
                    break
            break

print(ans)

1-2　DFS（深さ優先探索）

ATC 001 A 深さ優先探索

【解説】
DFS(depth-first search)は、ひたすら奥まで探索し、探索するものがなくなったら探索していないところまで戻ってまた探索するイメージ。
LIFO(Last-In First-Out)である__スタック__を用いて実装する。

【解答】

from collections import deque

def dfs(maze, sh, sw):
    #到達済みリストを初期化
    visited = [[0]*W for _ in range(H)]

    stack = deque([[sh,sw]])
    visited[sh][sw] = 1
    while stack:
        h, w = stack.pop()
        if maze[h][w] == "g":
            return("Yes")
        for i,j in [[1,0],[-1,0],[0,1],[0,-1]]:
            new_h, new_w = h+i, w+j
            if new_h < 0 or new_w < 0 or new_h >= H or new_w >= W:
                continue
            elif maze[new_h][new_w] != "#" and visited[new_h][new_w] == 0:
                visited[new_h][new_w] = 1
                stack.append([new_h, new_w])
    return("No")

H,W = map(int,input().split())
maze = [input() for _ in range(H)]

# スタート位置を見つける
for i in range(H):
    if maze[i].find("s") != -1:
        sh = i
        sw = maze[i].find("s")
        
print(dfs(maze, sh, sw))

1-3　BFS（幅優先探索）

ABC 007 C 幅優先探索

【解説】
BFS(breadth-first search)は、浅いものから順々に探索するイメージ。
FIFO(First-In First-Out)である__キュー__を用いて実装する。

【解答】

from collections import deque

def dfs(maze, sh, sw, gh ,gw):
    #到達済みリストを初期化
    visited = [[-1]*W for _ in range(H)]

    stack = deque([[sh,sw]])
    visited[sh][sw] = 0
    while stack:
        h, w = stack.popleft()
        if h == gh and w == gw :
            return(visited[h][w])
        for i,j in [[1,0],[-1,0],[0,1],[0,-1]]:
            new_h, new_w = h+i, w+j
            if new_h < 0 or new_w < 0 or new_h >= H or new_w >= W:
                continue
            elif maze[new_h][new_w] != "#" and visited[new_h][new_w] == -1:
                visited[new_h][new_w] = visited[h][w] + 1
                stack.append([new_h, new_w])
    return("No")

H,W = map(int,input().split())
sh,sw = map(int, input().split())
gh,gw = map(int, input().split())
maze = [input() for _ in range(H)]

print(dfs(maze, sh-1, sw-1, gh-1, gw-1))

1-4　特殊な状態の列挙

ABC 054 C One-stroke Path

【解説】
permutationsを使い、グラフの連結の仕方を全列挙する。
正しく連結されているかを判断し、カウントしていく。

【解答】

from itertools import permutations

N,M = map(int, input().split())
l = [list(map(int,input().split())) for _ in range(M)]

graph = [[False]*(N+1) for _ in range(N+1)]
for i in l:
    graph[i[0]][i[1]] = True
    graph[i[1]][i[0]] = True

cnt = 0

for i in permutations(range(1,N+1)):
    #始点が1からを考慮
    if i[0] != 1:
        continue
    isJoin = True
    for j in range(1,N):
        if not graph[i[j-1]][i[j]]:
            isJoin = False
            break
    if isJoin:
        cnt += 1

print(cnt)

JOI 2009 予選 D カード並べ

【解説】
permutaionsを使い、整数の並び方を列挙する。
mapとjoinを使って並び替えた整数を作りdicに追加し、最後にdicに入っている整数の数を答える。

【解答】

from itertools import permutations

N = int(input())
S = int(input())
l = [int(input()) for _ in range(N)]
dic = {}
for i in permutations(l,S):
    i = map(str,i)
    dic[("".join(i))] = 1

print(len(dic))

2 猪突猛進！ "貪欲法"

貪欲法とは

1.問題を複数の部分問題に分割する
2.各部分問題に対する解を評価する(各部分問題ごとに考えられる解のパターンは複数ある．)
3.評価が最も良いものをその部分問題の解(=局所最適解)として，次の部分問題の解(これも複数通り考えられる)を評価する

引用：簡単な貪欲法を解いてみた

2-1　硬貨の問題

JOI 2007 予選 A おつり

【解説】
大きい硬貨から枚数をカウントしていく。

【解答】

N = int(input())

N = 1000 - N
cnt = 0

l = [500,100,50,10,5,1]

for i in l:
    cnt += N // i
    N = N - i*(N//i)

print(cnt)

2-2　区間スケジューリング問題

キーエンス プログラミング コンテスト 2020 B - Robot Arms

【解説】
まずはロボットのアームの右端の位置により並び替える。
右端の位置が左にある順番に見ていき、重なっていたら除外する。
重なっていなければ、右端の位置を更新する。

【解答】

N = int(input())
l = [list(map(int,input().split())) for _ in range(N)]

ans = N
for i in l:
    x = 0 if i[0]-i[1] < 0 else i[0]-i[1]
    i[1] = i[0]+i[1]
    i[0] = x
    
l.sort(key=lambda x:x[1])

right = 0
for i in range(N):
    if right > l[i][0]:
        ans-=1
    else:
        right = l[i][1]

print(ans)

2-3　辞書順最小なものを求める Greedy

ABC 076 C Dubious Document 2

【解説】
まずは以下のように、Tの文字列と残りの文字数を？で埋めたリストSSを用意する。

coder??
?coder?
??coder

できた文字のリストSSと与えられたS'を1文字ずつ比較していく。
1．S'の文字が「?」またはSSと一致する場合
　→そのまま
2．S'の文字が「?」でない　かつ　SSの文字が「？」の場合
　→SSの「？」をS'の文字に変換する
3．それ以外の場合
　→作成できない文字列

その後、SSに残った「？」を辞書順最小となるように「a」で埋める
【解答】

S = input()
T = input()

n = len(S)-len(T)+1
ans = []
for i in range(n):
    SS = list("?"*(i) + T + "?"*(n-i-1))
    flag = True
    for i in range(len(S)):
        if S[i]=="?" or S[i]==SS[i]:
            pass
        elif S[i]!="?" and SS[i]=="?":
            SS[i] = S[i]
        else:
            flag = False
    if flag:
        ans.append("".join(SS).replace("?","a"))

if ans:
    ans.sort()
    print(ans[0])
else:
    print("UNRESTORABLE")

2-4　より厳しいところをとっていく Greedy

ABC 083 C Multiple Gift

【解説】
ひとつ前の数より大きくて、倍数となる最小のものは2倍したもの。
よって2倍していき、Yを超えるところまで調べる。

【解答】

X,Y = map(int,input().split())

cnt=0
while X<=Y:
    cnt+=1
    X = X*2

print(cnt)

ARC 006 C 積み重ね

【解説】
手前から一番上にある箱の重量を見て、乗せられたら乗せる。
乗せられなかったら、次の山の一番上にある箱と比較するというのを繰り返す。

【解答】

N = int(input())
W = [int(input()) for _ in range(N)]

l=[float("inf")]
for w in W:
    flag=True
    for i in range(len(l)):
        if l[i]>=w:
            l[i] = w
            flag=False
            break
    if flag:
        l.append(w)
        
print(len(l))

3 値を覚えて再利用 "動的計画法"

3-1　01ナップサック問題

AOJ Course 0-1ナップザック問題

【解説】
dp[i][j]・・・i番目までの荷物を使って、重量jまでの最適解を意味する。
・w[i] > jの場合
　この荷物は入れられないので、ひとつ前までの荷物の最適解で更新する。

・w[i] ≦ j の場合
　i番目の荷物を入れる時を考える。
　重量w[i]が増えてしまうので、i-1番目まででj-w[i]の重量の最適解に価値v[i]を足してあげることになる。
　あとは、それとi番目の荷物を入れない場合のmaxを取る。

引用：ツバサの備忘録 動的計画法(ナップサック問題について)
図があってすごいわかりやすい。

【解答】

N,W = map(int,input().split())

v = [0] * N
w = [0] * N
for i in range(N):
    v[i],w[i] = map(int,input().split())

dp = [[0] * (W+1) for _ in range(N)]

for i in range(N):
    for j in range(1, W+1):
        if w[i] > j:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j],v[i]+dp[i-1][j-w[i]])

print(max(dp[N-1]))

TDPC A コンテスト

【解説】
部分和問題。

入力が3で5になりうるか調べるとき、
5-3の__2__がTrueであれば5にできるよ！という感じで探索をしていく。

入力リスト[2,3]の時のデータdpの流れ。
dp[1][2] = dp[0][2-2] = dp[0][0] = True
dp[2][3] = dp[1][3-3] = dp[1][0] = True
dp[2][5] = dp[1][5-3] = dp[1][2] = True
[0,2,3,5]がTrueになる。

【解答】

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

_sum = sum(l)
dp = [[False]*(_sum+1) for _ in range(N+1)]
dp[0][0] = True

for i in range(1,N+1):
    for j in range(_sum+1):
        if l[i-1]>j:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = dp[i-1][j] or dp[i-1][j-l[i-1]]

print(sum(dp[N]))