結果
| 問題 | No.5017 Tool-assisted Shooting |
| コンテスト | |
| ユーザー |
 かえで
|
| 提出日時 | 2023-07-23 08:21:29 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.89.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 8,832 bytes |
| 記録 | |
| コンパイル時間 | 1,726 ms |
| コンパイル使用メモリ | 127,020 KB |
| 実行使用メモリ | 35,168 KB |
| スコア | 711 |
| 平均クエリ数 | 3835.10 |
| 最終ジャッジ日時 | 2023-07-23 08:21:42 |
| 合計ジャッジ時間 | 12,122 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge11 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 6 TLE * 1 -- * 93 |
ソースコード
// Copyright [2022] <Copyright Eita Aoki (Thunder) >
// どこが間違っているのかわからず。いったん中止
#include <string>
#include <sstream>
#include <random>
#include <iostream>
#include <queue>
#include <chrono>
using namespace std;
#define ll long long
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
// 時間を管理するクラス
class TimeKeeper
{
private:
chrono::high_resolution_clock::time_point start_time_;
int64_t time_threshold_;
public:
// 時間制限をミリ秒単位で指定してインスタンスをつくる。
TimeKeeper(const int64_t &time_threshold)
: start_time_(chrono::high_resolution_clock::now()),
time_threshold_(time_threshold)
{
}
// インスタンス生成した時から指定した時間制限を超過したか判定する。
bool isTimeOver() const
{
auto diff = chrono::high_resolution_clock::now() - this->start_time_;
return chrono::duration_cast<chrono::milliseconds>(diff).count() >= time_threshold_;
}
};
mt19937 mt_for_action(0); // 行動選択用の乱数生成器を初期化
using ScoreType = int64_t; // ゲームの評価スコアの型を決めておく。
constexpr const ScoreType INF = 1000000000LL; // あり得ないぐらい大きなスコアの例を用意しておく
constexpr const int T = 1000;
constexpr const int DY[4] = {0, 0, 1, -1}; // 右、左、下、上への移動方向のy成分
constexpr const int DX[4] = {1, -1, 0, 0}; // 右、左、下、上への移動方向のx成分
constexpr const char DC[4] = {'R', 'L', 'D', 'U'};
constexpr int width = 25; // フィールドの幅
constexpr int height = 60; // フィールドの高さ
constexpr int max_turn = 1000; // ゲームの最大ターン数
const char choice[3] = {'L', 'R', 'S'};
//敵機情報
struct Data {
int h;
int p;
int x;
int y;
Data(int h, int p, int x, int y) : h(h), p(p), x(x), y(y) {}
};
vector<Data> data_moto[25];
class State
{
private:
public:
ScoreType evaluated_score_ = 0; // 探索上で評価したスコア
int score_=0;
int first_action_ = -1; // 探索木のルートノードで最初に選択した行動
int sx=12;
int turn_ = 0; // 現在のターン
int power=0;
int kogeki=1;
vector<Data> data[25];
int lane[25];
State() {}
// ゲームの終了判定
bool isDone() const
{
/*処理*/
return this->turn_ == T;
//return /*(bool)終了判定*/;
}
// 探索用の盤面評価をする
void evaluateScore()
{
int res=0;
int min_i=-1;
int sho=1000;
//kogeki=1;
rep(i,25){
if (lane[i]==-1)continue;
if(lane[i]+1>data[i].size())continue;
Data z=data[i][lane[i]];
if(z.h==0)continue;
kogeki=1+(power/100);
if(kogeki<=0)kogeki=1;
//cerr<<__LINE__<<"---"<<kogeki<<endl;
//cerr<<z.h<<" "<<kogeki<<endl;
int tmp=z.y-(int)((z.h+kogeki-1)/kogeki)-abs(sx-z.x)-1;
double evaluated_score=(double)z.h/(double)z.p;
if(tmp>1&&sho>abs(sx-z.x)+evaluated_score&&z.y!=-1&&z.x!=-1&&z.h>0){
min_i=z.x;
sho=abs(sx-z.x)+evaluated_score;
res=tmp;
}
}
this->evaluated_score_ = res+score_;
cout<<"#res"<<res<<" score"<<score_<<endl;
//this->evaluated_score_ = /*(ScoreType)評価結果*/;
}
// 指定したactionでゲームを1ターン進める
void advance(const int action)
{
if(action==0){//L
sx++;
if(sx==25)sx=0;
}else if (action==1){//R
sx--;
if(sx==-1)sx=24;
}else{//S stay
}
rep(i,25){
if (lane[i]==-1)continue;
int size=data[i].size();
rep(j,size){
Data& z=data[i][j];//
if(z.y!=-1)z.y=z.y-1;
if(lane[i]==j&&z.y<0)lane[i]==j+1;
}
}
if(turn_==1)cerr<<__LINE__<<"---turn_"<<turn_<<"sx"<<sx<<" lane[sx]"<<lane[sx]<<" "<<data[sx].size()<<endl;
if (lane[sx]!=-1&&lane[sx]+1<=data[sx].size()) {
Data z=data[sx][lane[sx]];
z.h-=kogeki;
if(z.h<=0){
power+=z.p;
kogeki=1+(power/100);
lane[sx]++;
score_+=data_moto[sx][lane[sx]].h;
}
cout<<"#now x:"<<sx<<" h"<<z.h<<endl;
}
cout<<"#sx:"<<sx<<" score"<<score_<<"power:"<<power<<" kogeki:"<<kogeki<<endl;
++this->turn_;
}
// 現在の状況でプレイヤーが可能な行動を全て取得する
vector<int> legalActions() const
{
vector<int> actions;
/*処理*/
for (int action = 0; action < 3; action++)
{
int nx=sx;
if(action==0)nx++;
else if(action==1)nx--;
bool can_action = true;
rep(i,25){
int z=data[i].size();
if(z!=0){
rep(j,z){
auto q=data[i][j];
if(q.x!=nx)continue;
if(q.y==1)can_action=false;
if(q.y==0)can_action=false;
}
}
}
if (can_action)
{
actions.emplace_back(action);
}
}
cout<<"#legal action size:"<<actions.size()<<endl;
return actions;
}
};
// 探索時のソート用に評価を比較する
bool operator<(const State &state_1, const State &state_2)
{
return state_1.evaluated_score_ < state_2.evaluated_score_;
}
// ビーム幅と制限時間(ms)を指定してビームサーチで行動を決定する
int beamSearchActionWithTimeThreshold(
//vector<int> beamSearchActionWithTimeThreshold(
const State &state,
const int beam_width,
const int64_t time_threshold)
{
auto time_keeper = TimeKeeper(time_threshold);
auto legal_actions = state.legalActions();
priority_queue<State> now_beam;
State best_state;
now_beam.push(state);
for (int t = 0;; t++)
{
priority_queue<State> next_beam;
for (int i = 0; i < beam_width; i++)
{
if (time_keeper.isTimeOver())
{
//return best_state.actions_;
return best_state.first_action_;
}
if (now_beam.empty())
break;
State now_state = now_beam.top();
now_beam.pop();
auto legal_actions = now_state.legalActions();
for (const auto &action : legal_actions)
{
State next_state = now_state;
next_state.advance(action);
next_state.evaluateScore();
if (t == 0)
next_state.first_action_ = action;
//next_state.actions_.emplace_back(action);//
next_beam.push(next_state);
}
}
now_beam = next_beam;
best_state = now_beam.top();
if (best_state.isDone())
{
break;
}
}
//return best_state.actions_;
return best_state.first_action_;
}
int main()
{
#ifdef ONLINE_JUDGE
#else
//読み飛ばし
//rep(i,25){
// int nx;
// cin>>nx;
//}
#endif
State state;
for (int turn = 1; turn <= max_turn; turn++) {
/********************************************************************/
// 1. 入力を読み取る
int n;
cin >> n;
if (n == -1)return 0;
for (int i = 0; i < n; i++) {
int h1, p1, x1;
cin >> h1 >> p1 >> x1;
state.data[x1].emplace_back(h1, p1, x1, 59);
data_moto[x1].emplace_back(h1, p1, x1, 59);
if(state.lane[x1]==-1)state.lane[x1]=0;
}
/********************************************************************/
// 2.ビームサーチで探索する
//int action=beamSearchActionWithTimeThreshold(state, 64, 3);//幅64、3msec
int action=beamSearchActionWithTimeThreshold(state, 1, 3);//幅64、3msec
if(action==0){//L
state.sx++;
if(state.sx==25)state.sx=0;
}else if (action==1){//R
state.sx--;
if(state.sx==-1)state.sx=24;
}else{//S stay
}
/********************************************************************/
// 3.探索結果の行動を出力する
cout<<choice[action]<<endl;
}
return 0;
}