資工程式設計 一

資訊

程式碼範例都是用 Python 撰寫的。

題目

找出兩個字串的距離

令 $s, t$ 為兩個長度相等的字串，找出重新排序後兩個字串的最小距離是多少。舉例來說，yajusenpai 跟 pineapples 的距離 $d(s, t)$ 是 4，因為我們可以把 yajusenpai 重新排序成 pineayajus。

由於我們只需要知道 $d(s, t)$，並且輸入只包含了小寫的英文字母，因此我們可以透過建立一個長度為 26 的串列，紀錄下每個字母的出現次數，就可以快速算出總共有多少字母是可以匹配的。

我們分別用 count_s 和 count_t 來紀錄下每個字母出現的次數，取兩個值的最小值就是該字母最多的匹配數量。對於 yajusenpai 跟 pineapples 來說：

字母	count_s	count_t	min(count_s, count_t)
a	2	1	1
e	1	2	1
i	1	1	1
j	1	0	0
l	0	1	0
n	1	1	1
p	1	2	1
s	1	1	1
u	1	0	0
y	1	0	0

求出所有的匹配的字母數量總和之後，只要減去原字串的長度，就是不匹配的字母數，也就是題目所問的距離 $d(s, t)$。

s = input()
t = input()

count_s = [0] * 26 # 建立兩個長度為 26 的空串列
count_t = [0] * 26
matches = 0

for c in s: # 遍歷 s 跟 t，將出現次數存進 count_s 跟 count_t
    idx = ord(c) - ord('a')
    count_s[idx] += 1
for c in t:
    idx = ord(c) - ord('a')
    count_t[idx] += 1
    
for i in range(26): # 遍歷所有小寫字母，求出所有匹配的字母數量
    matches += min(count_s[i], count_t[i])

print(len(s) - matches) # 字串長度 - 匹配數 = 兩個字串的距離

找出方陣中某點所在欄、列與對角線的總和

一個大小為 $N \times N$ 的方陣（Square Matrix），提供 $M$ 個中心點的座標 $(x, y)$，求出該點所在欄、列與對角線的數值總和。

如果我們每遇到一個座標就計算一次數值總和，時間複雜度會是 $O(NM)$，如果預先計算好各欄、各列，與那那兩條對角線的總數的話，時間複雜度會是 $O(N^2 + M)$。那麼，那 $NM$ 的關係是什麼樣的時候，預先計算好數量才會更有效率呢？

$$MN = N^2 + M \;\Rightarrow\; M = \frac{N^2}{N - 1} \approx N \;\Rightarrow\; M > N$$

在這個題目中，我們考慮的情況是 $N \le 1024, M \le 200000$，因此顯然應該採用預先計算的做法。

---

我們先宣告需要計算的數值的陣列大小。因為是方陣，所以欄跟列的數量都會是 $N$，而對角線的數量則比較特別一些。

陣列是從零開始的索引（0-indices），對於左上到右下的對角線而言，每一條線都對應到一個固定的 $r-c$ 值，其中 $r, c \in [0, n-1]$，因此 $r-c$ 的是範圍是 $r-c \in [-(N-1), (N-1)]$，可得對角線條數為 $|-(N-1) - (N-1)| + 1 = 2N - 1$。

相似地，對於右上到左下的對角線而言，每一條線都對應到一個固定的 $r+c$ 值，其中 $r, c \in [0, n-1]$，因此 $r+c$ 的是範圍是 $r+c \in [0, 2(N-1)]$，可得對角線條數同為 $|2(N-1)| + 1 = 2N - 1$

以 $N = 3$ 的方陣為例：

$$\textbf{(r, c) coordinates} \qquad \begin{bmatrix} (0,0) & (0,1) & (0,2) \\ (1,0) & (1,1) & (1,2) \\ (2,0) & (2,1) & (2,2) \end{bmatrix}$$ $$\textbf{Values of } (r - c) \qquad \begin{bmatrix} 0 & -1 & -2 \\ 1 & 0 & -1 \\ 2 & 1 & 0 \end{bmatrix}$$ $$\textbf{Values of } (r + c) \qquad \begin{bmatrix} 0 & 1 & 2 \\ 1 & 2 & 3 \\ 2 & 3 & 4 \end{bmatrix}$$

row = [0] * N
col = [0] * N
diag1 = [0] * (2 * N - 1)
diag2 = [0] * (2 * N - 1)

再來，我們就可以遍歷方陣 $N$ 的資訊，並且將欄、列與對角線的數值總和存入我們剛剛宣告的四個陣列。在這兩個迴圈中，我們技巧性的以 $(r, c)$ 作為索引值、val 為該格的資料，方便進行資料的儲存。

• row[r] += val：將 val 存進 row[r] 中。
• col[c] += val：將 col 存進 col[c] 中。

這裡比較特別的是 diag1 的索引，因為 $r-c \in [-(N-1), (N-1)]$，但陣列是從零開始的索引，因此我們會需要將 diag1 的索引加上 $(N-1)$，將其平移到從零開始。

for r in range(N):
    vals = list(map(int, input().split())) # 以列為單位讀入陣列 matrix
    matrix.append(vals) # NxN 的方陣
    
    for c, val in enumerate(vals):
        row[r] += val
        col[c] += val
        diag1[r-c+N-1] += val
        diag2[r+c] += val

將欄、列與對角線的數值總和計算好後，我們就可以開始處理 $M$ 筆座標的總和。這裡要注意的是，因為 $M \le 200000$，如果我們一開始就把所有的 $M$ 存起來的話，很有可能會遇到記憶體不足的問題，因此這裡我們採用一次讀入一筆、輸出一筆的策略。

分別取得 $(r, c, d1, d2)$ 的索引值之後，就可以從剛剛計算好的四個串列取值。最後要 $-3 \times matrix[r][c]$ 的原因是要扣掉重複計算的該點數值。

for _ in range(M):
    t = tuple(map(int, input().split())) # 將座標以 tuple 讀入 t
    r, c = t
    d1 = (r - c) + (N - 1)
    d2 = r + c
    result = row[r] + col[c] + diag1[d1] + diag2[d2] - 3 * matrix[r][c]
    print(result)

完整的程式碼如下：

M = int(input()) # 有 M 筆測資
N = int(input()) # 方陣大小為 N

matrix = []

row = [0] * N
col = [0] * N
diag1 = [0] * (2 * N - 1)
diag2 = [0] * (2 * N - 1)

for r in range(N):
    vals = list(map(int, input().split())) # 以列為單位讀入陣列 matrix
    matrix.append(vals) # NxN 的方陣
    
    for c, val in enumerate(vals):
        row[r] += val
        col[c] += val
        diag1[r-c+N-1] += val
        diag2[r+c] += val
        
for _ in range(M):
    t = tuple(map(int, input().split())) # 將座標以 tuple 讀入 t
    r, c = t
    d1 = (r - c) + (N - 1)
    d2 = r + c
    result = row[r] + col[c] + diag1[d1] + diag2[d2] - 3 * matrix[r][c]
    print(result)

找出有幾組正整數 $(a, b, c, d)$ 使得 $abc + d = n$

若 $n = 4$ 的話，則 $(a, b, c, d)$ 有七種可能：

$$(1,1,1,3), (1,1,2,2), (1,1,3,1), (1,2,1,2), (1,3,1,1), (2,1,1,2), (3,1,1,1)$$

我們當然可以使用暴力法來枚舉所有可能的 $(a, b, c, d)$ 組合，且因為 $d$ 可以是任意 $\ge 1$ 的正整數，所以我們可以將題目的要求簡化成 $abc \le n-1$ 且 $(a, b, c) \in [1, n]$。

# O(n^3)

n = int(input())
limit = n-1
ans = 0

for a in range(1, limit+1):
	for b in range(1, limit+1):
		for c in range(1, limit+1):
			if a*b*c <= limit:
				ans += 1

這個解法的時間複雜度為 $O(n^3)$，因為我們使用了三層迴圈來枚舉 $a, b, c$ 的所有可能性。因此，我們需要一個更有效率的演算法。

首先，因為我們不需要知道 $c$ 確切是哪些數字，所以我們可以由一開始的要求 $abc \le n-1$，求出 $c$ 的最大值 $c_{max}$：

$$c_{\max} = \left\lfloor \frac{n - 1}{a b} \right\rfloor$$

此外，我們也可以再考慮 $b$ 的上限。由 $abc \le n-1$ 可得 $b \le \frac{n-1}{ac}$，為了讓 $b$ 最大，$c$ 的最小值為 $1$，因此 $b_{max} = \left\lfloor \frac{n-1}{a} \right\rfloor$。

# O(n log(n))

n = int(input())
limit = n-1
ans = 0

for a in range(1, limit+1):
	for b in range(1, limit // a + 1):
		ans += limit // (a*b)

這樣就可以把時間複雜度優化到 $O(n \log n)$，並且我們還可以再更進一步優化。

---

我們現在的答案 $\left\lfloor \frac{n - 1}{a b} \right\rfloor$（也就是 $c_{max}$）在固定的 $a$ 下，其實只會在某些特定點改變。令 $q = \left\lfloor \frac{n - 1}{a b} \right\rfloor$，因為 $q$ 是向下取整後的商，即使分母 $ab$ 增加，只要 $q$ 還沒有超過下一個整數值，那麼 $q$ 就不會改變。也就是說，在某些 $[b, b_2]$ 區間 $q$ 的值會是相同的。

所以，只要我們能知道 $b_2$ 的位置，我們的計算就可以進一步簡化成 $(b_2 - b + 1) \times q$。那麼要怎麼知道 $b_2$ 的位置呢？根據取整函數的定義，我們知道 $q \le \frac{n-1}{ab} \lt q + 1$，整理左邊的不等式即可得出 $b_2 = \left\lfloor \frac{n-1}{qa} \right\rfloor$。

# O(n)

n = int(input())
limit = n-1
ans = 0

for a in range(1, limit+1):
	b = 1
	while b <= limit // a:
		q = limit // (a*b)
		b2 = limit // (q*a)
		ans += (b2 - b + 1) * q
		b = b2 + 1 # 從 b2 的下一個值再開始考慮

這樣就可以把時間複雜度優化到 $O(n)$。

演算法

最大子數列問題（Maximum Subarray Problem）

假設一個數列為 $(-2, -3, 4, -1, -2, 1, 5, -3)$，它的最大子數列和是 7，因為 $4 + (-1) + (-2) + 1 + 5 = 7$ 。

如果我們使用暴力法，就必須嘗試所有的連續子數列組合。一個長度為 $n$ 的陣列，會有 $n(n+1)/2$ 個子數列，時間複雜度為 $O(n^2)$。因此，我們需要一個更有效率的演算法來快速求出最大子數列的和。

Kadane's algorithm

Kadane 的想法非常直覺，只需要使用兩個變數並遍歷數列一次。

• current_sum：當前正在追蹤的子數列總和
• best_sum：遇過的最大子數列總和

每讀到一個新數字時，就決定要「延續目前的子數列」，還是「從這個數字重新開始」。換句話說，如果 current_sum + n[i] 比 n[i] 還要大的話，就要延續目前的子數列；如果n[i] 比 current_sum + n[i] 還要大的話，代表重新開始會獲得更大的值。

這樣就能在一次掃描中完成計算，時間複雜度會優化成 $O(n)$。

def max_subarray_kadane(numbers):
    best_sum = float('-inf') # 負無限小
    current_sum = 0
    
    for x in numbers:
        current_sum = max(x, current_sum + x)
        best_sum = max(best_sum, current_sum)
        
    return best_sum

前綴和（Prefix sum）

除了 Kadane 的演算法之外，我們也可以透過前綴和的想法來求出最大子數列和。

假設原始數列為 $n$，我們定義他的前綴和數列 $p$ 為：

$$p[i] = n[0] + n[1] + ... + n[i]$$

那麼任意子數列區間 [l, r] 的總和，就可以用前綴差表示為：

$$n[l] + n[l+1] + ... + n[r] = p[r] - p[l-1]$$

為了求出最大的子數列和，我們會希望 $p[r]$ 盡可能大、並且 $p[l-1]$ 盡可能小。我們會需要三個變數：

• prefix：當前前綴和
• min_prefix：最小的前綴和（$p[l-1]$ 要盡可能小）
• best：遇過的最大子數列總和

每讀到一個新數字，就更新 prefix，並且以這個位置為 r 計算子數列和 prefix - min_prefix，並且跟 best 比較，若更大則更新。最後，也更新 min_prefix 確保他是最小的前綴和 p[l-1]。

這樣一樣能在一次掃描中完成計算，時間複雜度會優化成 $O(n)$。

def max_subarray_prefix(numbers):
    best = float('-inf')
    prefix = 0
    min_prefix = 0  # 最小前綴和

    for x in numbers:
        prefix += x
        best = max(best, prefix - min_prefix)
        min_prefix = min(min_prefix, prefix)

    return best