# [2022.12.04] 2022 東華盃程式設計競賽

拿密碼回來的時候比賽已經開始了，於是就以金刀 template 重諺看題的分工開打。
然而那邊的電腦沒有 Notepad++、也沒有 DevC++，只有我不會用的 Code::Blocks，所以光是開檔案跟第一次成功編譯就花了十幾分鐘的時間 QQ。模板打完又一直編譯失敗，分段註解之後才發現是 `#include <bits/stdc++.h>` 的鍋，

花了約 25 分鐘，在我還在跟各種標頭檔苦戰時，重諺已經先把一些題目看完了，這是 pB：

> Problem B: Map with Two Colors
> 給你 $n$ 點 $m$ 邊的圖，請你判斷是不是二分圖。
> 測資數量沒給、$n < 1000$、$m$ 沒給範圍。

特別之處：
1. 多筆輸入，題目寫輸入 $n = m = 0$ 時結束，但範例是 `EOF` 結束。
2. 輸出 `BICOLORABLE.` 或 `NOT BICOLORABLE.`，可能有句點坑掉了一些人 (?)

在半小時的時候這題還只有一隊有 submission，而且沒人 AC。當模板就緒之後我就直接用 DSU 寫掉這題了。
本來以為會是測資爛掉所以吃 WA，結果就直接 AC 了。

* 00:30 pB Accepted (+0)

接著換重諺上去寫 pH，我去看題。

> Problem D: Texas hold 'em
> 給你 $N$ 個人的兩張底牌以及五張公共牌，請輸出誰會贏，多於兩人會贏則輸出 `Tie`。
> $N \le 10$。

哈哈，是裸的 Texas Hold'em（德州撲克判手排大小）ㄟ，可惜我們把它從模板裡註解掉了 QQ

> Problem H: Egg Shortage
> 有 $n$ 間商店，其中第 $i$ 間有 $k_i$ 件商品，每個人總共只能買至多 $\ell_i$ 件，每件商品都只能買至多一個，且其中第 $j$ 件物品的價格是 $p_{i,j}$、收益是 $w_{i,j}$。
> 現在有兩個人帶著總共 $m$ 元打算分別去一家商店買東西（可以去同一家），求收益最大多少，以及在此收益之下最少要花多少錢。
> 測資數量 $\le 100$、$n \le 20$、$m, p_{i,j} \le 10^4$、$k_i \le 100$、$\ell_i \le 10$、$w_{i,j} \le 10^5$。

跟經典背包沒差多少，不過重諺把題目看錯成「每一家店的每個物品至多拿 $\ell_i$ 個」導致燒雞。

在他 debug 的時候我先把 pC 寫掉。

> Problem C: Optimal Resource
> 給你 $N$、$(A_i, B_i, C_i)_{i=1}^{3}$，並定義 $f_i(x) = A_i x^2 + B_i x + C_i$，請求出 $\max\limits_{\substack{x + y \le N \\ x, y \ge 1}}\{ f_1(x) + f_2(y), f_1(x) + f_3(y), f_2(x) + f_3(y) \}$。
> $N \le 10^4$、沒有 $A_i, B_i, C_i$ 的範圍。

其實題目沒有說到底能不能 $x + y < N$，但因為反正在 $A, B, C$ 都是正的時候不會影響到，所以我就寫了 $\mathcal{O}(N^2)$ 枚舉取 max 的作法。

* 00:47 pC Accepted (+0)

重諺又双叒叕少看 pH 題目了，他漏看了「兩個人」的條件，好在範例測資有 de 出這個問題。
而我發現 pA 是字串處理，換我上去寫掉它。

> Problem A: Black Friday
> 給你 $X$ 個商品的特價信息（皆為價面其中一種）以及 $Y$ 次購買物品，你需要計算出總共的花費，並四捨五入至整數。
> 特價種類有三種：
> 1. `Buy N gets M free`
> 2. `Buy 2 second one get M% off`
> 3. `The total amount over N get M% off`
> $Y \le X$、沒有其他限制。

特別之處：
1. 題目沒有寫要四捨五入，範例也都是整數。這是問 clarification 才回覆的。
2. 特價信息 3 的 over $N$ 其實是指 $\ge N$。這是經過很多次的測試才通靈出來的。

一開始用 double 計算再 round down，所以錯的很燒雞。

* 01:29 pA Compile Error
* 01:30 pA Wrong Answer

我在旁邊看算式有沒有問題時重諺終於把 pH 寫到可以過範測了！

* 01:38 pH Time Limit Exceeded

因為重諺算複雜度時沒有考慮到測資筆數 $t$，其實複雜度是 $\mathcal{O}(t (nmkl + n^2m)) \approx 2 \cdot 10^{10}$，我認為是要利用 $\ell_i \le 10$ 來做到更好的複雜度。
我接過 pH 的題敘想檢查重諺有沒有漏掉東西，順便問了一下 pF 沒寫的範圍限制，他去推 pG 的公式。

* 01:49 pF Request Clarification #1: "What is the upper bound of N?"

> Problem G: Coding Square Plan
> 給你一個長度 $2k$ 的 $\texttt{01}$ 字串 $s$，請求出在 $2^k \times 2^k$ 的方格內以希爾伯特曲線的方法依序填入數字 $0, 1, \ldots, 2^{2k}-1$ 之後，$s$ 代表的數字會在哪個格子。
> 測資數量 $\le 1024$、$2 \le 2k \le 30\,000$。

pG 一開始就有精神出來了，只不過因為要用到大數所以先放一邊。
重諺很快就推出遞迴式了，但我們遇到的第一個問題就是他的輸入格式。
他是用 input-EOF，而我們都不知道怎麼用 python 做這件事。

一開始用了 `EOFError` 的寫法如下：

try:
    s = input()
expect EOFError:
    pass
...

在範例過了之後交上去，結果因為重諺把輸出格式打成 `f'Case: {t}: ({x}, {y})'`，不出意外的吃了 WA。
結果修好之後反而變成 RE？

* 02:00 pG Wrong Answer
* 02:00 pG Runtime Error
* 02:01 pF Respond #1: "N <= 100"

pF $N \le 100$ 完全不會做，丟一邊。
我覺得這題可能像去年一樣又是測資再搞，所以就在字串長度是奇數的情況下在前面補零。

* 02:06 pG Runtime Error
* 02:09 pG Wrong Answer

這時其實非常危險，雖然 pB 跟 pC 兩題都是我們 1 try 首殺，其他題也都沒人 AC，但是一直到第 7 名都是 2 題，而且感覺上至少 pA、pD 題目也都不難只是搞人，如果有其他 3 隊過了某題我們就會直接沒有獎金。

分析了一下，好吧，還是只能繼續寫 code。重諺先回到旁邊 debug 算式，我則是繼續看 pA 有沒有什麼怪怪的地方。
猜了一下 `Buy N gets M free` 如果拿不到 $M$ 個 free 就只能都用買的（猜錯了），還是吃了 WA。

* 02:14 pA Wrong Answer

這時發現答案很可能不是整數，又因為題目寫 "Output a integer"，所以我們打算問一下如果答案不是整數會怎麼樣。

* 02:16 pA Request Clarification #2: "If the answer is a floating point number, how do we deal with it?"
* 02:17 pA Respond #2: "You should round it to integer."

把計算答案的方法改成乘以 $100$ 之後用整數運算，又測了各種（他們）可能做錯的地方，還是一直吃 WA。

* 02:25 pA Wrong Answer
* 02:25 pA Wrong Answer
* 02:27 pA Wrong Answer
* 02:28 pA Wrong Answer

直到這時我想說「搞不好他的 over 定義是爛的呢？」於是就把 `A <= N ? 100 : (100-M)` 改成 `A < N ? 100 : (100-M)`，結果上傳上去，GOAL！

* 02:28 pA Accepted (+6)

其實原本今天的目標是成功抓到測資的問題啦哈哈哈，終於達成了耶！

放心了一些，繼續開水題 pE。

> Problem E: Through The Dungeon
> 給你由 `W`、`T`、` `、`#` 構成的 $h \times w$ 迷宮矩陣，其中你的起始位置是 `W`、終點位置是 `T`。
> 你每一步可以往四方位不是障礙物 `#` 的地方移動，而且你可以至多做一次「傳送到四方位兩格遠且不是障礙物的地方」（也算一步），求 `W` 到 `T` 的最少步數。
> $h, w \le 1024$、只會有一個 `W` 跟 `T`、一定走的到終點。

特別之處：
1. 題目敘述沒有保證只有一個起點終點。這是問 clarification 才回覆的。
2. 題目沒有保證一定走的到終點。這是問 clarification 才回覆的。
3. 因為測資有大量空格，題本上又沒有用等寬字元，所以根本看不懂範例測資，也複製不下來。

這種只能做一次的通常都是從頭尾各做一遍，這題也不例外。

* 02:35 pE Compile Error
* 02:36 pE Wrong Answer

搞不好是走不到終點呢？

* 02:38 pE Request Clarification #3: "Is it possible that Kazuma can't reach treasure?"
* 02:40 pE Respond #3: "always can reach the treasure. Maybe needs teleport"

？？？
感覺他測資又爛了，但是這次的寫法應該沒踩到 `\r\n` 的問題，也不知道怎麼 debug。

把 pG 的 input 換成 `for s in sys.stdin.readlines()` 之後重新上傳。
得到 RE 之後認為可能是遞迴深度 $15\,000$ 過深，所以換成 bottom-up 的做法。

* 02:40 pG Runtime Error
* 02:44 pG Runtime Error

把 `#define int long long` 關掉重傳 pH。

* 02:52 pH Time Limit Exceeded

決定把長度偶數的判斷關掉之後就拿到 AC 了？？？
結果是他輸入的長度可能是奇數，這時候要直接忽略最後一個字元 = =
又成功通靈出一題 >////<

* 03:01 pG Wrong Answer
* 03:06 pG Accepted (+7)

我們輪流 debug pE 跟 pH，順便對沒給範圍的 pF 丟了一個詢問，希望可以有特殊解法。

* 03:13 pF Request Clarification #4: 問人數跟人數和有沒有上限
* 03:15 pE Request Clarification #5: "Will there be multiple or no 'K' or 'T' on the map?"
* 03:21 pF Respond #4: "all the number can be handle using int in C"
* 03:21 pE Respond #5: "both exactly one."

好吧，還是不會。

pH 前半邊的複雜度沒壓下來，倒是發現重諺在後半部找答案的地方根本就是 $\mathcal{O}(t (n^2 m^2))$ 的，把他改掉再 de 出一些小 bug 就成功 AC 了。
最可做的水題卻卡了快整場 QQ

* 03:27 pH Wrong Answer
* 03:30 pH Wrong Answer
* 03:30 pD No Output
* 03:33 pH Accepted (+4)

倒數半小時開始封版，啊封版之後怎麼還在發氣球 = =

最後的時間都在猜 pE 出了什麼問題，可惜到最後都沒有猜出來 QQ

* 03:35 pE Wrong Answer
* 03:42 pE Compile Error
* 03:43 pE Wrong Answer
* 03:44 pE Wrong Answer
* 03:53 pE Wrong Answer
* 03:57 pE Wrong Answer
* 03:58 pE Wrong Answer
* 03:59 pF No Output
* 03:59 pE Wrong Answer

還沒有講到的題目是 pF，不過感覺很不可做再加上其他題問題太多，所以賽中基本上沒有花任何時間來想這題。

> Problem F: On the giant's trail
> 給你 $N$ 個點的簡單圖的鄰接矩陣，起點跟終點是 $M$ 跟 $G$，每個點上都有一個數字 $a_i$。
> 你的力量 $\text{str}$ 一開始是 $a_M$，你走到一個點 $v$ 時要保證 $\text{str} > a_v$，之後 $\text{str}$ 就會加上 $a_v$。
> 你要找出在所有不經過重複點的 $M \leadsto G$ 路徑之中最小的 $\text{str}$。
> $N \le 100$、$a_i \ge 0$、$\sum a_i \le 2^{31}-1$。

特別之處：
1. 題目沒有給 $N$ 的範圍。這是問 clarification 才回覆的。
2. 題目沒有給 $a_i$ 的範圍。這是問 clarification 才回覆的。

因為這題光是讓 $a_M = 101$、$a_G = 101 + (N-2)$、其他 $a_i = 1$ 就等價於找 $M \leadsto G$ 的 Hamiltonian path 了，所以這個困難版更是完全不會做。

### 結果

Rank: 1
Score: 5 / 946

不出意外的拿下了第一名，但打得不甚理想。

檢討如下：
- pA：應該直接乘 100 算，不要用容易吃誤差的 double。
- pD：實作沒有那麼難卻被「模板沒帶到」這件事嚇到了，應該還是要好好分析類似題目的實作細節。
- pG：對 python 語法很不熟悉。話說如果我當時沒有特判奇數的 case 應該就會直接不知道測資有錯就過了ㄟ。
- pH：題目多次看錯，重諺在分析複雜度的地方燒雞。
- 很多函式都不知道要 include 什麼咚咚（`int64_t`、`atoi`、`setprecision`），如果又遇到類似情況必須先有準備。