576.1
かなりひどいことになった...。
256
上下方向にはKマス進める状態でDFSするときに、目的に到達できる最小のKを答えよ、という問題。左右には1マス移動のみ。
Kを順番に探索やるだけ。
576
整数配列があるので、長さLの区間でカバーするが、カバーするときにカバーする領域の値の合計値がA以上B以下になるようにすることと、他ので先にカバーされている区間はカバーしても値を回収できない。このとき、値を回収した領域の集合で同一性を判断するとして、何通りのカバー方法があるか答えよ、という問題。
区間の長さが同じなので、左から順に上下決めつつDPやるだけ。基本的に隣の区間との上下だけを気にすれば良いはず。二つ隣のの影響を受けるような場合には、隣のヤツが何も値を回収できなくなるので、ひどいことになる。
900
ある文字列をはばWで折り返して無限回繰り返し記述した結果のうちの、矩形領域が与えられる。元の文字列として可能なものは何通りあるか答えよ、という問題。
多分競合とか見つつ、周期性とか考えつつ、じゃないかと思ったけれど、そんなに簡単な話ではないっぽい。