[2022.12.07] 2023 Eurasia

2022-2023 ICPC, NERC, Northern Eurasia Onsite
Contest link: https://codeforces.com/contest/1773

今天有點晚出門，比賽前其實有點小趕。直接進入正題：

分工：

• 金刀：正著看
• 重諺：倒著看
• 迺絜：打模板

大約開賽五分鐘後我打完沒有 debug 的模板，然後看了計分板發現有兩隊過 F 了，我就通知兩個隊友。

迺絜

一開始感覺 pA 是水題，但沒有馬上想出做法，就直接跳過。
pB 到 pE 都是沒有一眼就看出作法，只有 pF 馬上精神掉。
上去把判 case 的部分寫完之後丟上去吃了一個 WA，原來是我在 \(a \le b\) 跟 \(a > b\) 的部分用了同個輸出 = =

SorahISA

• 0:10 pF Wrong Answer
• 0:13 pF Accepted (+1)

接著根據計分板發現了 pE 也有不少隊伍開掉，仔細看了一遍題目就發現他超水。
基本上等價於把所有數字離散化之後相鄰不是 \((i, i+1)\) 的 pair 都拆掉，組起來的次數當然就是 \(\text{cnt} + n\)。

SorahISA

• 0:20 pE Accepted (+0)

因為重諺在問「圖的 degree 有什麼性質可以用」，所以我也跑去看了一下 pK。
發現好像可以直接判 case 暴力構造：

• 在 \(k = 1\) 時可以接成一個環。
• 在 \(k = 2\) 時可以先接 \(1\) 跟 \(2, 3, \ldots, n\)，讓他變成一棵菊花。
• 在 \(k > 2\) 時可以再接 \(2\) 跟 \(3, 4, \ldots, n-1\) 得到 \(k = 4\)，以此類推得到 \(k = 2a\)。
• 對於 \(k = 2a+1\) 就只要接 \(\ell\) 跟 \(\ell+1\)，讓他們的度數都多一就可以了。

把東西都判掉之後順便寫了一個 checker 讓他在失敗的時候會吃 RE，本地構造了一些測資都沒問題就上傳ㄌ。

SorahISA

• 0:35 pK Runtime Error

ㄨㄚˊ，還是燒雞。
發現沒有判到 \(n > 1\) 且 \(n = k\) 時要輸出 NO，改掉之後重新交上去。

SorahISA

• 0:38 pK Wrong Answer

ㄨㄚˊㄨㄚˊㄨㄚˊ
重諺提醒我會不會有重邊的情況，馬上就發現 \((n, k) = (2, 1)\) 也會輸出環所以有重邊 QQ。

SorahISA

• 0:40 pK Accepted (+2)

看完 I, J, K, L 後發現不是構造就是互動，但是 I 看起來可以 python 建表。然後就繼續往前看題目了，順便跟金刀說 K 的題目，然後就被水掉了。
金刀水完題目後電腦就空出來了，我就跑去寫 python 打表，然後打一打就發現可能變數太多放不下，所以就先把電腦讓給迺絜寫 A，然後跟金刀一起看 D。
看了一下覺得跟增廣路徑的數量有關之後就讓迺絜想一下，然後我繼續把 I 的要上傳的程式打完。
打完上傳發現真的太大傳不上去，然後金刀開了一下字串 encoding 壓一下程式碼大小之後傳上去就過了。

重諺

• 3:23 pI Accepted (+0)

打完模板後我就開始看題，因為金刀看到 F，我就從 G, H 開始看。
G 是排列問機率的題目，一看完只覺得應該是 \(O(3^n)\) 這類的題目，大概想了 30 秒，沒有直接覺得他是水題，我就接著去看 H。
H 是互動題，感覺是某種分搜，有先嘗試一些想法跟策略，暫時先記錄下來並且跟重諺討論了一點進展。

迺絜

接著發現 A 是開賽後除了 E, F 最多人做的題目，我就開始再看一次 A 並且想它。然而我對於排列的敏感度其實很低，先想了一個簡單構造，然後證證看有沒有保證有解。
想了一下跟金刀說一下想法，金刀把他轉成另一個形式，然後接著再嘗試做下去。
接著基本上需要的性質都想完了，所以就開始實作。
但在最後把構造生出來的函數的地方又有點卡住，所以範測測出來怪怪的。
後來發現自己在耍蠢，位置直接存反，改掉之後再測了一次測資跟自己 assert 一些東西以後就傳上去。

迺絜

• 2:34 pA Accepted (+0)

接著看起來是正在打表的 pI, pB, pD 最可做，pB 金刀在做，pI 重諺在打表，所以我就去接手了 pD。

迺絜

金刀給了我一些 pD 基本的性質跟條件，比如說空格很少等等的基本條件。然後會發現拿掉西洋棋盤上黑白兩格的方法數算可以填滿的應該比較容易，就朝著這個方向去思考。
接著金刀去投飲料機我去裝水，我想了一下發現如果要拔掉一個點，那只要他的 matching 對面的點也可以找到伴，那就也可以拔。這個過程其實跟匈牙利的作法基本上一模一樣。
接下來基本上正確的想法的雛形就出來了，先提出一下想法，然後雖然有點小 bug，但是在重諺跟我說了一下之後我就馬上想到正確的做法了。

迺絜

接著重諺質疑了我說如果最初求的完美匹配不一樣會怎樣嗎？我在很短的時間內就做出了簡單的證明。
因為兩個匹配考慮的是同一張圖，只要某個匹配可以經由交錯路徑推出一對可以拔掉的點，那他們就一定可以被拔掉。所以在另一個完美匹配上也要是如此。接下來就是跟重諺確認一下實作細節，然後請重諺去實作這一題的想法。

迺絜

迺絜看完 pD 之後發現用匈牙利找一下交錯路徑+數一下經過的點就知道哪些點是可以拔的了，然後我就趁迺絜在驗範測的時候把 Matching 的部分先寫一寫，然後就開始 debug。
Debug 後發現我在耍蠢，不能直接用匈牙利的dfs來跑，所以寫了一個新的 DFS 來算方法數。
後來範測還是不對，發現其實 DFS 沒有好好走到交錯的路徑，修了一下以後給迺絜跟金刀確認過邏輯以後，就丟上去，然後就 AC 了。

重諺

這裡有一個小插曲，我確認完 pD 的實作以後原本要去裝水跟上廁所，他們要傳上去時，我想到一個在我一看完題目就想到的東西就是要記得跟 \(10^6\) 取 min。結果還好有提醒他們，應該是避免了 20 分鐘的 penalty。

迺絜

• 4:24 pD Accepted (+0)

• 5:01 pB Too Late (Accepted (+0))

結果

• Rank: 51 / 1704
• AC: 6 / 12
• Penalty: 754

燒雞

• pF、pK 判 case 題在測試時沒有測過明顯的邊界測資，導致多吃了三次 penalty。
• pD: 題目要取 min, max 的記得要取，不然會很尷尬。
• pA 真的做太慢了，迺絜還要繼續復健，加速思考跟穩定實作。
• pI: 多練一下 python