---
# System prepended metadata

title: AtCoder Beginner Contest 315 題解
tags: [Algo, AtCoder]

---

# 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)
```
:::