AtCoder Beginner Contest 315 題解

為第一次打AtCoder做準備 ~

All problems solved by python

A - tcdr (abc315 A)

題意

給定一個字串s，刪除其中的母音(a,e,i,o,u)。

思路

字串操作。

1
2
3
4
5
s = input()
target = "aeiou"
for ch in s:
    if ch not in target:
        print(ch, end="")

B - The Middle Day (abc315 B)

題意

給定 n 個月的日曆，第i個月有 DiD_i 天，且保證總天數為奇數，詢問中間的那一天是幾月幾號，即求 (ΣDi+1)/2(\Sigma D_i +1)/2 對應的月份和日期

思路

找出middle_day後，從第1個月開始遍歷，將middle_day扣除本月日數，直到無法相減為止，最後的結果即為日期。

1
2
3
4
5
6
7
8
9
10
11
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)

題意

給定 NN 碗冰淇淋，每碗冰淇淋都有其對應的口味 FiF_i 和滿意度 SiS_i，我們可以在其中任取兩碗，求最大滿意度。

  • 當 Fi≠FjF_i \neq F_j 時，滿意度為 Si+SjS_i + S_j
  • 當 Fi=FjF_i = F_j 時，滿意度為 Si+Sj2S_i + \frac{S_j}{2}

思路

直接考慮所需的兩種情況，即口味相同和口味不同的情況

  • 對口味相同的情況，maintain一個dict，保存所有相同口味的冰淇淋的滿意度，對不同的口味取出其最大兩項，即為此情況下的滿意度
  • 對口味不同的情況，maintain一個list，保存口味和滿意度的tuple，依照滿意度做排序後，從第2項開始遍歷，直到出現與首項口味不同的項為止，兩項相加即為這種情況的滿意度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 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)

個人覺得這題比E、F還難，但也許只是後面兩題的考點比較常見，所以自己比較熟悉而已。

題意

給定一個 H × W 的矩陣，若某行或某列所有元素相同，則可以被刪除，求最後剩餘的元素個數。

思路

所有元素相同即該行或該列只出現一個元素，因此我們maintain在某行或某列中，所有字母出現的對應次數(row/col)，以及在某行或某列中，出現幾種不同字母(row_c/col_c)。
接著找出該行或該列只有一種字母的直行橫列，並對該行或該列做刪除，最後剩餘的長寬相乘即為答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
# 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)

題意

假設有 N 本書，編號從 1 到 N。如果想要閱讀第 i 本書，則必須先閱讀與其相關的所有書。所求為閱讀第 1 本書之前，需要先閱讀哪些書。

思路：Topological sort

需要注意Python的遞迴深度預設只有10001000，在test case裡會有幾個Runtime Error，需要設定遞迴深度。
因為所求為閱讀第1本書之前需要閱讀哪些書，所以對第一個節點做DFS即可，輸出時忽略此節點。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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)

題意

在一個坐標系中有若干個檢查點，你需要依序經過這些檢查點，所求為走過的歐幾里得距離總和。你也可以選擇忽略一些檢查點不走，但如果跳過了 kk 個檢查點，最終的距離將要加上 2k−12^{k-1} 作為懲罰，求考慮懲罰後最短的距離。

思路：動態規劃

  • 令 dp[i][j]dp[i][j] 表示前i+1i+1個點中，跳過jj個點的最短路徑
  • 跳過jj個點的轉移方程：dp[i+j+1][k]=min(dp[i+j+1][k],dp[i][k−j]+distance)dp[i+j+1][k] = min(dp[i+j+1][k], dp[i][k-j] + distance)
  • 最後考慮 dp[N−1][k]dp[N-1][k] ，對忽略的點數量 kk 分別計算其懲罰，最後輸出最小值。
  • 因為懲罰為 2k−12^{k-1}，可以猜測若忽略的點數量過多，則懲罰會大到無法構成最佳解，因此可以設定 kk 的邊界，此處我設定成30。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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)