パーソナルブログメモリ

a = [1, 1]
for _ in "*" * 999: a += [sum(a[-2:])]
print(a)

バスの運行ルートを見つけるような問題で真ん中ぐらいの成績の解法

2024-10-12 | CodinGame

乗り物には人数の上限があって各点に決まった人数が乗ってくる

バスは駅から指定した点を通って帰ってくる

すべての人をなるべく少ない総距離で駅まで届ける方法を探す

 

こちらは2号

まず駅(中央)から一番遠い点を探し、そこから近い点を乗れるだけ選択してルートとして括る

次にその一番遠い点から、一番遠い点を探し、そこから近い点を乗れるだけ選択してルートとして括る(なくなるまで繰り返す)

最後にその括った点をランダムに2点ずつ入れ替えて総距離が減ったら入れ替えるを繰り返す

 

 

こちらは3号

1)駅と一番遠い点、2点からの距離の和が少ないものから満員前まで括っていく

2)次にその一番遠い点から、一番遠い点を探し、1)と同じことをする

3)客がいなくなるまで2)を繰り返す

4)最後にその括った点をランダムに2点ずつ入れ替えて総距離が減ったら入れ替えるを繰り返す

2号の方が120%ぐらい短い


最新の画像もっと見る

コメントを投稿

ブログ作成者から承認されるまでコメントは反映されません。