CODE FESTIVAL 2017 Final G Mancala
この記事は解説 Advent Calendar 17日目の記事です。
問題概要
一列に並んだ個のマスがある。各マスには個の石を置くことができる。ここで次の操作を何回か行う。
操作:ちょうど個の石が置いてある番目のマスどれかを選び、番目の石を個に、以下番目のマスに石を1つづつ追加する。
操作回数ができるだけ多くなるような戦略で行って、最終的にマス目に残った石の数がスコアとなる。 ありうる初期状態すべてのスコアの総和をとるといくつになるか。
解法
(公式Editorialに補足する形式となっています)
操作1回によって石の数は1つづつ減るので、(初期状態の石の個数)-(スコア)=(操作回数)となる。 操作回数を多くするための最適な戦略は操作可能なマス目の中で最もindexの小さいマス目を選ぶことである(Editorial参照)。
全ての初期状態の石の個数の和は(各マス目に入る石の数の期待値) (初期状態の場合の数)を考えると、
(各マス目に入る石の数の期待値) (初期状態の場合の数)
となるので、 全ての初期状態の操作回数の和を求めることができれば、引き算でスコアの総和を求めることができる。
状態を(番目を含む)番目以降のマス目で回操作が可能な番目以降のみを考えた初期状態の場合の数と定め、について後ろからDPを行う。
からを更新する際に気になるのが初期状態の時の番目のマスにある石の個数()である。
この個数がより大きい場合は番目のマスで操作することはできないので番目の操作回数をそのまま持ち越す。
そうでない場合は番目のマス目で回操作を行うことができる。こう立式できる理由は、最適な戦略では番目で何回か操作を行って番目が個になった時点で番目のマス目で操作を即座に行うことができるからである。(実際は即座に行うとは限らず、indexの小さいマスから順に操作を行うが、番目のマスの石の個数に影響を与えることはない)
ここまでだとに見えるが、操作の理論的な回数の上限を考えるともっと高速化することができる。 この問題だとの場合で石の数が順にとなっている場合の操作が最大で、回となっている。(検証用のソースコードも合わせて下に貼った) この高速化をすると十分間に合う。
Code Festival 2017 Final G Mancala
DPは想定された計算量で計算可能な状態を定義するところがそもそも難しい。この問題だと前から操作を行う最適な戦略で後ろからDPするので、再帰的な考えに慣れておく必要がありそう。