ICPC 競賽中如何製作 codebook

, ,

How to make team reference document in ICPC

前言

在 ICPC 競賽中一個不可或缺的元素就是在 規則 裡面被稱為 Team Reference Document 的東西。台大這邊俗稱叫 codebook。
在上一次的 WF 當中是規定每一隊可以帶至多 25 頁的紙本參考資料，必須是單面印刷，字體大小需要「0.5 公尺的距離下正常視力的人可以直接閱讀」，並且可以帶總共三份完全相同的拷貝。

codebook 是 ICPC 比賽與高中競賽相當不同的一點，平時就開始準備 codebook 可以讓你對這些模板更加熟悉，節省三人一機規則下寶貴的上機時間。

要放什麼？

  • 環境設定
    我們隊上使用 vim，因此理所當然的會有一份 vimrc。
    在 vimrc 中最佔篇幅的是我們設定的編譯快捷鍵 mapping，我們設定了三個快捷鍵：
    • F8 是加了 sanitizer 跟 warning 的編譯，平常正常寫題時就按這個編譯。我們盡量把幾乎所有 warning 跟 sanitizer 都開起來，這樣比較容易在還沒上傳前就找到錯誤，也養成寫程式碼的好習慣。
    • F9 是加了 O2 flag 的編譯。sanitizer 會讓程式跑得慢很多，有許多情況會需要在本機測速度，例如「跑跑看這個爆搜多快，會過乾脆就這樣傳」、「worst case 跑多久」或是「這題 TL 有點緊繃，用一下 time 看隨機大測資怎麼樣」。
    • F10 是執行。我們隊的習慣是會把每題的執行檔都編譯成不同的檔案，例如 a.cpp 會編譯成 a，c2.cpp 會編譯成 c2。如果沒 precompile 的話，通常編譯的速度不算快，在 ICPC 當中有不少時間會同時開兩題以上，因此會想要能夠快速的想要切換到另外一題測試。
      如果你平常有使用一些簡單的 default code / macro 而且可以塞進 codebook 的話可以就放進來，平時寫題的環境和比賽能夠盡量一致是最好的。
  • 有一定頻率考，但比較難當場寫出來的東西
    例如 Dinic / HopcroftKarp 系列、半平面交、Suffix Array 等等。
    有些 regional 當中也會考察 formal power series 的模板，雖然據說 world finals 不會考模 998244353 的題目，我們還是不敢拿掉。
  • 一些細節容易搞錯的東西
    例如：找歐拉迴路、二維凸包、KMP、字串 rolling hash、1D/1D DP 優化等等。
    一些敘述簡短的數學公式也會放上去，例如常考的線性規劃對偶、球座標公式，或是之前我們團練時推了超級久都推不出來的微分公式。這些數學公式可能基本上可以在比賽中自己推出來或背出來，但放在 codebook 上除了也許能加快速度就是不怕一萬只怕萬一推錯。
    「如果有 codebook 可以抄，你沒有理由不抄 codebook」
  • 一些莫名其妙的邪教
    這些東西考的機率都非常低，但我們之前在省 codebook 空間的時候實在太省了，於是比起線段樹那些我們隊伍平常自己就可以寫出來的東西就留下了這些。
    舉例來說有一般圖最大權匹配（護國神題？）、HLPP、擬陣交、min 25 篩。
    這些東西在一個正常的比賽通常不會是考點，可能就是擺在那邊當吉祥物，或是偶爾想吃毒直接砸下去就過了。

Hash

抄模板的時候，最怕的就是抄錯，更怕的是不知道是在其他地方錯了還是模板抄錯，或是模板本來就是錯的。

在 codebook 裡面加入 hash 的 idea 是從 KACTL 學來的。
比賽環境的 Ubuntu 通常會有各種標準的 hash 的指令，於是我們就可以用比如說 md5 的方式，在抄完一段程式碼之後可以快速比對我們抄的那段是否和 codebook 上寫的相同。

在 vimrc 內加入這段指令

1

ca Hash w !cpp -dD -P -fpreprocessed \| tr -d "[:space:]" \| md5sum \| cut -c-6

就可以先用 visual mode 把抄的那一段選起來之後，用 :Hash 來得到那一段的 hash。計算 hash digest 值時會無視註釋以及空白和空行，因此在抄模板時可以不抄註釋或是選擇在不同地方斷行，非常便利。

然而這個機制並沒有找到是哪裡抄錯的功能。在我們目前的幾個模板上，我加上了分段 hash 的功能，如果抄錯能夠至少分辨是哪一段抄錯。

養成一抄完就檢查 Hash 的好習慣才不會浪費一些莫名奇妙的時間…

AS-IS : 完全照抄

既然是模板，你應該要能夠把模板部份閉著眼睛貼上就能通過模板題。

平常在抄模板的時候，應該盡量就不帶腦袋當成 typeracer 盲打式的抄寫，不要準備一個模板是我某些地方還要因應不同場合改成不同寫法的，很容易不小心哪裡沒改錯就出 bug，而且如果不完全照抄的話，上面提到的 hash 機制也幾乎等於沒用。
如果是有一些常數或是步驟需要依情況更改的話，可以像是用 template 參數 / 函式引數或是傳一個 function 進去的方式。

一般化

template 比直接寫死一個型別好，vector 比使用陣列好。

現在的 C++ 有 auto 這種型別的簡短寫法（以前都需要用 template），會自動在編譯時期做 polymorphism，舉例來說，像是字串比對的 KMP 函數當中，雖然常常都是傳 std::string，但有時也會想要對 std::vector 做 KMP，這時把函數的參數改成 auto 就非常方便。

使用 vector 來說，除了原本的 vector 複製一遍非常簡單以外，複製也是函式參數的預設行為。這種比較 pure 的寫法會讓程式比較不容易出錯。

關於在不同型別的「無限大」這個值要開多大，可以使用 numeric_limits<T>::max() / 2 之類的寫法，如此一來就不用取捨要用效率可能比較快的 int 還是比較不會溢位的 long long 當成模板的預設型別了。

效率

因為模板抄下去之後我們通常不會想再改動，因此在準備時也需要考量要用執行的速度有效率的寫法。

例如說在兩維以上的陣列的情形，直接用 vector<vector<>> 的效率會有明顯的下降，這時如果我們對陣列只是一些比較單純的用法的話，可以簡單的用 native array 的方法開。

或者，在各種地方多加 const reference，除了可以在使用模板時確認你不會更動這個容器以外，理論上也會讓編譯器更容易做最佳化。

註釋

通常來說，註釋最重要的會是這個模板的使用方法，例如像是「李超線段樹預設是取 min 還是取 max」或是「floor sum 的複雜度是多少」之類的。
如果你的模板不能處理一些邊界情況，最好當然就是改成可以處理的寫法，再不然可以 assert 邊界情況，最慘就是寫在註釋，等到踩到坑或是某個隊員有記得才會發現。

程式碼風格一致 : 可抄性

在抄寫程式碼的時候，有些我們的 hash 指令無法當成相同但其實相同的細節，例如 i++ 與 ++i 或是只有單行的 statement 要不要加大括號。至少在一份模板的裡面風格能夠統一的話，會更易於抄寫。

隔離

演算法內部的細節通常不是我們在使用模板時關心的事情，例如我們通常在解完雙連通分量之後就不會再用到 low 值陣列了。在 ckiseki 隊上常用的是用 struct 或 class 等把演算法的內部細節藏住，對外主要 expose 幾個函式就好。當然如果整個模板就是一個函式的話，通常也擁有更高的獨立性，例如我們現在的最小有向生成樹的模板，就是只傳邊陣列進去回傳選哪些邊的一個函式。

用 struct 還有一個優點就是可以使用 constructor，指定在初始化的時候一定要做的步驟。前人流傳下來的有些模板會需要呼叫 init 之類的函式，常常忘了呼叫就會 debug 很久，是個浪費時間的坑。

善加利用空間

為了想要放更多東西進來我們的 codebook，我花了一些心力調整行距或空白之類的，並且把許多 .cpp 檔利用 C++20 有的各種語法糖節省空間，也把原本非常空卻佔了一整頁的目錄調整為只有半頁。放更多東西進來雖然讓我更安心，但也發現其實 codebook 準備得再好，也很難提高 ICPC 表現的上限XD，主要是能表現得更穩定。

平時的測試

最重要的是平時 virtual / 參加比賽就要多用模板，這樣你才會更知道你的模板有哪些禁忌事項，或是模板的效率怎麼樣、哪裡很難抄之類的。
library checker 是一個有用的網站，你可以從這邊看到一些會想 library 化的問題，以及可以上傳測試模板（雖然似乎正確服用方法是自己 clone 下來本地跑）。
目前 ckiseki 的 codebook repo 沒有 CI/CD 在 GH action 之類的跑這些自動測試，不過我們有維護一份 markdown + yaml 文件，除了寫每個模板有在哪裡測試過以外，也有稍微寫一下模板的注意事項、效率等等。

本文所講的許多重點都是實際上無法完美兼顧的，例如有時候會想要犧牲一些空間來放註釋，或是有時候想要讓程式碼直接獨立能夠使用而犧牲了一些一般化的能力。平時不管是比賽還是刷題，多使用多測試隊上的模板，才能找到適合的平衡點。

簡單的例子

以下幾項不是 25 頁的。

comments powered by Disqus