2017 TCO Marathon Round 1 が始まります - アルゴリズム忘備録

競技プログラミングには短時間で100％正解を求めるアルゴリズムマッチ(正式名称しらない)と、長時間でなるべく高い得点を稼ぐマラソンという分野があります。マラソンは大抵最適解が求まるような問題ではなく、ある程度のヒューリスティックなアルゴリズムを組んでギリギリまで高い解を狙う、と言った感じです。

そのマラソンにおける権威のあるイベントがTopCoder Open Marathon Matchと言われるものであり、上の問題はその2017年度版Round 1になります。

今回の問題は意訳すると以下のような感じです。

ノードの数及び、エッジ(接続元、先)及びそのエッジの長さといったグラフの構造が与えられる。このグラフのノードをを700x700の平面の格子座標上の任意の場所に配置する。ただし点の重複は認められない。このとき、元のエッジの長さと平面においた時のエッジの長さがなるべく変わらないような配置を求めよ。

スコアの計算式は Min(平面上での長さ / 元の長さ) / Max(平面上での長さ / もとの長さ) * 100万という式で与えられます。

開催中なので個別の問題に対する方針等の説明は書けないのですが、マラソンは一般的に競技プログラミングに慣れていなくても長時間開催されるので結構とっつきやすい印象があります。なので、ぜひ参加してみましょう。