第17回日本情報オリンピック　予選５

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

解説

まず，最終的にできる北西の端から南東の端へのパス上にないマスの木を伐採することは無意味であることがわかる．パスを定めたときにその上のマスの木をすべて伐採するのにかかる時間を求めるのは簡単である．このため北西の端から南東の端へのパスを全探索することで小課題 1 が解ける．

小課題 2 の条件下では，このパスにおいて北方向や西方向への移動を考えなくて良いことがわかる．このため動的計画法により北西のマスから順に，北西の端からそのマスまでのパスのうちでその上の木をすべて伐採するのにかかる時間の最小値を求めていくことで小課題 2 が解ける．

満点解法を解説する．北西の端からあるマスへのパスを考えたとき，そのパス上の木をすべて伐採するのにかかる時間と，そのパスの長さだけが重要である．たとえば，北西の端からある同一のマスへのパス，パス 1 とパス 2 が存在し，長さが等しく，その上の木をすべて伐採するのにかかる時間はパス 1 のほうが短いとしよう．このとき，最終的にできる南東の端へのパスがパス 2 を含むならば，それをパス 1 に変えたほうが全体の伐採にかかる時間が短くなる (パスの長さが異なる場合は必ずしもこれは成り立たないことに注意せよ)．

そのため，森林内のマスと自然数のペアに対し，北西の端からそのマスへのパスで，長さがその自然数であるもののうちで，そのパス上の木をすべて伐採するのにかかる時間の最小値を求めればよい．これは長さが短いものから順に計算していくことで，動的計画法により求めることができる．パスの長さとして考えるべき自然数の範囲は H*W までであるので，時間計算量 O((H*W)^2) でこの問題を解くことができる．