RECRUIT 日本橋ハーフマラソン 2021〜増刊号〜 やったこと

コンテストリンク

問題の分析

  • 収穫機の値段は 3 乗オーダーで増えていく。

  • 野菜の値段は指数オーダーで増えていく。

  • 収穫機は連結であれば、連結成分 \times 野菜の値段 のスコアを得ることができる。

やったこと

  • 連結であれば得であるので、連結を保ったまま移動するのが基本的には得であるので、それを維持した。

    • 後述するが連結を保って移動する際、外す点はできるだけ random にしたほうが点数が伸びるぽい。例えば、左上から取っていくみたいにすると、右下に固まってしまうみたいな欠点がある。

  • 収穫期で取るものは野菜の値段が高いもののうち、現在の収穫機にある程度近いものが良い。

この 2 つをやると大体 50 ケース 2 億付近に行きました。 TL が余っているので、ここでビームサーチをしました。

最初はビーム幅を 7 ぐらいにしてやってみる -> 220889373

ここで、サンプルコードの Action が

struct Action
{
    std::vector<int> vs;

private:
    explicit Action(const std::vector<int>& vs_) : vs(vs_) {}

public:
    static Action pass()
    {
        return Action({-1});
    }

    static Action purchase(int r, int c)
    {
        return Action({r, c});
    }

    static Action move(int r1, int c1, int r2, int c2)
    {
        return Action({r1, c1, r2, c2});
    }
};

と std::vector<int> で管理されていたのですが、

struct Action
{
  static int pass()
  {
    return -1;
  }
 
  static int purchase(int r, int c)
  {
    const int N = 16;
    return r * N + c;
  }
 
  static int move(int r1, int c1, int r2, int c2)
  {
    const int N = 16;
    return r1 * N * N * N + c1 * N * N + r2 * N + c2 + N * N;
  }

といったふうに int 型で管理したところ std::vector<int> の生成コストが相当に重かったらしくかなり高速化した。この効果でビーム幅を比較的増やせるようになったので以下の工夫も入れながらビームサーチをした。

ビーム幅を段階的に増やす

一般的なビームサーチは 1 手先の上位 k 個を採用する方法です。

f:id:jupiro:20210912062918p:plain
一般的なビームサーチ

今回は指数関数的に点数が増加してくるので、後半になるにつれて重要度が増していくと考え、ビーム幅を後半増やしました。

f:id:jupiro:20210912135345p:plain
後半につれて、ビーム幅を増やしていく

目的地を決めてまとめて移動する

ビームサーチは基本的に 1 手先を見ますが、優先度付きキューを日付ごとに持ち、取る野菜を決めて、それを収穫し終えてから、その翌日の優先度付きキューにいれることをしました。

多様性？

多様性なのかどうかはわかりませんが、連結成分を保ちながら移動する際に、毎回間接点ではないものを random に列挙すると点がそこそこ伸びました。稼いでるお金は同じだけど、収穫機の位置が違うみたいなことが起こりやすくなるのが原因かなと思っています。

うまくいかなかった工夫

評価関数

ビームサーチの評価関数は結局稼いだ金額そのものでした。他に締め切りとか盤面の状態とか収穫期の形みたいなのを入れたかったのですが、うまくいかず。。。。

擬似的なお金

ビームサーチである以上コピーコストがそこそこ大きいです。そこでコピーコストとかをすごく低くしながら、推定的なお金を計算しようと思ったりしたのですが、なかなかうまくいかず敗北。。。。

高速化

ビーム幅が 10 倍ぐらいになると 257M ぐらいにはなりそうなので、ここも頑張ってみたんですが、これもうまくいかず。。。

システムテスト形式なので、ある程度 TLE にもびびりながら最終的な結果に。(pretest は1774 ms なので、さすがに TLE はしないで欲しい )

リポジトリ

github.com