※ 引述《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) 数值上的问题.
不过, 如果你仔细的把题目再看看, 这题有特殊形式,
因此一下就能解出来..