Submission #15981814


Source Code Expand

Copy
#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>
#include <cassert>
#include <climits>
#include <cmath>

using namespace std;
using namespace chrono;

// 0以上UINT_MAX(0xffffffff)以下の整数をとる乱数 xorshift https://ja.wikipedia.org/wiki/Xorshift
static uint32_t randXor()
{
    static uint32_t x = 123456789;
    static uint32_t y = 362436069;
    static uint32_t z = 521288629;
    static uint32_t w = 88675123;
    uint32_t t;

    t = x ^ (x << 11);
    x = y; y = z; z = w;
    return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}

// 0以上1未満の小数をとる乱数
static double rand01()
{
    return (randXor() + 0.5) * (1.0 / UINT_MAX);
}

const static int NUM_TYPES = 26; // コンテストの種類数

// 全体のスコア(今回の問題のスコア)
static int getFullScore(const int D, const vector <int>& C, const vector <int>& T, const vector<vector<int>>& S)
{
    int score = 0;

    vector <int> last(NUM_TYPES, 0);

    for (int d = 0; d < D; d++)
    {
        const int j = T[d];
        last[j] = d + 1;
        for (int t = 0; t < NUM_TYPES; t++)
        {
            score -= (d + 1 - last[t]) * C[t];
        }
        score += S[d][j];
    }

    return score;
}

// d日目のコンテストT[d]を開いたときのスコア増分
static int getContestScore(const int d, const int D, const vector <int>& C, const vector <int>& T, const vector<vector<int>>& S)
{
    const int t = T[d];
    int score = S[d][t];

    int prev = d - 1;   // d日目以前に開かれる同じコンテストの日
    while (prev >= 0 && T[prev] != t)
    {
        prev--;
    }

    int next = d + 1;   // d日目以降に開かれる同じコンテストの日
    while (next < D && T[next] != t)
    {
        next++;
    }

    // sum(x) = x*(x+1)/2 つまり1,2...,xまでの等差数列の和とすると
    //	score -= sum(next - prev -1) * (-C[t]);                       // ... (1)
    //	score += sum(day  - prev -1) + sum(next - day  -1) * (-C[t]); // ... (2)

    // p---------n コンテストをおく前
    //  123456789 // ... (1)

    // p---d-----n コンテストをおいた後
    //  123 12345 // ... (2) 

    score += (next - d) * (d - prev) * C[t];    // (1)と(2)を計算すると、簡単になる。

    return score;
}

int main()
{
    auto startClock = system_clock::now();

    //  入力
    int D;
    cin >> D;
    vector<int> C(NUM_TYPES);
    for (int &c : C)
    {
        cin >> c;
    }

    vector<vector<int>> S(D, vector<int>(NUM_TYPES));
    for (auto &s : S)
        for (auto &x : s)
        {
            cin >> x;
        }

    vector<int> T(D);   // T[d] d日目に開くコンテスト
    for (int d = 0; d < D; d++)
    {
        T[d] = d % NUM_TYPES;
    }

    int score = getFullScore(D, C, T, S);   // 現在のスコア
    int bestScore = INT_MIN;                // 最高スコア
    vector <int> bestT;                     // 最高スコアを出したときのT

    const static double START_TEMP = 1500; // 開始時の温度
    const static double END_TEMP   =  100; // 終了時の温度
    const static double END_TIME   =  1.8; // 終了時間(秒)

    double temp = START_TEMP;   // 現在の温度

    long long steps;    // 試行回数
    for (steps = 0; ; steps++)
    {
        if (steps % 10000 == 0)
        {
            const double time = duration_cast<microseconds>(system_clock::now() - startClock).count() * 1e-6;   // 経過時間(秒)
            if (time >= END_TIME)
            {
                break;
            }

            const double progressRatio = time / END_TIME;   // 進捗。開始時が0.0、終了時が1.0
            temp = START_TEMP + (END_TEMP - START_TEMP) * progressRatio;
        }

        if (rand01() > 0.5)
        {
            // 近傍1 : d日目のコンテストをtに変えてみる
            const int d = randXor() % D;
            const int t = randXor() % NUM_TYPES;
            const int backupT = T[d];
            int deltaScore = 0;

            // 変更前のd日目のコンテストのスコアを引き、変更して、変更後のコンテストのスコアtを足す。
            deltaScore -= getContestScore(d, D, C, T, S);
            T[d] = t;
            deltaScore += getContestScore(d, D, C, T, S);
            const double probability = exp(deltaScore / temp); // 焼きなまし法の遷移確率

            if (probability > rand01())
            {
                // 変更を受け入れる。スコアを更新
                score += deltaScore;
                if (score > bestScore)
                {
                    bestScore = score;
                    bestT = T;
                }
            }
            else
            {
                // 変更を受け入れないので、元に戻す
                T[d] = backupT;
            }
        }
        else
        {
            // 近傍2 : d0日目のコンテストとd1日目コンテストを交換してみる
            const int diff = randXor() % 10 + 1;    // d0とd1は10日差まで
            const int d0 = randXor() % (D - diff);
            const int d1 = d0 + diff;

            int deltaScore = 0;

            // 変更前のd0日目とd1日目のコンテストのスコアを引き、変更後のd0日目とd1日目のコンテストのスコアを足す
            deltaScore -= getContestScore(d0, D, C, T, S);
            deltaScore -= getContestScore(d1, D, C, T, S);
            swap(T[d0], T[d1]);
            deltaScore += getContestScore(d0, D, C, T, S);
            deltaScore += getContestScore(d1, D, C, T, S);

            const double probability = exp(deltaScore / temp); // 焼きなまし法の遷移確率
            if (probability > rand01())
            {
                // 変更を受け入れる。スコアを更新
                score += deltaScore;
                if (score > bestScore)
                {
                    bestScore = score;
                    bestT = T;
                }
            }
            else
            {
                // 変更を受け入れないので、元に戻す
                swap(T[d0], T[d1]);
            }
        }
    }

    // 出力
    for (int t : bestT)
    {
        cout << t + 1 << endl;
    }
    cerr << "steps: " << steps << endl;
    cerr << "bestScore: " << max(0, bestScore + 1000000) << endl;

    return 0;
}

Submission Info

Submission Time
Task A - AtCoder Contest Scheduling
User shindannin
Language C++ (GCC 9.2.1)
Score 125898882
Code Size 6650 Byte
Status AC
Exec Time 1812 ms
Memory 4316 KB

Judge Result

Set Name test_ALL
Score / Max Score 125898882 / 365000000
Status
AC × 50
Set Name Test Cases
test_ALL test_00.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt, test_21.txt, test_22.txt, test_23.txt, test_24.txt, test_25.txt, test_26.txt, test_27.txt, test_28.txt, test_29.txt, test_30.txt, test_31.txt, test_32.txt, test_33.txt, test_34.txt, test_35.txt, test_36.txt, test_37.txt, test_38.txt, test_39.txt, test_40.txt, test_41.txt, test_42.txt, test_43.txt, test_44.txt, test_45.txt, test_46.txt, test_47.txt, test_48.txt, test_49.txt
Case Name Status Exec Time Memory
test_00.txt AC 1809 ms 3884 KB
test_01.txt AC 1804 ms 4080 KB
test_02.txt AC 1808 ms 3944 KB
test_03.txt AC 1804 ms 4212 KB
test_04.txt AC 1804 ms 4208 KB
test_05.txt AC 1803 ms 3996 KB
test_06.txt AC 1804 ms 4196 KB
test_07.txt AC 1804 ms 4008 KB
test_08.txt AC 1804 ms 4140 KB
test_09.txt AC 1804 ms 3944 KB
test_10.txt AC 1808 ms 4204 KB
test_11.txt AC 1806 ms 4144 KB
test_12.txt AC 1808 ms 4212 KB
test_13.txt AC 1805 ms 4200 KB
test_14.txt AC 1804 ms 4004 KB
test_15.txt AC 1809 ms 4012 KB
test_16.txt AC 1804 ms 4316 KB
test_17.txt AC 1804 ms 4024 KB
test_18.txt AC 1810 ms 3940 KB
test_19.txt AC 1810 ms 3888 KB
test_20.txt AC 1812 ms 4060 KB
test_21.txt AC 1804 ms 4204 KB
test_22.txt AC 1804 ms 3940 KB
test_23.txt AC 1808 ms 4212 KB
test_24.txt AC 1803 ms 3972 KB
test_25.txt AC 1804 ms 4316 KB
test_26.txt AC 1805 ms 4196 KB
test_27.txt AC 1808 ms 4204 KB
test_28.txt AC 1810 ms 4140 KB
test_29.txt AC 1803 ms 4032 KB
test_30.txt AC 1805 ms 4076 KB
test_31.txt AC 1803 ms 4004 KB
test_32.txt AC 1804 ms 3948 KB
test_33.txt AC 1810 ms 4068 KB
test_34.txt AC 1807 ms 3944 KB
test_35.txt AC 1812 ms 4192 KB
test_36.txt AC 1804 ms 4176 KB
test_37.txt AC 1807 ms 3944 KB
test_38.txt AC 1803 ms 3996 KB
test_39.txt AC 1804 ms 4192 KB
test_40.txt AC 1804 ms 4164 KB
test_41.txt AC 1806 ms 4180 KB
test_42.txt AC 1806 ms 4036 KB
test_43.txt AC 1806 ms 4216 KB
test_44.txt AC 1804 ms 4236 KB
test_45.txt AC 1803 ms 4056 KB
test_46.txt AC 1805 ms 4080 KB
test_47.txt AC 1810 ms 4008 KB
test_48.txt AC 1805 ms 4072 KB
test_49.txt AC 1812 ms 4048 KB