# AtCoder Beginner Contest 317 題解

> 我好菜啊我好菜啊我好菜啊

Solve problem **A - E** by *python*

***

## [A - Potions (abc317 A)](https://atcoder.jp/contests/abc317/tasks/abc317_a)
### 題意

給定 $N$ 瓶藥水以及其可以恢復的生命值 $P_i$ 、當前生命值 $H$ 、目標生命值 $X$，求哪瓶藥水可以使生命回復到目標生命值或以上，並且這瓶藥水的功效要最小。

### 思路

對所有藥水做遍歷，保存符合條件的藥水。

:::spoiler 神奇的代碼

N, H, X = map(int, input().split(" "))
P = list(map(int, input().split(" ")))

ans = -1
for i, p in enumerate(P):
    if H + p == X:
        ans = i + 1
        break
    elif H + p > X:
        if ans == -1 or p < P[ans]:
            ans = i + 1
print(ans)

:::

***

## [B - MissingNo. (abc317 B)](https://atcoder.jp/contests/abc317/tasks/abc317_b)
### 題意

給定長度為 $N$ 的數列 $A$，其為長度為 $N+1$ 的連續數列的子集合，找出缺少的那個數為何。

### 思路

排序後由小到大遍歷所有元素，若當前元素不等於前一個元素+1，則此處就是缺少的數。

:::spoiler 神奇的代碼

N = int(input())
A = list(map(int, input().split(" ")))

A.sort()
for i in range(1, N):
    if A[i] - A[i-1] > 1:
        print(A[i-1]+1)
        break

:::

***

## [C - Remembering the Days (abc317 C)](https://atcoder.jp/contests/abc317/tasks/abc317_c)
### 題意

給定 $N$ 個點和 $M$ 條邊，以及每條邊對應的權重 $C_i$ ，求最長的路徑

### 限制

- $2 <= N <= 10$

### 思路：DFS

構建出相鄰矩陣後，對每個點當作起點做DFS即可，並且令DFS返回路徑的長度，在以N個點作為起點的最大路徑中，再取其中的最大值。

:::spoiler 神奇的代碼

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

if M == 1:
    print(edges[0][2])
    exit()

# 對每個點DFS，紀錄最大的距離
adj = [[0]*(N+1) for _ in range(N+1)]
for edge in edges:
    X, Y, W = edge
    adj[X][Y] = W
    adj[Y][X] = W

visited = [False for _ in range(N+1)]

ans = 0
def dfs(v):
    cur = 0
    visited[v] = True
    for j in range(1, N+1):
        if adj[v][j] != 0 and not visited[j]:
            res = dfs(j)
            cur = max(cur, res+adj[v][j])
    visited[v] = False
    return cur 

for i in range(1, N+1):
    ans = max(ans, dfs(i))
print(ans)

:::

***

## [D - President (abc317 D)](https://atcoder.jp/contests/abc317/tasks/abc317_d)
### 題意

給定 $N$ 個選區，以及每個選區中兩個候選人分別的得票數 $X_i$ 、$Y_i$、該選區的席次 $Z_i$，求若X要贏得一半以上的席次，需要從對手手中搶走多少票。

### 限制

- $1 \leq N \leq 100$
- $X_i+Y_i$ is odd.
- $\sum_{i=1}^N Z_i \leq 10^5$
- $\sum_{i=1}^N Z_i$ is odd.

### 思路：DP

- 令 $dp[i]$ 表示取得i個席位所需要的最少票數
- 令 $x$、$y$、$z$ 表示每個選區的兩位候選人的分別得票數，以及席次，計算需要搶走的票數 $vote$
- 可寫出轉移方程為 $dp[i] = min(dp[i], dp[i-z] + vote)$
- 在所有取得一半以上席位所需要的最少票數中，取最小值即為答案。

:::spoiler 神奇的代碼

N = int(input())  
# DP 
MAX_ZSUM = 10**5 # 所有席位的總數的邊界數量
# dp[i] 表示取得i個席位所需要的最少票數
dp = [0] + [float("inf")] * MAX_ZSUM

ZSUM = 0 # 記錄所有席位的總數
for _ in range(N):
  x,y,z = map(int,input().split())
  ZSUM += z 
  vote = max((y-x+1)//2, 0) # 贏下此選區所需要的票數
  for i in range(MAX_ZSUM-1, z-1, -1): # 由大到小更新，避免重複計算同一個選區
     dp[i] = min(dp[i], dp[i-z] + vote)

ans = min(dp[(ZSUM+1)//2:]) # 取得一半以上席位所需要的最少票數
print(ans)

:::

***

## [E - Avoid Eye Contact (abc317 E)](https://atcoder.jp/contests/abc317/tasks/abc317_e)
### 題意

給定一個迷宮 $Maze$，其中有若干個監視者，其朝向分別用`<>^v`表示，不能被監視者的視線看到，求能否從給定的起點走到終點，並且輸出路徑長度。

### 思路：用BFS走迷宮

- 首先先構建迷宮的矩陣，並在上下左右加上牆壁，以免出界
- 再來對迷宮矩陣做處理，確定哪些路徑可走
- 先找出起點、終點、以及所有監視者的位置
- 再來處理監視者，為了不影響對其他監視者的處理，依照題目所述，先標記為 $!$
- 最後將地圖中的可走路徑標記為0，牆壁或可視為牆壁的符號標記為-1。
- 從起點開始做BFS，並且對可走路徑更新從起點走到此位置的最小距離
- 若找到終點或所有可走路徑都走完就終止，因為起點不等於終點，所以可以用走到終點的路徑長度是否為$0$來判斷能不能走到終點。

:::spoiler 神奇的代碼

# 構建迷宮的矩陣，並在上下左右加上牆壁，以免出界
H , W = map(int, input().split(" "))
Maze = [list(f"#{input()}#") for _ in range(H)]
Maze = [["#"]*(W+2)] + Maze + [["#"]*(W+2)]

# 先找出起點、終點、以及所有的箭頭位置
start = goal = None
arrows = []
for i in range(1, H+1):
    for j in range(1, W+1):
        if Maze[i][j] == "S":
            start = (i, j)
        elif Maze[i][j] == "G":
            goal = (i, j)
        elif Maze[i][j] in "<>^v":
            arrows.append((i, j))
# 再來處理箭頭
arrow_map = {"<":(0, -1), ">":(0, 1), "^":(-1, 0), "v":(1, 0)}
for pi, pj in arrows:
    di, dj = arrow_map[Maze[pi][pj]]
    i, j = pi+di, pj+dj
    while Maze[i][j] not in "#<>^v":
        Maze[i][j] = "!" # 為了不影響其他箭頭的判定情況，先標記為"!"
        i, j = i+di, j+dj
# 最後將地圖中的可走路徑標記為0，牆壁或可視為牆壁的符號標記為-1
# 這樣就可以用BFS來走迷宮了，且這個矩陣的元素代表路徑長度
for i in range(H+2):
    for j in range(W+2):
        if Maze[i][j] in "#!<>^v":
            Maze[i][j] = -1
        else:
            Maze[i][j] = 0
# BFS
from collections import deque
queue = deque([start])
while queue:
    pi, pj = queue.popleft()
    if (pi, pj) == goal: # 找到終點就停止
        break
    for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]: 
        if Maze[pi+di][pj+dj] == 0: #檢查上下左右是否可走且未走過
            Maze[pi+di][pj+dj] = Maze[pi][pj] + 1
            queue.append((pi+di, pj+dj))
print(-1) if Maze[goal[0]][goal[1]] == 0 else print(Maze[goal[0]][goal[1]])

:::