本番では、運良くEasy, Medが素早く解けたが結局Hardは方針すら立たなかった。
とはいえ、まったく手が出ない問題ではないので
将来的にはこのような問題は解けるようになりたい。
自力では解けなかったので他の人の解答を参考に。
今回は以下の方針およびコードを参考にしました。
TopCoder SRM 597 Div2 Hard LittleElephantAndSubset - kmjp's blog
Javaへの移植は以下
ここで、dpdpは利用できる数字のbitmapに対する選び方の合計を計算する。
dfsは引数valを数字の先頭とする値のうち、N以下かつ同じ数字を使わないものを
bitmap表現ごとにカウントして配列SZに保存する。
例えばval=15のときは、15,152,153...,159,1523,1524,....
の値について深さ優先で探索していく。
引数maskはvalのbitmap表現。
getNumber内では、1から9で始まる値についてdfsを実行することで
すべての値についてSZを計算する。
その後すべてのbitmap表現に対してdpdpで組合せの和を算出している。
方針について勉強になったのはもちろんだけど、
dpdp内にてmaskを構成するbitmap表現を列挙する方法が参考になった。
最大ビットmを求め、mとそれ以下の和でforループさせればいいのは
読めば理解できるけど、自分では思いつきそうにない。
べき乗集合の問題など、bitmap表現を用いる場合には常套手段なのかな？
あと、MOD計算では-1を表すのにMOD-1を用いるのも知らなかった。
まだまだ経験不足を思い知らされる。
