|
doba |
|
一応、なぜ#30425が800リットルで最も遠くまで行く方法だと言えそうかを説明しておきます。最も遠くまで行く方法を考えるので、ここでは終点のB町の存在は忘れます。
まず、「1000kmより先に進むには、ガソリンも運ばないとならないが、ガソリンはトラックのタンクでしか運べないので、中継地点を設けてそこまで何往復かすることによりタンクでガソリンを運ぶ」という基本方針は問題ないと思います。ただし、中継地点は１ステップ毎に必ず起点終点の２箇所だけなのか、ガソリンを置いてある場所が３箇所以上同時に存在するような状況を作った方が効率がいいということがあるのか（たとえば、A町から順にX,Y,Zという地点があって、A→Y→A→Y→A→X→A→X→A→X→Z→X→Z→Y→Zのような動きをして、AとXとYないしXとYとZに同時にガソリンが存在する状況を作る、とか）については、別途検討する必要があると思いますが、ここではとりあえず１区間ずつ完結させる方法で考えます。 以下、１つの輸送手段を特定する際には、各中継地点でのガソリン量と、中継地点間でガソリンを何回に分けて運ぶかのみによって表すことにします。それだと途中でガソリンを捨てる場合が表現できませんが、最も遠くまで行く方法を考える上では途中でガソリンを捨てることを考える必要はありません。（なぜなら、ある中継地点でガソリンを捨てる代わりに、その直前の区間の距離を長くした方が距離を稼げるからです。） カッコ内をガソリンを運ぶ回数とすると、例えば、次のような輸送手段を考えることができます。 800(8)650(8)500(5)230(3)80(1)0 ここで、800(8)650という区間は、始点のガソリン量が800リットル、終点のガソリン量が650リットルとなるようにガソリンを８回に分けて運ぶ（実際の走行は７往復半）ということを意味します。 ある区間をa(n)bとすると、 全ての区間が800≧a＞b≧0とa≦100nを満たしていればそのような輸送手段は実現可能であり、 その区間の長さをxとすると、区間内のトラックの走行距離は(2n-1)xで、 その間に減ったガソリンがa-bなので、 x＝10(a-b)/(2n-1) となります。 前の例の各区間長は、 10×(800-650)／15＝100km 10×(650-500)／15＝100km 10×(500-230)／9＝300km 10×(230-80)／5＝300km 10×(80-0)／1＝800km となり、到達距離は1600kmです。 各区間の始点と終点のガソリン量を決めると、当然輸送回数nが少ない方がxは大きくなる、すなわち、到達距離を稼げます。 また、輸送回数が同じである区間が連続する場合、その２つの区間をまとめても到達距離は変わりません。 例えば、前の例で、800(8)650(8)500という２つの連続した区間を800(8)500という１つの区間にまとめても、この範囲の合計区間長は200kmで変わりません。 逆に、ある区間を、輸送回数の同じ複数の区間に分割しても、全体の距離は変わりません。 例えば、500(5)230という区間を、500(5)400(5)300(5)230という３つの区間に分割しても、この範囲の合計区間長は300kmで変わりません。 以上を踏まえ、任意の輸送手段から出発して、なるべく到達距離を増やすように輸送手段を変形していくことを考えます。 まず、全ての区間を、ガソリン量が100の倍数になるところで分割します。ここでは、全体の距離は変わりません。 例えば、前の例だと、次のようになります。 800(8)700(8)650(8)600(8)500(5)400(5)300(5)230(3)200(3)100(3)80(1)0 次に、各区間において、可能な限り（つまり、a≦100nの範囲で）輸送回数を減らします。ここでの変更は、必ず全体の距離を増やす方向に働きます。 前の例は次のようになります。 800(8)700(7)650(7)600(6)500(5)400(4)300(3)230(3)200(2)100(1)80(1)0 最後に、輸送回数が同じ区間をまとめます。ここでは、全体の距離は変わりません。 この結果、どんな輸送手段から出発しても、（全体の距離を減らさずに）次の形に変形されます。 800(8)700(7)600(6)500(5)400(4)300(3)200(2)100(1)0 すなわち、この輸送手段が、到達距離最大となります。 ガソリン消費量最小の方は、往復回数の少ない区間をなるべく増やせばいいので、 終点からさかのぼって考えると ？(8)700(7)600(6)500(5)400(4)300(3)200(2)100(1)0 という形で総距離が2000kmになるように？を決めればよいことは直感的にわかると思います。 |
|
8月1日（水） 15:37:40
30432 |