>>296 >>299 Perl5
http://ideone.com/0yJ5U9
リスト処理ではなく、先ずは正規表現と文字列処理を使って書いてみた。
31…の3のように、食べているうちに後続の数値皿が通り過ぎてしまうような、
取りこぼしを起こし得る皿では、その数値を食べるか、あるいはスルーするか、
再帰的に両方に分岐し、木構造で計算しているが、
逆に食べている間に飛び越しを起こさないところでは、分岐が不要なので
来た順に直ちに食べることによって、枝分かれの過剰な細分化を抑制した。
それでも全探査すると、サンプルデータの三つ目まではすぐ解けるが、
四つめ以降は時間がかかりいつ終わるか分からない。
そこで、検索された食事秒数の最小値の更新状況を記録し、
同じ最小値が一定回数以上連続して繰り返し検出されるようになったら
最短値に収束したと見なし、探索を打ち切ることによって短時間で
解を出力できるようにした。打ち切り上限は10をハードコードしてあるが
今回のサンプルデータについては4か5で十分そうだ。
なお、23_ のような、2を食べることによって飛び越しを起こすポイントの
一番最後のものは,食べずにスルーして先に2を食べた方が、
次の周で早く食べ終わることは明らかだ。
これを演繹的に繰り返して、遡ってゆけば、上記のように木構造に
わたって動的に計算して探索しなくても、静的に求解できそうな気がしたが
難しそうなので、見送った。
探検
プログラミングのお題スレ Part9 [無断転載禁止]©2ch.net
■ このスレッドは過去ログ倉庫に格納されています
318デフォルトの名無しさん
2017/07/04(火) 21:28:12.76ID:QK6Kginy■ このスレッドは過去ログ倉庫に格納されています
ニュース
- 【東京】赤坂サウナ火事2人死亡 サウナ室のドアノブ外れ閉じ込められた可能性 ★8 [nita★]
- 【ドイツ】メルツ独首相「正しい措置」「技術革新と柔軟性が必要」 EUのエンジン車禁止撤回を歓迎 [少考さん★]
- 中国国防省が再反論 SNSで公開した音声とは“別の通報”で日本に訓練の時間や海域を通報したと主張★3 [夜のけいちゃん★]
- EU、エンジン車禁止見直しへ 35年以降も条件付き販売容認―日本勢に追い風 [蚤の市★]
- 資さんうどんが「PayPay」の取り扱いを停止 他のキャッシュレス決済は引き続き利用可能 [少考さん★]
- こども家庭庁、2026年から“独身税”を開始、年収200万なら年4200円、年収400万なら年7800円 ★7 [お断り★]
- 【ババア】高市早苗、稲田朋美、三浦瑠麗「中国との戦争と日本の徴兵制は仕方ない、賛成。」 [153490809]
- ゆるキャン△のセックス枠
- お前らって口にガムテープ貼られたら死にそう
- 反省ゼロのホモ野郎いい加減にしろよ
- 穴だらけのコンクリート←これ
- 萩生田😤「早期解散したら高市内閣に期待してる国民に申し訳ない。」 [153490809]
