AOJ 0581 お土産購入計画 (Gifts)
2012年の情報オリンピック予選の6問目。当時解けなかったのは当然としても、今見ても結構つらい問題で、5年越しにようやくACしたのでなんとなくブログに書いておく。
問題文
まあ日本語なので読みましょう
解法
流石にbitDPはしたくなって当然。
単純に考えると
dp[y][x][k][hash] := 「地点(x, y)におり後k回遡れる状態で、マンハッタン距離が3以下であるような周りの点の内辿ったことのある点の集合がhashで表される時の、それまでに買えたお土産の最大個数」
というdpを立てたくなる。
本質はその計算量で、この状態では、S = {マンハッタン距離が3以下であるような周りの点}としてO(HWK * 2^|S|)であり、|S|=24であることを考えると、概算としてこれは50*50*3 * 2^24 = 125829120000であって到底間に合わない。
ただこれには相当な無駄があって、例えば以下のような状態というのは考えなくて良い。
ここで、黒は今自分がいる点であり、オレンジは既に辿った点を表している。
このような状態になるためには、下と右のオレンジのラインの両方を辿り、黒に戻ってくるという遷移が必要で、これはKが6以上じゃないと不可能。
もっと変なケースを考えると一瞬怖い気持ちになるが、そもそもhashで持つのは既に辿った点の集合であるということに注意すると、更に考えなくていい状態が多いだろうと考えられる。
逆に考えなくてはならない状態の内、最もオレンジの個数が多いものは、こんな感じになる。
これは例えば右下下左上上と動くことによって達成できる状態で、この時点でk=0となる。
本当に最大か？？もうちょっと増えない？？という気持ちに一瞬なるが、まず、遡る動きをすると、kの数が減り、記憶しておかなければならないオレンジの位置が減ってしまうので、出来るだけオレンジは右下に来るようにしてよい。で、この状態になるまでの動きには無駄がない(黒に戻ってくる動き以外の全てで、オレンジの数が増えている)。そして、仮にここから下や右に移動したとすると、オレンジの丸が増える時には、少なくとも1つ以上の元々あるオレンジがフェードアウトするので、これ以上増えることはない(はず(本当か？(一応__builtin_popcountでhash計測したら5が最大だったょ)))。
したがって、大きく見積もっても、2^24通りの内、考え無くてはならない状態の上界は
Σ[i=0..5]24Ci = 55454であって、55454 * 50 ** 2 * 3 * 4 = 1663620000 = 1.7*10^9な時点で、JOI予選本番中であれば、普通にGOサインを出す判断ができる。
また、この上界はかなり余分めに見積もっているのは明らかで、本当に発生しうる状態のみを計算するように真面目に書けば、普通に少なくとも10分の1ぐらいにはなりそうに思える(そもそもオレンジが5個あるケースというのは、さっきの2x3の長方形しかないはずで、24C5どころか8通りしかないように見える)。実際、適当に書いても1秒以内でAC出来た。
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2632622
ちなみにJOIの公式の解説には「考えなければならない近傍は高々12個で状態は2^12なので余裕です」と書いてあるが、正直これはまだ理解できていない。仮に考えなければならない近傍が12個だったとして、その近傍の位置が固定されていればそれは当然2^12だが、実際には固定されていないはずでコンビネーションが出てくるべきなわけで、2^12という見積もり方は嘘なんじゃないかと思うのだけど、誰か分かる人おしえてほしい。
