PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[討論] GCJ結束了我要伸解法～

看板Prob_Solve (計算數學 Problem Solving)作者scan33scan33 (亨利喵)時間16年前 (2008/07/27 23:54)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串1/6 (看更多)

這裡好像很多人在比，所以想問問看解法，那我先就我知道的拋磚引玉吧！題目在： http://code.google.com/codejam/contest 防雷頁 1a.Greedy 最大配最小就對了。我也不知道怎麼對的，有誰要說明一下嗎？時間複雜度：O(n lg n) (sorting) 1b.無法分類呀orz 看似SAT問題，結果都不敢去做。但是其實他說每個人最多一個melted milk. 也就是說，決定melted milk要不要放是看人，在這裡應該可以看出端倪是要建一個人-牛奶的table ，記得某個人要哪些牛奶！另外要記得每一個人有沒有被satisfy Case 這個人不用melted milk就可以satisfy: 沒問題！ Case 這個人不用melted milk沒有satisfy: 那無論如何都要給他melted milk，由於只有一個melted milk所以選擇唯一。因此就每次都看過所有人，直到沒有人可以被多satisfy。由於兩種Case的決定都是deterministic，所以掃一次至少多satisfy一個人，而且是花人數的時間。因此，時間複雜度是O(牛奶數*人數^2) 1c.Linear Algebra(?) 聽說是把1當作I,去解 (X-3)^2 = 5 的矩陣X。就可以把(3+sqrt(5))^n 跟那個矩陣做mapping... 然後就可以divide and conquer乘次方. 但是最後面要怎樣轉回來不是很理解... O(n) (n是數字的encoding長度) 2a:Ring 窮舉by x,y 座標用 3*(x mod 3)+(y mod 3) map到 {0,1,2 ... 9} 這樣的 ring 然後對ring中任取3個元素a,b,c with constraint a<=b<=c做窮舉，然後再用排列組合公式求解。我的解法時間複雜度是O(n) (讀入input) 2b:Disjoint Set 把所有質數在10^6以下窮舉出來，然後用disjoint set演算法。(就是超強神Tarjan大大的接近linear演算法)跑一次整個範圍的數做merge. 要不要merge就看看是否有共同質因數大於P就好。我的解法時間複雜度是O((nlog*n) * p(1000000)) p(1000000) 是在 1000000以下的質數 2c:Joseph題環狀殺人問題，從1開始放牌，能放的先放就會對。因為大的不會插隊去match小的。時間複雜度我不會分析.... 3a:greedy 最小的儘量全部塞一起。目前還沒想到怎樣證orz... 時間複雜度：O(n lg n) (sorting) 3b:Divide and conquer and remember used stated (DP) 我們只在意餘數，所以其實在一個{1 .. 2*3*5*7}的ring就足以 model我們看到的所有數字。 State有strlen*2*3*5*7個，因為斷一次數字，後面要什麼數字，只跟前面分別對2,3,5,7的餘數有關，跟真正加減起來的數字無關。然後就對數字的每個數字之間都斷斷看，每次斷都加減看看就好。時間複雜度： O(n) 因為2,3,5,7是constant. 3c. 不會.... -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 122.99.4.64 ※ 編輯: scan33scan33 來自: 122.99.4.64 (07/27 23:56) ※ 編輯: scan33scan33 來自: 122.99.4.64 (07/28 09:27)