Submission #15983533


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;
}

int main()
{
    //  入力
    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;
    }

    // 焼きなまし法(ここから)
    auto startClock = system_clock::now();
    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 time = 0.0;   // 経過時間(秒)
    do
    {
        const double progressRatio = time / END_TIME;   // 進捗。開始時が0.0、終了時が1.0
        const double temp = START_TEMP + (END_TEMP - START_TEMP) * progressRatio;

        // 近傍 : d日目のコンテストをtに変えてみる。d,tはランダムに選ぶ。
        const int d = randXor() % D;
        const int t = randXor() % NUM_TYPES;
        const int backupT = T[d];
        int deltaScore = 0; // スコアの差分 = 変更後のスコア - 変更前のスコア
        deltaScore -= getFullScore(D, C, T, S);
        T[d] = t;   // 変更
        deltaScore += getFullScore(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;
        }

        time = (duration_cast<microseconds>(system_clock::now() - startClock).count() * 1e-6);
    } while (time < END_TIME);
    // 焼きなまし法(ここまで)


    // 出力
    for (int t : bestT)
    {
        cout << t + 1 << 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 94172294
Code Size 3835 Byte
Status AC
Exec Time 1816 ms
Memory 4380 KB

Judge Result

Set Name test_ALL
Score / Max Score 94172294 / 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 1810 ms 4280 KB
test_01.txt AC 1807 ms 3992 KB
test_02.txt AC 1810 ms 4180 KB
test_03.txt AC 1809 ms 4224 KB
test_04.txt AC 1812 ms 3988 KB
test_05.txt AC 1809 ms 3976 KB
test_06.txt AC 1810 ms 4160 KB
test_07.txt AC 1806 ms 4348 KB
test_08.txt AC 1811 ms 4024 KB
test_09.txt AC 1814 ms 4008 KB
test_10.txt AC 1807 ms 3992 KB
test_11.txt AC 1816 ms 4076 KB
test_12.txt AC 1812 ms 4216 KB
test_13.txt AC 1812 ms 4184 KB
test_14.txt AC 1809 ms 4052 KB
test_15.txt AC 1812 ms 3924 KB
test_16.txt AC 1810 ms 4184 KB
test_17.txt AC 1806 ms 4244 KB
test_18.txt AC 1816 ms 3876 KB
test_19.txt AC 1814 ms 3808 KB
test_20.txt AC 1809 ms 3864 KB
test_21.txt AC 1810 ms 4212 KB
test_22.txt AC 1806 ms 3920 KB
test_23.txt AC 1808 ms 4380 KB
test_24.txt AC 1814 ms 4220 KB
test_25.txt AC 1810 ms 4020 KB
test_26.txt AC 1807 ms 4224 KB
test_27.txt AC 1807 ms 4244 KB
test_28.txt AC 1811 ms 3932 KB
test_29.txt AC 1812 ms 4132 KB
test_30.txt AC 1809 ms 4028 KB
test_31.txt AC 1810 ms 4032 KB
test_32.txt AC 1814 ms 4056 KB
test_33.txt AC 1806 ms 4116 KB
test_34.txt AC 1814 ms 4348 KB
test_35.txt AC 1807 ms 4076 KB
test_36.txt AC 1813 ms 4028 KB
test_37.txt AC 1805 ms 3980 KB
test_38.txt AC 1810 ms 3972 KB
test_39.txt AC 1810 ms 4024 KB
test_40.txt AC 1808 ms 4116 KB
test_41.txt AC 1812 ms 4196 KB
test_42.txt AC 1810 ms 3980 KB
test_43.txt AC 1806 ms 4180 KB
test_44.txt AC 1811 ms 4256 KB
test_45.txt AC 1812 ms 4164 KB
test_46.txt AC 1807 ms 4260 KB
test_47.txt AC 1809 ms 4244 KB
test_48.txt AC 1814 ms 4132 KB
test_49.txt AC 1815 ms 4008 KB