[過去ﾛｸﾞ]
プログラミングのお題スレ Part9 [無断転載禁止]©2ch.net (1002ﾚｽ)
プログラミングのお題スレ Part9 [無断転載禁止]©2ch.net http://mevius.5ch.net/test/read.cgi/tech/1480579110/
上
下
前次
1-
新
通常表示
512ﾊﾞｲﾄ分割
ﾚｽ栞
抽出解除
ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索
歴削→次ｽﾚ
栞削→次ｽﾚ
過去ﾛｸﾞﾒﾆｭｰ
296: デフォルトの名無しさん [] 2017/06/26(月) 21:09:32.46 ID:92/cX5j1 前にあったやつ。 回転寿司にやってきた私は、コンベア上の寿司をすべて食べて帰ることにしている。 コンベアは毎秒1皿分の速度で流れ、目の前の皿を取るか取らないかを選ぶことができる。 皿取ると同時に食べ始め、食べている間は次の皿を取ることができない。 私が取る以外、皿は追加されたり無くなったりしない。 コンベアの状態が次のような文字列で与えられる。 "31_2" 数字はその皿を食べ終えるのにかかる秒数を表し、_は皿がないことを表す。1文字目が目の前にあり毎秒、左へ回転する。 例えば、"31_2"で最初の皿を食べたとき食べ終わった時の状態は、"2_1_"となる。 すべての寿司を食べ終えるまで最短何秒かかるか求めよ。 "12_3" > 6秒 "313__" > 8秒 "4_35_1264_23_434" > 60秒 "123456789123456789" > 98秒 "88967472612377988186" > 149秒 "19898693316679441672" > 170秒 "93769682716711132249893" > ? http://mevius.5ch.net/test/read.cgi/tech/1480579110/296
298: デフォルトの名無しさん [sage] 2017/06/26(月) 23:01:34.06 ID:GM19K0OY 皿がもうちょっと多いと難しくなるけど、>>296なら力業でも http://mevius.5ch.net/test/read.cgi/tech/1480579110/298
299: デフォルトの名無しさん [sage] 2017/06/26(月) 23:40:33.73 ID:JhsaOf6q >>296 Perl ttp://ideone.com/iUAYUy 実行結果は $ perl 9_296.pl 12_3: 6 313__: 10 (合わない…orz) 4_35_1264_23_434: 62 (合わない…orz) 123456789123456789: 98 88967472612377988186: 151 (合わない…orz) 19898693316679441672: 170 93769682716711132249893: 176 となり、半分が合わない。 そのうち 313__ を手で研鑽すると 10 になるのだが、 313__ は本当に8になるの？ http://mevius.5ch.net/test/read.cgi/tech/1480579110/299
304: デフォルトの名無しさん [] 2017/06/27(火) 00:12:08.45 ID:PK1LDhK1 >>296 は、 目の前にあるやつを食べ続けるだけで最短になっちゃうのもあるってことか。 http://mevius.5ch.net/test/read.cgi/tech/1480579110/304
305: デフォルトの名無しさん [sage] 2017/06/27(火) 00:46:54.34 ID:v9AhJc3r >>296 http://ideone.com/PGKCb4 計算量は2^n*n (n:コンベアの長さ) n=24はほぼ限界 n!をbitDPで計算量落とす。 (空皿処理で昔より手を抜いている) http://mevius.5ch.net/test/read.cgi/tech/1480579110/305
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
324: 318 [sage] 2017/07/06(木) 01:35:51.32 ID:iCfNzc8Y >>323 3324と3364の解を見ていて気が付いた点があります。 一定以上同じ最小値が繰り返し計算されたかの判定値を20にしていますが、 3324の15や3364の19は20ではなくて13回しか現れず、これが最小値のため 解として表示されています。 これは、3324の15や3364が4桁しかないので、 最小値が20回現れる前に全探査が完了し、その中で見つかった最小値を 解として表示していることによります。 >>318の一定回数繰り返したら収束とみなすという判定方法は、 ニュートン法のような数値計算では有効ですが、 >>296の問題の解の判定方法としては適切とは言えないかもしれませんね…orz http://mevius.5ch.net/test/read.cgi/tech/1480579110/324
361: デフォルトの名無しさん [sage] 2017/07/14(金) 06:57:35.22 ID:PYQ8V1MO >>296 http://ideone.com/VzYVY9 C++。解けた気がする。 状態をメモ化してみた。 何で動いてるのか自分でもよくわからない。 暇だったので解いてみた。 http://mevius.5ch.net/test/read.cgi/tech/1480579110/361
381: デフォルトの名無しさん [sage] 2017/07/17(月) 22:48:25.95 ID:5edeqhg+ >>296 手計算で計算出来るレベルにまで計算量を減らせた もちろん数学的な裏付け付きで ある条件を見たせば一瞬で求まる "123456789123456789" > 98秒 残念ながら、これだけはその条件を満たしてない http://mevius.5ch.net/test/read.cgi/tech/1480579110/381
388: デフォルトの名無しさん [sage] 2017/07/19(水) 18:12:29.37 ID:Np9hKHT2 >>296 >>373 http://ideone.com/B9vl8l C++。結局、i7-6700のmem2G使って7分で解けた。 どうしようもない位遅いな。 でも一応題意には添えたと思う。 もう見たくない・・・。Orz 高速化するにはインラインアセンブリ使うか、スレッド分割できるようなアルゴリズムかんがえるか。 よくわからんけど、数学で頑張ってる人に期待だ。 http://mevius.5ch.net/test/read.cgi/tech/1480579110/388
390: デフォルトの名無しさん [sage] 2017/07/21(金) 15:21:18.13 ID:7e+pM3K/ >>296 http://ideone.com/mXPglY C++。試しに再起化してみたら処理速度倍になった。 自分の環境では3分ちょいで解ける。 相変わらずメモリ馬鹿食いするけど。 もう俺には無理。 俺の中では終了でーす。Orz http://mevius.5ch.net/test/read.cgi/tech/1480579110/390
391: デフォルトの名無しさん [sage] 2017/07/22(土) 08:54:36.28 ID:OQXA8cUK >>388 数学で頑張ってる人だけど、 もうちょっとまって >>296の問題だけなら簡単だけど、 まだ全体を解明できてない というか、忙しくて>>381から進んでない http://mevius.5ch.net/test/read.cgi/tech/1480579110/391
413: デフォルトの名無しさん [sage] 2017/07/24(月) 19:11:05.16 ID:7nQ6Z7f9 >>296 超高速版が出来ました！ http://ideone.com/FrRkof 一皿9秒が上限であれば、計算オーダーはn 関数自体は何秒でも大丈夫です コードだけじゃ意味がわからないでしょうけど、とりあえずコードだけ あまりテストしてないので、バグってたらごめんなさい http://mevius.5ch.net/test/read.cgi/tech/1480579110/413
469: デフォルトの名無しさん [sage] 2017/08/12(土) 19:40:20.63 ID:Bi4KH0eW pile_maxとその位置から下限が得られますが、 >>296 の例では98秒の物以外はすべてその下限になっています 一個その下限になるような例を見つければ答えがわかるのですが、 自力で検索してみればわかると思いますがそのような例はあっさり見つかります 98秒の例は効率良く食べられない場合になります 効率良く食べられる側のなかでも、pileから得られる下限値より大きくなる場合もあります http://mevius.5ch.net/test/read.cgi/tech/1480579110/469
ﾒﾓ帳
(0/65535文字)
上
下
前次
1-
新
書
関
写
板
覧
索
設
栞
歴
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
AAｻﾑﾈｲﾙ
Google検索
Wikipedia
ぬこの手
ぬこTOP
0.041s