臺北市資訊學科能力競賽 2020

第二次打北市賽了，上次北市賽的時候流感，還好打得還不錯，今年也沒有再流感了（不然就不能比賽了 QQ），是說我已經一年沒有生病了，以前大概每三個月會感冒一次，去年甚至年初年底各一次流感，看來回家都先洗手和在捷運上戴口罩是有用的 (?)。

題目

pA 100/100

有一個 的棋盤，一開始你在左上角，每一步都可以往右邊或下面走，並且可以往上走最多 次，但是往上走完就要馬上往下走，且一旦到了右下角就不能再動了，求有幾種走法能到達右下角。、。

好像 有騙到一些人去想數學解，但這其實就是 的 DP 而已。

pB 100/100

把線段按斜率的絕對值排序。

pC 100/100

有 6 種棋子，每一種都有無限個，從中取 個排成一列，且第一種和第二種要取偶數個，求排列數 。。

題本上寫的限制是 ，後來才發公告改成 的。因為一開始範圍是 ，所以我就先想線性解， 取 個棋子的排列數， （）表示第一種和第二種棋子數量是奇數還偶數。

寫完之後 TLE，我就在想是不是模的常數太大，所以開始壓常，結果壓到了本機 0.1 秒都還是 TLE，我才開始發現不對勁，assert 看看 ，然後差點當場氣死，他的測資有超過 的，發問之後還很久都沒有人回，後來就發公告說改成 了。

改成 就變矩陣快速冪。

pD 0/100

以下都在 （ 是質數）下做事。給一個多項式函數 ，和一堆多項式方程式，令 是它們的聯立解，求 。 可能有多個，但 保證唯一。

看到這是數學加上多項式我就知道我沒救了，而且我也沒聽過任何可以拿來做這個的東西。大部分的人都 0 分，最高分是 33 分，這個子題是「有一個方程式次數是 1」，我本來也想拿這個子題，但怎麼做都沒過，好像有過的人都不是用正常的作法，還有枚舉 居然可以過，大概是測資爛了，應該是模逆元的部分壞掉吧。不過大家想了很多測資爛掉的可能，像是 不是質數、、有數字不在 的範圍，每一個也都有人 assert 過，但沒有一個是真的 assert 出問題的。

pE 100/100

有一個 的棋盤，有些格子是障礙物，還 個相異格子是寶藏點，你可以選擇一個寶藏點作為起點，並選擇一個數字 ，每次操作可以選擇一個寶藏點，滿足這個寶藏點編號比目前所在的寶藏點大，且目前所在地到那裡的最短路徑長恰為 ，接著移動到那個寶藏點，求最多能做幾次操作。

這題題目敘述沒寫到要走最短路徑，原本敘述的意思是每次操作都走恰 步就好了，也是後來才發公告改的，根本就變成完全不一樣的題目了。最氣的是我寫完原題的解後 WA，過了幾分鐘才有公告，又浪費我一堆時間。我覺得原題是還不錯的題目，如果把格子塗成黑白先間，那麼走到同色的格子肯定會花偶數步、異色的格子肯定花奇數步，所以答案會是「一個連通塊裡，某一顏色的寶藏點最大數量減 1」或「可以黑白交錯走的最大步數」，但改完之後就變糞題了。

如果從把每一個寶藏點都視為一個節點，然後從每個點連有向邊到所有編號較大的點，邊權是最短路徑長，這樣會得到一張 DAG，要求的就是同權重的最長路徑。建圖可以從每個寶藏點 BFS 一次，這樣時間複雜度是 ，求最長路徑則是 的 DP。我忘記題目給的限制是多少，反正這樣可以過。

小插曲，第一個子題是 、 但 無限，後面是 很大但 ，我最後在求答案時只有求前 個寶藏點為起點的最長路徑而已，似乎後面子題的 都比 大，所以沒出事，但第一個子題就一直沒過，最後幾分鐘才過的。

結語

因為北市賽可以帶 codebook，開場就先把 default code 打完。去年是用 Code::Blocks 打，然後一直當機，今年 TOI 模考的時候因為被 Code::Blocks 弄到很氣，所以學了 vim，本來我很煩惱說北市賽好像沒給 vim，還好測機的時候發現有，才能正常打 code。（沒有 vim 我會一直打出 hjkl）

打完 default code 後，就開始讀題目，看完 pB 的時候還在想我真的沒讀錯題目嗎？！然後決定的做題順序是 BCAED，不先 pA 是因為我看完 pC 就馬上想到解法了，但 pA 想了比較久。

是說我真的超愛 pE 的原題，比暴搜完找最長路徑有營養多了。= =

總分400/500
rank 10

其實第 2 到 10 名都是 400 分，我最後一名是因為我先在 pD 丟了很多次，最後才過 pE，然後比序方式是看「最後一次分數改變時的提交次數」，所以 pD 那幾次就被算進去了 = =，沒有道理的 R。

不過這種比賽的一等獎我也不稀罕，能進全國賽就好了。還好最後 pE 有過，不然我大概不會進 @@。