這題是很典型的連續背包問題。結論非常簡單：只要不斷貪婪地將單位重量價值最大的礦砂放進背包，直到背包已滿或所有礦砂均已被放入，就能最大化總價值。
一個簡單的做法是將所有礦砂依照單位重量價值由大到小排序，依序放入背包直到滿即可。複雜度是 $O(n \log n)$。
雖然並不是本題的考點，但有一個值得一提的 $O(n)$ 做法存在。以下為了方便說明，假定所有的 $x_i$ 均相異。
演算法與 quickselect 非常相似，期望時間複雜度為 $O(n)$。
這題是一道最短路徑的問題，但給定的限制中有幾個點要注意：
條件 1 保證這張圖存在拓樸排序，求解可用 top-down DP，或找出拓樸排序後用 bottom-up DP。
// ord = 拓樸排序的點順序
// fr[x] = 連到 x 的所有點
fill(dis, dis+n+1, INF);
dis[1] = 0;
for (int i=1; i<=n; i++) {
int p = ord[i];
// 找所有能連到 p 的點 j，更新 p 的最短距離
for (Edge j: fr[p]) dis[p] = min(dis[p], dis[j.to] + j.weight);
}
以上的做法複雜度是 $O(n+m)$，可以在限制內解完所有測資。
值得一提的是這題有幾個預設的錯誤解法：
把給定的 $X$ 拆成兩個不相交集合 $X_1$ 和 $X_2$，再暴力求出所有樣本和 $X_1$ 及 $X_2$ 的交集狀況就可以了。由於集合的拆法有 $O(2^m)$ 種且枚舉完以後需要花 $O(n)$ 檢查，總時間複雜度為 $O(2^m \times n)$ (其中 $m$ 為 $X$ 的字元種類數)。
要怎麼實作得比較簡潔是這一題的重點，這裡給一些小技巧供參考：
一個集合可以用一個 int 儲存，其中第 $i$ 個 bit 記錄這個集合有沒有第 $i$ 個元素。接下來就能利用 bitwise and/or 等內建運算來算出題目大部分的所求。如果不喜歡位元運算，C++ 也有提供 std::bitset 以協助實作。
若用 int 儲存集合，可以用一個 for 迴圈枚舉所有的子集合。
for (int i=x; ; i=(i-1)&x) {
cout << i << '\n';
if (i==0) break;
}
這個迴圈枚舉並輸出 $x$ 的每個子集合 $i$，是常見且有效率的寫法。
題目所求的 $P_5$ 是比較難算的部分，但仔細想一想可以發現 $P_5$ 只能是 $0$ 或 $2$。以下簡單說明：
當然這題測資範圍並不要求觀察出這個結論，即使枚舉所有的子集合仍然能拿到滿分。
換個方式來思考這一題：假設每次機器在選定最小重量的袋子後，由你決定放入哪顆水果。那麼這題存在一個非常簡單的結論：如果給定的包裝結果是可能的，只要重量越輕的水果越先放，總是能達成該包裝結果。
或許這個結論不難猜，但要好好證明也許會花點時間。假設題目給定的包裝是存在解的，也就是存在一個解的序列：
\[(b_1, w_1), (b_2, w_2), \cdots,(b_n, w_n).\]這裡用 $(b_i, w_i)$ 代表第 $i$ 步驟的水果放在第 $b_i$ 袋，且放的水果重量為 $w_i$。
我們將焦點放在這個解序列中，由「放入相同袋子的兩步驟」所形成的子區間：
\[(b, w_1), \cdots, (b, w_2).\]可以發現上述序列若 $w_1 > w_2$，我們其實可以交換這兩個步驟的順序，且合法的解仍然存在：
\[(b, w_2), \cdots, (b, w_1), \cdots\]儘管交換後 $b$ 一度變輕導致 $(b, w_1)$ 可能會比原本 $(b, w_2)$ 的位置還前面，我們發現在放完 $w_1$ 後，只要這個子區間的水果還沒被放完，$b$ 就不會是最輕的，因此這樣的操作是合法的。（當然，對放水果順序的影響只會出現在注目的子區間內，子區間外的所有順序都無需改動。）
經過複數次上述「交換同袋子水果順序」的操作以後，我們可以將任意一個解的序列交換成對每個袋子而言收到的水果重量皆為從小到大。由於任意解的順序都可以經由以上的交換得到同一個序列，若從小拿到大仍然無法滿足題目給定的包裝，代表無解。
實作上我們會需要一個資料結構可以
只要將包裝結果中的每個袋子的水果依重量排序，便可隨時查出該將哪個水果放入袋子中；找出最輕的袋子與更新重量部分，可以用堆積或 std::priority_queue 維護，在 $O(\log m)$ 時間完成每個操作。因此整體的複雜度為 $O(n(\log n+\log m))$。
首先這題有一個簡單的 naïve $O(n^3)$ 做法:
for (int i=1; i<=n; i++) {
for (int j=i+1; j<=n; j++) {
if (have_common_friends(i, j))
answer++;
}
}
計算 have_common_friends() 最簡單的方法是寫一個迴圈，需時 $O(n)$。
我們利用 std::bitset f[i] 的第 $j$ 個 bit 記錄 $i$ 和 $j$ 是不是朋友，以優化上述 have_common_friends() 的迴圈實作。想求 $i$ 和 $j$ 有沒有共同朋友時，可用 std::bitset 的 and 運算與 method any() (i.e. (f[i] & f[j]).any()) 得出。
由於 std::bitset 的實作方式為 bit array，執行時間會比一般的陣列快數十倍以上。當然自己用陣列來實作 bit array 也是可行的：
unsigned bit(int x) {
return 1u << x;
}
void add_friend(int i, int j) {
j--;
f[i][j/32] |= bit(j%32);
}
bool have_common_friends(int i, int j) {
int len = (n+31) / 32;
for (int k=0; k<len; k++) {
if (f[i][k] & f[j][k]) return true;
}
return false;
}
從題敘中的圖 1 可以觀察到所有的商店服務範圍都是一個 $45$ 度的正方形，要怎麼把這題的座標轉 $45$ 度好好用區間資料結構維護就是這一題的重點。
考慮將平面上的所有點做如下的變換：
\[\begin{pmatrix}x\\ y\end{pmatrix} \mapsto \begin{pmatrix}x'\\ y'\end{pmatrix} := \begin{pmatrix}x+y\\ x-y\end{pmatrix}.\]可以發現變換前兩點 $(x_1, y_1), (x_2, y_2)$ 的曼哈頓距離
\[|x_1-x_2| + |y_1-y_2|,\]等於變換後兩點 $(x_1’, y_1’), (x_2’, y_2’)$ 的切比雪夫距離
\[\max\\\{|x_1'-x_2'|, |y_1'-y_2'|\\\}.\]在變換後原 $(x, y, r)$ 的範圍就會變成以新座標 $(x+y, x-y)$ 為中心，邊長 $2r$ 且邊平行於 $x, y$ 軸的正方形，也就是說一個映射後的座標 $(a’, b’)$ 若滿足
\[\begin{cases}x'-r\leq a'\leq x'+r,\\ y'-r\leq b'\leq y'+r,\end{cases}\]則 $(a, b)$ 與 $(x, y)$ 的曼哈頓距離在 $r$ 以內。注意題目所求為變換前的整數點，而變換後的某個整數點 $(x’, y’)$ 在變換前也是整數點 (i.e. $(\frac{y’-x’}{2}, \frac{y’+x’}{2}) \in \mathbb{Z}^2$) 的充分必要條件是 $x’\equiv y’\ (\operatorname{mod}2)$，必須小心處理奇偶性問題。
值得一提的是這個變換在程式競賽中頗常見，例如 IOI2017 的 pair 也出現一樣的技巧。上面連結的解析裡面有對這個變換的證明，如果讀者對旋轉矩陣不熟，推薦可以直接把這個變換記起來。
做完上述變換後，在不考慮題目問的是整數點的情況下，可以把題目簡化成這樣：
平面上有一些與 $x,y$ 軸平行的矩形，每塊矩形皆有權重。定義一個點的點負重為所有覆蓋該點的矩形的權重和，請求出點負重的最大值。
這個問題是一個含有區間更新的 2D RMQ 問題，但因為所有矩形為已知，可以離線利用掃描線掃其中一軸，並用線段樹或平衡二元搜尋樹維護掃描線上的最大值，時間複雜度 $O(n \log n)$。
由於原始題目有 $x’\equiv y’\ (\operatorname{mod}2)$ 這個條件，無法直接套用上述的演算法，必須做一些處理。這裡提供兩個參考做法：
這個將 2D 問題轉成掃描線降維的技巧相當著名，一個應用是計算二維的矩形面積覆蓋問題 (ref1, ref2)，有 $40$ 多年的歷史了。由於這個技巧在網路上可以找到的資源非常多，限於篇幅這裡就不詳細介紹了，對此技巧不熟的讀者也能從學著做這題開始。
本節假定讀者知道什麼是機率分佈與隨機變數，並了解「一組隨機變數為 iid (independent and identically distributed，獨立同分佈)」的意思。此外，為了討論方便，以下先約定一些符號：
直接用矩陣乘法定義計算 $\mathbf{AB}$ 需要 $O(n^3)$ 時間，這在 $n=2800$ 時並沒有辦法在時限內完成計算；另一方面，相乘結果 $\mathbf{AB}$ 稀疏並不保證 $\mathbf{A}$ 和 $\mathbf{B}$ 也是稀疏，故改用稀疏矩陣乘法也不能改善效率。但
設 $\mathbf{v} \in \mathbb{Z}_p^n$。若 $\mathbf{C}$ 的第 $i$ 列全為 $0$，則我們有 $(\mathbf{Cv})_i = 0$；若 $\mathbf{C}$ 的第 $i$ 列有任一元素 (aka $c_{ij}$) 非 $0$，直覺告訴我們當 $p$ 夠大且 $\mathbf{v}$ 為隨機時，第 $i$ 個分量 $(\mathbf{Cv})_i = c_{i1}v_1+c_{i2}v_2+\ldots+c_{in}v_n$ 有很大機會不為 $0$。以下讓我們把這件事情好好地寫下來並加以證明，讓妄想成為現實。
[定理A] 設 $X_1, X_2, \ldots, X_n \sim \mathcal{U}(\mathbb{Z}_p)$ 為 iid。若 $c_1, c_2, \ldots, c_n \in \mathbb{Z}_p^\times$，則我們有
\(c_1X_1 + c_2X_2 + \ldots + c_nX_n \sim \mathcal{U}(\mathbb{Z}_p).\)
我們對 $n$ 用數學歸納法來證明。當 $n = 1$ 時，設 $x \in \mathbb{Z}_p$，則有
\[\mathbb{P}[c_1X_1 = x] = \mathbb{P}[X_1 = x/c_1] = 1/p.\]注意 $x$ 可以是任意的，故 $c_1X_1 \sim \mathcal{U}(\mathbb{Z}_p)$。
當 $n \geq 2$ 時，設 $x \in \mathbb{Z}_p$，則有
\[\begin{split} \mathbb{P}[c_1X_1 + \ldots + c_nX_n = x] &= \sum_{y\in\mathbb{Z}_p}\mathbb{P}[c_1X_1 + \ldots + c_{n-1}X_{n-1} = y,\ c_nX_n = x-y]\\ &= \sum_{y\in\mathbb{Z}_p}\mathbb{P}[c_1X_1+\ldots+c_{n-1}X_{n-1}=y]\mathbb{P}[c_nX_n = x-y]\\ &= \sum_{y \in \mathbb{Z}_p}(\frac{1}{p})(\frac{1}{p}) = 1/p. \end{split}\]上式的第二行用到了不同 $X_i$ 之間的獨立性，而第三行用到了歸納法假設與 $n=1$ 的結論。又 $x$ 可以是任意的，本定理得證。
我們把定理A寫成比較容易用的形式：
[推論A] 設 $X_1, X_2, \ldots, X_n \sim \mathcal{U}(\mathbb{Z}_p)$ 為 iid。已知 $c_1, c_2, \ldots, c_n \in \mathbb{Z}_p$ 並令 $Y = c_1X_1 + c_2X_2 + \ldots + c_nX_n$，則
我們用以下的函式來展示演算法是怎麼進行的。這個函式接受兩個參數 $\mathbf{A’} \in \mathcal{M}_{r\times n}(\mathbb{Z}_p), \mathbf{B’} \in \mathcal{M}_{n\times m}(\mathbb{Z}_p)$，回傳 $\mathbf{C’} = \mathbf{A’B’} \in \mathcal{M}_{r\times m}(\mathbb{Z}_p)$ 中所有非 $0$ 元素的位置。初始我們將 $\mathbf{A’}\gets\mathbf{A}, \mathbf{B’}\gets\mathbf{B}$ 傳入這個函式。
計算 $\mathbf{C’v_i} = \mathbf{A’}(\mathbf{B’v_i})$ 需要 $O(n(m+r))$ 時間。考慮在同一遞迴深度下的所有函式呼叫，我們有
因此每一層遞迴呼叫的總計算量為 $O(tn^2)$。最後由 $\mathbf{B}$ 的大小為 $n\times n$ 可知最大遞迴深度為 $O(\log n)$，故時間複雜度為 $O(tn^2 \log n)$。
上述的演算法並不保證 $100\%$ 能得出正確的結果。由推論 A 知，若 $\mathbf{C’}$ 的第 $i$ 列不全為 $0$，則對任意 $j \in {1, 2, \ldots, t}$，可以發現 $(\mathbf{C’v_j})_i = c_{i1}(\mathbf{v_j})_1+c_{i2}(\mathbf{v_j})_2+\ldots+c_{in}(\mathbf{v_j})_n$ 仍有 $1/p$ 的機率為 $0$，亦即一個不全為 $0$ 的列被誤判的機率為 $1/p^t$。在同一遞迴深度下最多只有 $2n$ 個不全為 $0$ 的列，而最大遞迴深度為 $\lceil\log_2 n\rceil+1$，可知完整的計算過程中，至少一列被判錯的機率不高於
\[\frac{2n (\lceil\log_2 n \rceil+1)}{p^t} \leq \frac{5600\cdot13}{37^t} = 72800/37^t.\]於是只要挑 $t = 5$，即可讓錯誤的機率降低至不到 $1\%$。
一個值得注意的是，唯有每個 $j$ 皆滿足 $(\mathbf{C’v_j})_i = 0$ 時，才能斷定 $\mathbf{C’}$ 的第 $i$ 列全為 $0$；如果做法不同，可能會對錯誤率的估計造成很大的影響。以下介紹本題的另一個做法：設定 $t=1$ 並呼叫函式 $s$ 次，最後把得到的結果 (i.e. 非 $0$ 元素位置所形成的集合) 取聯集。儘管看起來跟原做法很像，上一段的估計並不能使用，實際測試 $s = 5$ 大部分時候也會得到錯誤的結果，必須重新為這個演算法估計出錯機率。
考慮 $\mathbf{C}$ 的一個非 $0$ 元素 $c_{ij}$，不妨假設某次呼叫 $c_{ij}$ 被分到 $\mathbf{C’}$ 的第 $i’$ 列。如果 $(\mathbf{C’v_1})_{i’} = 0$，那麼 $c_{ij}$ 就不會被發現。由於遞迴深度不超過 $13$，我們知道 $c_{ij}$ 沒被發現的機率不超過 $1-(36/37)^{13} < 0.3$，故呼叫函式 $s$ 次均沒有被發現的機率不超過 $0.3^s$。另，由非 $0$ 元素個數不超過 $2n \leq 5600$ 個，可知計算完成後，有非 $0$ 元素沒被找出來的機率不超過 $5600\cdot0.3^s$，於是只要取 $s = 11$，即可讓錯誤的機率降低至不到 $1\%$。
在這個子任務中，乘積 $\mathbf{C}$ 的每列只有一個非 $0$ 元素，不妨設第 $i$ 列的非 $0$ 元素的值為 $c_i$，位置在 $(i, j_i)$ 吧。首先觀察
\[\mathbf{C}\begin{pmatrix}1\\ 1\\ \vdots\\ 1\end{pmatrix} = \begin{pmatrix}c_1\\ c_2\\ \vdots\\ c_n\end{pmatrix}.\]這樣一來就能在 $O(n^2)$ 時間內知道 $c_i$ 了。這個子任務中另一個比較容易被忽略的條件是 $p \geq 2801$，這代表 $p > n$。這樣一來我們有
\[\mathbf{C}\begin{pmatrix}1\\ 2\\ \vdots\\ n\end{pmatrix} = \begin{pmatrix}c_1j_1\\ c_2j_2\\ \vdots\\ c_nj_n\end{pmatrix}.\]只要求得 $c_i$ 在 $\mathbb{Z}_p^\times$ 下的反元素，便能推出 $j_i$。這不僅是正確機率 $100\%$ 的演算法，時間複雜度還只要 $O(n^2)$。
在這個子任務中，修改一開始介紹的「隨機」演算法，便能得到一個 $100\%$ 正確的做法。取
\[\mathbf{v_1} = \begin{pmatrix}1\\ 1\\ \vdots\\ 1\end{pmatrix}, \mathbf{v_2} = \begin{pmatrix}1\\ 2\\ \vdots\\ m\end{pmatrix}\]用這兩個向量測試保證可以找出所有的非 $0$ 元素。因為若 $c_{i,x}$ 與 $c_{i,y}$ $(x \neq y)$ 非 $0$，用 $\mathbf{v_1}$ 誤判出 $0$ 的條件是 $c_{i,x} + c_{i,y} = 0$，而此時
\[(\mathbf{Cv_2})_i = c_{i,x} x + c_{i,y} y = (c_{i,x} + c_{i,y})x + c_{i,y}(y-x) = c_{i, y}(y-x).\]由於 $m \leq n < p$，我們有 $y-x \neq 0$，因此 $(\mathbf{Cv_2})_i = c_{i,y}(y-x) \neq 0$。
時間複雜度如同前面分析過的，為 $O(n^2 \log n)$，但這次演算法 $100\%$ 會得出正確的結果。
首先要湊到的路徑數最大是 $10^{18}$ 種，能湊到這麼多走法且周長最小的地圖是 $33 \times 33$，走法數 $\binom{64}{32} \approx 1.8 \times 10^{18}$。
注意此時半周長為 $66$，和題目要求的上限 $90$ 相差不到一半，可以擴展的空間其實不多。解題的時候如果能意識到「用加法的構造法」(i.e. 把 $T$ 分解成多個數字再分別加起來的構造法，或者是類似的遞迴構造法) 窒礙難行，可能會是一個非常有幫助的提示。
如果往乘法的方向來構造解答的話，可以發現一個可行的方向是利用進位制來操作。下面為 $2$ 進位的例子：
| $1$ | $1$ | $1$ | $1$ |
|---|---|---|---|
| $1$ | - | - | - |
| $1$ | - | $x$ | $\bar{x}$ |
| $1$ | - | $|x$ | $2x$ |
| $1$ | $1$ | $1$ | $1$ |
|---|---|---|---|
| $1$ | - | - | - |
| $1$ | - | $x$ | $\bar{x}$ |
| $1$ | $\bar{1}$ | $x+1$ | $2x+1$ |
這裡用豎線與頂線代表左邊與上面的閘門。以上兩圖為例，如果在地圖的最上方與最左方留下一列及一行 $1$，可以透過操作閘門來將任意一個數字 $x$ 變成 $2x$ 或者 $2x+1$。依照上述的方法將 $T$ 拆成 $2$ 進位來構造可以得到一個 $n+m = 121$ 左右的解，得分為 $38$ 分。
多進位的思考方式和 $2$ 進位差不多，主要的差別是細節處理的 case 會比較多。以 $6$ 進位為例：
| $1$ | $1$ | $1$ | $1$ | $1$ |
|---|---|---|---|---|
| $1$ | - | - | - | - |
| $1$ | - | $x$ | $\bar{x}$ | $\bar{x}$ |
| $1$ | - | $|x$ | $2x$ | $3x$ |
| $1$ | - | $|x$ | $3x$ | $6x$ |
這裡要注意的是上面以及左邊的兩道門，如果將門打開的話讓最上面／最左邊的 $1$ 直接進到構造區域的話可以調整最終 $6x$ 那格的大小。
運用這兩個 $+3$ 及 $+1$ 的閘門可以湊出 $6x$ 到 $6x+5$ 間的所有整數。以 $6x+5$ 為例，我們開 $3$ 個門 $3+1+1$ 來湊出餘數 $5$：
| $1$ | $1$ | $1$ | $1$ | $1$ |
|---|---|---|---|---|
| $1$ | - | - | $|1$ | $|1$ |
| $1$ | - | $x$ | $x+1$ | $x+2$ |
| $1$ | - | $|x$ | $2x+1$ | $3x+3$ |
| $1$ | $\bar{1}$ | $x+1$ | $3x+2$ | $6x+5$ |
在 $6$ 進位的例子中，每湊一個位數需要多 $2$ 列及 $2$ 行。由於 $10^{18}$ 寫成 $6$ 進位會有 $24$ 位數，構造出的地圖半周長 $n+m$ 的最大值是 $4 + (2+2) \times 24 = 100$。
類似地也有 $10$ 進位用 $4\times3$ 方格的構造法，每湊一個位數需要多 $3$ 列及 $2$ 行，構造出的地圖半周長為 $4 + (2+3) \times 19 = 99$。
再更往上的進位構造方法仍然類似，但細節又再更複雜一些。以 $20$ 進位為例：
| $1$ | $1$ | $1$ | $1$ | $1$ | $1$ |
|---|---|---|---|---|---|
| $1$ | - | - | - | - | - |
| $1$ | - | $x$ | $\bar{x}$ | $\bar{x}$ | $\bar{x}$ |
| $1$ | - | $|x$ | $2x$ | $3x$ | $4x$ |
| $1$ | - | $|x$ | $3x$ | $6x$ | $10x$ |
| $1$ | - | $|x$ | $4x$ | $10x$ | $20x$ |
這個時候如果照之前 $6$ 與 $10$ 進位的作法，上面與左邊的門打開能影響的走法數分別為 $+10, +4, +1, +10, +4, +1$。可以發現有一些 $20$ 以內的正整數是湊不到的，這裡提供幾個解決的方向：
在最左邊放兩行可以幫助湊到一個 $2$，進而湊出 $3$ 與 $13$ 等原本湊不出來的餘數。以下圖為例可以在左邊湊出一個 $2$ 與利用上面的 $1$ 來湊出餘數 $3$：
| $1$ | $1$ | $1$ | $1$ | $1$ | $1$ | $1$ |
|---|---|---|---|---|---|---|
| $1$ | - | - | - | - | - | $|1$ |
| $1$ | - | - | $x$ | $\bar{x}$ | $\bar{x}$ | $x+1$ |
| $1$ | - | - | $|x$ | $2x$ | $3x$ | $4x+1$ |
| $1$ | $\bar{1}$ | - | $|x$ | $3x$ | $6x$ | $10x+1$ |
| $1$ | $2$ | $\bar{2}$ | $x+2$ | $4x+2$ | $10x+2$ | $20x+3$ |
這個做法完全繼承了上面 $6$ 進位的做法，只在當餘數為 $3,13$ 時才將 $2$ 拿出來湊餘數，半周長 $n+m = 89$。
在最左邊湊出一行 $5$ 的 channel，可以利用這個 channel 將 $5,10,15$ 送到構造區域的最下列，再利用上列的 $1$ 構造出 $1,2,3,4$ 的組合。
| $1$ | $1$ | $1$ | $1$ | $1$ | $1$ | $1$ | $1$ |
|---|---|---|---|---|---|---|---|
| $1$ | $2$ | $\bar{2}$ | - | - | - | - | - |
| $1$ | $3$ | $5$ | - | - | - | - | - |
| $1$ | - | $|5$ | - | $x$ | $\bar{x}$ | $\bar{x}$ | $\bar{x}$ |
| $1$ | - | $|5$ | - | $|x$ | $2x$ | $3x$ | $4x$ |
| $1$ | - | $|5$ | - | $|x$ | $3x$ | $6x$ | $10x$ |
| $1$ | - | $|5$ | - | $|x$ | $4x$ | $10x$ | $20x$ |
如上圖在 $(3,3)$ 可以湊出第一個 $5$。接著就可以利用上面的 $4$ 個 $1$ 與左邊的 $3$ 個 $5$ 才湊出所有餘數。以 $12$ 為例，需要 $2$ 個 $5$ 與 $2$ 個 $1$：
| $1$ | $1$ | $1$ | $1$ | $1$ | $1$ | $1$ | $1$ |
|---|---|---|---|---|---|---|---|
| $1$ | $2$ | $\bar{2}$ | - | - | - | $|1$ | $2$ |
| $1$ | $3$ | $5$ | - | - | - | - | $|2$ |
| $1$ | - | $|5$ | - | $x$ | $\bar{x}$ | $\bar{x}$ | $x+2$ |
| $1$ | - | $|5$ | - | $|x$ | $2x$ | $3x$ | $4x+2$ |
| $1$ | - | $|5$ | $\bar{5}$ | $|x$ | $3x$ | $6x$ | $10x+2$ |
| $1$ | - | $|5$ | $10$ | $x+10$ | $4x+10$ | $10x+10$ | $20x+12$ |
這個解法可以在第一個 $4 \times 5$ 構造出 $0$ 到 $19$ 之間的所有整數，接下來每擴張 $3$ 列 $3$ 行又會再多一位數。因此需要半周長 $87$。
做過很多動態規劃的人，這題可以練習自己想想看。
枚舉所有安排方法共 $2^n$ 種，每種方法花 $O(n)$ 時間計算最終時間，取最小值即可。時間複雜度 $O(n2^n)$，適用於第一子任務。
老練的直覺會告訴我們這題解法不是動態規劃就是貪婪。
老練關鍵：題目為一個序列每個位置要做一些決定，我們大膽假設根據前綴 $(1, 2, 3, \ldots, i-1)$ 的最佳解可以推導出前綴 $i$ 的最佳解。
設 $D_i$ 為完成工作 $1$ 到工作 $i$ 的最短時間。透過手算可以得知第一筆範例測試的 $D = 1, 2, 7, 10$。
可以發現在這個狀態設計下怎麼列轉移式都是錯的，因為工作 $i$ 做完後會根據它是在黑機或白機完成而後續產生不同效果。
由錯誤狀態（一）我們知道要多記一個維度代表工作 $i$ 是在哪裡完成的。設 $D^h_i$ 為完成工作 $1$ 到工作 $i$ 且工作 $i$ 在 $h$ 機完成的最短時間，其中 $h=0$ 代表白機，$h=1$ 代表黑機。透過手算可以得知第一筆範例測試的 $D^0 = 2, 4, 7, 12$、$D^1 = 1, 2, 9, 10$。
可以發現在這個狀態設計下列完轉移式有機會通過範例測試，但上傳後卻不能 AC，因為工作 $i$ 在白機完成的時間會根據前面有多少個連續的工作在黑機上而有不同的延遲時間。
若工作 $i$ 在 $h$ 機完成而工作 $i-1$ 在 $1-h$ 機完成，我們稱 $i$ 為一個交換點。為了方便討論，我們加入工作 $0$，其中 $b_0 = w_0 = t_0 = 0$，這樣一來所有的安排方法都至少有一個交換點 $1$。
設 $D^h_i$ 為在 $1-h$ 機完成工作 $i-1$ 的情況下，$h$ 機開始工作 $i$ 的最早可能時刻。透過手算可以得知第一筆範例測試的 $D^0 = 0, 5, 5, 10$、$D^1 = 0, 6, 6, 8$。
在這個狀態設計下，我們算完 $D^0$ 和 $D^1$ 後，枚舉最後一個交換點的 $2n$ 種可能，就能涵蓋所有的安排方法。更明確地說，我們的答案為
\[\min\left\{\min_{1\leq i\leq n}\left\{D^0_i+\sum_{k=i}^nw_k\right\}, \min_{1\leq i\leq n}\left\{D^1_i+\sum_{k=i}^nb_k\right\}\right\}.\]$D^0_1 = D^1_1 = 0$。
這邊只列出白機 (i.e. $D^0$) 的轉移式；黑機的轉移式可直接由對稱性得出。
\[D^0_i = \min_{1\leq p\leq i-1} \left(D^1_p + \max_{p\leq c\leq i-1}\left(\sum_{k=p}^c b_k + t_c\right)\right).\]其中 $p$ 為前一個交換點，亦即工作 $p$ 到 $i-1$ 都在黑機上完成而工作 $p-1$ 在白機上完成。
選定 $p$ 後轉移式有三個部分：
枚舉 $c$ 從 $p$ 到 $i-1$ 取最大值便是所有資料皆傳送到白機的時間。
直接加總計算 $\sum_{k=p}^cb_k$ 需要 $O(n)$ 時間，給定 $p$ 有 $O(n)$ 個 $c$ 要枚舉，給定 $i$ 有 $O(n)$ 個 $p$ 要枚舉，總共有 $O(n)$ 個 $D^h_i$ 要計算，時間複雜度 $O(n^4)$。
定義前綴和 $S^1_i = \sum_{k=1}^ib_k$，如此一來 $\sum_{k=p}^cb_k$ 便能簡化成 $S^1_c-S^1_{p-1}$。
預先花 $O(n)$ 時間算出 $S^1$，即可 $O(1)$ 查詢 $\sum_{k=p}^cb_k$，時間複雜度降為 $O(n^3)$。
化簡
\[\begin{split} D^0_i &= \min_{1\leq p\leq i-1} \left(D^1_p+\max_{p\leq c\leq i-1}\left(\sum_{k=p}^cb_k+t_c\right)\right)\\ &= \min_{1\leq p\leq i-1} \left(D^1_p+\max_{p\leq c\leq i-1}\left((S^1_c-S^1_{p-1})+t_c\right)\right)\\ &= \min_{1\leq p\leq i-1} \left(D^1_p - S^1_{p-1} + \max_{p\leq c\leq i-1}(S^1_c+t_c)\right). \end{split}\]對於所有的 $1 \leq l \leq r \leq n$，定義
\[E_{l, r} = \max_{l\leq c\leq r}(S^1_c+t_c).\]則轉移式可寫成
\[D^0_i = \min_{1\leq p\leq i-1} \left(D^1_p - S^1_{p-1} + E_{p, i-1}\right).\]注意我們有
\[\begin{cases}E_{i-1, i-1} = S^1_{i-1} + t_{i-1},\\E_{p, i-1} = \max\{E_{p+1, i-1}, S^1_p+t_p\}, &\text{if }p < i-1.\end{cases}\]如此一來 $E_{\cdot, i-1}$ 就能在 $O(n)$ 時間內算出，時間複雜度降為 $O(n^2)$，已可通過第二子任務。
為了進一步降低時間複雜度，我們試著利用 $D^0_i$ 算過的部分來計算 $D^0_{i+1}$。
首先觀察，如果 $S^1_i + t_i < S^1_{i-1} + t_{i-1}$，則：
但是世界沒有這麼簡單，當 $S^1_i + t_i \geq S^1_{i-1} + t_{i-1}$ 時無法直接從 $D^0_i$ 推出 $D^0_{i+1}$，我們必須考慮更多。
考慮一個 $5$-tuple 序列 $T_i = \left((L_{i, j}, R_{i, j}, A_{i, j}, B_{i, j}, C_{i, j})\right)_{j=1}^{m_i}$，其中：
我們想將 $T_i$ 更新成 $T_{i+1}$。注意當 $i$ 固定時，$E_{p, i-1}$ 對 $p$ 而言為遞減序列，故 $A_{i, j}$ 對 $j$ 而言亦為遞減序列。若 $m_i = 0$ 或 $S^1_i + t_i < S^1_{i-1} + t_{i-1}$ (i.e. $E_{i-1, i} > E_{i, i}$)，只要在 $T_i$ 結尾插入
\[\left(i, i, S^1_i+t_i, D^1_i-S^1_{i-1}, \min\left\{C_{i, m_i}, (S^1_i+t_i)+(D^1_i-S^1_{i-1})\right\}\right),\]就得到 $T_{i+1}$ 了，和稍早前我們推出的轉移式吻合。另一方面，當 $S^1_i + t_i \geq S^1_{i-1} + t_{i-1} = A_{i, m_i}$ 時，由 $A_{i, j}$ 對 $j$ 的單調性可知，存在某個 $j^\star \in [1, m_i]$ 使得：
只要從 $T_i$ 把 $[j^\star, m_i]$ 區間的 $5$-tuple 刪除，並在結尾插入
\[\left(L_{i, j^\star}, i, S^1_i + t_i, \min\left\{\min_{j^\star\leq j\leq m_i}B_{i, j}, D^1_i - S^1_{i-1}\right\}, \min\left\{C_{i, j^\star-1}, (S^1_i+t_i) + \min\left\{\min_{j^\star\leq j\leq m_i}B_{i, j}, D^1_i - S^1_{i-1}\right\}\right\}\right),\]就能得到 $T_{i+1}$。
每次更新需要 $O(n)$ 時間計算 $\min_{j^\star\leq j\leq m_i}B_{i, j}$，需要更新 $O(n)$ 次，所以時間複雜度為 $O(n^2)$，那麼爛？並沒有。注意一開始 $T_1$ 是空的，而每次更新只會插入一個 $5$-tuple。更新時若把 $d$ 個元素刪除，需要時間 $O(d)$，但計算過程中只被插入 $O(n)$ 次，所以更新的總時間為 $O(n)$。
整體時間複雜度 $O(n)$，已可通過第三子任務。