全ての選出と交換に渡る全ての敵の組み合わせを計算 その3 選り分けの仕組み

まだ仕上がっていませんが、正しい結果かどうかの選り分けはなんとかうまくいきそうです。
選り分けは次のような問題に変換して考えることにしました。

以下のように並んだ地図がある。

shop 0, gate 0, shop 1, gate 1, ..., shop N-2, gate N-2, end

旅人はこの地図上をshop 0から開始して一つずつ右へ進んでいく。
旅人はM個のアイテムを持てる。
shop 0ではS個のアイテムがあり、旅人はそこから所持するアイテムをM個選ぶ。
各shop i (i ≧ 1)ではM個のアイテムがあり、旅人はこのアイテムのうちの一つと所持アイテムのうちの一つを交換できる。交換しないことも選べる。
gate iでは持っているアイテムがチェックされる。認められれば先へ進め、そうでなければ旅はそこで終了である。
認められる条件は次の二つがともに成立すること:

  • shop i+2のアイテムを持っていない
  • gateごとに決められている必要品リストにのっている全てのアイテムを持っている

(shop N-1, shop Nというのは地図にはないが、それらにあるアイテムも決められているものとする)
旅人がendまでたどり着くことは可能か判定せよ。

ただしshop iにあるアイテムの列をShop[i]で表すとき、Shop[i] + Shop[i+1]の中には重複はないものとする (i ∈ 0..N-1) (+は二つの列の連結を表すものとする)

まず、必要品リストの条件を満足させることを考えます。
gate iでアイテムaが要求されているとすると、gate iより左にあるshopのどこかでアイテムaを得てそれをgate iまで保持し続けねばなりません。
ここでアイテムaを得ることができるshopが複数あったときは、一番右にあるものを使うことになります。たとえばshop 2とshop 4でaを得ることができたとしてもshop 2でaを得て保持し続けることはできません。gate 2でshop 4のアイテムを持っていないことがチェックされるからです。

ここで「shop iでアイテムaを得て少なくともgate jまで保持し続ける」といった遂げねばならない仕事をすべてメモした予定表を作ります。

ただし「shop iでaを得て少なくともgate jまで保持し続ける」と「shop iでaを得て少なくともgate j+2まで保持し続ける」のように開始地点とアイテムが同じ仕事が複数あれば、一番長いものだけを残してあとは消します。

このとき次の条件が成立するか確認します。

  • 一度に進行する仕事はM個まで
  • shop i (i ≧ 1)を開始地点とする仕事は各iごとに1個まで

この条件が成立しないときは不可能なので、この時点で不可能と出力します。

これで必要品リストの条件のことは忘れて、後は作った予定表を守りながら、ゲートでの規制(○○を持っていない)条件を満足させることができるかを考えればいいです。

各shopそれぞれにおいてこれから先規制されることのないアイテムをできるだけ手持ちに多くする選び方が規制条件を満足させるにはよい選び方であり、このような選び方がすべてだめなら、他の選び方もすべてだめであることが予想できるでしょう。
実はさらに、あるルールに従った選び方のうちの一つをとり、この選び方でだめならほかの全ての選び方もだめだといえるのです。
だから、その一つの選び方でうまくいくのか確かめるだけで判定できます。
このその場での最善を選択することを繰り返す方法は貪欲法と呼ばれているそうです。
このことの証明はまた今度の記事にします。

筆者: oupo (連絡先: oupo.nejiki@gmail.com)