題意
箱の中にビー玉が $n$ 個あり、それぞれ色が付いています。
このビー玉を使ってアリスとボブの2人がゲームをします。
2人は「好きなビー玉を1個選んで取る」という操作を交互に繰り返します。（アリスが先攻です）
ビー玉が全て取りつくされて箱が空っぽになったらゲーム終了で、下記に従ってアリスの得点が決まります。
- アリスが取った色の種類数を $a$ とする
- その $a$ 種類の色のうち、アリスが独占した色、つまりボブが取っていない色の種類数を $b$ とする
- アリスの得点は $a+b$ となる
アリスは、得点をなるべく大きくしようと行動します。
ボブは、アリスの得点をなるべく小さくしようと行動します。
アリスは何点獲得できるでしょうか？
ビー玉の個数と色が与えられたとき、アリスの得点を求めるプログラムを作成してください。
サンプル
下図のように、12個のビー玉があるとします。
2人が最適に行動すると、下図のような結果になるでしょう。
- アリスが取った色は5種類
- その5種類の色のうち、アリスが独占した色、つまりボブが取っていない色は2種類（黄、青）
となっているため、5 + 2 = 7 より、アリスの得点は7点となります。
考えたこと
上図のサンプルでは、例えば青いビー玉は1個しかないため、アリスはこれを取るだけで独占となります。すると $a$ と $b$ が1ずつ増加することになり、2点獲得です。
このように「1個しかない色」がまだ残っているゲーム前半では、アリスはそれを狙うべきでしょう。また、ボブも積極的にそれを取り、アリスの独占回数を減らすべきでしょう。
そして「1個しかない色」がなくなったゲーム後半では、アリスの独占回数を増やしたくないボブは、アリスが取ったビー玉と同じ色のビー玉をすぐ取るという行動に出るべきでしょう。
すなわち、下記のようなゲームの流れになりそうだと考えました。
- 1個しかない色の種類数を $p$ とする
- 2個以上ある色の種類数を $q$ とする
- ゲーム前半は、アリスとボブが $p$ を半分ずつ奪い合う（独占なので1色取るたびに2点）
- $p$ が奇数なら、アリスは $p+1$ 点獲得することになる
- $p$ が偶数なら、アリスは $p$ 点獲得することになる
- ゲーム後半は、アリスは $q$ 種類の色のビー玉を順番に取る（独占ではないので1色取るたびに1点）
- アリスは $q$ 点獲得することになる
まとめると、この問題の答え、つまりアリスの得点は下記のようになります。
- $p$ が奇数なら、答えは $p+1+q$
- $p$ が偶数なら、答えは $p+q$
さきほどのサンプルに当てはめると、$p=3$ および $q=3$ より、アリスの得点は $3+1+3=7$ と計算できます。
Codeforces に提出！
このビー玉取りゲームの問題は、Codeforcesというサイトで開催されたプログラミングコンテスト「Educational Codeforces Round 172」の B 問題で出題されたものです。
問題のタイトルは「Game with Colored Marbles」です。
実際に、
- ビー玉が1個しかない色の種類数を $p$ とする
- ビー玉が2個以上ある色の種類数を $q$ とする
- $p$ が奇数なら、答えは $p+1+q$
- $p$ が偶数なら、答えは $p+q$
という計算を行うプログラムを実装して提出してみたところ、無事に正解と判定されました。良かったです。
int score = p + ((p % 2 == 1) ? 1 : 0) + q;
はじめに問題文を読んだときは「へんてこな得点計算をするゲームだなぁ」と思いましたが、意外とシンプルな計算式でアリスの得点を求めることができました。
以上、私が考えたメモでした。