Movie Promotion (UVa Live Archive Asia - 2009 Hsinchu(Taiwan))

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&page=show_problem&problem=2532

問題

ユーザがU人、映画がM個ある。各ユーザは各映画に対して $r_{i,j}$ という評価を下した。この評価からユーザと映画の傾向を知るため、変数 $\hat{r}_{i,j},u_i,m_j$ を用意する。 $\hat{r}_{i,j}$ は $\hat{r}_{i,j}=u_i+m_j$ という風に定義し、 $u_i,m_j$ は $\sum_{i,j}(r_{i,j}-\hat{r}_{i,j})^2$ が最小になるように定義する。ただし計算を安定にするためにユーザ0と映画0を定義して、ユーザ0を除く全てのユーザは映画0を3と評価し、ユーザ0は映画0を除く全ての映画を3と評価したことにする。また $u_0=0,m_0=0$ とする。
こうして決めた $u_i,m_j$ を基にして、映画をユーザに配って宣伝を行うことにした。宣伝の効果は $\sum_{f,t}({\rm floor}(u_f+m_t))^2$ となる。ただし同じ映画は2本までしか配ることができず、すでに見た映画を配ることもできない。また全てのユーザに1つずつ映画を配らないといけない。宣伝の効果の最大値を求めよ。
U<=256
M<=256
1<=r<=5

解法

まずu,mを決める。これはラグランジュの未定乗数法を使うと $\sum_{i,j}(r_{i,j}-(u_i+m_j))^2+\lambda_u u_0+\lambda_m m_0 \to \min$ の式をとけば良い。
これは各変数で偏微分するとu+m+2個の連立方程式になるのでガウスの消去法を使って計算が可能。
宣伝の効果の最大値は最小費用流を使って求めれば良い。