simanのブログ

ゆるふわプログラマー。競技プログラミングやってます。Ruby好き

Marathon Match 130 GraphLabeling 戦略

問題

www.topcoder.com

戦略

大まかな戦略としてはラベル付けを行う際の最大値を事前に決定して、ノード全体にラベル付けが成功した場合は最大値を徐々に減らしていくという二分探索風な戦略を取りました。

  • ラベル付けを行う前に与えるラベルの最大値 X を事前に決定する
  • 任意の点からラベル付けを開始し、各ノードへ再帰的に訪問する
  • 各頂点においてラベル付けを行う際に、開始地点からの距離が偶数のノードは 0 からラベル付けが行えるかどうかをチェックする (0, 1, 2 ... X)。距離が奇数のノードは X からラベル付けが行えるかどうかをチェックする (X, X - 1, X - 2, ... 0)。
  • すべてのノードに対してラベル付けが成功した場合は最大値 X の値を更新する(X = X / 2)、失敗した場合は過去のベストの値から少し下げた値を設定する(X = BEST_X * random_value [0.95, 1.0))
  • この手順を制限時間まで繰り返す

ラベルの最大値 X を決定する

ラベル付けを行う際に最大値を決定します。こうすることでラベル付けが完了した際に X スコアが確定したグラフを手に入れることが出来ます。

ラベル付けを行う

任意の点から開始してラベル付けを行います。開始地点から距離が偶数のノードは 0 から割り振り可能なラベルを探索、距離が奇数のノードは X から割り振り可能なラベルの探索を行います。

X = 100 の例

f:id:simanman:20211103120144p:plain:w240

f:id:simanman:20211103120719p:plain:w240

f:id:simanman:20211103120707p:plain:w240

f:id:simanman:20211103120826p:plain:w240

f:id:simanman:20211103120925p:plain:w240

f:id:simanman:20211103121016p:plain:w240

X = 100 ではラベル付けが成功したので、次の試行では X = 50 の値で同じ処理を行います。もし失敗した場合は X = [95, 99] の範囲からランダムに選びます。成功したときは大きく最大値を下げて、失敗した場合は小さく下げていく感じになります。

この処理を制限時間まで繰り返して一番良かったラベル付けを出力します。

まとめ

ゴロム定規を知らなかったので全体的なスコアは低かったのですが疎なグラフでは高いスコアを出せていたので方針をまとめてみました。