公式

C - Reversible Card Game 解説 by riano_


ゲームの開始前に、Bob が各カードをどちらの向きで取るか決めたとき、それが実現できるかを考えます。

各ターン開始時に「取りたい向きのカードが偶数」であれば、Alice が \(1\) 枚裏返すことで「取りたい向きのカードが奇数」になります。すなわち、\(0\) ではあり得ないので、取りたい向きのカードを \(1\) 枚とることができます。すると、再度「取りたい向きのカードが偶数」の状態でターンが始まります。

すなわち、「取りたい向きのカードが偶数」の状態でゲームを開始すると、全てのカードを取りたい向きで取ることができます(同様に偶奇を考えると、「取りたい向きのカードが奇数」の状態でゲームを開始すると、全てのカードを取りたい向きで取ることが不可能と分かります)。

\(A_i>B_i\) であるカードが偶数枚であれば、全てのカードの大きい数字が書いてある面を「取りたい向き」に定めたとき、「取りたい向きのカードが偶数」となるので、これが最善です。\(A_i>B_i\) であるカードが奇数枚の時は、差が最小のカードのみ小さい数字の面を「取りたい向き」に定めると、取りたい向きのカードが偶数枚の状態でゲームを始めることができます。全てのカードを大きい数字の面で取ることは不可能であることも合わせると、これが最善です。

投稿日時:
最終更新: