Marathon Match 130 でやったこと

コンテストリンク

OEIS にかけるということが本質なんてことがマラソンであるなんて思いもしなかった

結果

provisional : 27 位 56.19053

やったこと

基本的には Greedy + 山登り

  • 解がある程度小さい時は、次数が大きい頂点から採用できる値で一番小さいものを貪欲に選んでいく

  • 解がある程度大きい時は、ノードに入れる値を小さい方から見ていき、採用できる値を採用していく

ちょっとした工夫として、bitset を用いた枝刈りをした。具体的には、ある値 x があるノード n とのノード間でダメであった時、bitset に n を格納することで、 n を辺に持つようなノードには x が挿入できないとした。

大反省

実は完全グラフには Golomb ruler というものがあり、これを埋め込むかどうかがこのマラソンの一番の本質であった。

n が小さいケースで OEIS をかけるなんてのは、アルゴだったらまずやってそうなことだが、マラソンだから全く思いつかなかった。

その他 MM 特有の得た知見

  • provisional で -1 のケースが存在した時、 AHC と異なり全体が 0 点になるのではなく、そのケースのみが 0 点になる。

  • exection-xxx.log は自分の submit による他人の score の変化値が乗っている。

  • 今回からコンパイラが C++17 になっている (うれしい！)

便利すぎ！！