Google Code Jam 2010 Round 3

D

10進数表記で合計がNになるように、B進数の整数の和に分割することを考える。このとき、各桁に同じ数が出現しないような整数の和に分割する方法は何通りあるか答えよ、という問題。

この手の問題は基本的に上から決めるか下から決めるか、のどっちか。キャリーがあるので、下から決めるのが妥当、と判断。

K個の整数に分割することを考える。このとき、K個の整数の和が決まれば、何通りの結合方法があるか分かる。これはDPで計算可能。今現在いくつの整数の和なのか、使った最大の整数はいくつか、合計値はいくつか、という三つでDPする。

これを用いて、一番下の桁から決定していく。いくつの整数の和に分割しようと、そのときの和はNと法Bで等しいことが求められる。これらを全部確かめていく。キャリーがある分、次の桁が変わるが、その上までキャリーが伝搬することはない(あっても1くらい)ので、実際に計算する必要があるのは、各桁についてB/2通り前後で済む。

ある桁を計算するときにK個の値の和に分割したとすると、次の桁を計算するときにはK以下個の和に分割しないといけない。また、次の桁がM個の和であるとすると、M個分については、任意に並び替えが可能。(これは上の桁が存在するため、結果的に異なる整数の集合に分割できることになるため。)また、K-M個のところに0を割り当ててしまうと、整数としてみたときにK-1個に分割していたことになってしまうので、そうならないように気を付ける。つまり、最初のDPのときに、K個の中に0を含むかどうかで場合分けしておく必要がある。

後はメモ付き探索して、下から順に桁を決定していけばおしまい。基本的にint溢れに気を付けて実装するだけの問題。