GCJ 2021

第一次打owo
因為也算是大比賽(? 所以就留一點紀錄ㄅ

Qualification Round

沒啥印象，只記得是在1!完隔天寫的
唯一有印象的是在寫pD的時候發現我不會手刻quick sort 爛死

Round 1B

因為1A的時候家裡有事，所以就拖到大半夜場1B了QQ

開場看完pA，想了很久發現只是要解同餘方程
然後到wolfarm搜了一下11的模逆元就一發過了

pA 00:30:05 (O O O)

之後看完pB，直覺上範圍那麼小 答案一定不會太大
就直接爆搜了一遍，發現答案上界是402
好耶.jpg 暴力寫掉

pB 00:46:54 (O O)

到這裡大概排在前100覺得很穩，就開始沒很認真想pC
claim了幾個greedy解又WA了幾次後拿到第一筆

pC 01:43:01 (O X)

然後就結束了

最後收在rk 267，很輕鬆就進了

Round 2

開場看完pA，想了2分鐘才發現
不對啊 倒數和好像不會爆欸
寫了code確定不會爆後就直接丟

pA 00:06:54 (O)

之後看pB，一開始直覺是某種greedy
不過各種我想到的greedy都很快就找到反例，就沒往那想了
之後直覺告訴我40秒爆搜可能ok，畢竟答案最大只有logn而已
所以就寫了一個這樣的爆搜：

const int N = 1000001;
void build(int now = 1, int sum = 1, int cnt = 1) {
    dp[sum] = max(dp[sum], cnt);
    for (int i = now + now; sum + i < N; i += now) {
        build(i, sum + i, cnt + 1);
    }
}

本機就跑不完了，但我還是傳了，結果就吃了一個sample TLE
後來再想一下發現N可以除以3
這個優化打完再傳就過了= =

pB 00:30:48 (O O)

之後看pC，發現可以歸約成DAG的topological sort數量
然後想了很久沒想法，丟google才發現他是NP，氣死
之後想了一個小時發現還是沒想法，又發現第一筆$\mathcal{O}(n!)$不會過，就果斷丟了

在覺得自己沒救的時候去開了pD，發現第一筆只是二分匹配而已
就很愉快的砸了Dinic

pD 01:43:29 (O X)

之後因為不會pC只好繼續想，發現只要對於每個$i$，計算出有$i$條邊被匹配的距離和最小值就好，這個很合理的可以想到KM可做，但我沒有KM的模板R
結果這題很佛心的給了$nm \leq 100$，所以就直接砸MCMF就好
寫完之後還很擔心會不會假解，後來生幾筆測資都對就直接丟了

pD 02:16:44 (O ?)

剩下的時間就拿去優化pC第一筆，但還是壓不過QQ

然後就結束了

最後好險pD有過，收在rk 733
就這樣很愉快的靠MCMF拿到T-shirt了=w=

Round 3

開場看完A發現好難喔，不過好像原本GCJ就應該要是這個難度，也沒到很意外(?
想了十分鐘發現不妙，可能連一題都拿不到，就先寫了一個暴力的pA1傳上去

pA 00:14:33 (O X)

然後就開始燒雞，想了很久都沒想到就去開B了
開完之後還是沒啥想法，連B1都沒有
就回去繼續想A了

又想了很久忽然從n是奇數的greedy解想到n是偶數的解
寫了一下丟

pA 00:54:55 (X X)

然後就開始燒雞，找了一堆錯bug，傳了好幾次總算過了

pA 01:15:15 (O X)

但只有第一筆，第二筆被卡常
之後開壓一下就過了= =

pA 01:25:30 (O O) +7

剩下的時間就全部都在燒雞
開完C和D發現都不會
所以回去繼續想pB1

最後大概20分鐘才想到怎麼爆搜，寫了很久之後壓線傳

pB 02:27:42 (X X)

88，又吃TLE
然後就結束了

最後收在rk 389，算勉強還行吧
於是今年的GCJ就這樣結束了>w<