結果

問題 No.5017 Tool-assisted Shooting
ユーザー Pechi
提出日時 2023-07-16 20:42:17
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,667 ms / 2,000 ms
コード長 14,139 bytes
コンパイル時間 5,439 ms
コンパイル使用メモリ 284,776 KB
実行使用メモリ 24,360 KB
スコア 4,105,754
平均クエリ数 1000.00
最終ジャッジ日時 2023-07-16 20:45:03
合計ジャッジ時間 164,379 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 100
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#define _USE_MATH_DEFINES
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#define _USE_MATH_DEFINES
#include<bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
#include<optional>
#include<random>
#include <array>
#include <complex>
#include<chrono>
using namespace std;
#define LP(I,S,G) for (long long int I = (S); I < (G); ++I)
#define IN(X)   for (int in = 0; in < X.size(); in++)cin >> X[in]
#define OUT(X)  for (int in = 0; in < X.size(); in++)cout << X[in]<<" "
#define SORT(X) sort((X).begin(), (X).end())
#define CSORT(X,Y) sort(X.begin(), X.end(),Y)
#define COPY(X,Y) copy(X.begin(), X.end(), Y.begin())
#define ALL(X,Y) for (auto X = (Y).begin(); X != (Y).end(); X++)
#define FULL(a)  (a).begin(),(a).end()
#define BFS(Q,S) for(Q.push(S);Q.size()!=0;Q.pop())
typedef long long int ll;
typedef unsigned long long int ull;
chrono::system_clock::time_point starttime;
using namespace std::chrono;
inline float getTime() {
    return duration_cast<milliseconds>(system_clock::now() - starttime).count();
}
bool phase = 0;
int dx[] = { -1,0,1 };
ll MAX(ll A, ll B) { return ((A) > (B) ? (A) : (B)); }
ll MIN(ll A, ll B) { return ((A) < (B) ? (A) : (B)); }
inline long long int xor128() {
    static long long int x = 123456789, y = 362436069, z = 521288629, w = 88675123;
    long long int t = (x ^ (x << 11));
    x = y; y = z; z = w;
    return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
}
#define X_SIZE 25
#define MAX_TURN 1000
vector<ll> enemy_count(X_SIZE, 0);
mt19937_64 rnd;
using namespace std;
using ull = unsigned long long;
//https://nyaannyaan.github.io/library/inner/inner-hash.hpp
struct Hash {
    ull val;
    static constexpr ull M = (1ull << 61) - 1;
    Hash() {}
    static Hash set(const ll& a) {
        Hash res;
        res.val = cast(a);
        return res;
    }
    Hash& operator+=(const Hash& r) {
        if (((*this).val += r.val) >= M) (*this).val -= M;
        return *this;
    }
    Hash& operator+=(const ll& r) {
        ull s = cast(r);
        if (((*this).val += s) >= M) (*this).val -= M;
        return *this;
    }
    Hash& operator-=(const Hash& r) {
        if (((*this).val += M - r.val) >= M) (*this).val -= M;
        return *this;
    }
    Hash& operator-=(const ll& r) {
        ull s = cast(r);
        if (((*this).val += M - s) >= M) (*this).val -= M;
        return *this;
    }
    Hash& operator*=(const Hash& r) {
        (*this).val = modmul((*this).val, r.val);
        return *this;
    }
    Hash& operator*=(const ll& r) {
        ull s = cast(r);
        (*this).val = modmul((*this).val, s);
        return *this;
    }
    bool operator==(const Hash& r) const { return (*this).val == r.val; }
    Hash operator+(const Hash& r) { return Hash(*this) += r; }
    Hash operator+(const ll& r) { return Hash(*this) += r; }
    Hash operator-(const Hash& r) { return Hash(*this) -= r; }
    Hash operator-(const ll& r) { return Hash(*this) -= r; }
    Hash operator*(const Hash& r) { return Hash(*this) *= r; }
    Hash operator*(const ll& r) { return Hash(*this) *= r; }
    Hash operator-() const {
        Hash res;
        res.val = (*this).val == 0 ? 0 : M - (*this).val;
        return res;
    }
    Hash pow(long long e) {
        Hash a{ *this }, res{ Hash::set(1) };
        for (; e; a *= a, e >>= 1) {
            if (e & 1) res *= a;
        }
        return res;
    }
    static Hash get_basis() {
        static auto rand_time =
            chrono::duration_cast<chrono::nanoseconds>(
                chrono::high_resolution_clock::now().time_since_epoch())
            .count();
        static mt19937_64 rng(rand_time);
        Hash h;
        while (isPrimitive(h.val = rng() % (M - 1) + 1) == false)
            ;
        return h;
    }
private:
    static constexpr ull MASK30 = (1ull << 30) - 1;
    static constexpr ull MASK31 = (1ull << 31) - 1;
    static constexpr ull MASK61 = M;
    static inline ull CalcMod(ull x) {
        ull xu = x >> 61;
        ull xd = x & MASK61;
        ull res = xu + xd;
        if (res >= M) res -= M;
        return res;
    }
    static ull modpow(ull a, ull b) {
        ull r = 1;
        for (a = CalcMod(a); b; a = modmul(a, a), b >>= 1) r = modmul(r, a);
        return r;
    }
    static bool isPrimitive(ull x) {
        for (auto& d : vector<ull>{ 2, 3, 5, 7, 11, 13, 31, 41, 61, 151, 331, 1321 })
            if (modpow(x, (M - 1) / d) <= 1) return false;
        return true;
    }
    static inline constexpr ull cast(const long long& a) {
        return a < 0 ? a + M : a;
    }
    static inline ull modmul(const ull& a, const ull& b) {
        ull au = a >> 31;
        ull ad = a & MASK31;
        ull bu = b >> 31;
        ull bd = b & MASK31;
        ull mid = ad * bu + au * bd;
        ull midu = mid >> 30;
        ull midd = mid & MASK30;
        return CalcMod(au * bu * 2 + midu + (midd << 31) + ad * bd);
    }
};
namespace std {
    template<>
    struct hash<Hash> {
    public:
        size_t operator()(const Hash& data)const {
            return hash<ull>()(data.val);
        }
    };
}
struct HashSpace {
    static vector <Hash> hashVal;
    static bool isFirstInit;
    int Sx = X_SIZE * 3;
    HashSpace() {
        if (isFirstInit) {
            vector<Hash> pw[1];
            Hash basis[1];
            pw[0] = { vector<Hash>(Sx + 1) };
            basis[0] = Hash::get_basis();
            isFirstInit = 0;
            pw[0][0] = Hash::set(1);
            for (int i = 1; i <= Sx; i++) pw[0][i] = pw[0][i - 1] * basis[0];
            hashVal = pw[0];
        }
    }
};
vector<Hash> HashSpace::hashVal;
bool HashSpace::isFirstInit = 1;
struct State {
    vector<deque<array<int, 4>>> enemy_table;
    int power;
    static HashSpace t;
    Hash myHash;
    int myScore;
    int x;
    int turn;
    // 初期状態の生成
    State(vector<deque<array<int, 4>>>& in_e, int in_p, int in_x, int in_t) :enemy_table(in_e) {
        power = in_p;
        myScore = 0;
        if (!phase)myScore = power;
        x = in_x;
        turn = in_t;
        for (int i = 0; i < X_SIZE; ++i) {
            if (enemy_table[i].size() != 0)myHash += t.hashVal[i * 3] * enemy_table[i].front()[0] + t.hashVal[i * 3 + 1] * enemy_table[i].front()[1] 
                + t.hashVal[i * 3 + 2] * enemy_table[i].front()[3];
        }
        myHash += x;
    }
    int score() {
        return myScore;
    }
    Hash hash() {
        return myHash;
    }
    Hash update_hash(int x) {
        Hash ret = Hash::set(0);
        ret -= t.hashVal[x * 3] * enemy_table[x].front()[0] + t.hashVal[x * 3 + 1] * enemy_table[x].front()[1] + t.hashVal[x * 3 + 2] * 
            enemy_table[x].front()[3];
        array<int, 4> note = enemy_table[x].front();
        enemy_table[x].pop_front();
        if (enemy_table[x].size() != 0)ret += t.hashVal[x * 3] * enemy_table[x].front()[0] + t.hashVal[x * 3 + 1] * enemy_table[x].front()[1] + t
            .hashVal[x * 3 + 2] * enemy_table[x].front()[3];
        enemy_table[x].push_front(note);
        return ret;
    }
    // スコアとハッシュの差分計算
    // 状態は更新しない
    pair<int, Hash> try_apply(ull op, ull score, Hash hash) {
        x += dx[op];
        hash += dx[op];
        if (enemy_table[x].size() != 0) {
            if (enemy_table[x].front()[0] <= turn + 2) {
                x -= dx[op];
                return { -10000,Hash::set(0) };
            }
            if (enemy_table[x].front()[1] - (1 + power / 100) <= 0) {
                if (phase)score += enemy_table[x].front()[3] * 10000;
                else score += enemy_table[x].front()[2] * 10000;
                hash += update_hash(x);
            }
            else {
                hash -= t.hashVal[x * 3 + 1] * (1 + power / 100);
                score += enemy_table[x].front()[2] - (enemy_table[x].front()[1] - (1 + power / 100));
            }
        }
        for (int i = 0; i < 25; ++i) {
            if (enemy_table[i].size() == 0)continue;
            if (enemy_table[i].front()[0] == turn) {
                hash += update_hash(i);
            }
        }
        x -= dx[op];
        return { score,hash };
    }
    // 状態を更新する
    // 元の状態に戻すための情報を返す
    pair<pair<int, int>, queue<pair<int, array<int, 4>>>> apply(ull op) {
        x += dx[op];
        int bp = power;
        queue < pair<int, array<int, 4>>> backup;
        if (enemy_table[x].size() != 0) {
            if (enemy_table[x].front()[0] <= turn + 2) {
                ++turn;
                return { {op,0},{} };
            }
            enemy_table[x].front()[1] -= (1 + power / 100);
            if (enemy_table[x].front()[1] <= 0) {
                power += enemy_table[x].front()[3];
                backup.push({ x,enemy_table[x].front() });
                enemy_table[x].pop_front();
            }
        }
        for (int i = 0; i < X_SIZE; ++i) {
            if (enemy_table[i].size() == 0)continue;
            if (enemy_table[i].front()[0] == turn) {
                backup.push({ i,enemy_table[i].front() });
                enemy_table[i].pop_front();
            }
        }
        ++turn;
        return { {op,bp},backup };
    }
    // applyから返された情報をもとに状態を元に戻す
    ull back(pair<pair<int, int>, queue<pair<int, array<int, 4>>>> backup) {
        power = backup.first.second;
        --turn;
        while (backup.second.size() != 0) {
            int i = backup.second.front().first;
            enemy_table[i].push_front(backup.second.front().second);
            backup.second.pop();
        }
        if (enemy_table[x].size() != 0) enemy_table[x].front()[1] += (1 + power / 100);
        x -= dx[backup.first.first];
        return backup.first.first;
    }
};
HashSpace State::t;
struct Node;
struct Kouho {
    ull op;
    shared_ptr<Node> parent;
    int score;
    Hash hash;
    ull p; // 優先度(複数もたせたほうがいい場合があるかもしれない。)
};
using Parent = optional<pair<ull, shared_ptr<Node>>>;
using Children = vector<pair<ull, weak_ptr<Node>>>;
struct Node {
    Parent parent; // 操作、親への参照
    Children child; // 操作、子への参照
    int score;
    Hash hash;
    Node(Parent parent, Children child, ull score, Hash hash) :
        parent(parent), child(child), score(score), hash(hash) {}
};
// 多スタート用に構造体にまとめておくと楽
struct Tree {
    State state;
    shared_ptr<Node> node;
    ull rank;
    // 注意: depthは深くなっていくごとに-1されていく
    void dfs(vector<Kouho>& next_states, bool one, ull& p, ull depth) {
        if (depth == 0) {
            ull score = node->score;
            Hash hash = node->hash;
            // 検算
            // assert(score==state.score());
            // assert(hash==state.hash());
            // 次の操作を列挙
            for (ull op = 0; op < 3; ++op) {
                int nx = state.x + dx[op];
                if (nx < 0 || nx >= X_SIZE)continue;
                auto[next_score, next_hash] = state.try_apply(op, score, hash);
                if (next_score >= 0) {
                    next_states.emplace_back(Kouho{ op,node,next_score,next_hash,p });
                    p += 1;
                }
            }
        }
        else {
            auto node_backup = node;
            auto child = &node_backup->child;
            // 有効な子だけにする
            child->erase(remove_if(child->begin(), child->end(), [](pair<ull, weak_ptr<Node>>& x) {return x.second.expired(); }), child->end());
            bool next_one = one & child->size() == 1;
            // 定数調整の必要あり
            if (depth == 5) {
                p = 0;
            }
            ++rank;
            for (const auto&[op, ptr] : *child) {
                node = ptr.lock();
                pair<pair<int, int>, queue<pair<int, array<int, 4>>>> backup = state.apply(op);
                dfs(next_states, next_one, p, depth - 1);
                if (!next_one) {
                    state.back(backup);
                }
            }
            if (!next_one) {
                node = node_backup;
                --rank;
            }
        }
    }
};
int beam(vector<deque<array<int, 4>>>& enemy_table, int x, int turn, int power) {
    constexpr ull TURN = 30;
    constexpr ull M = 40; // ビーム幅
    State state(enemy_table, power, x, turn);
    ull score = state.score();
    Hash hash = state.hash();
    Tree tree{ move(state),shared_ptr<Node>(new Node(Parent(),Children(),score,hash)),0 };
    vector<shared_ptr<Node>> cur{ tree.node };
    vector<Kouho> next_states;
    //  cerr << state.x << "\n";
    unordered_set<Hash> set;
    for (ull i = 0; i < TURN; ++i) {
        next_states.clear();
        ull tmp = 0;
        tree.dfs(next_states, true, tmp, i - tree.rank);
        if (i + 1 != TURN) {
            // 上位M個を残す
            if (next_states.size() > M) {
                nth_element(next_states.begin(), next_states.begin() + M, next_states.end(), [](Kouho& a, Kouho& b) {
                    if (a.score == b.score) {
                        return a.p > b.p;
                    }
                    else {
                        return a.score > b.score;
                    }
                    });
                next_states.erase(next_states.begin() + M, next_states.end());
            }
            cur.clear();
            set.clear();
            for (const auto&[op, parent, next_score, next_hash, p] : next_states) {
                // 重複除去
                if (set.count(next_hash) == 0) {
                    set.insert(next_hash);
                    auto child_ptr = shared_ptr<Node>(new Node(Parent({ op,parent }), Children(), next_score, next_hash));
                    parent->child.emplace_back(op, weak_ptr<Node>(child_ptr));
                    cur.emplace_back(child_ptr);
                }
            }
        }
    }
    // 最良の状態を選択
    ull arg_max = -1;
    ull max = 0;
    if (next_states.size() == 0)return 1;
    for (ull i = 0; i < next_states.size(); ++i) {
        if (next_states[i].score >= max) {
            max = next_states[i].score;
            arg_max = i;
        }
    }
    auto[op, ptr, best_score, _, __] = next_states[arg_max];
    vector<ull> ret{ op };
    //  cerr << "score: " << best_score<<" ";
    //  cerr << "rank: " << TURN - tree.rank << endl;
        // 操作の復元
    while (ptr->parent.has_value()) {
        auto[op, parent] = ptr->parent.value();
        ret.emplace_back(op);
        ptr = parent;
    }
    reverse(ret.begin(), ret.end());
    return ret[0];
}
int simulate(int x, int power, int turn, vector<deque<array<int, 4>>> enemy_table) {
    /*  for (int i = turn + 1; i < MIN(turn + TURN, 1060); ++i) {
            normal_distribution<> dist_h(7.7 + 0.15*i, 1.5 + 0.03*i);
            for (int k = 0; k < 25; ++k) {
                if (xor128() % 10000 < MAX(100, MIN(800, enemy_count[k] * 10000 / (turn+1)))) {
                    int h = MAX(1, (int)dist_h(rnd));
                    normal_distribution<> dist_p(0.8*h, 0.1*h);
                    int p= MAX(0, (int)dist_p(rnd));
                    enemy_table[k].push_back({ i,h,p });
                }
            }
        }
    */
    return beam(enemy_table, x, turn, power);
}
int main() {
    int n, turn = 0, x = 12, power = 0;
    cin >> n;
    vector<deque<array<int, 4>>> enemy_table(25);
    string move = "LSR";
    while (n != -1) {
//      cerr << n << endl;
        if (turn >= 500)phase = 1;
        for (int i = 0; i < n; ++i) {
            int h, p, ix;
            cin >> h >> p >> ix;
            enemy_table[ix].push_back({ turn + 60,h,h, p });
        }
        vector<int> cnt(3, 0);
        for (int i = 0; i < 1; ++i)++cnt[simulate(x, power, turn, enemy_table)];
        int max_id = 0;
        for (int i = 0; i < 3; ++i)if (cnt[i] > cnt[max_id])max_id = i;
        x += dx[max_id];
        if (enemy_table[x].size() != 0) {
            enemy_table[x].front()[1] -= (1 + power / 100);
            if (enemy_table[x].front()[1] <= 0) {
                power += enemy_table[x].front()[3];
                enemy_table[x].pop_front();
            }
        }
        //      cerr << turn << "\t:";
        for (int i = 0; i < X_SIZE; ++i) {
            if (enemy_table[i].size() == 0) {
                //              cerr << "- ";
                continue;
            }
            //          cerr << enemy_table[i].front()[0] - turn << " ";
            if (enemy_table[i].front()[0] == turn) {
                enemy_table[i].pop_front();
            }
        }
        //      cerr <<power<< "\n";
        cout << move[max_id] << endl;
        ++turn;
        if (turn == 1000)break;
        cin >> n;
    }
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0