【AtCoder】Introduction to Heuristics Contest A - AtCoder Contest Scheduling

問題

解法

• 公式解説の内容を（巨大近傍法を除き）実装（124895469点）

• に変更（コンテスト1位の shindannin さんのパラメータを採用）

• を線形に減少するように変更（ から に）

• 差分計算における prev, next の求め方を std::set を使わずに線形探索に変更（オーダーは悪化しているが、定数倍の差で10倍近く高速化できる）

• の更新を 10000 回に 1 回行う（現在時刻の取得回数を減らして高速化）

• 戻す操作を update_point, update_swap を使わずに行う（関数の呼び出し回数を減らして高速化）

以上の改善を行った結果、126193376点になった。

// 初期解: ランダム
// 更新: 1点変更 + 2点スワップ (差分計算によってスコア計算を高速化)
// 差分計算における prev, next の求め方を std::set を使わずに線形探索に変更
// T の更新を 10000 回に 1 回行う
// 戻す操作を update_point, update_swap を使わずに行う
// 焼きなまし
// T0 = 1500, T1 = 100 (shindanninさんのパラメータ)
// TL = 1950 [ms]
// t = elapsed() / TL
// T = T0 ^ (1 - t) * T1 ^ t -> T = T0 * (1 - t) + T1 * t
// d = new_score - old_score
// d < 0 (score が減少する場合) でも確率 exp(d / T) で遷移
#include "my_template.hpp"
#include "misc/xor_shift.hpp"
#include "misc/timer.hpp"

using namespace std;

constexpr f64 TL = 1950;
constexpr f64 T0 = 1500;
constexpr f64 T1 = 100;

struct State {
    i64 score;
    vector<int> t;
};

struct Solver {
    int D;
    vector<i64> c;
    vector<vector<i64>> s;
    State st;
    Solver() {
        INT(Dtmp);
        D = Dtmp;
        VEC(i64, ctmp, 26);
        c = ctmp;
        VV(i64, stmp, D, 26);
        s = stmp;
    }
    i64 calc_score(vector<int>& t) {
        vector<int> last(26, -1);
        i64 res = 0;
        REP(i, D) {
            res += s[i][t[i]];
            last[t[i]] = i;
            REP(j, 26) res -= c[j] * (i - last[j]);
        }
        return res;
    }
    void init() {
        st.t.resize(D);
        REP(i, D) st.t[i] = rnd.rand_int(26);
        st.score = calc_score(st.t);
    }
    // 1点変更
    void update_point(int d, int q) {
        // t[d] <- q としたときの score を差分計算
        int old_q = st.t[d];
        st.score -= s[d][old_q];
        {
            int prev = d - 1, next = d + 1;
            while (prev >= 0 and st.t[prev] != st.t[d]) prev--;
            while (next < D and st.t[next] != st.t[d]) next++;

            int d1 = (d - prev), d2 = (next - d);
            st.score += c[old_q] * (d1 * (d1 - 1) / 2 + d2 * (d2 - 1) / 2);
            int d3 = (next - prev);
            st.score -= c[old_q] * (d3 * (d3 - 1) / 2);
        }
        st.t[d] = q;
        {
            int prev = d - 1, next = d + 1;
            while (prev >= 0 and st.t[prev] != st.t[d]) prev--;
            while (next < D and st.t[next] != st.t[d]) next++;

            int d1 = (d - prev), d2 = (next - d);
            st.score -= c[q] * (d1 * (d1 - 1) / 2 + d2 * (d2 - 1) / 2);
            int d3 = (next - prev);
            st.score += c[q] * (d3 * (d3 - 1) / 2);
        }
        st.score += s[d][q];
    }
    // 2点スワップ
    void update_swap(int d1, int d2) {
        int q1 = st.t[d1], q2 = st.t[d2];
        update_point(d1, q2);
        update_point(d2, q1);
    }
    void solve() {
        init();
        int count = 0;
        f64 t, T;
        while (true) {
            if (count % 10000 == 0) {
                t = timer.elapsed() / TL;
                if (t >= 1.0) break;
                T = T0 * (1.0 - t) + T1 * t;
            }
            count++;
            if (rnd.rand_int(2)) {
                // 1点変更
                int d = rnd.rand_int(D);
                int old_q = st.t[d];
                int new_q = rnd.rand_int(26);
                if (old_q == new_q) continue;

                i64 old_score = st.score;
                update_point(d, new_q);
                i64 new_score = st.score;
                if (old_score > new_score and rnd.rand_double() > exp((new_score - old_score) / T)) {
                    // もどす
                    st.t[d] = old_q;
                    st.score = old_score;
                }
            } else {
                // 2点スワップ
                int d1 = rnd.rand_int(D - 1);
                int d2 = rnd.rand_int(d1 + 1, min(D - 1, d1 + 15));
                if (st.t[d1] == st.t[d2]) continue;

                i64 old_score = st.score;
                update_swap(d1, d2);
                i64 new_score = st.score;
                if (old_score > new_score and rnd.rand_double() > exp((new_score - old_score) / T)) {
                    // もどす
                    swap(st.t[d1], st.t[d2]);
                    st.score = old_score;
                }
            }
        }
        show(count);
        show(st.score);
        REP(i, D) print(st.t[i] + 1);
    }
};

int main() {
    timer.reset();
    Solver solver;
    solver.solve();
    return 0;
}