A君とB君が島にいる。A君は島から海岸へ泳ぐと45分,B君は30分かかる。船を使うと15分かかるが,船は1艘しかない。
A君,B君が共により早く海岸へたどり着くにはどうすれば良いか。
良くある,数人が行って帰ってという問題とは違う。最初そういう類の問題かと思った
A君,B君共にコンスタントに泳げ,乗り換え時間は考えないことにする。グラフにすると以下のような感じ。
A君の45分を短縮するのが目標。単純に途中で船を乗り換えることを考えると以下のようなグラフになる(最初はA君が船で移動すると仮定した場合)。
A君の時間を減らすことを考えるが,B君よりも減らしては,B君の方が時間が掛かってしまうので意味がない。
結局A君とB君が同時に海岸に到着すれば良いことになる。
論理的な解法の場合はこれで良いがプログラムするときはより掛かった方の時間を少なくすることを考える。
プログラムは以下のように適当に距離を設定して,色んな距離で時間を計測してみる。
const int DIST = 300; // 島から海岸までの距離(適当な値) const int A = 3, B = 2, C = 1; // 各者の速度比(Cが船),45,30,15でも可。 int a, b; // A,Bが島から海岸までかかる時間 int m = INT_MAX; // A,Bが島から海岸までかかる最悪の時間(これを小さくするのが目標) int pos = INT_MAX; // 乗り換え場所 for( int S=0; S< DIST; S++) { // 乗り換え場所を色々試す a = 0; b = 0; for( int L=0; L< DIST; L++) { // 距離 if( L < S) { // 乗り換え場所が来るまでA君が船を使うと仮定 a += C; // 最初A君が船 b += B; // B君は泳ぎ } else { a += A; // 乗り換え場所が来たらA君が泳ぎ b += C; // B君は船 } } if( a < m && b < m ) { // 今までよりトータル時間が短ければ記録 より時間が掛かっている方を記録にする 乗り換え場所を記録する } } ps( "乗り換え位置:全体の%gの位置\n", (double)pos/DIST); ps( "トータル時間:%g分\n", (double)m*15/DIST/C); // Cが15分でDISTに到着
先にA君が泳ぎでB君が船というパターンもある。その場合乗り換え位置は真ん中から対称になる。何れにしても時間は同じ。
DISTの値を大きくすれば精度は上がるが,単純にループさせているので時間も掛かるようになる。
その場合,乗り換え位置は二分探索法で探すようにするなど工夫が必要。本当はDISTはA,B,Cの最小公倍数の100倍くらいが良いと思う。
高校生の履修単位不足が問題になっているが,私は数年前まで単位不足で大学を卒業できない夢で夜中に飛び起きたことが何回もあった。
最近ようやくそういうことが無くなったが単に記憶が無くなってきただけっていう感じもするのが悲しい。
またまた金魚が危篤状態。今度こそ本当にダメかと思ったが無事復活。
解速度
即