第14回日本情報オリンピック　予選６

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

解説

単純な解法として，JOI 君がお菓子を購入する屋台をあらかじめ固定してしまうという方法が考えられる．お菓子を購入する屋台を固定したとき，ある区画を通れるかどうかは，その区画および隣接する区画にある屋台のうち，どの屋台でお菓子を購入するかを調べると判定できる．通れる区画がわかっていれば，JOI 君が (1, 1) から (H, W) まで東あるいは南への移動のみで移動できるかどうかは動的計画法により判定できる．この解法の場合，屋台の数を S とすると，お菓子を購入する屋台の選び方は 2^S 通りになり，入力 1 に対しては正解できるが，入力 2 以降については現実的な時間で解を求めることができない．

もし，JOI 君が同じ屋台でもお菓子を購入するとして考えると，比較的簡単な解法がある．すなわち，各区画について，その区画を通るときに買い物によってかかるお金の額を計算し，それをもとに (1, 1) から (H, W) までの移動のための金額を動的計画法によって求めることができる．しかし実際には，JOI 君は同じ屋台では複数回買い物をしないため，どの屋台で買い物をしたかも動的計画法の状態として持っておく必要がある．

重要な点は，JOI 君が東あるいは南の区画へしか移動しないため，動的計画法において，JOI 君がいる区画の近くについてのみ，その屋台でお菓子を購入したかを持っておけばよいということである．具体的には，区画 (i, j) について考えているとき，区画 (i-1, j+1), (i, j+1), (i+1, j), (i+1, j-1) について，そこに屋台が存在したときにお菓子を購入したかを持っておけば十分である．隣の区画へ移動するときには，移動の後の状態で新たに状態として持つようになる区画のそれぞれについて，そこに屋台があるときにお菓子を購入するかどうかを決めるようにすればよい．実装上は，屋台が存在しない区画にも，値段が 0 のお菓子を販売している屋台が存在すると考えると比較的考えやすくなる．

このようにして動的計画法を行うと，O(HW) で正しく答えを求めることができる．ただし，動的計画法の状態遷移は若干複雑になるので，注意してプログラムを作成する必要がある．