Hatena::Grouptopcoder

TopCoder煮ブログ

本家ブログはこっち → http://d.hatena.ne.jp/nitoyon/

2008-10-05DIV1 Medium 特訓中

CustomDice (SRM416 DIV1 Medium)

| 12:22 | CustomDice (SRM416 DIV1 Medium) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - CustomDice (SRM416 DIV1 Medium) - TopCoder煮ブログ

んー、解けない…。

しばらく考えて方針は決まったがコードに落とせない。1位のコードを見たら見事。んー、読めるが書けない。

動的計画法の適用

一応まとめておく。

平均 M をみたす全ての組み合わせを見つけるために、さいころの値が変わる面の数を順番に増やしながら DP していく。

例えば、2面だったとして、合計が24(21 + 3)になる組み合わせ D3 は以下の2通り(1 2 3 4 5 6 からの差分で記している)。

1: 0 0 0 0 0 3
2: 0 0 0 0 1 2

2面が変わるときに合計が27(21 + 6)になる組み合わせ D6 は以下の3通り。

1: 0 0 0 0 0 6
2: 0 0 0 0 1 5
3: 0 0 0 0 2 4
4: 0 0 0 0 3 3

では、3面を変えるときを許容した場合、D6 の増分は D3 の要素数になる。

なぜか。D3 の各要素に 0 0 0 1 1 1 を足すと、3面変わるときに取りうる全ての組み合わせになるからだ。

具体例を見れば納得できるはず。

1: 0 0 0 0 0 6
2: 0 0 0 0 1 5
3: 0 0 0 0 2 4
4: 0 0 0 0 3 3
5: 0 0 0 1 1 4  (←0 0 0 0 0 3 + 0 0 0 1 1 1)
6: 0 0 0 1 2 3  (←0 0 0 0 1 2 + 0 0 0 1 1 1)

4面変わるときの D6 は同じように、D2 に 0 0 1 1 1 1 を足す。結果として、D6の組み合わせは次のようになる。

1: 0 0 0 0 0 6
2: 0 0 0 0 1 5
3: 0 0 0 0 2 4
4: 0 0 0 0 3 3
5: 0 0 0 1 1 4
6: 0 0 0 1 2 3
7: 0 0 1 1 1 3  (←0 0 0 0 0 2 + 0 0 1 1 1 1)
8: 0 0 1 1 2 2  (←0 0 0 0 1 1 + 0 0 1 1 1 1)
9: 0 1 1 1 1 2  (←0 0 0 0 0 1 + 0 1 1 1 1 1)
0: 1 1 1 1 1 1  (←0 0 0 0 0 0 + 1 1 1 1 1 1)

同じように、これに 1 1 1 1 1 1 を足したものは、D12 の6面変わるときの組み合わせを出すときに利用できる。