結果
| 問題 |
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);
}