はむこの勉強記録

http://bit.ly/2ktf20t の写し

ちょっと早い数列aの全列挙 where sum(a) == x && a <= b, given x, b

Topcoder 691 Div.1 Medで、「数列aの全列挙 where sum(a) == x && a <= b, given x, b」が必要だったが、頭の良い実装方法がわからず、3回くらい実装方針変えたりめちゃくちゃ大変だったので、メモ。

|a|=10なので、rep(i0, min(x, b0)) rep(i1, min(x-i1, b1)) …としても良かったのだが、流石に舐めくさっている。以下のような状態を持って、可逆な再帰を組んだ:「ちょうどi個を見終えて、残りがsで、現在の配列がaである場合。」。また、前処理でimosして、先を全部集めても無理なら枝刈りをいれるようにした。

ideone.com

github.com

500万個ヒットに対して、僕のがローカルで大体2s。kmjpさんの実装と速度比較してみたら、kmjpさんのが大体3sくらいだった。ちょっと早い。もっと早い列挙ください。

kmjp.hatenablog.jp