結果

問題 No.5003 物理好きクリッカー
ユーザー とばり
提出日時 2018-12-06 07:54:06
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 9,314 ms / 10,000 ms
コード長 2,877 bytes
コンパイル時間 1,626 ms
実行使用メモリ 21,900 KB
スコア 4,454,573
平均クエリ数 10000.00
最終ジャッジ日時 2021-07-19 08:55:13
合計ジャッジ時間 311,205 ms
ジャッジサーバーID
（参考情報） 		judge10 / judge14
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

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; // 9sec
#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;

    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;
        bool forceNext = r * (timeLimit - t) > timeLimit * randInt(r);

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

    return 0;
}
0