ゲームの言い換え

箱木さんは必要になるまで箱を買う必要はありません。 よって、球橋さんがボールを選んだあとで、そのボールを入れることのできる箱が存在しないときに限り、箱木さんは箱を買うことにして良いです。

\(c\) 種類目のボールを色 \(c\) のボールと呼び、\(i\) 個目の箱を箱 \(i\) と呼ぶことにします。

まず、球橋さんのとる戦略について考えます。 箱木さんが新しく箱を買わなくて済む場合は球橋さんにとって損なので、そのようなボールはなるべく選びたくありません。 つまり、色 \(c\) のボールが 容量より少ない数 入っている箱のことを色 \(c\) の箱と呼ぶことにすると、まだ色 \(c\) の箱が無いような \(c\) が存在するときは、球橋さんは必ず色 \(c\) のボールを選びます。

そうでない場合、どのボールを渡しても箱木さんはお金を払うことなく \(1\) 円を手に入れてしまいます。球橋さんはこのような状況はなるべく早く脱したいので、残りの容量が最も少ない箱の色 \(c\) を選び、その箱の容量がなくなるまで色 \(c\) のボールを選び続けます。

球橋さんがこのような戦略を取ることをふまえると、箱木さんの視点では、このゲームは、次のような（球橋さんの参加しない）ゲームに言い換えることができます。

最初、箱木さんは空のリスト \(L\) を持っていて、以下の操作を好きなだけ繰り返す。

• リストの長さが \(M\) 未満である場合、好きな箱 \(i\) を選び、\(P_i-1\) 円を払って \(L\) に \(V_i-1\) を追加する。
• そうでない場合（つまり、リスト \(L\) の長さが \(M\) である場合）、リストに含まれる値の最小値を \(m\) とする。\(m\) 円を得て、リストから \(m\) を \(1\) つ消去する。

\(O(2^N N)\) 解法

ここで、ある（箱木さんが最適に行動したとは限らない）ゲームが終わったとして、箱木さんの所持金の変化について考えます。 箱木さんがこのゲームで買った箱を \(i_1,\dots,i_k\) と置きます。

\(0<k<M\) のときは、お金を払うだけになってしまうので、何も買わない (\(k=0\)) ほうがましです。\(k=0\) の場合は答えは \(0\) です。

次に \(k\ge M\) の場合を考えます。 箱木さんが払う金額は \(V_{i_1}+\dots+V_{i_k}-k\) 円です。 また、リストに対する操作を観察することで、ゲーム終了時にリストに残っている要素は、 \(V_{i_1}-1,\dots,V_{i_k}-1\) のうち、大きい方から \(M-1\) 個の要素であることが分かります。 よって、箱木さんが得る金額は \(V_{i_1}-1,\dots,V_{i_k}-1\) の小さい方から \(k-(M-1)\) 個の和です。 以上より、すべての箱の選び方を試すことで、箱木さんの最適な行動を求めることができます。計算量は \(O(2^N N \log N)\) です。 事前に入力を \(V_i\) でソートしておくことで、\(O(2^N N)\) になります。

\(O(N \log N)\) 解法

入力が \(V_i\) で降順にソートされているとします。箱木さんが選ぶ箱のうち、添字が小さい方から \(M\) 個目にあたるものを \(t\) とおき、\(t\) で場合分けします。

ある \(t\) を固定したとき、箱木さんは次のように箱を選びます。

• 箱 \(1,\dots,t-1\) から \(M-1\) 個の \(i\) を選ぶ
  • 箱木さんはそれぞれ \(P_i-1\) 円払う
• 箱 \(t\) を選ぶ
  • 箱木さんは \(P_t-1\) 円払う
• 箱 \(t+1,\dots,N\) から任意の個数選ぶ
  • 箱木さんは箱 \(i\) を選んだ場合 \(V_i-P_i\) 円得る

よって、この場合の箱木さんの最適な行動は、次のようになります。

• 箱 \(1,\dots,t-1\) のうち \(P_i\) の小さい方から \(M-1\) 個選ぶ
• 箱 \(t\) を選ぶ
• 箱 \(t+1,\dots,N\) から \(V_i-P_i\) が正になるものをすべて選ぶ

\(1,\dots,t-1\) のうち \(P_i\) の小さい方から \(M-1\) 個の和を各 \(t=1\dots,N\) について求めることは、ヒープなどのデータ構造を使うことで \(O(N \log N)\) でできます。 \(t,\dots,N\) のうち \(V_i-P_i\) が正になるものの和を各 \(t=1\dots,N\) について求めることは、\(t\) の降順に順番に1つずつ計算していけば \(O(N)\) です。 以上より、この問題を \(O(N \log N)\) で解くことができます。

C++による実装例