[過去ﾛｸﾞ]
プログラミングのお題スレ Part9 [無断転載禁止]©2ch.net (1002ﾚｽ)
プログラミングのお題スレ Part9 [無断転載禁止]©2ch.net http://mevius.5ch.net/test/read.cgi/tech/1480579110/
上
下
前次
1-
新
通常表示
512ﾊﾞｲﾄ分割
ﾚｽ栞
抽出解除
必死ﾁｪｯｶｰ(本家)
(べ)
自ID
ﾚｽ栞
あぼーん
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索
歴削→次ｽﾚ
栞削→次ｽﾚ
過去ﾛｸﾞﾒﾆｭｰ
454: デフォルトの名無しさん [sage] 2017/08/12(土) 19:04:22.18 ID:Bi4KH0eW >>413です もちろん合っているつもりのコードです 作者が言っても何の説得力もありませんが http://mevius.5ch.net/test/read.cgi/tech/1480579110/454
456: デフォルトの名無しさん [sage] 2017/08/12(土) 19:10:18.10 ID:Bi4KH0eW それぞれの寿司を食べている期間をレーン上の線分で表します この線の重なり具合をpileで表しました 効率良く食べられた場合はレーンがpile_max周するまでの間に食べきることが出来ます 170行目の判定がそれで、trueの場合は効率良く食べられない場合です http://mevius.5ch.net/test/read.cgi/tech/1480579110/456
460: デフォルトの名無しさん [sage] 2017/08/12(土) 19:19:17.76 ID:Bi4KH0eW 効率良く食べられない方が簡単なのでその場合から お寿司を以下のグループに分けます ---- 各グループのお寿司は、レーンの特定の位置から食べ始めた場合、pile[グループ]周以内で食べ終わることが出来る このとき、pile_max = Σ pile[グループ] となる --- このようなグループの分け方の最小の物が存在します http://mevius.5ch.net/test/read.cgi/tech/1480579110/460
461: デフォルトの名無しさん [sage] 2017/08/12(土) 19:22:56.16 ID:Bi4KH0eW 同じグループのお寿司は連続して食べます 開始時と、各グループのお寿司を食べ終わった後、最初に来るお寿司から食べはじめ、pile[グループ]以内で食べられる食べ方でそのグループを食べ終える ということを繰り返せば最小の時間で食べ終えることが出来ます http://mevius.5ch.net/test/read.cgi/tech/1480579110/461
462: デフォルトの名無しさん [sage] 2017/08/12(土) 19:26:29.79 ID:Bi4KH0eW グループ分けした時に1個のグループになった場合は、 効率良く食べられることになります つまり、pile_max周以下で食べ終えることが出来ます この時は、コード上にあるダミーのお寿司を追加してから最小時間を求め、ダミーのお寿司を食べてる時間を引けば求められます http://mevius.5ch.net/test/read.cgi/tech/1480579110/462
464: デフォルトの名無しさん [sage] 2017/08/12(土) 19:30:27.01 ID:Bi4KH0eW グループの分け方は少し難しいです レーンの各整数位置に対して、 お寿司の線の両端にあたる点同士 線の重なりがpile_max未満である区間の点(両端を含む) を同じグループの点とし、 これらを続けることで最小のグループ分けが出来ます 線の両端の点のグループが、そのお寿司のグループになります http://mevius.5ch.net/test/read.cgi/tech/1480579110/464
465: デフォルトの名無しさん [sage] 2017/08/12(土) 19:31:42.19 ID:Bi4KH0eW それぞれ、証明は出来ているつもりです http://mevius.5ch.net/test/read.cgi/tech/1480579110/465
466: デフォルトの名無しさん [sage] 2017/08/12(土) 19:32:49.51 ID:Bi4KH0eW もちろん、一般の巡回問題はこの方法では無理です http://mevius.5ch.net/test/read.cgi/tech/1480579110/466
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
470: デフォルトの名無しさん [sage] 2017/08/12(土) 19:43:06.99 ID:Bi4KH0eW いずれの場合も、PCを使わなくても手計算で十分可能です http://mevius.5ch.net/test/read.cgi/tech/1480579110/470
ﾒﾓ帳
(0/65535文字)
上
下
前次
1-
新
書
関
写
板
覧
索
設
栞
歴
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
AAｻﾑﾈｲﾙ
Google検索
Wikipedia
ぬこの手
ぬこTOP
0.048s