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