# AtCoder Beginner Contest 315 題解
> 為第一次打AtCoder做準備
Solve problem **A - F** by *python*
***
## [A - tcdr (abc315 A)](https://atcoder.jp/contests/abc315/tasks/abc315_a)
### 題意
給定一個字串s，刪除其中的母音(a,e,i,o,u)。
### 思路
字串操作。
:::spoiler 神奇的代碼
```python3=
s = input()
target = "aeiou"
for ch in s:
if ch not in target:
print(ch, end="")
```
:::
***
## [B - The Middle Day (abc315 B)](https://atcoder.jp/contests/abc315/tasks/abc315_b)
### 題意
給定 n 個月的日曆，第i個月有 $D_i$ 天，且保證總天數為奇數，詢問中間的那一天是幾月幾號，即求 $(\Sigma D_i +1)/2$ 對應的月份和日期
### 思路
找出`middle_day`後，從第1個月開始遍歷，將`middle_day`扣除本月日數，直到無法相減為止，最後的結果即為日期。
:::spoiler 神奇的代碼
```python3=
M = int(input())
days = list(map(int, input().split()))
mid = (sum(days) + 1) // 2 # Middle day
# Find the middle day
for i in range(0, M):
if mid - days[i] <= 0:
print(i + 1, mid)
break
else:
mid -= days[i]
```
:::
***
## [C - Flavors (abc315 C)](https://atcoder.jp/contests/abc315/tasks/abc315_c)
### 題意
給定 $N$ 碗冰淇淋，每碗冰淇淋都有其對應的口味 $F_i$ 和滿意度 $S_i$，我們可以在其中任取兩碗，求最大滿意度。
- 當 $F_i \neq F_j$ 時，滿意度為 $S_i + S_j$
- 當 $F_i = F_j$ 時，滿意度為 $S_i + \frac{S_j}{2}$
### 思路
直接考慮所需的兩種情況，即口味相同和口味不同的情況
- 對口味相同的情況，maintain一個dict，保存所有相同口味的冰淇淋的滿意度，對不同的口味取出其最大兩項，即為此情況下的滿意度
- 對口味不同的情況，maintain一個list，保存口味和滿意度的tuple，依照滿意度做排序後，從第2項開始遍歷，直到出現與首項口味不同的項為止，兩項相加即為這種情況的滿意度。
:::spoiler 神奇的代碼
```python3=
# Input & Pre-processing:
N = int(input())
flavors = []
dic = {i:[] for i in range(1, N + 1) }
for _ in range(N):
f, d = map(int, input().split())
dic[f].append(d)
flavors.append((f, d))
flavors.sort(key=lambda x: x[1], reverse=True)
ans = 0
# Same flavor
for f in range(1, N + 1):
if len(dic[f]) >= 2:
dic[f].sort(reverse=True)
ans = max(ans, dic[f][0] + dic[f][1] // 2)
# Diff flavor
for f, d in flavors[1:]:
if f != flavors[0][0]:
ans = max(ans, flavors[0][1] + d)
break
print(ans)
```
:::
***
## [D - Magical Cookies (abc315 D)](https://atcoder.jp/contests/abc315/tasks/abc315_d)
> 個人覺得這題比E、F還難，但也許只是後面兩題的考點比較常見，所以自己比較熟悉而已。
### 題意
給定一個 H × W 的矩陣，若某行或某列所有元素相同，則可以被刪除，求最後剩餘的元素個數。
### 思路
所有元素相同即該行或該列只出現一個元素，因此我們maintain在某行或某列中，所有字母出現的對應次數(row/col)，以及在某行或某列中，出現幾種不同字母(row_c/col_c)。
接著找出該行或該列只有一種字母的直行橫列，並對該行或該列做刪除，最後剩餘的長寬相乘即為答案。
:::spoiler 神奇的代碼
```python3=
# Preprocess
A = 26 # 字母個數 # c_(i,j) is a lowercase English letter.
row = [[0] * A for _ in range(H)] # row[i][j] 表示在第i橫列中字母j出現的次數
row_c = [0] * H # row_c[i] 表示在第i橫列中不同字母的個數
col = [[0] * A for _ in range(W)] # col[i][j] 表示在第i直行中字母j出現的次數
col_c = [0] * W # col_c[i] 表示在第i直行中不同字母的個數
num_row, num_col = H, W # 剩餘的橫列和直行的數量
for i in range(H):
for j in range(W):
idx = ord(c[i][j]) - ord('a') # 字母的索引
# 依照上述的定義更新 row, row_c, col, col_c
row[i][idx] += 1
if row[i][idx] == 1:
row_c[i] += 1
col[j][idx] += 1
if col[j][idx] == 1:
col_c[j] += 1
# Start
while True:
del_row, del_col = [], []
for i in range(H):
if row_c[i] == 1 and num_col >= 2: # 依照題目的定義刪除橫列
del_row.append(i)
for j in range(W):
if col_c[j] == 1 and num_row >= 2: # 依照題目的定義刪除直行
del_col.append(j)
if del_row == [] and del_col == []:
break
def remove(i, j): # 刪除c[i][j]，並更新 row, row_c, col, col_c
if c[i][j] != ' ':
idx = ord(c[i][j]) - ord('a')
row[i][idx] -= 1
if row[i][idx] == 0:
row_c[i] -= 1
col[j][idx] -= 1
if col[j][idx] == 0:
col_c[j] -= 1
c[i][j] = ' '
for i in del_row:
for j in range(W):
remove(i, j)
num_row -= len(del_row)
for j in del_col:
for i in range(H):
remove(i, j)
num_col -= len(del_col)
# Output
print(num_row * num_col)
```
:::
***
## [E - Prerequisites (abc315 E)](https://atcoder.jp/contests/abc315/tasks/abc315_e)
### 題意
假設有 N 本書，編號從 1 到 N。如果想要閱讀第 i 本書，則必須先閱讀與其相關的所有書。所求為閱讀第 1 本書之前，需要先閱讀哪些書。
### 思路：Topological sort
需要注意Python的遞迴深度預設只有$1000$，在test case裡會有幾個Runtime Error，需要設定遞迴深度。
因為所求為閱讀第1本書之前需要閱讀哪些書，所以對第一個節點做DFS即可，輸出時忽略此節點。
:::spoiler 神奇的代碼
```python3=
import sys
sys.setrecursionlimit(10**9)
# Input
N = int(input())
prerequisities = [list(map(int, input().split(" ")))[1:] for _ in range(N)]
# Process
flags = [0] * N # 0: WHITE, 1: GRAY, 2: BLACK
ans = []
def dfs(i):
if flags[i] == 2:
return True
if flags[i] == 1:
return False
flags[i] = 1
for j in prerequisities[i]:
if not dfs(j-1): return False
flags[i] = 2
ans.append(i+1)
return True
dfs(0)
for idx in ans[:-1]:
print(idx, end=" ")
```
:::
***
## [F - Shortcuts (abc315 F)](https://atcoder.jp/contests/abc315/tasks/abc315_f)
### 題意
在一個坐標系中有若干個檢查點，你需要依序經過這些檢查點，所求為走過的歐幾里得距離總和。你也可以選擇忽略一些檢查點不走，但如果跳過了 $k$ 個檢查點，最終的距離將要加上 $2^{k-1}$ 作為懲罰，求考慮懲罰後最短的距離。
### 思路：動態規劃
- 令 $dp[i][j]$ 表示前$i+1$個點中，跳過$j$個點的最短路徑
- 跳過$j$個點的轉移方程：$dp[i+j+1][k] = min(dp[i+j+1][k], dp[i][k-j] + distance)$
- 最後考慮 $dp[N-1][k]$ ，對忽略的點數量 $k$ 分別計算其懲罰，最後輸出最小值。
- 因為懲罰為 $2^{k-1}$，可以猜測若忽略的點數量過多，則懲罰會大到無法構成最佳解，因此可以設定 $k$ 的邊界，此處我設定成30。
:::spoiler 神奇的代碼
```python3=
import math
# Input
N = int(input())
checkpoints = [list(map(int, input().split(" "))) for _ in range(N)] # coordinates of checkpoint i
BOUND = min(N, 30)
dp = [[math.inf] * BOUND for _ in range(N)]
dp[0][0] = 0
for i in range(N):
for j in range(BOUND):
next_i = i + 1 + j # 找到下一個點，中間跳過j個點
if next_i >= N:
break
distance = math.dist(checkpoints[i], checkpoints[next_i])
# 跳過j個點的轉移方程：dp[i+j+1][k] = min(dp[[i+j+1][k], dp[i][k-j] + distance)
for k in range(j, BOUND): # 對k = [j, BOUND) 的範圍進行更新
dp[next_i][k] = min(dp[next_i][k], dp[i][k-j] + distance)
ans = dp[N-1][0] # 跳過0個點的最短路徑，penalty = 0
for k in range(1, BOUND):
ans = min(ans, dp[N-1][k] + 2**(k-1))
print(ans)
```
:::
Sign in with Wallet
Connect another wallet