こんにちは。突然ですが、点つなぎをやったことがありますか?そこで、ちょっとこんなことを考えてみましょう。 -------------------------------------- N個の点があります。点iは座標(Xi, Yi)にあります。 あなたは点を通るルートを選びます。 例えば、N=4なら、 1->3->2->4 1->2->4->3 4->2->3->1 のように通ることができます！ ここで、そのように通ると、合計の移動距離は いくつになりますか? という問題です。 --------------------------- そこで皆さんには、この合計の移動距離の 「最大値」-「最小値」の最大値を求めてほしいです。 具体的には、以下のようにされます。 -------------------------- スタートすると、N個の点の座標を適当に 設定します。i個目の点の座標は(Xi, Yi)です。 次に、スクリプト内にある「前処理」 が実行されます。ここはあなたが設計します。 次に、T回「ルートを求める。」が実行されます。 ここはあなたが設計します。ここでは、 リスト「ルート」に、通る点のルートを設定します。 例えば、1->2->3->4となるときは、リストの中身は 1 2 3 4 としてください。ここで、あなたはなるべく 最適なルートを設定する必要があります！ そうして求められた最長距離-最短距離の最大化を 返します。 -------------------------- 上の操作を、c(N, T)と置きます。 続きはメモとクレジットをご覧ください。
※注意！！※ 使い方を最初に必ず読んで下さい。 サンプルプログラムは、ランダムに点を選んでいます。 制約は以下の通りです。 4≦N≦10000 2≦T≦100 -230≦Xi≦230 -150≦Yi≦100 ちなみに、Nこの点を通る順番は、 N!通りあります。全探索は希望としてはあまりないでしょう。TLEとなります。 まず、効率的なアルゴリズムを思いついたら、 この作品をリミックスし、エントリーフレームに 自分のユーザー名を書いてください。次に、 「前処理」「ルートを求める」の定義に、使い方に 書かれたものに対応するように組みます。 そして、採点プログラムを私が実行して、スコアを コメントします。 スコアは以下の値の合計です。 c(10,100) c(20, 100) c(100, 100) c(1000, 100) c(10, 2) c(10000, 100) ※計算量も考慮しましょう！ これらのケースの実行に2分以上かかった場合は 「TLE」判定となり0点が与えられてしまいます！
