Codeforces Round #280 (Div. 2)

題目積得有點多...其實最想寫的還是 CF #284, 令我第一次走去理解bipartite matching, 然後引申起另一堆bipartite matching的題目...還有Facebook Hacker Cup 2015, 以路過的心態玩了一下, 感覺題目的質量與所想的不太一樣就是了, 總之也學到很多, 有空再寫吧

這篇還是先紀錄下 CF #280, 雖然都是Div 2, 由於盡量會做 D & E, 基本也是D1 的A-C了..

Codeforces Round #280 (Div 2)

題目: http://codeforces.com/contest/492/problems

有點記憶不清楚, 應該都是一題一題在公司偷偷做的吧...

發現準確度的確下降了, 基本都不是一棍AC =.=

A: (頹題)

基本數學頹題吧...就不詳說了

B: (Binary Search)

bsearch的應用題, 題意大約是:

Given 一條長度為L的路, 然後一個數字d 為路燈的照明半徑, 問最少安多少台路燈

就直接Search答案 試試放下路燈能否Cover整條路就好

C: (Greedy, Sorting)

開始有吃屎感覺的一題...

題意: 有一個人要考 n 個科目, 每個科目他得到一個分數 a_i, 他可以寫b_i 份論文來把第 i 個科目的分數+1, 所有科目的分數都有一樣的上限 r , 每一科可以重覆以寫論文方式加分, 目標是把平均分大於等於 avg 分, 問他最少要寫多少論文

其實算法很直接的, 就是以 論文數先排序, 以最少論文可以加一分為先.

然後就盡量加分吧...直到那個科目已經到r 分了, 就開始下一個科目...

不知怎的實作時錯很多白痴位...

D: (Binary Search, Math)

這場的作者很喜歡bsearch啊...

啊咦不對..官方答案不是用bsearch的說...好像是linear time的算法

看了一下comment  還是有人提出這題可以用bsearch 解的...不算很奇特吧...

題目也很有趣, 是以電子射擊遊戲作背景。

題意: 有2個玩家要打 n 隻怪物, 第 i 隻怪物要射擊 a_i 下才會死.  玩家A跟玩家B 各自有不同的射擊速度, 一個是1秒射x發,  一個是1秒射y發,  求給予 n 隻怪物最後一擊的玩家 (可以是兩個一起)

我的想法是這樣: for 每一隻怪, 直接bsearch時間(秒數), 看看該秒兩個玩家共射了多少發, 直到找到答案(最小射得死怪物的秒數), 再來看看該秒數是否能整除 x 跟 y, 就知道玩家A跟B在該秒數有否射出子彈 (導至最後一擊)

E: (Math)

最難也是最有成功感的一題 (廢話)

題意出奇意料地簡單: 

有一個 n x n 的 matrix,  有一些格子有蘋果樹 (同一格可以有數棵), 然後有一個人, 每次他移動時會以當時他的位置(x,y) 移向 ((x + dx)%n, (y + dy)%n)的格子, 他會一直走, 直到走到一個他曾經到妨的格子就完結。求他開始的格子位置, 使他整個旅程能看到最多的蘋果樹, 若有多個答案, 隨便輸出一個即可

題目確保 n 與 dx 互質, n與 dy 互質

哇...最後那句簡直是...很難不知道它就是重點...

因為這一句, 起碼有數個有用的結論可以導出:

1. 不論選擇那一個格子開始 (sx, sy), 走了 k 步之後,  sx 變成 sx % n + k*dx %n
   k*dx %n, for 1<=k<=n,  肯定是[0,n-1]的permutation, sy同理一樣 (由於gcd(n,dx) = 1, 不記得從那學到這些number theory了...)
2. 由 1 可以推出: 不論從那一個格子開始, 走 n 步就會成為cycle了 (所以題目才用n x n 的matrix啊...)
3. 由 2 可以推出: 一個cycle中的 n 個格子, 那一個作為開始點都沒所謂; 而不是該cycle的格子則會與另外一格子組成cycle,  總共有n 條cycle, 互相不交集
4. 由 3 可以推出: 每一 row 的 n 個格子, 簡化地說,  第一row 的 n 個格子正是屬於 n 條互不交集的cycle, 而且都可以作為開始點

思路自然就變為: 比較 (0,i)  0<=i <= n-1  作為起點的cycle 的蘋果樹數目

當然直接做還是 O(n^2) 是不行的

把思路逆轉一下...選一個格子, 逆推出該格子所屬的cycle 於 第一行的格子的column數
i.e. Given (x,y),  找 (x+k*dx)%n = 0 中的k, 然後算出  (y+k*dy)%n

由於 k 可以以O(n) precompute, 逆推這一步實施只是O(1)

以O(m)  把在(x,y) 蘋果樹數目project (歸入) (0, (y+k*dy)%n) 中

最後O(n) 找出總數為最小的格子, 該格子就是答案了...

LL n,m,dx,dy;
int cx[100010], cy[100010], k[1000010];
int ans[1000010] = {0}, t = 0;
int main(){
    scanf("%I64d%I64d%I64d%I64d", &n,&m, &dx, &dy);
    for(int i=0; i<m;i++) scanf("%d%d", &cx[i], &cy[i]);
    
    for(int i=0; i<n;i++){
        LL tmp = i*dx % n; k[tmp] = i;
    } 
    
    for(int i=0; i<m;i++){
        LL ny = (cy[i] - k[cx[i]]*dy + n*n)%n;
        ans[ny]++;
    }
    
    for(int i=0; i<n;i++) if(ans[i] > ans[t]) t = i;
    printf("%d %d\n", 0, t);
    return 0;   
}