結果
| 問題 | No.5017 Tool-assisted Shooting |
| コンテスト | |
| ユーザー |
 FplusFplusF
|
| 提出日時 | 2023-08-08 05:44:03 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,932 ms / 2,000 ms |
| コード長 | 6,016 bytes |
| コンパイル時間 | 3,343 ms |
| コンパイル使用メモリ | 229,044 KB |
| 実行使用メモリ | 24,504 KB |
| スコア | 4,092,094 |
| 平均クエリ数 | 990.00 |
| 最終ジャッジ日時 | 2023-08-08 05:47:17 |
| 合計ジャッジ時間 | 86,731 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge11 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 100 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
const int INF=1e9;
using pii=pair<int,int>;
using tii=tuple<int,int,int>;
#define rep(i,n) for (int i=0;i<(int)(n);i++)
#define all(v) v.begin(),v.end()
template<class T> void chmin(T &a,T b){
if(a>b){
a=b;
}
}
template<class T> void chmax(T &a,T b){
if(a<b){
a=b;
}
}
int H=60,W=25,T=1000;
struct Input{
int n;
vector<int> h,p,x;
void input_cin(){
cin >> n;
if(n==-1) exit(0);
h.assign(n,0);
p.assign(n,0);
x.assign(n,0);
rep(i,n) cin >> h[i] >> p[i] >> x[i];
}
}Input;
struct shooter{
int i;
int j;
int l;
int s;
};
struct enemy{
int i;
int fh;
int h;
int p;
};
struct state{
int turn;
double point;
vector<queue<enemy>> q_enemy;
shooter me;
string root;
};
bool operator<(const state &a,const state &b){
return (double)a.point*(double)a.me.l<(double)b.point*(double)b.me.l;
}
struct solver{
string beam_search(int now_turn,state first_state,int depth,int width){
vector<state> now_beam,next_beam;
now_beam.push_back(first_state);
rep(d,depth){
rep(w,width){
if((int)now_beam.size()<=w) break;
rep(m,3){
state new_state=now_beam[w];
if(m==0){
new_state.root.push_back('S');
}
if(m==1){
new_state.me.j--;
if(new_state.me.j<0) new_state.me.j+=W;
new_state.root.push_back('L');
}
if(m==2){
new_state.me.j++;
if(W<=new_state.me.j) new_state.me.j-=W;
new_state.root.push_back('R');
}
if(!new_state.q_enemy[new_state.me.j].empty()&&new_state.me.i==new_state.q_enemy[new_state.me.j].front().i) new_state.point=-1e9;
if(!new_state.q_enemy[new_state.me.j].empty()&&0<new_state.q_enemy[new_state.me.j].front().h){
new_state.q_enemy[new_state.me.j].front().h-=new_state.me.l;
if(new_state.root.back()=='S') new_state.point+=T-now_turn;
if(new_state.q_enemy[new_state.me.j].front().h<=0){
/*if(now_turn<=300) new_state.point+=new_state.q_enemy[new_state.me.j].front().fh*new_state.q_enemy[new_state.me.j].front().fh;
else new_state.point+=new_state.q_enemy[new_state.me.j].front().fh*new_state.q_enemy[new_state.me.j].front().p;*/
new_state.point+=new_state.q_enemy[new_state.me.j].front().fh;
new_state.point+=(depth-(new_state.turn-now_turn))*(depth-(new_state.turn-now_turn));
new_state.me.s+=new_state.q_enemy[new_state.me.j].front().p;
new_state.q_enemy[new_state.me.j].pop();
}
}else{
int now_d=2;
if(300<=now_turn) now_d=5;
new_state.point-=now_d;
int sz=new_state.root.size();
if(1<=sz&&new_state.root[sz-1]=='S') new_state.point-=now_d;
if(2<=sz&&((new_state.root[sz-1]=='L'&&new_state.root[sz-2]=='R')||(new_state.root[sz-1]=='R'&&new_state.root[sz-2]=='L'))) new_state.point-=now_d;
}
new_state.me.l=1+new_state.me.s/100;
new_state.me.i--;
rep(j,W){
if(!new_state.q_enemy[j].empty()&&new_state.me.i<new_state.q_enemy[j].front().i){
new_state.point-=new_state.q_enemy[j].front().fh-new_state.q_enemy[j].front().h;
new_state.q_enemy[j].pop();
}
}
if(!new_state.q_enemy[new_state.me.j].empty()&&new_state.me.i==new_state.q_enemy[new_state.me.j].front().i) new_state.point=-1e9;
new_state.turn++;
next_beam.push_back(new_state);
}
}
sort(all(next_beam));
reverse(all(next_beam));
swap(now_beam,next_beam);
next_beam.clear();
}
return now_beam.front().root;
}
void solve(){
int score=0;
shooter me={H+T,12,1,0};
vector<queue<enemy>> q_enemy(W);
string root;
rep(t,T){
me.i--;
rep(j,W){
if(!q_enemy[j].empty()&&me.i<q_enemy[j].front().i) q_enemy[j].pop();
}
if(!q_enemy[me.j].empty()&&me.i==q_enemy[me.j].front().i) assert(0);
Input.input_cin();
rep(i,Input.n){
q_enemy[Input.x[i]].push({me.i-H+1,Input.h[i],Input.h[i],Input.p[i]});
}
state first_state={0,0,q_enemy,me,""};
root=beam_search(t,first_state,10,10);
if(root.empty()){
cout << "S" << endl;
}else{
cout << root.front() << endl;
if(root.front()=='L'){
me.j--;
if(me.j<0) me.j+=W;
}
if(root.front()=='R'){
me.j++;
if(W<=me.j) me.j-=W;
}
}
if(!q_enemy[me.j].empty()&&me.i==q_enemy[me.j].front().i) assert(0);
if(!q_enemy[me.j].empty()&&0<q_enemy[me.j].front().h){
q_enemy[me.j].front().h-=me.l;
if(q_enemy[me.j].front().h<=0){
score+=q_enemy[me.j].front().fh;
me.s+=q_enemy[me.j].front().p;
q_enemy[me.j].pop();
}
}
me.l=1+me.s/100;
}
}
}Solver;
int main(){
Solver.solve();
}