第12回日本情報オリンピック 予選6

2012年12月21日
情報オリンピック日本委員会

問題
   お土産購入計画 (Gifts)

解説

単純な場合

まず単純な場合として,JOI 君が一度も寄り道をしない,すなわち東か南の区画への移動のみを行う場合を考えよう.この場合は「JOI 君が区画 (i, j) にいるとき,そこまでに購入したお土産の個数の最大値」を f(i, j) とすると,これは動的計画法によって効率良く計算することができる. f(i + 1, j + 1) は区画 (i + 1, j + 1) が住宅ならば 0 であり,そうでなければ f(i + 1, j + 1) は f(i, j + 1) と f(i + 1, j) のうち大きい方に区画 (i + 1, j + 1) で購入するお土産の個数を加えたものである.道では 0 個のお土産を買うとすればよい.

この場合に上記のような動的計画法が使えるのは,JOI 君が東か南にしか進むことが出来ないので「JOI 君が区画 (i, j) から国際空港へ向かうときに購入するお土産の個数を最大化するとき,最も北西の区画から区画 (i, j) までの道のりは関係ない」という事実が成り立つためである.

寄り道をする場合

JOI 君が寄り道をする場合,JOI 君が北や西に進む可能性があるために上記の単純な場合と同様な考え方の動的計画法を使うことができない.単純に JOI 君のいる区画が分かっただけでは,先ほどと同様にそれまでの道のりを無視するということができない.そこで動的計画法を使うために,JOI 君のいる区画の他にどのようなことが分かっていればそれまでの道のりを無視することができるようになるのかを考えよう.

まず,JOI 君が今までに何回寄り道をしたかという情報が必要である.ただしこれだけでは十分ではない.何回寄り道をしたかが分かっても,どのお土産店を訪れたかが分かっていなければ動的計画法を使うことができない.お土産店を訪れたかどうかの情報をどう扱えばよいかについて考える必要がある.

ひとつの方法として,各お土産店をすでに訪れたどうかを覚えておくというものがある.あるお土産店を訪れたかどうかが分かっていれば,その区画を再び訪れた際に同じ店で 2 回お土産を購入してしまうことを防ぐことができる.しかしこれでは各お土産店について訪れたか訪れていないかの 2 通りの情報があるため,全体で 2(お土産店の個数) 通りのパターンがある.お土産店は最大で H × W 個存在するため,これでは時間内に大きなデータに対して答を計算することはできない.ただし,用意された採点データのうち小さいものについてはこれでも解けるだろう.

このままでは扱うパターン数が多すぎるので,無駄な情報を省くことを考えよう.今 JOI 君がいる区画からどうやってもたどり着けない区画にあるお土産店については,訪れたかどうかを覚えておくのは無駄である.また,あるお土産店を訪れたあとに今 JOI 君がいる区画へ来るのが不可能な場合も,そのお土産店についての情報を覚えておく必要はない.すなわち,覚えておくべき情報は「今 JOI 君がいる区画からたどり着くことができ,かつその区画を通って今 JOI 君がいる区画へ来ることが可能であるような区画にあるお土産店」に関するもののみである.

この場合に扱うパターン数がどの程度になるかを計算しよう.許される寄り道の回数が最も大きい K = 3 の場合でも,前述の条件を満たす区画は最大でも 12 個しかない.よって状態は (現在位置, 寄り道の回数, お土産店の情報) で表され,その数は全部で 50 × 50 × 4 × 212 ≒ 4.0 × 107 である.この状態数であれば大きいデータでも実装方法によって数秒から数十秒で答を計算することが可能であり,用意された採点用データに対して満点を得ることができる.