AtCoder Beginner Contest 331 解題紀錄 (A - E)

AtCoder Beginner Contest 331 題解 (A - E)

只寫出了4題，感覺 pD 就差臨門一腳了，繼續努力吧 ~

All problems solved by python

---

A - Tomorrow (abc331 A)

題意

給你一年的月份$M$和每月的天數$D$，給定一個日期 $y$年$m$月$d$日，輸出明天的日期。

思路：簡單模擬

將日期+1後計算有沒有溢位即可。

M, D = map(int, input().split())
y, m, d = map(int, input().split())

d += 1 
if d > D:
    d = 1
    m += 1
if m > M:
    m = 1
    y += 1
print(y, m, d)

---

B - Buy One Carton of Milk (abc331 B)

題意

給定需要購買的雞蛋數$N$，以及購買$6$個、$8$個、$12$個雞蛋的價格$S$、$M$、$L$，求購買 至少 $N$ 個雞蛋的最小花費。

思路：DP

令$dp[i]$表示購買$i$個雞蛋的最小花費，考慮到購買$N+d$個雞蛋的花費可能會比恰好購買$N$個雞蛋的花費還要小，因此我們可以將$dp$的大小設為$N+12$，並且初始化$dp[0]=0$，$dp[6]=S$，$dp[8]=M$，$dp[12]=min(L, S*2)$。

N, S, M, L = map(int, input().split())

MAX_N = N + 12
dp = [float("inf")] * (MAX_N+1) # dp[i]表示購買i個雞蛋所需的最小花費
dp[0], dp[6], dp[8], dp[12] = 0, S, M, min(L, S * 2)
for i in range(13, MAX_N+1):
    dp[i] = min(dp[i - 6] + S, dp[i - 8] + M, dp[i - 12] + L)
print(min(dp[N:MAX_N+1]))

---

C - Sum of Numbers Greater Than Me (abc331 C)

題意

給定一個長度為$N$的數列$A$，對於每個$A[i]$，求出數列中大於$A[i]$的元素之和。

思路：Counter + 前綴和

• 先保存數列$A$的下標和值$(val, idx)$，然後對此 $tuple$ 進行排序。
• 對於排序後的元素計算後綴和，由於要求是嚴格大於，所以計算後綴和時需要保存相同元素的個數，可以一邊排序一邊計算相同元素的個數。這邊使用Counter直接計算每個元素出現的次數。
• 最後按照原本的下標輸出答案即可。

from collections import Counter

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

ans = [0] * N

cnt = Counter(A)
nums = [(val, idx) for idx, val in enumerate(A)]
nums.sort()

suf = [0] * N # suf[i]表示nums中大於nums[i]的元素之和

for i in range(N-2, -1, -1):
    cur = nums[i][0] # 當前元素
    nxt = nums[i+1][0] # Array中的下一個元素，計算後綴和過程的前一個元素
    if cur < nxt: # 元素不相等，則後綴和為後一個元素的後綴和加上後一個元素的個數乘以後一個元素的值
        suf[i] = suf[i+1] + cnt[nxt] * nxt
    else: # 元素相等，則不能更新後綴和，後綴和為後一個元素的後綴和
        suf[i] = suf[i+1]

for i, (val, idx) in enumerate(nums): # 按照原本的順序，更新答案
    ans[idx] = suf[i]
print(*ans)

---

D - Tile Pattern (abc331 D)

題意

• 給定一個大小維 $N*N$ 的矩陣 $G$ ， $G$ 由 $'W'$ 和 $'B'$ 組成， $'W'$ 說明該坐標為白色， $'B'$ 為黑色
• 用 $N*N$ 的矩陣 $G$ 撲滿一個無限大的平面，並且將平面分成無數個 $N*N$ 的小矩形，每個小矩形中的格子顏色都是一樣的，並且顏色對應 $G[i\%N][j\%N]$
• 有 $Q$ 個詢問，每個詢問給出一個矩形的左上角坐標 $(A,B)$ 和右下角坐標 $(C,D)$ ；請問這個矩形中黑色塊的數量是多少？

思路：二維前綴和

• 首先從計算二維前綴和的角度考慮，令 $f(x, y)$ 表示從 $(0, 0)$ 到 $(x, y)$ 的矩形中黑色塊的數量，則答案為 $f(c, d) - f(a, d) - f(c, b) + f(a, b)$
• 將題目的座標轉換成一下，$(C, D) \rightarrow (C+1, D+1)$，這樣可以保證符合上述的前綴和定義

• 由於計算整個平面的二維前綴和不太實際，因此接下來需要提高計算 $f(x, y)$ 的的速度，對於 $f(x, y)$ ，我們可以將其分成四個部分，分別是 $[(0, 0), (H, W)]$ 、 $[(H, 0), (x, W)]$ 、 $[(0, W), (H, y)]$ 、 $[(H, W), (x, y)]$ ，其中 $H = x // N * N$ 表示 $x$ 的最大的 $N$ 的倍數， $W = y // N * N$ 表示 $y$ 的最大的 $N$ 的倍數。
• 先計算 $N * N$ 的平面中的二維前綴和 $pre\_sum$ ，其中 $pre\_sum[i][j]$ 表示從 $(0, 0)$ 到 $(i, j)$ 的矩形中黑色塊的數量
• 而 $[(0, 0), (H, W)]$ 這個 H * W 的矩形中的黑色塊數量可以直接計算，而 $[(H, 0), (x, W)]$ 、 $[(0, W), (H, y)]$ 、 $[(H, W), (x, y)]$ 這三個矩形中的黑色塊數量可以利用 $pre\_sum$ 來計算，因此我們可以得到各個部分的黑色塊數量，將其相加即可得到 $f(x, y)$ 的值。
  • $res1 = (x // N) * (y // N) * pre\_sum[N][N]$
  • $res2 = pre\_sum[x \% N][y \% N]$
  • $res3 = pre\_sum[x \% N][N] * (y // N)$
  • $res4 = pre\_sum[N][y \% N] * (x // N)$
• $f(x, y) = res1 + res2 + res3 + res4$

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

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

# 計算二維前綴和
pre_sum = [[0]*(N+1) for _ in range(N+1)]
for i in range(1, N+1):
    for j in range(1, N+1):
        pre_sum[i][j] = (grid[i-1][j-1] == 'B') + pre_sum[i - 1][j] + pre_sum[i][j - 1] - pre_sum[i - 1][j - 1]

# 在無限重複的平面上，計算(0, 0)到(x, y)內的黑色格子數量
def f(x, y):
    res = (x // N) * (y // N) * pre_sum[N][N]
    res += pre_sum[x % N][y % N]
    res += pre_sum[x % N][N] * (y // N)
    res += pre_sum[N][y % N] * (x // N)
    return res

for (A, B, C, D) in quries:
    C += 1
    D += 1
    print(f(C, D) - f(A, D) - f(C, B) + f(A, B))

---

E - Set Meal (abc331 E)

題意

給定長度為 $N$ 的主餐 $mains$ ， $mains[i]$ 表示主餐的價值，給定長度為 $M$ 的配菜 $sides$ ， $sides[i]$ 表示配菜的價值，給定長度為 $L$ 的限制 $limits$ ， $limits[i]$ 表示第 $i$ 個限制， $limits[i][0]$ 表示主餐的下標， $limits[i][1]$ 表示配菜的下標，不能使用這一組搭配，求最大的餐點搭配價值。

類題

• Codeforces 1574D. The Strongest Build

思路：貪心 + 二分查找優化

• 將主餐和配菜分別按照價值進行排序，然後從價值最高的主餐開始選擇，如果這個主餐和配菜的組合不在限制中，則選擇這個組合，否則選擇價值次高的主餐，直到選擇完所有的主餐或者所有的配菜。

以下思路是參考 dreamoon 大神的題解影片做出的優化，可以推廣到類題中。

• 依照排序後的值建立一個多維矩陣，若解的座標為 $(i, j, k)$ ，則 $(i+1, j, k)$、$(i, j+1, k)$、$(i, j, k+1)$ 必為不能走的位置，否則存在比 $(i, j, k)$ 更大的解。因此我們只需要檢查在多維矩陣中，在每個座標軸上，往下一個座標都不能走的位置。
• 但這樣檢查很麻煩，所以我們可以對每個限制，檢查其每個座標軸的前一個位置。若限制 $limits[i]$ 為 $(i, j, k)$ ，則可以檢查 $(i-1, j, k)$、$(i, j-1, k)$、$(i, j, k-1)$ 是否為答案即可。

比賽時提交優化後

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

limits = set()
for x, y in L:
    limits.add((x-1, y-1))

mains = [(val, idx) for idx, val in enumerate(A)]
sides = [(val, idx) for idx, val in enumerate(B)]

mains.sort(key=lambda x: x[0], reverse=True)
sides.sort(key=lambda x: x[0], reverse=True)

ans = 0
for i in range(M):
    flag = False
    for j in range(N):
        x, y = mains[i][1], sides[j][1]
        if (x, y) in limits:
            flag = True
            continue
        ans = max(ans, mains[i][0] + sides[j][0])
        break
    if not flag:
        break
print(ans)

from bisect import bisect_left

def solve() -> int:
    M, N, L = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    L = [list(map(int, input().split())) for _ in range(L)]

    limits = set()
    for x, y in L:
        limits.add((x-1, y-1))

    arrA = [(val, idx) for idx, val in enumerate(A)]
    arrB = [(val, idx) for idx, val in enumerate(B)]
    arrA.sort(key=lambda x: x[0])
    arrB.sort(key=lambda x: x[0])

    if (arrA[-1][1], arrB[-1][1]) not in limits:
        return arrA[-1][0] + arrB[-1][0]
    ans = 0
    for (i, j) in limits:
        x = bisect_left(arrA, (A[i], i)) # 二分查找 A[i] 在 arrA 中的位置 x
        y = bisect_left(arrB, (B[j], j)) # 二分查找 B[j] 在 arrB 中的位置 y
        if x > 0 and (arrA[x - 1][1], j) not in limits: # (x - 1, y) 不在限制中
            ans = max(ans, arrA[x - 1][0] + B[j])
        if y and (i, arrB[y - 1][1]) not in limits: # (x, y - 1) 不在限制中
            ans = max(ans, A[i] + arrB[y - 1][0])
    return ans

if __name__ == "__main__":
    print(solve())

---

F - Palindrome Query (abc331 F)

題意

<++>

類題

• CSES 2040 - Palindrome Queries

思路：Rollong Hash + Segment Tree

---

Reference

• ABC321 Editorial
• CSES String Section Editorial
• AtCoder Beginner Contest 331 A 至 E 題讲解 by dreamoon