 pc ( No.5 ) |
- 日時： 2011/11/04 15:12
- 名前： 宇奈月
- それでは、正解を発表します。
ｍ２とｎ2の部分はどの経路を選んでも合計は同じになります。
ｍｎの和が最大になる経路を探せばよいです。
m番島からn番島への運賃がmnであるとき、運賃合計を最大にする周遊経路を探してみましょう。
運賃最大の経路において、a番島からb番島への移動とc番島からd番島への移動があるとします。
(a,b,c,dはすべて異なるものとします)
・・・ab・・・cd・・・(経路1)
この経路のb番島からc番島への経路を逆にした次のような経路を考えます
・・・ac・・・bd・・・(経路2)
経路1のbからcまでの運賃と経路2のcからbまでの運賃は等しくなります。
よって、経路1の運賃-経路2の運賃=ab+cd-ac-bd=(a-d)(b-c)
経路1の運賃が最大なので、(a-d)(b-c)≧0です。
a,b,c,dはすべて異なりますので、(a-d)(b-c)＞0です。
a＞dであればb＞c、a＜dであればb＜cです。
運賃最大経路が、s1,s2,s3,・・・,s12,s1となっているとします。
s1=1の場合を調べます。
s1,s2,s3,s4に注目すると、s1=1＜s4ですので、s2＜s3でなくてはいけません。
s1,s2,s4,s5に注目すると、s2＜s4がいえます。
同様にして、s2＜s3,s4,s5,s6,s7,s8,s9,s10,s11
よって、s2は2または3です。
s10,s11,s12,s1に注目すると、s12＜s11です。
s2の場合と同様にして、s12＜s11,s10,s9,s8,s7,s6,s5,s4,s3となり、s12は2か3です。
(s2,s12)=(2,3),(3,2)となります。
向きが異なるだけですので(s2,s12)=(2,3)としておきます。
s1を除けばs2が最小なので先ほどと同様にして、s3＜s4,s5,s6,s7,s8,s9,s10,s11
すると、s3=4と確定します。
s11＜s10,s9,s8,s7,s6,s5,s4よりs11=5
以下同様にs4=6,s10=7,s5=8,s9=9,s6=10,s8=11,s7=12と決まります。
従って運賃を最大にする周遊経路は、1,2,4,6,8,10,12,11,9,7,5,3とその逆順の経路となります。
これはこの問題の運賃を最小にする周遊経路でもあります。
この中で運賃最小の移動は2番島から1番島への移動です。
従って求める経路は2,1,3,5,7,9,11,12,10,8,6,4,2と移動する経路です。
|
|
FAQ
RSS