- 323 名前：デフォルトの名無しさん mailto:sage [2017/07/04(火) 21:28:12.76 ID:QK6Kginy.net]
- >>296 >>299 Perl5
ideone.com/0yJ5U9
リスト処理ではなく、先ずは正規表現と文字列処理を使って書いてみた。
3１…の3のように、食べているうちに後続の数値皿が通り過ぎてしまうような、
取りこぼしを起こし得る皿では、その数値を食べるか、あるいはスルーするか、
再帰的に両方に分岐し、木構造で計算しているが、
逆に食べている間に飛び越しを起こさないところでは、分岐が不要なので
来た順に直ちに食べることによって、枝分かれの過剰な細分化を抑制した。
それでも全探査すると、サンプルデータの三つ目まではすぐ解けるが、
四つめ以降は時間がかかりいつ終わるか分からない。
そこで、検索された食事秒数の最小値の更新状況を記録し、
同じ最小値が一定回数以上連続して繰り返し検出されるようになったら
最短値に収束したと見なし、探索を打ち切ることによって短時間で
解を出力できるようにした。打ち切り上限は10をハードコードしてあるが
今回のサンプルデータについては4か5で十分そうだ。
なお、23_ のような、2を食べることによって飛び越しを起こすポイントの
一番最後のものは,食べずにスルーして先に2を食べた方が、
次の周で早く食べ終わることは明らかだ。
これを演繹的に繰り返して、遡ってゆけば、上記のように木構造に
わたって動的に計算して探索しなくても、静的に求解できそうな気がしたが
難しそうなので、見送った。
|
 |
