提出 #14821684

---

ソースコード 拡げる

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

mt19937 rnd;
uniform_real_distribution<> dist01(0.0, 1.0);
double rnd01(){ return dist01(rnd);}

const double TIME_LIMIT = 1950;
double elapsed;
chrono::system_clock::time_point t_start;
void update_time(){
    auto t_now = chrono::system_clock::now();
    elapsed = chrono::duration_cast<chrono::milliseconds>(t_now - t_start).count();
}
bool timeover(){ return (elapsed > TIME_LIMIT);}

const int D = 365, T = 26;
int C[T], S[D][T];
int CS[D+2][T];

vector<int> st[T];

int ans[D];
int opt = -1e9;

int calc_score(){
    int last[T];
    for(int i=0; i<T; i++) last[i] = -1;
    int res = 0;
    for(int i=0; i<D; i++){
        res += S[i][ans[i]];
        last[ans[i]] = i;
        for(int j=0; j<T; j++) res -= C[j] * (i-last[j]);
    }
    return res;
}

int calc_diff(int t, int bef, int aft){
    int res = opt + S[t][aft] - S[t][bef];
    {
        auto it = lower_bound(st[bef].begin(), st[bef].end(), t);
        int d1 = *next(it) - t, d2 = t - *prev(it);
        res -= CS[d1+d2][bef] - CS[d1][bef] - CS[d2][bef];
    }
    {
        auto it = lower_bound(st[aft].begin(), st[aft].end(), t);
        int d1 = *it - t, d2 = t - *prev(it);
        res += CS[d1+d2][aft] - CS[d1][aft] - CS[d2][aft];
    }
    return res;
}

int calc_swap(int t, int bef, int aft){
    int res = opt + S[t][aft] - S[t][bef] - S[t+1][aft] + S[t+1][bef];
    {
        auto it = lower_bound(st[bef].begin(), st[bef].end(), t);
        int d1 = *next(it) - t, d2 = t - *prev(it);
        res -= CS[d1-1][bef] + CS[d2+1][bef] - CS[d1][bef] - CS[d2][bef];
    }
    {
        auto it = lower_bound(st[aft].begin(), st[aft].end(), t+1);
        int d1 = *next(it) - t, d2 = t - *prev(it);
        res += CS[d1-1][aft] + CS[d2+1][aft] - CS[d1][aft] - CS[d2][aft];
    }
    return res;
}

int update_cnt = 0;

void try_update(){
    // pick random & update
    int t = rnd() % D;
    int bef = ans[t], aft = rnd() % T;
    if(bef == aft) return;

    // calculate
    int score = calc_diff(t, bef, aft);
    const int T = 4000;
    double temp = T * (1 - elapsed/TIME_LIMIT);
    double prob = exp((score - opt) / temp);
    if(rnd01() < prob){
        opt = score;
        ans[t] = aft;
        st[aft].insert(lower_bound(st[aft].begin(), st[aft].end(), t), t);
        st[bef].erase(lower_bound(st[bef].begin(), st[bef].end(), t));
        update_cnt++;
    }else{
        // rollback
    }
}

void try_swap(){
    // pick random & update
    int t = rnd() % (D-1);
    int bef = ans[t], aft = ans[t+1];
    if(bef == aft) return;

    // calculate
    int score = calc_swap(t, bef, aft);
    const int Temp = 4000;
    double temp = Temp * (1 - elapsed/TIME_LIMIT);
    double prob = exp((score - opt) / temp);
    if(rnd01() < prob){
        opt = score;
        swap(ans[t], ans[t+1]);
        (*lower_bound(st[aft].begin(), st[aft].end(), t))--;
        (*lower_bound(st[bef].begin(), st[bef].end(), t))++;
        update_cnt++;
    }else{
        // rollback
    }
}

int main(){
    t_start = chrono::system_clock::now();
    // get input & initialize
    int _; cin >> _;
    for(int j=0; j<T; j++) cin >> C[j];
    for(int i=0; i<D; i++) for(int j=0; j<T; j++) cin >> S[i][j];
    for(int i=0; i<=D+1; i++) for(int j=0; j<T; j++) CS[i][j] = i*(i-1)/2*C[j];

    for(int i=0; i<D; i++) for(int j=0; j<T; j++) if(S[i][ans[i]] < S[i][j]) ans[i] = j;
    opt = calc_score();
    cerr << "before score: " << opt << endl;

    for(int j=0; j<T; j++) st[j].push_back(-1);
    for(int i=0; i<D; i++) st[ans[i]].push_back(i);
    for(int j=0; j<T; j++) st[j].push_back(D);

    // iterate
    int iter = 0;
    while(!timeover()){
        iter++;
        try_update();
        if(iter%10 == 0) try_swap();
        if(iter % 100000 == 0) update_time();
    }

    // output result
    for(int i=0; i<D; i++) cout << ans[i]+1 << endl;


    // output debug
    cerr << "score: " << opt << endl;
    cerr << "iter: " << iter << endl;
    update_time();
    cerr << "elapsed: " << elapsed << endl;
    cerr << "update count: " << update_cnt << endl;
    return 0;
}

提出情報

ジャッジ結果