#1120797 (C++23) No.5017 Tool-assisted Shooting

• 問題: No.5017 Tool-assisted Shooting
• ユーザー: FplusFplusF
• 提出日時: 2025-09-12 21:58:13
• 言語: C++23 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 1,594 ms / 2,000 ms
• コード長: 10,700 bytes
• コンパイル時間: 3,287 ms
• コンパイル使用メモリ: 305,812 KB
• 実行使用メモリ: 26,072 KB
• スコア: 4,175,764
• 平均クエリ数: 950.00
• 最終ジャッジ日時: 2025-09-12 23:41:18
• 合計ジャッジ時間: 160,205 ms
• ジャッジサーバーID （参考情報）: judge7 / judge3

ファイルパターン	結果
other	AC * 100

ソースコード

#include <bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
using tii=tuple<int,int,int>;
using qii=tuple<int,int,int,int>;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
constexpr int INF=1e9;
constexpr ll INF_ll=1e18;
#define rep(i,n) for (int i=0;i<(int)(n);i++)
#define replr(i,l,r) for (int i=(int)(l);i<(int)(r);i++)
#define all(v) v.begin(),v.end()
#define len(v) ((int)v.size())
template<class T> inline bool chmin(T &a,T b){
    if(a>b){
        a=b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T &a,T b){
    if(a<b){
        a=b;
        return true;
    }
    return false;
}

namespace Timer{
    chrono::system_clock::time_point program_start,start;
    void program_start_snap(){
        program_start=start=chrono::system_clock::now();
    }
    void snap(){
        start=chrono::system_clock::now();
    }
    int get_ms(){
        auto now=chrono::system_clock::now();
        int ms=chrono::duration_cast<chrono::milliseconds>(now-start).count();
        return ms;
    }
    int get_ms_all_program(){
        auto now=chrono::system_clock::now();
        int ms=chrono::duration_cast<chrono::milliseconds>(now-program_start).count();
        return ms;
    }
}

mt19937 mt;
uint32_t rand_int(uint32_t r){  //[0,r)
    assert(r!=0);
    return ((uint64_t)mt()*r)>>32;
}
int rand_int(int l,int r){  //[l,r)
    assert(l<r);
    return l+rand_int(r-l);
}
constexpr double one_div_mt_max=1.0/(double)mt19937::max();
double rand_double(){  //[0.0,1.0]
    return mt()*one_div_mt_max;
}

template<class T> T get_random_element(const vector<T> &v){
    assert(!v.empty());
    return v[rand_int(len(v))];
}

template<class T> void add(vector<T> &a,vector<T> b){
    for(auto i:b) a.push_back(i);
}

constexpr int W=25,H=60,T=1000;

namespace Solver{
    
    struct Enemy{
        int first_hp,hp,power,end_turn;
        Enemy(int h,int p,int turn):first_hp(h),hp(h),power(p),end_turn(turn+H){}
    };
    
    using Score=int;
    
    struct Candidate{
        int action;
        Score score;
        int parent;
        Candidate(int action_,Score score_,int parent_):action(action_),score(score_),parent(parent_){}
        auto operator<=>(const Candidate &other) const{
            return this->score<=>other.score;
        }
    };
    
    struct State{
        vector<queue<Enemy>> q;
        int pos=12,score=0,level=1,power_sum=0;
        
        int point=0;
        
        vector<int> actions;
        
        int turn=0;
        
        State():q(W){}
        
        auto operator<=>(const State &other) const{
            return this->point*this->level<=>other.point*other.level;
        }
        
        void add_enemy(int x,int h,int p){
            Enemy enemy(h,p,turn);
            q[x].push(enemy);
        }
        
        Candidate try_advance(int d,int parent) const{
            
            int new_pos=pos+d;
            
            if(new_pos==-1) new_pos=W-1;
            if(new_pos==W) new_pos=0;
            
            int new_point=point,new_level=level;
            
            if(!q[new_pos].empty()){
                Enemy enemy=q[new_pos].front();
                
                if(enemy.end_turn==turn+1){
                    return Candidate(d,-INF,parent);
                }
                
                
                enemy.hp-=min(enemy.hp,level);
                
                if(enemy.hp<=0){
                    
                    new_point+=enemy.first_hp;
                    
                    new_level=1+(power_sum+enemy.power)/100;
                }else{
                    if(enemy.end_turn==turn+2){
                        return Candidate(d,-INF,parent);
                    }
                }
            }else{
                new_point-=10;
                if(d==0) new_point-=10;
                if(!actions.empty()&&actions.back()+d==0) new_point-=10;
            }
            
            rep(w,W){
                if(!q[w].empty()){
                    Enemy enemy=q[w].front();
                    if(enemy.end_turn!=turn+1){
                        if(w!=new_pos) new_point-=enemy.first_hp-enemy.hp;
                    }
                }
            }
            
            Score new_score=new_point*new_level;
            
            
            return Candidate(d,new_score,parent);
            
        }
        
        void advance(int d){
            pos+=d;
            
            if(pos==-1) pos=W-1;
            if(pos==W) pos=0;
            
            
            actions.push_back(d);
            
            if(!q[pos].empty()){
                Enemy &enemy=q[pos].front();
                
                if(enemy.end_turn==turn+1){
                    //cerr << turn << " " << enemy.first_hp << " " << enemy.hp << " " << enemy.power << " miss" << endl;
                    score=-INF;
                    point=-INF;
                }
                
                
                enemy.hp-=min(enemy.hp,level);
                
                if(enemy.hp<=0){
                    score+=enemy.first_hp;
                    
                    point+=enemy.first_hp;
                    
                    power_sum+=enemy.power;
                    level=1+power_sum/100;
                    q[pos].pop();
                }else{
                }
            }else{
                point-=10;
                int sz=len(actions);
                if(actions.back()==0) point-=10;
                if(2<=sz&&actions[sz-2]+actions[sz-1]==0) point-=10;
            }
            
            turn++;
            
            rep(w,W){
                if(!q[w].empty()){
                    Enemy &enemy=q[w].front();
                    if(enemy.end_turn==turn){
                        q[w].pop();
                    }else{
                        /*int dist=(pos-w+W)%W;
                        if(!(dist==0||dist==1||dist==W-1)) point-=enemy.first_hp-enemy.hp;*/
                        if(pos!=w) point-=enemy.first_hp-enemy.hp;
                    }
                }
            }
            
            if(!q[pos].empty()){
                Enemy &enemy=q[pos].front();
                
                if(enemy.end_turn==turn+1){
                    //cerr << turn << " " << enemy.first_hp << " " << enemy.hp << " " << enemy.power << " miss" << endl;
                    score=-INF;
                    point=-INF;
                }
            }
            
        }
    };
    
    constexpr int Depth=20,Width=5;
    
    vector<int> beam_search(State first_state){
        vector<State> dp;
        
        dp.push_back(first_state);
        
        rep(depth,Depth){
            
            //vector<Candidate> candidates;
            
            vector<priority_queue<Candidate,vector<Candidate>,greater<Candidate>>> pq(W);
            
            rep(width,Width){
                if(len(dp)<=width) break;
                const State &state=dp[width];
                replr(d,-1,2){
                    Candidate candidate=state.try_advance(d,width);
                    if(candidate.score==-INF) continue;
                    
                    int pos=state.pos+d;
                    
                    if(pos==-1) pos=W-1;
                    if(pos==W) pos=0;
                    
                    if(!pq[pos].empty()&&candidate<pq[pos].top()) continue;
                    pq[pos].push(candidate);
                    if(len(pq[pos])==Width) pq[pos].pop();
                }
            }
            
            //cerr << "?" << endl;
            
            vector<Candidate> candidates;
            
            rep(pos,W){
            
                while(!pq[pos].empty()){
                    Candidate candidate=pq[pos].top();
                    pq[pos].pop();
                    candidates.push_back(candidate);
                    //if(len(candidates)==Width) break;
                }
                
            }
            
            sort(all(candidates));
            reverse(all(candidates));
            
            
            vector<State> new_dp;
            
            for(auto &candidate:candidates){
                State state=dp[candidate.parent];
                state.advance(candidate.action);
                
                new_dp.push_back(state);
            }
            
            swap(dp,new_dp);
            
        }
        
        if(dp.empty()) return {0};
        
        
        //cerr << "beam " << dp[0].point << " " << dp[0].level << " " << dp[0].actions[0] << endl;
        
        
        return dp[0].actions;
        
    }
    
    void solve(){
        
        State state;
        
        
        rep(_,T){
            int n;
            cin >> n;
            
            if(n==-1) break;
            
            rep(i,n){
                int h,p,x;
                cin >> h >> p >> x;
                
                //cerr << h << " " << p << " " << x << endl;
                
                state.add_enemy(x,h,p);
            }
            
            state.actions.clear();
            int action=beam_search(state)[0];
            
            
            state.advance(action);
            
            char c='X';
            
            if(action==-1) c='L';
            else if(action==0) c='S';
            else if(action==1) c='R';
            else assert(0);
            
            cout << c << '\n';
            cout.flush();
            
            //cerr << state.turn << " ? " << c << endl;
            
            /*if(!state.q[state.pos].empty()){
                
                Enemy enemy=state.q[state.pos].front();
                cerr << " !!! " << enemy.end_turn << " " << enemy.hp << endl;
            }
            
            cerr << state.turn << " : ";
            
            rep(w,W){
                if(!state.q[w].empty()){
                    cerr << state.q[w].front().end_turn-state.turn << " ";
                }else{
                    cerr << "-1 ";
                }
            }
            cerr << endl;
            
            assert(state.turn<=200);*/
            
            //cerr << len(state.q[state.pos]) << " " << n << " " << state.turn << endl;
            
            //cerr << state.turn << " " << state.score << " " << Timer::get_ms() << endl;
        }
        
        cerr << state.score << ' ' << Timer::get_ms_all_program() << '\n';
        
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    Timer::program_start_snap();
    
    #ifdef LOCAL
    
    rep(i,W){
        int _;
        cin >> _;
    }
    
    #endif



    Solver::solve();
    exit(0);
}