Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

【Code Thanks Festival 2018 H - Median Game】中央値Xが実現出来るかでにぶたん

解けなかったです。エディトリの理解。正しいとは限りません。

汎用性の高い考え方な気がしました。

H - Median Game

問題

カードの山をAliceから引いていく。

引いた都度、整数の和を記録していく。

最後に、書き出した整数のうち中央値(偶数の場合は中央右側)をスコアとする。

Aliceはこれを最大化したい、Bobは最小化したい。

最善の場合、スコアはいくつになるか?

制約: N=1000

方針

貪欲ではうまくいかなそうです。

中央値をX以上に出来るかを考えて、二分探索に帰着させます。

似たような話としては、平均値がX以上になるか二分探索するという典型問題があり、それの類問と言えます。

この問題は二分探索 x DPの組み合わせです。

  • Aliceから見て、dp1[i] := i番目を見ている時のX以上 - X未満の最大値
  • Bobから見て、dp2[i] := i番目を見ている時のX以上 - X未満の最小値

として例えば、dp1[i] = max { ([i,j)をとる。それがX以上なら足す。未満なら引く)+ dp2[j] }

のように書けそうです。もしdp1[0]が0以上なら中央値をXに出来ます。

考察

こういう相互のDPは、お互いの値が足せないと意味がないため、お互いに何か単一の値の最大・最小など逆行するものを目指すと考えるしかない。

ここでは、X以上とX未満の個数差について最大と最小を目指すと捉えることにしている。つまり、片方から見るとmin of maxだし、もう片方から見るとmax of minという形にする。