[閒聊] CodeChef Starters 75

看板Marginalman作者fxfxxxfxx (愛麗絲)時間1年前 (2023/01/27 05:15)推噓2(2推 0噓 1→)

留言3則, 3人參與討論串1/1

CodeChef 是印度一個類似 Codeforces 的網站也是一場會有上萬人比的大型網站這次是第一次寫他們的比賽比賽分成四個等級 div1~4 因為我積分是 0 所以只能去 div4 被迫寫了一堆連水題都算不上的題目好在這場比完之後分數就到 div2 了不同 div 之間還是會有很多共同的題目像 div3 少了 div4 的前兩題但比 div4 又多了一題更難的雖然這題並沒有 div3 的人寫出來看起來實際上 div4 前排的比 div3 要強應該都是剛創帳號的人這次有八題，八題都有寫出來排在 div4 裡的第 4 名沒有 penalty 所以爽傳就傳我覺得不太好就是了 https://i.imgur.com/gLOglBm.png

P1 TAXSAVING 給 X, Y 要你計算 X - Y 這也太爛了 = = P2 Profit Increment 給 X, Y 計算 Y + X / 10 這兩題都是國小數學應用題加第一堂程式課的等級 P3 Two Ranges 給兩個範圍 [a, b] 和 [c, d] 問聯集有多大分重疊和不重疊的 case 就可以了 P4 Three Powers of Two 給一個以二進位表示的數字字串(長度 <= 2e5) 問是否能夠表示成恰好三個二的次方數的和 corner case 題，有 > 3 個 1 會失敗恰 3 個會成功恰 2 個會成功 (大的那個以小一位的兩個表示) 恰 1 個必須 >= (100)_2 才能以兩個小二位及一個小一位構成恰 0 個會失敗 P5 Prefix Ones 給一個只以 01 組成的字串要在移除一個 substring (可空) 後開頭是連續的 1 越長越好其實就是原本開頭連續 1 的長度，再加上這之後最長的連續的 1 的個數 P6 Equal Hamming Distance https://www.codechef.com/START75D/problems/EQUALHAMMING 從這題開始像平常會寫到的題目如果 A[i] = B[i] 則不管選什麼都不會影響差距所以可能性直接乘二假設 I_1, I_2, ..., I_k 都能使 A[I_i] =/= B[I_i] 如果 k 是奇數則不可能成功，必須要讓選 A 或 B 的數量一致所以會是 k!/(k/2)!/(k/2)! 趕快複製以前寫過的乘法反元素最後乘回 2^{A[i]=B[i]的個數} 就好 P7 Chefs Favourite Function https://www.codechef.com/START75D/problems/CHEFFFUNC 可以證明 f(x) 就是以二進制表示時 0 的個數不過在這裡我們只需要證明 f(x) <= log2(x) 就好 g(x) 比較重要，可以發現是以下的數列 1, 3, 2, 7, 6, 5, 4, 15, ... 重點是要去證明 g(2^k) = 2^{k+1} - 1 g(2^k+i) = g(2^k) - i, for 0 <= i < 2^k 因為 x <= 10^9 讓我們有 f(x) <= 32 所以只要找到 [L, R] 範圍內最大的 2^k 再去檢查 [2^k, 2^k+32] 就好， O(log^2 x) P8 Minimum Replacement https://www.codechef.com/START75D/problems/MISREP 假設 A[i] <= A[j] 會把 A[i], A[j] 變成 0, A[j] - A[i] 最後一個人一定會是每個人乘上 +1 或 -1 的總和因此，如果存在解讓他是 0，把負的移項就會變成兩群和一樣的 subset (聯集是整個 A) 而如果存在兩群和一樣的切割法則藉由不斷挑兩群各一個非零的成員來做就好因為每次會減少一樣的值所以兩邊和永遠一樣所以這是經典的 partition problem 問題，屬於 NP-complete 但因為 A_i <= 300，可以很簡單的用 DP 來達到 O(N*NK) psuedo-polynomial N 和 K 都 <= 300 所以這樣就可解了 _____________ 我覺得體驗沒有到很好，可能會再比個幾場試試水溫 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.16.175 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1674767705.A.C51.html

推

Jaka

01/27 05:16, 1年前 , 1^F

01/27 05:16, 1^F

推

pandix

01/27 05:22, 1年前 , 2^F

01/27 05:22, 2^F

→

fxfxxxfxx

01/27 05:22, 1年前 , 3^F

01/27 05:22, 3^F

‣ 返回看板[ Marginalman ] 心情

‣ 更多 fxfxxxfxx 的文章

文章代碼(AID): #1ZqkrPnH (Marginalman)