[過去ﾛｸﾞ] プログラミングのお題スレ Part21 (1002ﾚｽ)
上下前次1-新
抽出解除 必死ﾁｪｯｶｰ(本家) (べ) 自ID ﾚｽ栞 あぼーん
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
15(1): デフォルトの名無しさん [sage] 2022/11/15(火) 12:07:08.40 ID:Er9Q2z1T(1/12) AAS
寿司問題はやり方考えたが確認はしてない
再帰的に解けると想定
寿司2個を食べ終わる時間で寿司1個であるかのようにみなす (寿司セット)
たとえば寿司3個の場合なら、最も最短時間の寿司セットを作って寿司2個の場合に帰着させたら解けるはず
最も最短時間の寿司セットというは合ってるか不明だが、そういうやり方で少ない寿司の場合にもっていけるはず
16: デフォルトの名無しさん [sage] 2022/11/15(火) 12:09:32.73 ID:Er9Q2z1T(2/12) AAS
とりあえず寿司3個の場合をランダムか総当りで生成して、2個を連結させる方法が正しいのか確認できそうだがしていない
19(3): デフォルトの名無しさん [sage] 2022/11/15(火) 14:16:46.10 ID:Er9Q2z1T(3/12) AAS
>>15はべつの言い方でいうと与えられたレーンで食べる順を確定させられるペアを見つけるってことだが
総時間が短いものか、空き時間が短いものか、空き時間が短いうちで最も最長のものか、そういういった組み合わせが考えられるが
正解があるかは不明
20: 19 [sage] 2022/11/15(火) 16:22:52.97 ID:Er9Q2z1T(4/12) AAS
単に空の時間が少ないようにペアをあわせていけば解ける気がしてきた
空は0として "313__"の場合はこうなって解ける
2行目への変化だと1秒と3秒の寿司を食べるとして4秒の寿司へ変わる
次は4秒寿司と3秒寿司が続けて食べられて7秒寿司へ
最後は一秒まって7秒寿司をたべて8秒で終わる
31300
34000
07000
21: 19 [sage] 2022/11/15(火) 16:42:03.18 ID:Er9Q2z1T(5/12) AAS
これもやってみたら手動で正解できた "123456789123456789" > 98秒
123456789123456789
303456789303456789
703056789703056789
709050789709050789
0090C07890090C0789
009000J89009000J89
0090000X90090000X9
00I0000XI0000000X0
00I0000YI000000000
00I0000Z0000000000
00W000000000000000
10以上の数値は英字で置き換えた
C 12
J 19
X 27
Y 54
Z 73
W 96
24: 19 [sage] 2022/11/15(火) 19:36:17.27 ID:Er9Q2z1T(6/12) AAS
上でいってるやつをコードにした
一個結果がちがってるが よく検討していない
Python
外部ﾘﾝｸ:ideone.com
25(1): デフォルトの名無しさん [sage] 2022/11/15(火) 19:43:49.49 ID:Er9Q2z1T(7/12) AAS
可能性としては、このアルゴリズム自体が最小値を出す可能性があるだけでかならずしも最小値ではないだとおもう
29(1): デフォルトの名無しさん [sage] 2022/11/15(火) 21:35:09.43 ID:Er9Q2z1T(8/12) AAS
>>26修正しておなじやつ全部解けたけど、最小値を出す保証はないとおもう
外部ﾘﾝｸ:ideone.com
30: デフォルトの名無しさん [sage] 2022/11/15(火) 21:45:59.70 ID:Er9Q2z1T(9/12) AAS
大局的なこと、試行錯誤はやらずに空レーンでの待ちが少なくなるように2個セットをつくり続けて寿司個数が少ない場合に帰着させるだけ
これで正解が出させるほうが不思議
32(1): デフォルトの名無しさん [sage] 2022/11/15(火) 22:11:55.75 ID:Er9Q2z1T(10/12) AAS
>>31それ自分だと9秒になるが、>>26だと8秒になるな
しかし、どうやっても8秒だと無理とおもうが
人間の試行錯誤で
34: デフォルトの名無しさん [sage] 2022/11/15(火) 23:06:20.13 ID:Er9Q2z1T(11/12) AAS
>>3333(1): デフォルトの名無しさん [sage] 2022/11/15(火) 22:47:43.33 ID:Ohwd0nE1(1) AAS
>>32
これじゃダメ？
1: *_22（取る）
2: _*22（食べる）
3: __22（休み）
4: __2*（取る）
5: *_2_（食べる）
6: _*2_（休み）
7: __*_（取る）
8: ___*（食べる）
8を確認できたよ
36: デフォルトの名無しさん [sage] 2022/11/15(火) 23:14:58.48 ID:Er9Q2z1T(12/12) AAS
空なしで連続して食べれるなら食べてしまうやり方で失敗する例が2_22か
これがあるならば待ちで0か1で食べれるのに2以上待たないと駄目な例もありそうだ
ややこしい
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.053s