[過去ﾛｸﾞ]
プログラミングのお題スレ Part9 [無断転載禁止]©2ch.net (1002ﾚｽ)
プログラミングのお題スレ Part9 [無断転載禁止]©2ch.net http://mevius.5ch.net/test/read.cgi/tech/1480579110/
上
下
前次
1-
新
通常表示
512ﾊﾞｲﾄ分割
ﾚｽ栞
抽出解除
必死ﾁｪｯｶｰ(本家)
(べ)
自ID
ﾚｽ栞
あぼーん
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索
歴削→次ｽﾚ
栞削→次ｽﾚ
過去ﾛｸﾞﾒﾆｭｰ
318: デフォルトの名無しさん [sage] 2017/07/04(火) 21:28:12.76 ID:QK6Kginy >>296 >>299 Perl5 http://ideone.com/0yJ5U9 リスト処理ではなく、先ずは正規表現と文字列処理を使って書いてみた。 3１…の3のように、食べているうちに後続の数値皿が通り過ぎてしまうような、 取りこぼしを起こし得る皿では、その数値を食べるか、あるいはスルーするか、 再帰的に両方に分岐し、木構造で計算しているが、 逆に食べている間に飛び越しを起こさないところでは、分岐が不要なので 来た順に直ちに食べることによって、枝分かれの過剰な細分化を抑制した。 それでも全探査すると、サンプルデータの三つ目まではすぐ解けるが、 四つめ以降は時間がかかりいつ終わるか分からない。 そこで、検索された食事秒数の最小値の更新状況を記録し、 同じ最小値が一定回数以上連続して繰り返し検出されるようになったら 最短値に収束したと見なし、探索を打ち切ることによって短時間で 解を出力できるようにした。打ち切り上限は10をハードコードしてあるが 今回のサンプルデータについては4か5で十分そうだ。 なお、23_ のような、2を食べることによって飛び越しを起こすポイントの 一番最後のものは,食べずにスルーして先に2を食べた方が、 次の周で早く食べ終わることは明らかだ。 これを演繹的に繰り返して、遡ってゆけば、上記のように木構造に わたって動的に計算して探索しなくても、静的に求解できそうな気がしたが 難しそうなので、見送った。 http://mevius.5ch.net/test/read.cgi/tech/1480579110/318
319: デフォルトの名無しさん [sage] 2017/07/04(火) 21:31:48.78 ID:QK6Kginy >>318 書き忘れたけど、食事秒数を探索中に、それまでに見つかっている最小病数を超えたら 打ち切るという、簡単な枝刈りを取り入れてあります。 連投ｽﾏｿ http://mevius.5ch.net/test/read.cgi/tech/1480579110/319
ﾒﾓ帳
(0/65535文字)
上
下
前次
1-
新
書
関
写
板
覧
索
設
栞
歴
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
AAｻﾑﾈｲﾙ
Google検索
Wikipedia
ぬこの手
ぬこTOP
0.041s