→ Jaka: 大師 01/22 00:01
推 ririoshi: 大師 01/22 00:01
→ DDFox: 大師 01/22 00:04
→ sustainer123: 大師 01/22 00:08
推 pandix: 大師 01/22 01:27
吃了四個 penalty 還花了 44:44
但排名竟然沒想像中爛
可能是因為第四題沒那麼好想
https://i.imgur.com/OPOElDm.png
1. Minimum Common Value
直接用 set 把 nums1 有的數存起來再去看 nums2 裡有沒有重複的就好
很顯然可以改用 2-poitner 來做會比較有效率但沒必要
2. Minimum Operations to Make Array Equal II
看了一下排行榜，penalty 率超高
連第一頁的也一樣 笑死大家都沒考慮到 k=0
k個一份，如果多的份數和少的份數一樣就是合法的
如果不足一份就直接不合法
3. Maximum Subsequence Score
先依據 nums2 的值由大排到小
因此在處理某個人時，在他之前的都是 nums2 比他大的
因此乘法的右邊就一定是自己
乘法的左邊就用一個 minHeap 來維護最大的 k-1 個 nums1 的值即可
因為把其中一個 second 寫成 first 吃到 penalty
這樣竟然能過範例測資也是神奇
4. Check if Point Is Reachable
花了 10 秒丟一個 return gcd(x, y) == 1 試試
果不其然是錯的
想了一陣子之後，發現幾個性質
1. 不能讓值變成 <= 0，不然永遠回不去，因為無法讓另一個也變負的
2. 因此想讓值變大只能用 *2 的
3. 因此對 (X, Y) 而言，假如 X = 2 * Z
則 (X, Y) 是否能到達若且唯若 (Z, Y)
4. 因此我們可以等價的轉換成都是奇數的形式
5. 如果都是奇數且不失一般性令 X >= Y，則
(X, Y) 能否到達等價於 (X - Y, Y) 能否到達
不能減另一個方向因為會讓其中一邊 <= 0
所以可以讓 (X, Y) 不斷遞減，
且每兩次操作至少減半一次(第5步的 X-Y 一定是偶數)
所以是 O(logn) 可以解
最後一題還不錯，可惜這場吃太多 penalty 了
錯了也常沒多想就隨便上傳
祝大家新年快樂
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.16.175 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1674316820.A.A18.html