RECRUIT 日本橋ハーフマラソン 2021 A問題 解説

Seed=0 の出力 (turn=850)

Recruit 日本橋ハーフマラソン 2021 A問題 の解説です。

A問題について、コンテスト中は311,660点で17位、コンテスト後は346,841点で1位相当のスコアを出しました。ここではコンテスト後の解法を紹介します。

問題概要

長さ の配列 が与えられます。

とします。

を自由に選んで を

のように更新する処理を最大 回まで行えます。

の値をできるだけ小さくしてください。

方針

最初の 回で をできるだけ小さくし、最後の 回で全ての要素が小さくなるように調整しました。

優先度付きキューを用いた、ある種の貪欲法で処理しました。

なお、この解法は下記の解説動画を参考にしています。 www.youtube.com

端に寄せる

この問題のポイントは 付近の小さい値と 付近の大きい値をたくさん生成することです。小さい値だけでなく、大きい値も作ることで、微調整がききやすくなり、スコアが大幅に改善します。

具体的には、優先度付きキューを2つ用意し、片方には 未満の値を入れ、もう片方には 以上の値を入れます。前者からは最大値 と2番目に大きい値 、後者からは最小値 と2番目に小さい値 を取り出します。

のときは を行い、

のときは を行います。

と だけの比較ではダメなのか

結論から言うと、単純に と を比較するよりも、次の値まで考慮したほうがスコアが少し高くなります。

例えば、 の場合に行われる最初の2回の処理を考えてみます。

と を比較した場合、

の2つの処理が行われます。2個目の処理の効率が悪いことがわかります。

一方で と まで考慮して比較した場合、

の2つの処理が行われます。この場合は2個目の処理も効率がよいです。

一例の、しかも一部分だけで良し悪しを判断するのは危険ですが、実験してみた結果、2番目まで考慮したほうがスコアが上がりました。

終盤の調整

付近の値は必ず 付近になるように、 付近の値もできるだけ小さくなるようにします。

先ほどと同様の優先度付きキューを使用します。

のときは を行い、

のときは を行います。

処理の回数を 回に抑えるために、必要に応じて後者の処理をスキップする必要があります。

提出コード

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
//using namespace atcoder;

struct Solver {
    int n;
    int m;
    int k;
    vector<int> a;
    priority_queue<pair<int,int>> small;
    priority_queue<pair<int,int>> big;
    vector<int> p;
    vector<int> q;
    double score = 0;

    void input() {
        cin >> n >> m >> k;
        a = vector<int>(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
    }

    void magic(int pi, int qi) {
        assert(0 <= pi < n && 0 <= qi < n);
        p.push_back(pi);
        q.push_back(qi);
        a[pi] += a[qi];
        a[pi] %= k;
    }

    void heap_push(int i) {
        if (a[i] < k / 2) {
            small.push(make_pair(a[i], i));
        } else {
            big.push(make_pair(-a[i], i));
        }
    }

    void init() {
        for (int i = 0; i < n; i++) {
            heap_push(i);
        }
    }

    void solve() {
        pair<int,int> sp = small.top();
        small.pop();
        pair<int,int> bp = big.top();
        big.pop();
        for (int i = 0; i < m-n; i++) {
            int pi, qi;
            if (sp.first + small.top().first <= 2*k + bp.first + big.top().first) {
                pi = bp.second;
                qi = sp.second;
                bp = big.top();
                big.pop();
            } else {
                pi = sp.second;
                qi = bp.second;
                sp = small.top();
                small.pop();
            }
            magic(pi, qi);
            heap_push(pi);
        }
        small.push(sp);
        big.push(bp);

        int tmp = small.top().second;
        small.pop();
        while (!big.empty()) {
            int pi, qi;
            if (small.empty() || small.top().first < k + big.top().first) {
                pi = big.top().second;
                qi = tmp;
                big.pop();
            } else if (big.size() < m - p.size()) {
                pi = tmp;
                qi = big.top().second;
                tmp = small.top().second;
                small.pop();
            } else {
                tmp = small.top().second;
                small.pop();
                continue;
            }
            magic(pi, qi);
            heap_push(pi);
        }
    }

    void print() {
        for (int i = 0; i < n; i++) {
            score += log2(k) - log2(a[i]+1);
        }
        //cout << "Score: " << ceil(score) << endl;

        for (int i = 0; i < p.size(); i++) {
            cout << p[i] << ' ' << q[i] << endl;
        }
    }
};

int main() {
    Solver solver;
    solver.input();
    solver.init();
    solver.solve();
    solver.print();
}

更なる高みへ

上記の提出コードの実行時間は10ms以下です。実行時間制限が2000msであることを踏まえると、似たような計算を何度も行えることがわかります。よって、山登り法や焼きなまし法と組み合わせることでスコアを改善できる可能性が高いです。解説動画のように、ノイズを焼きなますなどの方法で350,000点以上を目指せると思います。（個人的には貪欲法だけで高得点を出せたことに満足しているので、これ以上の改善は行いません。）

最後に

非自明な戦略を元に、貪欲法だけで高スコアが出る問題でした。発想力や考察力が問われたと思います。

最後まで読んでいただき、ありがとうございました。