不参加だったけどEasyもMediumもミスしてたのでまぁ助かったか。
https://community.topcoder.com/stat?c=problem_statement&pm=14518
問題
整数Kが与えられる。
N*Mのグリッドで構築され(N,Mは50以下)、一部のセルが埋まった迷路のうち、左上から右下マスまで隣接マスをたどって移動する際の最小移動マス数がKになるものを構築せよ。
解法
空きマス目が(K+1)となる道を作ることを考えよう。
右にずっと移動して下に移動する迷路を作れば移動マス数が(N+M-2)となるので、K≦98の場合はこれでよい。
それ以上は何かしら折り返しが必要である。
まず上端に以下のような構成を作ると、51マス空きマスを配置できる。
.................................................. #################################################.
あとはその下に以下の構成をつなげていけば、102マスずつ空きマスを配置できる。
.................................................. .################################################# .................................................. #################################################.
残りはこんな感じで少し短めの折り返しを作ろう。
折り返しの長さでマス数を2ずつ調整できるので、あとは最終行の有無で1マス調整できる。
############...................................... ############.##################################### ############...................................... #################################################.
まとめ
なんだこの問題。
