ctyl's problem solving

競技プログラミングが主な話題です。

CODE FESTIVAL 2017 Final G Mancala

この記事は解説 Advent Calendar 17日目の記事です。

問題概要

G - Mancala

一列に並んだ N個のマスがある。各マスには 0 \leq x \leq K個の石を置くことができる。ここで次の操作を何回か行う。

操作:ちょうど i個の石が置いてある i番目のマスどれかを選び、 i番目の石を 0個に、 i-1以下番目のマスに石を1つづつ追加する。

操作回数ができるだけ多くなるような戦略で行って、最終的にマス目に残った石の数がスコアとなる。 ありうる初期状態すべてのスコアの総和をとるといくつになるか。

解法

(公式Editorialに補足する形式となっています)

操作1回によって石の数は1つづつ減るので、(初期状態の石の個数)-(スコア)=(操作回数)となる。 操作回数を多くするための最適な戦略は操作可能なマス目の中で最もindexの小さいマス目を選ぶことである(Editorial参照)。

全ての初期状態の石の個数の和は(各マス目に入る石の数の期待値)  \times N \times (初期状態の場合の数)を考えると、

(各マス目に入る石の数の期待値)  \times N \times (初期状態の場合の数)  \\ = \frac{K}{2} \times N \times (K + 1)^{N}

となるので、 全ての初期状態の操作回数の和を求めることができれば、引き算でスコアの総和を求めることができる。

状態 dp(i, j)を(i番目を含む)i番目以降のマス目でj回操作が可能なi番目以降のみを考えた初期状態の場合の数と定め、 iについて後ろからDPを行う。

dp(i+1, j)からdp(i,*)を更新する際に気になるのが初期状態の時の i番目のマスにある石の個数( 0 \leq x \leq K)である。

この個数がiより大きい場合は i番目のマスで操作することはできないので i+1番目の操作回数をそのまま持ち越す。

そうでない場合はi番目のマス目で \frac{x+j}{i}回操作を行うことができる。こう立式できる理由は、最適な戦略ではi+1番目で何回か操作を行ってi番目がi個になった時点でi番目のマス目で操作を即座に行うことができるからである。(実際は即座に行うとは限らず、indexの小さいマスから順に操作を行うが、i番目のマスの石の個数に影響を与えることはない)

ここまでだと O(N^{4})に見えるが、操作の理論的な回数の上限を考えるともっと高速化することができる。 この問題だと N=K=100の場合で石の数が順に 1,2,3,\dots,100となっている場合の操作が最大で、3281回となっている。(検証用のソースコードも合わせて下に貼った) この高速化をすると十分間に合う。

Code Festival 2017 Final G Mancala


DPは想定された計算量で計算可能な状態を定義するところがそもそも難しい。この問題だと前から操作を行う最適な戦略で後ろからDPするので、再帰的な考えに慣れておく必要がありそう。