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 所以這樣就可解了
_____________
我覺得體驗沒有到很好，可能會再比個幾場試試水溫