IOI 2014 Day2 - Friend
概要
Author : KoD
解法
問題を少し一般化して、頂点$ iを選ぶと$ p_i点、選ばないと$ q_i点得られるとしたときの最大化を考える。
最初$ p_iは人$ iの coinfidence に一致し、$ q_i = 0である。
最後に追加された人を$ iとし、その host を$ jとする。
1. $ iが IAmYourFriendで追加されている場合
元の問題の答えは、$ p_jを$ p_j + q_iで、$ q_jを$ q_j + \max (p_i, q_i)で同時に置き換え、人$ iを取り除いた新たな問題の答えに等しい。
2. $ iが MyFriendsAreYourFriends で追加されている場合
元の問題の答えは、$ p_jを$ \max(p_i + p_j, p_i + q_j, q_i + p_j)で、$ q_jを$ q_j + q_iで同時に置き換え、人$ iを取り除いた新たな問題の答えに等しい。
3. $ iが WeAreYourFriends で追加されている場合
元の問題の答えは、$ p_jを$ \max(p_i + q_j, q_i + p_j)で、$ q_jを$ q_j + q_iで同時に置き換え、人$ iを取り除いた新たな問題の答えに等しい。
この手順を繰り返すことで最終的に一人しかいない場合に帰着される。