#886592 (C++17) No.5017 Tool-assisted Shooting

• 問題: No.5017 Tool-assisted Shooting
• ユーザー: yunix
• 提出日時: 2023-07-01 14:37:24
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 1,917 ms / 2,000 ms
• コード長: 18,990 bytes
• コンパイル時間: 2,777 ms
• コンパイル使用メモリ: 164,392 KB
• 実行使用メモリ: 26,236 KB
• スコア: 4,420,492
• 平均クエリ数: 1000.00
• 最終ジャッジ日時: 2023-07-16 13:37:53
• 合計ジャッジ時間: 199,602 ms
• ジャッジサーバーID （参考情報）: judge14 / judge15

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1,901 ms; 25,868 KB
testcase_01	AC	1,905 ms; 25,368 KB
testcase_02	AC	1,885 ms; 24,872 KB
testcase_03	AC	1,896 ms; 25,108 KB
testcase_04	AC	1,884 ms; 25,700 KB
testcase_05	AC	1,906 ms; 25,760 KB
testcase_06	AC	1,898 ms; 25,416 KB
testcase_07	AC	1,894 ms; 25,556 KB
testcase_08	AC	1,897 ms; 24,752 KB
testcase_09	AC	1,873 ms; 24,908 KB
testcase_10	AC	1,914 ms; 24,956 KB
testcase_11	AC	1,902 ms; 24,860 KB
testcase_12	AC	1,910 ms; 25,736 KB
testcase_13	AC	1,899 ms; 25,432 KB
testcase_14	AC	1,900 ms; 24,980 KB
testcase_15	AC	1,916 ms; 25,316 KB
testcase_16	AC	1,897 ms; 25,428 KB
testcase_17	AC	1,900 ms; 24,988 KB
testcase_18	AC	1,904 ms; 25,700 KB
testcase_19	AC	1,899 ms; 26,140 KB
testcase_20	AC	1,897 ms; 25,320 KB
testcase_21	AC	1,894 ms; 25,648 KB
testcase_22	AC	1,879 ms; 25,716 KB
testcase_23	AC	1,907 ms; 24,872 KB
testcase_24	AC	1,902 ms; 25,136 KB
testcase_25	AC	1,908 ms; 25,560 KB
testcase_26	AC	1,907 ms; 24,816 KB
testcase_27	AC	1,900 ms; 25,976 KB
testcase_28	AC	1,903 ms; 25,392 KB
testcase_29	AC	1,896 ms; 25,916 KB
testcase_30	AC	1,892 ms; 25,108 KB
testcase_31	AC	1,894 ms; 25,292 KB
testcase_32	AC	1,902 ms; 25,800 KB
testcase_33	AC	1,892 ms; 26,236 KB
testcase_34	AC	1,900 ms; 25,396 KB
testcase_35	AC	1,902 ms; 25,764 KB
testcase_36	AC	1,909 ms; 25,016 KB
testcase_37	AC	1,907 ms; 25,564 KB
testcase_38	AC	1,904 ms; 24,960 KB
testcase_39	AC	1,911 ms; 25,344 KB
testcase_40	AC	1,912 ms; 25,336 KB
testcase_41	AC	1,898 ms; 24,780 KB
testcase_42	AC	1,899 ms; 25,296 KB
testcase_43	AC	1,904 ms; 25,444 KB
testcase_44	AC	1,903 ms; 25,288 KB
testcase_45	AC	1,906 ms; 25,680 KB
testcase_46	AC	1,902 ms; 25,580 KB
testcase_47	AC	1,894 ms; 25,320 KB
testcase_48	AC	1,901 ms; 25,648 KB
testcase_49	AC	1,898 ms; 25,724 KB
testcase_50	AC	1,895 ms; 25,396 KB
testcase_51	AC	1,909 ms; 25,424 KB
testcase_52	AC	1,902 ms; 25,864 KB
testcase_53	AC	1,901 ms; 25,724 KB
testcase_54	AC	1,897 ms; 25,248 KB
testcase_55	AC	1,904 ms; 25,660 KB
testcase_56	AC	1,910 ms; 25,060 KB
testcase_57	AC	1,896 ms; 25,028 KB
testcase_58	AC	1,896 ms; 25,656 KB
testcase_59	AC	1,901 ms; 25,408 KB
testcase_60	AC	1,917 ms; 25,168 KB
testcase_61	AC	1,915 ms; 25,536 KB
testcase_62	AC	1,902 ms; 25,172 KB
testcase_63	AC	1,904 ms; 25,100 KB
testcase_64	AC	1,899 ms; 25,040 KB
testcase_65	AC	1,904 ms; 25,516 KB
testcase_66	AC	1,906 ms; 25,272 KB
testcase_67	AC	1,904 ms; 25,808 KB
testcase_68	AC	1,912 ms; 24,876 KB
testcase_69	AC	1,914 ms; 25,128 KB
testcase_70	AC	1,877 ms; 25,596 KB
testcase_71	AC	1,917 ms; 25,896 KB
testcase_72	AC	1,899 ms; 25,600 KB
testcase_73	AC	1,914 ms; 25,468 KB
testcase_74	AC	1,899 ms; 24,948 KB
testcase_75	AC	1,912 ms; 25,276 KB
testcase_76	AC	1,900 ms; 25,432 KB
testcase_77	AC	1,907 ms; 25,228 KB
testcase_78	AC	1,903 ms; 25,504 KB
testcase_79	AC	1,897 ms; 24,892 KB
testcase_80	AC	1,894 ms; 24,968 KB
testcase_81	AC	1,902 ms; 25,320 KB
testcase_82	AC	1,882 ms; 25,160 KB
testcase_83	AC	1,894 ms; 24,928 KB
testcase_84	AC	1,903 ms; 25,556 KB
testcase_85	AC	1,902 ms; 25,144 KB
testcase_86	AC	1,901 ms; 25,140 KB
testcase_87	AC	1,911 ms; 25,632 KB
testcase_88	AC	1,907 ms; 24,144 KB
testcase_89	AC	1,902 ms; 25,196 KB
testcase_90	AC	1,885 ms; 26,144 KB
testcase_91	AC	1,903 ms; 25,588 KB
testcase_92	AC	1,892 ms; 25,504 KB
testcase_93	AC	1,898 ms; 25,436 KB
testcase_94	AC	1,890 ms; 25,312 KB
testcase_95	AC	1,904 ms; 24,824 KB
testcase_96	AC	1,905 ms; 25,096 KB
testcase_97	AC	1,899 ms; 25,404 KB
testcase_98	AC	1,912 ms; 25,468 KB
testcase_99	AC	1,910 ms; 25,040 KB

コンパイルメッセージ

main.cpp: メンバ関数 ‘char GreedyCommander::check_die(char)’ 内:
main.cpp:491:17: 警告: ‘dx’ may be used uninitialized [-Wmaybe-uninitialized]
  491 |     if (can_move(dx))
      |         ~~~~~~~~^~~~
main.cpp:477:9: 備考: ‘dx’ はここで定義されています
  477 |     int dx;
      |         ^~

ソースコード

#include <iostream>
#include <string>
#include <vector>
#include <tuple>
#include <chrono>
#include <algorithm>
#include <random>
#include <map>
#include <set>
#include <queue>
#include <random>
#include <chrono>
#include <cmath>
#include <climits>
#include <bitset>
#include <time.h>

using namespace std;
using Ps = pair<short, short>;
using vec_int = vector<int>;
using P = pair<int, int>;
using P2 = pair<P, P>;
using P3 = pair<float, int>;
using T = tuple<int, int, int>;
using T2 = tuple<float, int, int>;
using T3 = tuple<float, int, int, int, int>;
using T4 = tuple<int, int, int, int>;
using T5 = tuple<int, int, int, int, int>;
using TT = tuple<int, int, int>;
using ll = long long;
using uc = unsigned char;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

// #pragma GCC optimize("Ofast")

std::mt19937 mt{12345};
int RAND_ARR_LEN = 100000;
int RAND_RANGE = 1000000000;
float TIME_LIMIT = 5000;
float INV_TIME_LIMIT = 1. / 1000.;
const int JOB_MAX_LEN = 1003;
std::uniform_int_distribution<int> dist(1, RAND_RANGE);

int WAITING_TASK = 1001;

void remove_val_and_pop_from_last(vec_int &A, int val)
{
    for (int i = 0; i < A.size(); i++)
    {
        if (A.at(i) == val)
        {
            A.at(i) = A.at(A.size() - 1);
            A.pop_back();
            return;
        }
    }
    throw runtime_error("trying to remove non-existing value");
}

class Rand
{
private:
    int count = 0;
    vec_int rand_arr;

public:
    Rand(){
        rep(i, RAND_ARR_LEN){
            rand_arr.push_back(dist(mt));
}
}
;
int get();
int get_rand(int from, int to);
float get_float();
}
;

int Rand::get()
{
    int num = rand_arr.at(count);
    count += 1;
    count %= RAND_ARR_LEN;
    return num;
}

int Rand::get_rand(int from, int to)
{
    int diff = to - from;
    int num = get() % diff;
    return num + from;
}

float Rand::get_float()
{
    // 0~1の間の一様乱数
    return (float)get() / (float)RAND_RANGE;
}

Rand ro;

class PseudoSet
{
private:
    vec_int index_arr;

public:
    vec_int data;
    PseudoSet(){};
    PseudoSet(int value_range)
    {
        index_arr = vec_int(value_range, -1);
    }

    bool count(int value);
    void insert(int value);
    void erase(int value);
    vec_int get_data() { return data; };
    int size() { return data.size(); };
    int get_random() { return data.at(ro.get_rand(0, size())); };
};

bool PseudoSet::count(int value)
{
    return index_arr[value] != -1;
}

void PseudoSet::insert(int value)
{
    if (count(value))
        return;
    index_arr[value] = data.size();
    data.push_back(value);
}

void PseudoSet::erase(int value)
{
    if (!count(value))
    {
        // throw runtime_error("no existing value:"+to_string(value));
        return;
    }
    int tail_value = data[data.size() - 1];
    if (value == tail_value)
    {
        data.pop_back();
        index_arr[value] = -1;
    }
    else
    {
        index_arr[tail_value] = index_arr[value];
        index_arr[value] = -1;
        data[index_arr[tail_value]] = tail_value;
        data.pop_back();
    }
}

float get_time(bool init)
{
    static std::chrono::system_clock::time_point start;
    if (init)
    {
        start = std::chrono::system_clock::now();
    }
    std::chrono::system_clock::time_point end = std::chrono::system_clock::now();
    return std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count(); // 処理に要した時間をミリ秒に変換
}

double current_tmp(double current_time, double T0, double T1)
{
    return T1 + (T0 - T1) * (TIME_LIMIT * 0.92 - current_time) / (TIME_LIMIT * 0.92);
    // double start_time = TIME_LIMIT * 0.6;
    // double x = (current_time - start_time) / (TIME_LIMIT * 0.32);
    // return pow(T1, 1 - x) + (T0, x);
}

bool is_valid_transition(int diff, double current_time, double T0, float T1)
{
    float t = current_tmp(current_time, T0, T1);
    float rand = ro.get_float();
    // diffが正だったら常にアクセぷと
    return rand < exp(((float)diff) / t);
}

struct Enemy
{
    int max_HP;
    int HP;
    int power;
    int x;
    int y;
};

struct State
{
    int turn;
    int score;
    int earned_power;
    int x;
    vector<char> commands;
    vector<int> steps;
};

struct History
{
    int enemy_index;
    int damage;
    int gained_score;
    int gained_power;
    int x;
};

class Game
{
private:
    vector<History> histories;
    vector<vec_int> poped_enemy;

public:
    int earned_power;
    int turn;
    int score;
    int x_pos;
    vector<deque<int>> enemy_queue;
    Game();
    void move(char command, bool output);
    void attack();
    void pop_enemies(int n);
    void process_turn();
    bool is_game_over();
    bool is_alive(int enemy_index) { return enemies[enemy_index].HP > 0 && turn <= enemies[enemy_index].y; }
    int get_enemy_index(int x);
    vector<Enemy> enemies;

    bool can_kill_enemy(int enemy_ind, int turns);
    void roll_back_a_turn();
    void process_turns(vector<char> &commands);

    State make_state()
    {
        return State{
            turn, score, earned_power, x_pos, vector<char>(), {0}};
    }
};

Game::Game()
{
    turn = 0;
    x_pos = 12;
    earned_power = 0;
    score = 0;
    enemy_queue = vector<deque<int>>(25);
    poped_enemy = vector<vec_int>(1200);
}

void Game::roll_back_a_turn()
{
    turn--;
    History history = histories.at(histories.size() - 1);
    histories.pop_back();
    x_pos = history.x;
    if (history.enemy_index == -1)
        return;

    enemies[history.enemy_index].HP += history.damage;

    if (history.gained_score > 0)
    {
        score -= history.gained_score;
        earned_power -= history.gained_power;
    }
    for (auto enemy_ind : poped_enemy.at(turn))
    {
        int x = enemies[enemy_ind].x;
        enemy_queue.at(x).push_front(enemy_ind);
    }
    poped_enemy.at(turn).clear();
}

void Game::process_turns(vector<char> &commands)
{
    for (auto command : commands)
    {
        move(command, false);
        attack();
        process_turn();
    }
}

void Game::pop_enemies(int n)
{
    vec_int h(n), p(n), x(n);
    rep(i, n) cin >> h.at(i) >> p.at(i) >> x.at(i);

    for (int i = 0; i < n; i++)
    {
        enemies.push_back(Enemy{h.at(i), h.at(i), p.at(i), x.at(i), 59 + turn});
        enemy_queue.at(x.at(i)).push_back(enemies.size() - 1);
    }
}

bool Game::is_game_over()
{
    int enemy_ind = get_enemy_index(x_pos);

    if (enemy_ind == -1)
        return false;
    if (enemies[enemy_ind].y == turn && enemies[enemy_ind].HP > 0)
        return true;

    return false;
}

void Game::move(char command, bool output)
{
    switch (command)
    {
    case 'L':
        x_pos--;
        break;
    case 'R':
        x_pos++;
        break;
    case 'S':
        break;
    default:
        throw runtime_error("invalid command:" + command);
    }
    if (output)
    {
        cout << command << endl;
    }
}

void Game::attack()
{

    int enemy_ind = get_enemy_index(x_pos);
    if (enemy_ind == -1)
    {
        histories.push_back(History{-1, 0, 0, 0, x_pos});
        return;
    }
    // 敵が見つかった
    int my_power = 1 + earned_power / 100;

    // 攻撃
    int damage = min(my_power, enemies.at(enemy_ind).HP);
    enemies.at(enemy_ind).HP -= damage;

    // 敵が死んだ
    if (enemies.at(enemy_ind).HP == 0)
    {
        earned_power += enemies.at(enemy_ind).power;
        my_power += enemies.at(enemy_ind).power;
        score += enemies.at(enemy_ind).max_HP;
        poped_enemy.at(turn).push_back(enemy_queue.at(x_pos).front());
        enemy_queue.at(x_pos).pop_front();
        histories.push_back(History{
            enemy_ind,
            damage,
            enemies.at(enemy_ind).max_HP,
            enemies.at(enemy_ind).power,
            x_pos});
    }
    else
    {
        histories.push_back(History{enemy_ind, damage, 0, 0, x_pos});
    }
}

void Game::process_turn()
{
    turn++;
}

int Game::get_enemy_index(int x)
{
    while (!enemy_queue.at(x).empty())
    {
        int ind = enemy_queue.at(x).front();

        if (enemies.at(ind).y < turn)
        {
            poped_enemy.at(turn).push_back(enemy_queue.at(x).front());
            enemy_queue.at(x).pop_front();
            continue;
        }
        return ind;
    }
    return -1;
}

bool Game::can_kill_enemy(int enemy_ind, int turns)
{
    // 殺すのにturnsかかる
    int diff = enemies[enemy_ind].y - turn - 1;
    return diff > turns;
}

struct GreedyCommander
{
private:
    Game *game;
    int target_enemy;
    int find_target();
    bool will_die();

public:
    GreedyCommander(Game *game) : game(game)
    {
        target_enemy = -1;
    };
    char get_command();
    bool can_move(int dx);
    char check_die(char command);
    void set_target(int target) { target_enemy = target; };
    bool is_target_alive() { return game->is_alive(target_enemy); };
};

int GreedyCommander::find_target()
{
    int x = game->x_pos;
    int current_power = game->earned_power / 100 + 1;
    double best_efficiency = 0;
    double best_enemy = -1;
    for (int i = max(0, x - 8); i <= min(24, x + 8); i++)
    {
        int enemy_ind = game->get_enemy_index(i);
        if (enemy_ind == -1)
            continue;
        int res_HP = game->enemies[enemy_ind].HP;
        int turns = max(abs(x - i) - 1, 0) + res_HP / current_power;
        if (res_HP % current_power != 0)
            turns++;

        if (!game->can_kill_enemy(enemy_ind, turns))
            continue;

        int sc;
        if (game->earned_power / 100 >= 50)
        {
            sc = game->enemies[enemy_ind].max_HP;
        }
        else
        {
            sc = game->enemies[enemy_ind].power;
        }
        double eff = (double)sc / (double)turns;
        if (eff > best_efficiency)
        {
            best_efficiency = eff;
            best_enemy = enemy_ind;
        }
    }
    return best_enemy;
}

bool GreedyCommander::can_move(int dx)
{
    int x = game->x_pos + dx;
    if (x < 0 || x >= 25)
        return false;
    int enemy_index = game->get_enemy_index(x);
    if (enemy_index == -1)
        return true;
    int y = game->enemies[enemy_index].y;
    if (y == game->turn || y == game->turn + 1)
        return false;

    return true;
}

char GreedyCommander::check_die(char command)
{
    int dx;
    switch (command)
    {
    case 'R':
        dx = 1;
        break;
    case 'L':
        dx = -1;
        break;
    case 'S':
        dx = 0;
        break;
    }

    if (can_move(dx))
    {
        return command;
    }
    for (int dx2 = -1; dx2 <= 1; dx2++)
    {
        if (dx2 == dx)
            continue;
        if (can_move(dx2))
        {
            switch (dx2)
            {
            case -1:
                return 'L';
            case 0:
                return 'S';
            case 1:
                return 'R';
            }
        }
    }
    // cerr << "command:" << command << " x:" << game->x_pos << endl;
    int enemy_ind = game->get_enemy_index(game->x_pos + dx);
    // cerr << game->turn << " " << game->enemies[enemy_ind].y << endl;
    // 諦める
    return command;
}

char GreedyCommander::get_command()
{
    if (target_enemy == -1 || !game->is_alive(target_enemy))
    {
        target_enemy = find_target();
    }

    char command;
    if (target_enemy == -1)
    {
        command = 'S';
    }
    else
    {
        int enemy_x = game->enemies[target_enemy].x;
        if (enemy_x == game->x_pos)
        {
            command = 'S';
        }
        else if (enemy_x < game->x_pos)
        {
            command = 'L';
        }
        else
        {
            command = 'R';
        }
    }

    command = check_die(command);
    return command;
}

// 30ターン先までを先読みして10ターン分の行動を決める
class ChokudaiCommander
{
private:
    Game *game;
    queue<char> command_queue;
    void prepare_moves();

public:
    ChokudaiCommander(Game *game) : game(game){};
    char get_command();
    bool can_move(int dx);
    char check_die(char command);
};

void ChokudaiCommander::prepare_moves()
{
    // queueに10ターン分くらいのコマンドを詰める
    // Chokudaiサーチを20ms分やる
    // 状態としてはvector<deque<int>>, スコア, power <- index
    State initial_state = game->make_state();
    int turn0 = initial_state.turn;
    vector<priority_queue<P>> pqs(50);
    vector<deque<int>> enemies = game->enemy_queue;
    vector<State> states;
    states.push_back(initial_state);
    pqs.at(0).emplace(states[0].earned_power, 0);

    float t0 = get_time(false);

    GreedyCommander greedy = GreedyCommander(game);

    int best_state = -1;
    double best_eff = 0;

    int count = 0;
    int turn = game->turn;
    int res_turn = 1000 - turn;
    int res_step = res_turn / 15 + 2;
    float res_time = 1900 - t0;
    float duration = res_time / res_step;

    while (true)
    {
        float ct = get_time(false);
        if (ct - t0 > duration)
            break;

        int flag = 0;
        for (int turn = 0; turn < 30; turn++)
        {
            if (pqs.at(turn).empty())
            {
                continue;
            }
            flag = 1;
            auto [score, state_ind] = pqs.at(turn).top();
            pqs.at(turn).pop();
            game->process_turns(states[state_ind].commands);

            vector<deque<int>> enemies2 = game->enemy_queue;
            int x = game->x_pos;
            int current_power = game->earned_power / 100 + 1;
            for (int i = max(0, x - 8); i <= min(24, x + 8); i++)
            {
                int enemy_ind = game->get_enemy_index(i);
                if (enemy_ind == -1)
                    continue;

                int res_HP = game->enemies[enemy_ind].HP;
                int turns = max(abs(x - i) - 1, 0) + res_HP / current_power;
                if (res_HP % current_power != 0)
                    turns++;
                if (!game->can_kill_enemy(enemy_ind, turns))
                    continue;

                greedy.set_target(enemy_ind);
                // cerr << "enemy:" << enemy_ind << " turn:" << turn << " alive:" << greedy.is_target_alive() << " target x:" << game->enemies[enemy_ind].x << " turns:" << turns << endl;
                int turn_count = turn;
                vector<char> commands = vector<char>(states[state_ind].commands);
                bool game_over = false;
                int initial_x = game->x_pos;
                while (true)
                {
                    if (!greedy.is_target_alive())
                        break;
                    char command = greedy.get_command();
                    // cerr << "command:" << command << " hp:" << game->enemies[enemy_ind].HP << endl;
                    commands.push_back(command);
                    game->move(command, false);
                    if (game->is_game_over())
                    {
                        game_over = true;
                    }
                    game->attack();
                    game->process_turn();
                    turn_count++;
                    if (game->is_game_over() || game_over)
                    {
                        game_over = true;
                        break;
                    }
                }
                // cerr << "turn:" << turn_count << " gameover?" << game_over << endl;
                State next_state = game->make_state();
                next_state.steps = states[state_ind].steps;
                next_state.steps.push_back(turn_count);
                rep(i, turn_count - turn)
                {
                    game->roll_back_a_turn();
                }
                game->x_pos = initial_x;
                game->enemy_queue = enemies2;

                if (game_over)
                    continue;
                if (turn_count >= 50)
                    continue;
                // cerr << "next_state turn:" << turn_count << endl;
                next_state.commands = commands;
                states.push_back(next_state);
                int score;
                if (initial_state.earned_power / 100 > 50)
                {
                    score = next_state.score - initial_state.score;
                }
                else
                {
                    score = next_state.earned_power - initial_state.earned_power;
                }

                if (best_eff < (double)score / (double)turn_count && turn_count >= 10)
                {
                    best_eff = (double)score / (double)turn_count;
                    best_state = states.size() - 1;
                }
                pqs.at(turn_count).emplace(score, states.size() - 1);
                // cerr << "end:" << turn << " " << turn_count << endl;
            }
            rep(i, turn)
            {
                game->roll_back_a_turn();
            }
            game->x_pos = initial_state.x;
            game->enemy_queue = enemies;
        }
        count++;
        if (flag == 0)
        {
            break;
        }
    }

    // 30ターンよりも先を調べて、最もearned_powerの効率がよかったやつを採用する
    // cerr << "turn:" << game->turn << " "
    //     << "count:" << count << " best_state:" << best_state << " best_eff:" << best_eff << endl;
    if (best_state == -1)
    {
        command_queue.push('S');
    }
    else
    {
        int count = 0;
        for (auto tmp : states[best_state].steps)
        {
            count = tmp;
            if (count > 15)
                break;
        }
        for (int i = 0; i < count && i < states[best_state].commands.size(); i++)
        {
            command_queue.push(states[best_state].commands.at(i));
        }
    }
}

char ChokudaiCommander::get_command()
{
    if (command_queue.empty())
    {
        prepare_moves();
    }
    char result = command_queue.front();
    command_queue.pop();
    return result;
}

double T0 = 500.;
double T1 = 0;

int main(int argc, char *argv[])
{
#ifdef LOCAL
    vec_int pp;
    rep(i, 25)
    {
        int val;
        cin >> val;
        pp.push_back(val);
    }
#endif
#ifdef OPTUNA_STUDY
    cerr << "optuna study, override parameters" << endl;
    T0 = stod(argv[1]);
    T1 = stod(argv[2]);
#endif
    get_time(true);

    Game game = Game();
    ChokudaiCommander commander = ChokudaiCommander(&game);
    // GreedyCommander commander = GreedyCommander(&game);

    rep(i, 1000)
    {
        game.process_turn();
        if (game.is_game_over())
            break;
        int n;
        cin >> n;
        if (n == -1)
            break;
        game.pop_enemies(n);
        char command = commander.get_command();
        game.move(command, true);
        // cerr << i << " " << game.turn << " " << game.x_pos << endl;
        if (game.is_game_over())
            break;
        game.attack();
    }
    cerr << " time: " << get_time(false) << " turn:" << game.turn << " power:" << game.earned_power << " score:" << game.score << endl;
    return 0;
}