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

Re: [問題] codejam 2012 round 1B-1

看板Prob_Solve (計算數學 Problem Solving)作者Leon (Achilles)時間11年前 (2013/07/30 03:09)推噓2(2推 0噓 0→)

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

※ 引述《shaopin (problem maker)》之銘言： : (context)題目在這: : http://code.google.com/codejam/contest/1836486/dashboard#s=p0&a=0 : 我的問題是關於: : 1. : 假設有一個個方程組如下: : 21 + 75*x = 24 + 75*y = 30 + 75*z; : x+y+z =1 : 該用什麼algorithm解他?(library就別提了) : 2. : 為什麼這樣解出來的x,y,z就剛好是 : 那三個人每一個人避免被淘汰所需的最小支持度? : 感謝 This is linear programming (LP).... 你可以看看原來的題目, 每個人的得分是 J + X*Y 所以, 要是三個人的狀況下, A = 24, B = 30, C = 21. 我們換個方式問, 請問, A 一定被淘汰的狀況下, 他的得票率有可能是多少? It implies.. 24 + 75*x < 30 + 75*y ; 24 + 75*x < 21 + 75*z ; s.t x + y + z = 1. 這就是一個標準的 LP 中 feasible region 的例子. (我那時候的高中數學有敎這一段) 那個邊界條件, 就是 "避免被淘汰的" 情況. 然後你變換一下 75* x - 75*y = 6 75* x - 75*z = -3 75*x + 75*y + 75*z = 75 變成一個標準的解 linear equation 問題: A*v = b. A is full rank and easy to generate. 正面攻擊法, 是用 Gauss-elimiation method 去作很少人會用 Determinant 去解的, 因為那個會有 det(A) 數值上的問題. 不過, 如果你仔細的把題目再看看, 這題有特殊形式, 因此一下就能解出來.. -- 一簫一劍平生意負盡狂名十五年 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 128.125.20.198