結果

問題 No.5003 物理好きクリッカー
ユーザー とばりとばり
提出日時 2018-12-06 08:27:19
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 9,314 ms / 10,000 ms
コード長 3,265 bytes
コンパイル時間 1,520 ms
実行使用メモリ 22,008 KB
スコア 4,636,940
平均クエリ数 10000.00
最終ジャッジ日時 2021-07-19 09:00:14
合計ジャッジ時間 310,895 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 9,303 ms
21,360 KB
testcase_01 AC 9,308 ms
21,672 KB
testcase_02 AC 9,312 ms
21,684 KB
testcase_03 AC 9,296 ms
21,696 KB
testcase_04 AC 9,289 ms
21,540 KB
testcase_05 AC 9,290 ms
21,852 KB
testcase_06 AC 9,311 ms
21,528 KB
testcase_07 AC 9,290 ms
21,732 KB
testcase_08 AC 9,289 ms
21,684 KB
testcase_09 AC 9,287 ms
21,864 KB
testcase_10 AC 9,306 ms
21,528 KB
testcase_11 AC 9,292 ms
21,888 KB
testcase_12 AC 9,289 ms
21,372 KB
testcase_13 AC 9,314 ms
21,192 KB
testcase_14 AC 9,305 ms
21,828 KB
testcase_15 AC 9,292 ms
21,348 KB
testcase_16 AC 9,301 ms
21,864 KB
testcase_17 AC 9,285 ms
21,348 KB
testcase_18 AC 9,290 ms
21,516 KB
testcase_19 AC 9,291 ms
21,360 KB
testcase_20 AC 9,290 ms
21,528 KB
testcase_21 AC 9,285 ms
21,864 KB
testcase_22 AC 9,313 ms
21,492 KB
testcase_23 AC 9,314 ms
21,360 KB
testcase_24 AC 9,295 ms
21,864 KB
testcase_25 AC 9,284 ms
21,372 KB
testcase_26 AC 9,309 ms
21,924 KB
testcase_27 AC 9,291 ms
21,324 KB
testcase_28 AC 9,287 ms
21,504 KB
testcase_29 AC 9,287 ms
21,912 KB
testcase_30 AC 9,284 ms
21,348 KB
testcase_31 AC 9,287 ms
21,504 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

// #define DEBUG

struct MSecTimer
{
    std::chrono::system_clock::time_point from_;

    MSecTimer()
    {
        restart();
    }

    void restart()
    {
        from_ = std::chrono::system_clock::now();
    }

    int64_t elapsed()
    {
        auto now = std::chrono::system_clock::now();
        return std::chrono::duration_cast<std::chrono::milliseconds>(now - from_).count();
    }
};

int randInt(int n)
{
    static std::random_device rnd;
    static std::mt19937 mt(rnd());
    return mt() % n;
}

enum Action
{
    CLICK,
    ENHCLICK
};

const int64_t inf = (1LL << 50);

int64_t getScore(const std::vector<Action>& seq)
{
    int levelClick = 0,
        costClick = 15;
    int64_t score = 0;

    for (int act : seq)
    {
        switch (act)
        {
            case CLICK:
                score += (1LL << levelClick);
                break;
            case ENHCLICK:
                score -= costClick;
                levelClick++;
                costClick *= 10;
                break;
        }
        if (score < 0) return -inf;
    }
    return score;
}

std::vector<Action> generateNextState(const std::vector<Action>& current)
{
    auto next = current;

    int i = randInt(current.size());

    if (next[i] == CLICK) next[i] = ENHCLICK;
    else next[i] = CLICK;

    return next;
}

std::vector<Action> SA(int numTurn)
{
#ifdef DEBUG
    const int64_t timeLimit = 1000; // 1sec
#else
    const int64_t timeLimit = 9000; // 9sec
#endif

    std::vector<Action> current(numTurn, CLICK);
    int64_t currentScore = getScore(current);

    auto best = current;
    int64_t bestScore = currentScore;

    MSecTimer timer;
    double beginTemp = 1000000000,
           endTemp = 1000000;

    while (timer.elapsed() < timeLimit)
    {
#ifdef DEBUG
        std::cerr << "elapsed: " << timer.elapsed() << " current: " << currentScore
                  << " best: " << bestScore << std::endl;
#endif
        // 次の状態を生成
        auto next = generateNextState(current);

        int64_t nextScore = getScore(next);

        int64_t t = timer.elapsed(),
                r = 10000;
        double temp = beginTemp + t * (endTemp - beginTemp) / timeLimit,
               propability = exp((nextScore - currentScore) / temp);
        bool forceNext = propability > (double)randInt(r) / r;
        // bool forceNext = r * (timeLimit - t) > timeLimit * randInt(r);
        // bool forceNext = false;

        if (nextScore > currentScore or (forceNext and currentScore > 0))
        {
            currentScore = nextScore;
            current = next;
        }

        if (currentScore > bestScore)
        {
            bestScore = currentScore;
            best = current;
        }
    }

    return best;
}

int main()
{
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);

    int n;
    std::cin >> n;

    std::string s;
    std::cin >> s;

    auto ans = SA(n);

    for (int i = 0; i < n; i++)
    {
        if (ans[i] == ENHCLICK) std::cout << "enhclick" << std::endl;
        else std::cout << "click" << std::endl;

        std::string response;
        std::cin >> response;
    }

#ifdef DEBUG
    std::cerr << "[Score] " << getScore(ans) << std::endl;
#endif

    return 0;
}
0