//------------------------------------------------------------------------------ /// @file /// @author ハル研究所プログラミングコンテスト実行委員会 /// /// @copyright (C)HAL Laboratory, Inc. /// @attention このファイルの利用は、同梱のREADMEにある /// 利用条件に従ってください。 //------------------------------------------------------------------------------ /* 概要: 1. 初期地点と各巻物の座標からダイクストラ法をして雑に巻物間ターン数を見積もる (16 秒) 2. 見積もったターン数を使って、巻物を回収する順番を巡回セールスマン問題の要領で計算 (8 秒) 3. 順番に従って、A* 探索で最終的な経路を決定 (35 秒) ダイクストラ法と A* 探索では、現在地点から直進して辿り着ける場所を隣接ノードとして扱う */ #include <cmath> #include <array> #include <queue> #include <vector> #include <chrono> #include <numeric> #include <iostream> #include <algorithm> #include "Answer.hpp" //#define PRINT_DEBUG using namespace std; //------------------------------------------------------------------------------ namespace hpc { // >>> ユーティリティ >>> template<class T> void print_2d_array(const T& arr) { #ifdef PRINT_DEBUG for (const auto& ar : arr) { for (const auto& a : ar) { cerr << a << " "; } cerr << "\n" << endl; } #endif } using Meter = short; using RegionId = short; using AreaId = short; using Angle = int; using PosId = int; template<typename T> inline bool neq(const T& a, const T& b) { if (sizeof(T) == sizeof(double)) { return *(long long*)&a != *(long long*)&b; } else { return a != b; } } template<typename T> inline bool eq(const T& a, const T& b) { if (sizeof(T) == sizeof(double)) { return *(long long*)&a == *(long long*)&b; } else { return a == b; } } template<typename T> struct Vec2 { T x, y; constexpr Vec2() {} constexpr Vec2(const T& aX, const T& aY) : x(aX), y(aY) {} constexpr Vec2(const Vector2& v) : x(v.x), y(v.y) {} template<typename S> constexpr Vec2(const Vec2<S>& v) : x((T)v.x), y((T)v.y) {} inline Vec2 operator+(const Vec2& rhs) const { return Vec2(x + rhs.x, y + rhs.y); } inline Vec2 operator+(const T& rhs) const { return Vec2(x + rhs, y + rhs); } inline Vec2 operator-(const Vec2& rhs) const { return Vec2(x - rhs.x, y - rhs.y); } template<typename S> inline Vec2 operator*(const S& rhs) const { return Vec2(x * rhs, y * rhs); } inline Vec2& operator+=(const Vec2& rhs) { x += rhs.x; y += rhs.y; return *this; } inline bool operator!=(const Vec2& rhs) const { if (sizeof(x) == sizeof(double)) { return neq(x, rhs.x) || neq(y, rhs.y); } else { return x != rhs.x || y != rhs.y; } } inline bool operator==(const Vec2& rhs) const { if (sizeof(x) == sizeof(double)) { return eq(x, rhs.x) && eq(y, rhs.y); } else { return x == rhs.x && y == rhs.y; } } inline operator Vector2() const { return Vector2((float)x, (float)y); } inline double l2_norm() const { return sqrt(x * x + y * y); } inline double l2_norm_square() const { return x * x + y * y; } }; template<typename T, typename S> inline Vec2<T> operator*(const S& lhs, const Vec2<T>& rhs) { return rhs * lhs; } template<typename T> ostream& operator<<(ostream& os, const Vec2<T>& vec) { os << vec.y << ' ' << vec.x; return os; } struct Rectangle { Meter d, r, u, l; Rectangle(const Meter& D, const Meter& R, const Meter& U, const Meter& L) : d(D), r(R), u(U), l(L) {} }; // >>> 定数 >>> constexpr double PI = 3.141592653589793; constexpr array<Vec2<int>, 4> Dxy{ Vec2<int>{ 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } }; // DRUL constexpr double EPS = 1e-3; constexpr int DIVISION_SIZE = 1; constexpr double EPS_TERRAIN_COEF = 1e-8; constexpr array<double, 4> TERRAIN_COEF = { 1.0 - EPS_TERRAIN_COEF, 0.6 - EPS_TERRAIN_COEF, 0.3 - EPS_TERRAIN_COEF, 0.1 - EPS_TERRAIN_COEF }; using AStarPosId = int; constexpr int A_STAR_DIVISION_SIZE = 5; constexpr AStarPosId A_STAR_N_INTERMEDIATE = 50 * 50 * A_STAR_DIVISION_SIZE * A_STAR_DIVISION_SIZE; constexpr AStarPosId A_STAR_N_Y_INT = 50 * 50 * A_STAR_DIVISION_SIZE; constexpr AStarPosId A_STAR_N_NORMAL = A_STAR_N_INTERMEDIATE + A_STAR_N_Y_INT * 2; constexpr AStarPosId A_STAR_N_STARTS = 250; // <<< 定数 <<< // >>> ステージ情報等 >>> double T0; int stage_num; int n_scrolls; array<Vec2<Meter>, 20> scroll_poses; Meter scroll_distance[20][20]; Meter scroll_distance_from_start[20]; array<array<RegionId, 50>, 50> region_ids; // 座標 -> 連結成分の ID vector<Terrain> region_terrains; // 連結成分の ID -> 地形 array<array<RegionId, 50>, 50> area_ids; // 座標 -> 長方形の ID vector<Rectangle> area_rectangles; // 長方形 ID -> DRUL // <<< ステージ情報等 <<< // 時間 inline double time() { return static_cast<double>(chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now().time_since_epoch()).count()) / 1000000000.0; } // 整数判定 inline bool is_integer(const double& x) { return eq((double)x, (double)(int)x); } // sin, cos の前計算 array<double, 8192> sin_table, cos_table; void init_sin_cos_table() { constexpr double eps = 1e-4; sin_table[0] = sin(0.0 + eps); cos_table[0] = cos(0.0 + eps); for (int base = 1; base < (int)sin_table.size(); base <<= 1) { for (int i = 0; i < base; i++) { sin_table[base + i] = sin(2 * PI * ((double)i + 0.5) / base + eps); cos_table[base + i] = cos(2 * PI * ((double)i + 0.5) / base + eps); } } } // 2 次元 array をひとつの値で埋める関数 template<class T, size_t s1, size_t s2> inline void fill_2d_array(array<array<T, s2>, s1>& arr, const T& val) { fill((T*)arr.data(), (T*)(arr.data() + arr.size()), val); } // <<< ユーティリティ <<< // >>> 関数いろいろ >>> // まっすぐ進んで地形の境界をまたぐ場所を取得する関数 Vec2<double> go_straight(const Vec2<double>& pos, const Angle& angle, const RegionId& region_id) { // 境界を伝う場合は無理なので別途処理 // 遅い地形から出るときはすぐ止まる const Vec2<double> e(cos_table[angle], sin_table[angle]); // 移動方向への単位ベクトル const Vec2<double> e_inv(1.0 / e.x, 1.0 / e.y); const int x_direction = e.x > 0.0 ? 1 : -1; const int y_direction = e.y > 0.0 ? 1 : -1; Vec2<double> p = pos; // 現在地点 Vec2<int> int_p((int)p.x, (int)p.y); // すぐ止まる場合 if (is_integer(pos.y)) { if (y_direction == 1) { if (region_id != region_ids[int_p.y][int_p.x]) return pos; } else { if (region_id != region_ids[int_p.y - 1][int_p.x]) return pos; } } if (is_integer(pos.x)) { if (x_direction == 1) { if (region_id != region_ids[int_p.y][int_p.x]) return pos; } else { if (region_id != region_ids[int_p.y][int_p.x - 1]) return pos; } } AreaId area_id = area_ids[int_p.y][int_p.x]; Vec2<Meter> next(e.x > 0.0 ? area_rectangles[area_id].r : area_rectangles[area_id].l, e.y > 0.0 ? area_rectangles[area_id].d : area_rectangles[area_id].u); bool over_x = false; // 境界の x 軸を越えて止まったかどうか while (true) { // 方向に従って進む double dist_y = ((double)next.y - p.y) * e_inv.y; double dist_x = ((double)next.x - p.x) * e_inv.x; if (dist_y < dist_x) { // 縦に超えた場合 over_x = false; p += (dist_y + 1e-4) * e; } else { // 横に越えた場合 over_x = true; p += (dist_x + 1e-4) * e; } int_p = Vec2<int>(p); if (p.y < 0.0) int_p.y = -1; // キャストしたときに -0.5 が 0 になってしまうのを補正 if (p.x < 0.0) int_p.x = -1; if (y_direction == 1) { if (int_p.y == 50) break; } else { if (int_p.y == -1) break; } if (x_direction == 1) { if (int_p.x == 50) break; } else { if (int_p.x == -1) break; } area_id = area_ids[int_p.y][int_p.x]; next = Vec2<Meter>(x_direction > 0.0 ? area_rectangles[area_id].r : area_rectangles[area_id].l, y_direction > 0.0 ? area_rectangles[area_id].d : area_rectangles[area_id].u); if (region_ids[int_p.y][int_p.x] != region_id) { // 進んだ先が領域外(・進む前は領域内) break; } } // end while p += -(1e-4) * e; if (over_x) { if (x_direction == 1) { //HPC_ASSERT(abs(p.x - (double)int_p.x) < EPS); p.x = (double)int_p.x; } else { //HPC_ASSERT(abs(p.x - (double)int_p.x - 1.0) < EPS); p.x = (double)int_p.x + 1.0; } } else { if (y_direction == 1) { //HPC_ASSERT(abs(p.y - (double)int_p.y) < EPS); p.y = (double)int_p.y; } else { //HPC_ASSERT(abs(p.y - (double)int_p.y - 1.0) < EPS); p.y = (double)int_p.y + 1.0; } } //HPC_ASSERT(0.0 <= p.x && p.x <= 50.0 && 0.0 <= p.y && p.y <= 50.0); return p; } template<class T, int max_size> struct Queue { array<T, max_size> data; int left, right; Queue() : data(), left(0), right(0) {} inline bool empty() const { return left == right; } inline void push(const T& value) { data[right] = value; right++; } inline void pop() { left++; } inline T front() const { return data[left]; } template <class... Args> inline void emplace(const Args&... args) { data[right] = T(args...); right++; } inline void clear() { left = 0; right = 0; } }; Queue<pair< pair<Angle, Vec2<double>>, pair<Angle, Vec2<double>> >, 4096> q_boundary; inline int ceil_int(const double& val) { int int_val = (int)val; return val == (double)int_val ? int_val : ++int_val; } // まっすぐ進んで行ける場所を取得 template<bool start_y_boundary, bool start_x_boundary, bool a_star> vector<pair<Meter, Vec2<double>>> _get_boudary(Vec2<double> pos, const RegionId& region_id, const double& jump_power) { constexpr int angle_limit = a_star ? 256 : 128; constexpr int force_angle_max = a_star ? 64 : 8; constexpr int division_size = a_star ? A_STAR_DIVISION_SIZE : DIVISION_SIZE; vector<pair<Meter, Vec2<double>>> res; res.reserve(300); q_boundary.clear(); Vec2<int> int_pos((int)pos.x, (int)pos.y); const Terrain& terrain = region_terrains[region_id]; double jump_dist = jump_power * TERRAIN_COEF[(int)terrain]; RegionId outer_region_id; double outer_jump_dist; // 境界に沿って進む if (start_y_boundary || start_x_boundary) { if (start_y_boundary) { if (start_x_boundary) return res; // 格子点は面倒なので // 実はそんなに面倒じゃないかも //HPC_ASSERT((region_id == region_ids[int_pos.y][int_pos.x]) || (region_id == region_ids[int_pos.y - 1][int_pos.x])); if (region_id != region_ids[int_pos.y][int_pos.x]) outer_region_id = region_ids[int_pos.y][int_pos.x]; else outer_region_id = region_ids[int_pos.y - 1][int_pos.x]; outer_jump_dist = jump_power * TERRAIN_COEF[(int)region_terrains[outer_region_id]]; for (int i = 0; (double)i / (double)DIVISION_SIZE < outer_jump_dist; i++) { // 敢えて DIVISION_SIZE にしてる Vec2<double> p = Vec2<double>(pos.x + (outer_jump_dist - (double)i / (double)DIVISION_SIZE), pos.y); if (0.5 <= p.x && p.x <= 49.5 && region_ids[int_pos.y][(int)p.x] != region_ids[int_pos.y - 1][(int)p.x]) { res.emplace_back(1, p); } p = Vec2<double>(pos.x - (outer_jump_dist - (double)i / (double)DIVISION_SIZE), pos.y); if (0.5 <= p.x && p.x <= 49.5 && region_ids[int_pos.y][(int)p.x] != region_ids[int_pos.y - 1][(int)p.x]) { res.emplace_back(1, p); } } } else { //HPC_ASSERT((region_id == region_ids[int_pos.y][int_pos.x]) || (region_id == region_ids[int_pos.y][int_pos.x - 1])); if (region_id != region_ids[int_pos.y][int_pos.x]) outer_region_id = region_ids[int_pos.y][int_pos.x]; else outer_region_id = region_ids[int_pos.y][int_pos.x - 1]; outer_jump_dist = jump_power * TERRAIN_COEF[(int)region_terrains[outer_region_id]]; for (int i = 0; (double)i / (double)DIVISION_SIZE < outer_jump_dist; i++) { Vec2<double> p = Vec2<double>(pos.x, pos.y + (outer_jump_dist - (double)i / (double)DIVISION_SIZE)); if (0.5 <= p.y && p.y <= 49.5 && region_ids[(int)p.y][int_pos.x] != region_ids[(int)p.y][int_pos.x - 1]) { res.emplace_back(1, p); } p = Vec2<double>(pos.x, pos.y - (outer_jump_dist - (double)i / (double)DIVISION_SIZE)); if (0.5 <= p.y && p.y <= 49.5 && region_ids[(int)p.y][int_pos.x] != region_ids[(int)p.y][int_pos.x - 1]) { res.emplace_back(1, p); } } } //HPC_ASSERT(jump_dist <= outer_jump_dist); } // angle == 0 のときは面倒なので省略 { // const auto p = go_straight(pos, 0, region_id); // これやると後が面倒 q_boundary.emplace(make_pair(0, Vec2<double>(99.9, 99.9)), make_pair(0, Vec2<double>(99.9, 99.9))); } while (!q_boundary.empty()) { const auto v = q_boundary.front(); q_boundary.pop(); const auto& left = v.first; const auto& right = v.second; const Angle angle = left.first >= right.first ? left.first * 2 + 1 : right.first * 2; // 中央の方角 const Vec2<double> e(cos_table[angle], sin_table[angle]); // 移動方向への単位ベクトル Vec2<double> p; if ((left.second - right.second).l2_norm_square() > 1.0 || angle < 4) { // > 1.0 なら確実 p = go_straight(pos, angle, region_id); } else { // 左右の間隔が狭いとき、処理省略 if (is_integer(left.second.x) && is_integer(right.second.x)) { p = Vec2<double>(left.second.x, pos.y + e.y * (left.second.x - pos.x) / e.x); } else if (is_integer(left.second.y) && is_integer(right.second.y)) { p = Vec2<double>(pos.x + e.x * (left.second.y - pos.y) / e.y, left.second.y); } else { p = go_straight(pos, angle, region_id); } } if (!start_x_boundary && !start_y_boundary) { //HPC_ASSERT(neq(p, pos)); // ほんまか? } if (neq(p, pos) && p.x >= 0.5 && p.x <= 49.5 && p.y >= 0.5 && p.y <= 49.5) { // フィールドの端でない場合 // ふちで止まる場合 double dist = (p - pos).l2_norm(); int n_jumps; if (!start_x_boundary && !start_y_boundary) { n_jumps = (int)ceil(dist / jump_dist); // なんか遅い? } else { if (outer_jump_dist >= dist) n_jumps = 1; else n_jumps = 1 + (int)ceil((dist - outer_jump_dist) / jump_dist); } res.emplace_back(n_jumps, p); // ふちで止まらない場合: 再遠点 // 速 -> 遅 の場合は省略 Vec2<double> top; if (!start_x_boundary && !start_y_boundary) { top = pos + (double)n_jumps * jump_dist * e; } else { top = pos + (outer_jump_dist + (double)(n_jumps - 1) * jump_dist) * e; } if (0.5 <= top.x && top.x <= 49.5 && 0.5 <= top.y && top.y <= 49.5 && (int)region_terrains[region_ids[(int)top.y][(int)top.x]] <= (int)terrain ) { res.emplace_back(n_jumps, top); } // ふちで止まらない場合: ふちの先の別の境界 for (double y = floor(min(p.y, top.y)) + 1.0; y < max(p.y, top.y); y++) { //HPC_ASSERT(is_integer(y)); double x = pos.x + e.x * (y - pos.y) / e.y; // y 軸を越えないとこの行に到達し得ないので e.y != 0.0 if (0.5 <= x && x <= 49.5 && 0.5 <= y && y <= 49.5) { if (region_terrains[region_ids[(int)y][(int)x]] != region_terrains[region_ids[(int)y - 1][(int)x]]) { res.emplace_back(n_jumps, Vec2<double>(x, y)); //HPC_ASSERT((Vec2<double>(x, y) - pos).l2_norm() < n_jumps * jump_power * 1.01); } } } for (double x = floor(min(p.x, top.x)) + 1.0; x < max(p.x, top.x); x++) { //HPC_ASSERT(is_integer(x)); double y = pos.y + e.y * (x - pos.x) / e.x; // x 軸を越えないとこの行に到達し得ないので e.x != 0.0 if (0.5 <= x && x <= 49.5 && 0.5 <= y && y <= 49.5) { if (region_terrains[region_ids[(int)y][(int)x]] != region_terrains[region_ids[(int)y][(int)x - 1]]) { res.emplace_back(n_jumps, Vec2<double>(x, y)); //HPC_ASSERT((Vec2<double>(x, y) - pos).l2_norm() < n_jumps * jump_power * 1.01); } } } } if (angle < angle_limit) { if (angle < force_angle_max || (left.second - p).l2_norm_square() > 1.0 / (double)DIVISION_SIZE) { q_boundary.emplace(left, make_pair(angle, p)); } if (angle < force_angle_max || (right.second - p).l2_norm_square() > 1.0 / (double)DIVISION_SIZE) { q_boundary.emplace(make_pair(angle, p), right); } } } return res; } // 今いる地点から直進して到達できる箇所を取得する関数 template<bool a_star> vector<pair<Meter, Vec2<double>>> get_boudary(Vec2<double> pos, const RegionId& region_id, const double& jump_power) { bool x_is_integer = is_integer(pos.x); bool y_is_integer = is_integer(pos.y); vector<pair<Meter, Vec2<double>>> res; if (y_is_integer) { res = _get_boudary<true, false, a_star>(pos, region_id, jump_power); } else if (x_is_integer) { res = _get_boudary<false, true, a_star>(pos, region_id, jump_power); } else { res = _get_boudary<false, false, a_star>(pos, region_id, jump_power); } return res; } // region_ids 等の初期化 void init_region(const Stage& aStage) { // >>> 地形の連結成分を調べて region_ids を埋める >>> fill_2d_array(region_ids, (RegionId)-1); region_terrains.clear(); RegionId region_id = 0; for (int i = 0; i < n_scrolls; i++) { // 巻物がある場所はそのタイル単体でひとつの region とする const Vec2<Meter>& pos = scroll_poses[i]; region_ids[pos.y][pos.x] = region_id; const Terrain& terrain = aStage.terrain(Vector2(pos.x, pos.y)); region_terrains.push_back(terrain); region_id++; } auto oof = [&](const Vec2<int>& tile) { // フィールド外かどうか return tile.x < 0 || 50 <= tile.x || tile.y < 0 || 50 <= tile.y; }; for (int y = 0; y < 50; y++) { // 地形が同じ隣接した区画を region としてまとめる for (int x = 0; x < 50; x++) { if (region_ids[y][x] != -1) continue; const Terrain& terrain = aStage.terrain(Vector2((float)x, (float)y)); region_terrains.push_back(terrain); deque<Vec2<int>> q; q.emplace_back(x, y); region_ids[y][x] = region_id; while (!q.empty()) { const Vec2<int> v = q.front(); q.pop_front(); for (const Vec2<int>& dxy : Dxy) { const Vec2<int> u = v + dxy; if (!oof(u) && region_ids[u.y][u.x] == -1 && terrain == aStage.terrain(Vector2((float)u.x, (float)u.y))) { region_ids[u.y][u.x] = region_id; q.push_back(u); } } } region_id++; } } // <<< 地形の連結成分を調べて region_ids を埋める <<< // >>> region を長方形に分割して area にする >>> fill_2d_array(area_ids, (AreaId)-1); area_rectangles.clear(); AreaId area_id = 0; // 貪欲に長方形を作る for (int y = 0; y < 50; y++) { for (int x = 0; x < 50; x++) { if (area_ids[y][x] != -1) continue; area_ids[y][x] = area_id; RegionId reg_id = region_ids[y][x]; int r = x + 1; for (; r < 50; r++) { if (region_ids[y][r] != reg_id || area_ids[y][r] != -1) break; area_ids[y][r] = area_id; } int d = y + 1; for (; d < 50; d++) { for (int ux = x; ux < r; ux++) { if (region_ids[d][ux] != reg_id) goto brbr; } for (int ux = x; ux < r; ux++) { area_ids[d][ux] = area_id; } } brbr: area_rectangles.emplace_back(d, r, y, x); area_id++; } } // <<< region を長方形に分割して area にする <<< } int temporarily_removed_scroll = 0; // 一時的に巻物を取り除いたとして region_ids を修正する void modify_region(const Vec2<double>& aPos) { const Vec2<Meter> pos(aPos); const int idx_scrolls = region_ids[pos.y][pos.x]; if (idx_scrolls >= n_scrolls) return; // 巻物が無い場所なら何もしない temporarily_removed_scroll = idx_scrolls; auto oof = [&](const Vec2<int>& tile) { // フィールド外かどうか return tile.x < 0 || 50 <= tile.x || tile.y < 0 || 50 <= tile.y; }; for (const Vec2<int>& dxy : Dxy) { const Vec2<int> p = pos + dxy; if (!oof(p) && region_ids[p.y][p.x] >= n_scrolls && region_terrains[region_ids[p.y][p.x]] == region_terrains[region_ids[pos.y][pos.x]]) { // 隣接タイルが巻物でなく、自分と同じ地形なら region_ids[pos.y][pos.x] = region_ids[p.y][p.x]; return; } } } // 修正を元に戻す void undo_modify_region() { const Vec2<Meter>& pos = scroll_poses[temporarily_removed_scroll]; region_ids[pos.y][pos.x] = temporarily_removed_scroll; } // <<< 関数いろいろ <<< // >>> ダイクストラ法 >>> constexpr PosId N_INTERMEDIATE = 50 * 50 * DIVISION_SIZE * DIVISION_SIZE; constexpr PosId N_Y_INT = 50 * 50 * DIVISION_SIZE; inline PosId pos_id(const Vec2<double>& pos) { //HPC_ASSERT(0.0 < pos.x && pos.x < 50.0 && 0.0 < pos.y && pos.y < 50.0); if (is_integer(pos.y)) { return N_INTERMEDIATE + (int)pos.y * 50 * DIVISION_SIZE + (int)(pos.x * DIVISION_SIZE); } else if (is_integer(pos.x)) { return N_INTERMEDIATE + N_Y_INT + (int)pos.x * 50 * DIVISION_SIZE + (int)(pos.y * DIVISION_SIZE); } else { return (PosId)(pos.y * DIVISION_SIZE) * 50 * DIVISION_SIZE + (int)(pos.x * DIVISION_SIZE); } } inline vector<PosId> pos_ids(const Vec2<Meter>& pos) { vector<PosId> res; res.reserve(DIVISION_SIZE * DIVISION_SIZE + 4 * DIVISION_SIZE); for (int y = 0; y < DIVISION_SIZE; y++) { for (int x = 0; x < DIVISION_SIZE; x++) { res.push_back((pos.y * DIVISION_SIZE + y) * 50 * DIVISION_SIZE + pos.x * DIVISION_SIZE + x); } } for (int i = 0; i < DIVISION_SIZE; i++) { if (pos.y != 0) res.push_back(N_INTERMEDIATE + pos.y * 50 * DIVISION_SIZE + pos.x * DIVISION_SIZE + i); if (pos.y != 49) res.push_back(N_INTERMEDIATE + (pos.y + 1) * 50 * DIVISION_SIZE + pos.x * DIVISION_SIZE + i); if (pos.x != 0) res.push_back(N_INTERMEDIATE + N_Y_INT + pos.x * 50 * DIVISION_SIZE + pos.y * DIVISION_SIZE + i); if (pos.x != 49) res.push_back(N_INTERMEDIATE + N_Y_INT + (pos.x + 1) * 50 * DIVISION_SIZE + pos.y * DIVISION_SIZE + i); } return res; } array<Meter, 50 * 50 * DIVISION_SIZE*(2 + DIVISION_SIZE)> dijkstra_dists; array<Vec2<double>, 50 * 50 * DIVISION_SIZE*(2 + DIVISION_SIZE)> dijkstra_poses; array<PosId, 50 * 50 * DIVISION_SIZE*(2 + DIVISION_SIZE)> dijkstra_froms; array<array<bool, 50>, 50> dijkstra_targets; // 今の地点に未取得の巻物が存在するか確認する関数 // 存在すれば取得して取得枚数を返す inline int check_scroll(const PosId& id) { if (id < N_INTERMEDIATE) { const int y = id / (50 * DIVISION_SIZE * DIVISION_SIZE); const int x = (id % (50 * DIVISION_SIZE)) / DIVISION_SIZE; if (dijkstra_targets[y][x]) { dijkstra_targets[y][x] = false; return 1; } else { return 0; } } else if (id < N_INTERMEDIATE + N_Y_INT) { const int y = (id - N_INTERMEDIATE) / (50 * DIVISION_SIZE); const int x = ((id - N_INTERMEDIATE) % (50 * DIVISION_SIZE)) / DIVISION_SIZE; int res = 0; if (dijkstra_targets[y][x]) { dijkstra_targets[y][x] = false; res++; } if (dijkstra_targets[y - 1][x]) { dijkstra_targets[y - 1][x] = false; res++; } return res; } else { const int x = (id - N_INTERMEDIATE - N_Y_INT) / (50 * DIVISION_SIZE); const int y = ((id - N_INTERMEDIATE - N_Y_INT) % (50 * DIVISION_SIZE)) / DIVISION_SIZE; int res = 0; if (dijkstra_targets[y][x]) { dijkstra_targets[y][x] = false; res++; } if (dijkstra_targets[y][x - 1]) { dijkstra_targets[y][x - 1] = false; res++; } return res; } } // ダイクストラ法 void dijkstra(const Vec2<double>& start, const double& power, const int& n_targets) { long long q_pop_cnt = 0, u_cnt = 0; struct QElem { Meter dist; PosId id; QElem(Meter aDist, int aId) : dist(aDist), id(aId) {} bool operator<(const QElem& rhs)const { return dist < rhs.dist; } bool operator>(const QElem& rhs)const { return dist > rhs.dist; } }; auto get_region_id = [&](const Vec2<double>& p) { if (is_integer(p.y)) { const RegionId &id1 = region_ids[(int)p.y][(int)p.x], &id2 = region_ids[(int)p.y - 1][(int)p.x]; return (int)region_terrains[id1] > (int)region_terrains[id2] ? id1 : id2; } else if (is_integer(p.x)) { const RegionId &id1 = region_ids[(int)p.y][(int)p.x], &id2 = region_ids[(int)p.y][(int)p.x - 1]; return (int)region_terrains[id1] > (int)region_terrains[id2] ? id1 : id2; } else { return region_ids[(int)p.y][(int)p.x]; } }; modify_region(start); // region_ids の修正 fill(dijkstra_dists.begin(), dijkstra_dists.end(), (Meter)10000); const PosId start_id = pos_id(start); dijkstra_dists[start_id] = (Meter)0; dijkstra_poses[start_id] = start; int n_remain_targets = min(10, n_targets); // 枝刈り priority_queue<QElem, vector<QElem>, greater<QElem>> q; q.emplace(0, start_id); while (!q.empty()) { const QElem v = q.top(); q.pop(); q_pop_cnt++; if (dijkstra_dists[v.id] != v.dist) continue; n_remain_targets -= check_scroll(v.id); if (n_remain_targets == 0) break; Vec2<double> v_pos = dijkstra_poses[v.id]; auto us = get_boudary<false>(v_pos, get_region_id(v_pos), power); for (const auto& u : us) { u_cnt++; const PosId u_id = pos_id(u.second); //HPC_ASSERT(u.first >= 1); //HPC_ASSERT((v_pos - u.second).l2_norm() < u.first * power * 1.01); const Meter new_dist = v.dist + u.first; if (dijkstra_dists[u_id] > new_dist) { dijkstra_dists[u_id] = new_dist; dijkstra_poses[u_id] = u.second; dijkstra_froms[u_id] = v.id; q.emplace(new_dist, u_id); } } } undo_modify_region(); } // ダイクストラの後処理 void dijkstra_postprocess(const int& start_scroll) { // start_scroll が -1 のとき、初期地点スタートのダイクストラの処理 そうでなければ巻物スタート for (int goal_scroll = 0; goal_scroll < n_scrolls; goal_scroll++) { const Vec2<Meter>& goal_pos = scroll_poses[goal_scroll]; const vector<PosId> goal_ids = pos_ids(goal_pos); Meter& d = start_scroll == -1 ? scroll_distance_from_start[goal_scroll] : scroll_distance[start_scroll][goal_scroll]; d = 10000; for (const PosId& goal_id : goal_ids) { if (d > dijkstra_dists[goal_id]) { d = dijkstra_dists[goal_id]; } } } } // <<< ダイクストラ法 <<< // >>> 巡回セールスマン問題 >>> inline int popcount(unsigned int n) { n = (n & 0x55555555) + ((n >> 1) & 0x55555555); n = (n & 0x33333333) + ((n >> 2) & 0x33333333); n = (n & 0x0f0f0f0f) + ((n >> 4) & 0x0f0f0f0f); n = (n & 0x00ff00ff) + ((n >> 8) & 0x00ff00ff); n = (n & 0x0000ffff) + ((n >> 16) & 0x0000ffff); return n; } array<array<int, 20>, 1 << 20> tsp_dp; // 実際の 10000 倍して持つ array<array<char, 20>, 1 << 20> tsp_from; array<array<array<int, 20>, 20>, 20> tsp_dist; vector<char> tsp_path; double expected_score = 0.0; // 巡回セールスマン問題を動的計画法で解く関数 template <int _n_scrolls> void tsp() { for (int i = 0; i < _n_scrolls; i++) { for (int j = 0; j < _n_scrolls; j++) { double d = (double)scroll_distance[i][j]; //HPC_ASSERT(d <= 1e5); for (int n_gotten = 0; n_gotten < _n_scrolls; n_gotten++) { tsp_dist[n_gotten][i][j] = (int)(d * 10000.0); d /= 1.1; } } } for (int j = 0; j < _n_scrolls; j++) { tsp_dp[1 << j][j] = (int)scroll_distance_from_start[j] * 10000; } for (int s = 1; s < (1 << _n_scrolls) - 1; s++) { const int n_gotten = popcount(s); for (char i = 0; i < (char)_n_scrolls; i++) { if ((s >> i & 1) == 0) continue; #define TSP_PROCESS(j) if (j < _n_scrolls && (s >> j & 1) == 0) { \ int d = tsp_dp[s][i] + tsp_dist[n_gotten][i][j]; \ if (tsp_dp[s | 1 << j][j] > d) { \ tsp_dp[s | 1 << j][j] = d; \ tsp_from[s | 1 << j][j] = i; \ } \ } TSP_PROCESS(0); TSP_PROCESS(1); TSP_PROCESS(2); TSP_PROCESS(3); TSP_PROCESS(4); TSP_PROCESS(5); TSP_PROCESS(6); TSP_PROCESS(7); TSP_PROCESS(8); TSP_PROCESS(9); TSP_PROCESS(10); TSP_PROCESS(11); TSP_PROCESS(12); TSP_PROCESS(13); TSP_PROCESS(14); TSP_PROCESS(15); TSP_PROCESS(16); TSP_PROCESS(17); TSP_PROCESS(18); TSP_PROCESS(19); #undef TSP_PROCESS // ↑は↓をループアンローリングしたもの /* for (int j = 0; j < _n_scrolls; j++) { if (s >> j & 1) continue; int d = tsp_dp[s][i] + tsp_dist[n_gotten][i][j]; if (tsp_dp[s | 1 << j][j] > d) { tsp_dp[s | 1 << j][j] = d; tsp_from[s | 1 << j][j] = i; } } */ tsp_dp[s][i] = (int)1e9; } } int s = (1 << _n_scrolls) - 1; const int min_idx = min_element(tsp_dp[s].data(), tsp_dp[s].data() + _n_scrolls) - tsp_dp[s].data(); const int d = tsp_dp[s][min_idx]; for (int i = 0; i < _n_scrolls; i++) { tsp_dp[s][i] = (int)1e9; } tsp_path.resize(_n_scrolls); int p = min_idx; for (int i = _n_scrolls - 1; i >= 0; i--) { tsp_path[i] = p; const int next_s = s ^ 1 << p; p = tsp_from[s][p]; s = next_s; } #ifdef PRINT_DEBUG cerr << "tsp dist = " << (double)d / 10000.0 << endl; for (const int pa : tsp_path) { cerr << pa << " "; } cerr << endl; #endif expected_score += (double)d / 10000.0; } // <<< 巡回セールスマン問題 <<< // >>> A* 探索 >>> array<Meter, 50 * 50 * A_STAR_DIVISION_SIZE*(2 + A_STAR_DIVISION_SIZE) + A_STAR_N_STARTS * 2> a_star_dists; array<Vec2<double>, 50 * 50 * A_STAR_DIVISION_SIZE*(2 + A_STAR_DIVISION_SIZE) + A_STAR_N_STARTS * 2> a_star_poses; array<AStarPosId, 50 * 50 * A_STAR_DIVISION_SIZE*(2 + A_STAR_DIVISION_SIZE) + A_STAR_N_STARTS * 2> a_star_froms; inline vector<AStarPosId> a_star_pos_ids(const Vec2<Meter>& pos) { vector<AStarPosId> res; res.reserve(A_STAR_DIVISION_SIZE * A_STAR_DIVISION_SIZE + 4 * A_STAR_DIVISION_SIZE); for (int y = 0; y < A_STAR_DIVISION_SIZE; y++) { for (int x = 0; x < A_STAR_DIVISION_SIZE; x++) { res.push_back((pos.y * A_STAR_DIVISION_SIZE + y) * 50 * A_STAR_DIVISION_SIZE + pos.x * A_STAR_DIVISION_SIZE + x); } } for (int i = 0; i < A_STAR_DIVISION_SIZE; i++) { if (pos.y != 0) res.push_back(A_STAR_N_INTERMEDIATE + pos.y * 50 * A_STAR_DIVISION_SIZE + pos.x * A_STAR_DIVISION_SIZE + i); if (pos.y != 49) res.push_back(A_STAR_N_INTERMEDIATE + (pos.y + 1) * 50 * A_STAR_DIVISION_SIZE + pos.x * A_STAR_DIVISION_SIZE + i); if (pos.x != 0) res.push_back(A_STAR_N_INTERMEDIATE + A_STAR_N_Y_INT + pos.x * 50 * A_STAR_DIVISION_SIZE + pos.y * A_STAR_DIVISION_SIZE + i); if (pos.x != 49) res.push_back(A_STAR_N_INTERMEDIATE + A_STAR_N_Y_INT + (pos.x + 1) * 50 * A_STAR_DIVISION_SIZE + pos.y * A_STAR_DIVISION_SIZE + i); } return res; } // A* 探索 (多点スタート) void a_star(const vector<pair<Meter, Vec2<double>>>& starts, const Vec2<Meter>& int_start, const Vec2<Meter>& goal, const double& power) { struct QElem { Meter g; Meter dist; AStarPosId id; QElem(const Meter& aG, const Meter& aDist, const int& aId) : g(aG), dist(aDist), id(aId) {} bool operator<(const QElem& rhs)const { return g < rhs.g; } bool operator>(const QElem& rhs)const { return g > rhs.g; } }; auto get_region_id = [&](const Vec2<double>& p) { if (is_integer(p.y)) { const RegionId &id1 = region_ids[(int)p.y][(int)p.x], &id2 = region_ids[(int)p.y - 1][(int)p.x]; return (int)region_terrains[id1] > (int)region_terrains[id2] ? id1 : id2; } else if (is_integer(p.x)) { const RegionId &id1 = region_ids[(int)p.y][(int)p.x], &id2 = region_ids[(int)p.y][(int)p.x - 1]; return (int)region_terrains[id1] > (int)region_terrains[id2] ? id1 : id2; } else { return region_ids[(int)p.y][(int)p.x]; } }; auto is_goal = [&](const Vec2<double>& p) { return goal.x <= p.x && p.x <= goal.x + 1 && goal.y <= p.y && p.y <= goal.y + 1; }; auto a_star_pos_id = [&](const Vec2<double>& pos) -> AStarPosId { //HPC_ASSERT(0.0 < pos.x && pos.x < 50.0 && 0.0 < pos.y && pos.y < 50.0); if (is_integer(pos.y)) { return A_STAR_N_INTERMEDIATE + (int)pos.y * 50 * A_STAR_DIVISION_SIZE + (int)(pos.x * A_STAR_DIVISION_SIZE); } else if (is_integer(pos.x)) { return A_STAR_N_INTERMEDIATE + A_STAR_N_Y_INT + (int)pos.x * 50 * A_STAR_DIVISION_SIZE + (int)(pos.y * A_STAR_DIVISION_SIZE); } else { return (AStarPosId)(pos.y * A_STAR_DIVISION_SIZE) * 50 * A_STAR_DIVISION_SIZE + (int)(pos.x * A_STAR_DIVISION_SIZE); } }; auto get_special_us = [&](const Vec2<double>& pos, const RegionId& reg_id) { // 角に飛ぶ Terrain terrain = region_terrains[reg_id]; const double jump_dist = TERRAIN_COEF[(int)terrain] * power; vector<pair<Meter, Vec2<double>>> res; for (const double& fy : array<double, 2>{2e-3, 1.0 - 2e-3}) for (const double& fx : array<double, 2>{2e-3, 1.0 - 2e-3}) { const Vec2<double> g = Vec2<double>(goal) + Vec2<double>(fx, fy); //HPC_ASSERT(0.0 < g.x && g.x < 50.0 && 0.0 < g.y && g.y < 50.0); const Vec2<double> vec = g - pos; const double dist = vec.l2_norm(); const Vec2<double> jump = vec * (jump_dist / dist); const int n = (int)(dist / jump_dist); if (n >= 20) continue; Vec2<double> p(pos); for (int i = 1; i <= n; i++) { p += jump; Vec2<int> int_p(p); if (region_terrains[region_ids[int_p.y][int_p.x]] != terrain) goto brcon; } res.emplace_back(n + 1, g); brcon:; } return res; }; constexpr double inv_root_2 = 0.70710678118655; modify_region(Vec2<double>(int_start)); // region 修正 fill(a_star_dists.begin(), a_star_dists.end(), (Meter)10000); // 距離の初期化 priority_queue<QElem, vector<QElem>, greater<QElem>> q; for (int idx_starts = 0; idx_starts < (int)starts.size(); idx_starts++) { // プライオリティキューの初期化 const pair<Meter, Vec2<double>>& s = starts[idx_starts]; const Meter& dist = s.first; Vec2<double> p = s.second; const AStarPosId id = A_STAR_N_NORMAL + idx_starts; const Meter h = (Meter)ceil( ( (p - ((Vec2<double>)(goal) + 0.5)).l2_norm() - inv_root_2 ) / power ); a_star_dists[id] = dist; a_star_poses[id] = p; q.emplace(dist + h, dist, id); } const vector<AStarPosId> goals = a_star_pos_ids(goal); int n_remain_goals = (int)goals.size(); int n_a_star_nodes = 0; int best_dist = 10000; while (!q.empty()) { const QElem v = q.top(); q.pop(); if (a_star_dists[v.id] != v.dist) continue; n_a_star_nodes++; const Vec2<double>& v_pos = a_star_poses[v.id]; // 終了判定 if (is_goal(v_pos)) { n_remain_goals--; if (best_dist == 10000) best_dist = v.dist; if (n_remain_goals == 0) break; } if (best_dist + 2 < v.dist) break; const auto special_us = get_special_us(v_pos, get_region_id(v_pos)); for (const auto& u : special_us) { const AStarPosId u_id = a_star_pos_id(u.second); const Meter new_dist = v.dist + u.first; if (a_star_dists[u_id] > new_dist) { a_star_dists[u_id] = new_dist; a_star_poses[u_id] = u.second; a_star_froms[u_id] = v.id; const Meter h = (Meter)ceil( ( (u.second - ((Vec2<double>)(goal) + 0.5)).l2_norm() - inv_root_2 ) / power ); q.emplace(new_dist + h, new_dist, u_id); } } const auto us = get_boudary<true>(v_pos, get_region_id(v_pos), power); for (const auto& u : us) { const AStarPosId u_id = a_star_pos_id(u.second); const Meter new_dist = v.dist + u.first; if (a_star_dists[u_id] > new_dist) { a_star_dists[u_id] = new_dist; a_star_poses[u_id] = u.second; a_star_froms[u_id] = v.id; const Meter h = (Meter)ceil( ( (u.second - ((Vec2<double>)(goal) + 0.5)).l2_norm() - inv_root_2 ) / power ); q.emplace(new_dist + h, new_dist, u_id); } } } #ifdef PRINT_DEBUG cerr << "n_a_star_nodes=" << n_a_star_nodes << " n_remain_goals=" << n_remain_goals << endl; #endif //HPC_ASSERT(n_remain_goals < (int)goals.size()); undo_modify_region(); // region の修正を戻す } // <<< A* 探索 <<< vector<Vec2<double>> overall_path; int calculated_score = 0; int calculated_scr; int real_score; void find_answer(const Vec2<double>& start) { // 探索 vector<pair<Meter, Vec2<double>>> starts{ make_pair(0, start) }; Vec2<Meter> int_start(start); vector<vector<vector<Vec2<double>>>> pathss; vector<vector<pair<Meter, Vec2<double>>>> startss; double power = 1.0; for (int idx_scrolls = 0; idx_scrolls < n_scrolls; idx_scrolls++) { startss.push_back(starts); const Vec2<Meter>& goal = scroll_poses[tsp_path[idx_scrolls]]; a_star(starts, int_start, goal, power); const vector<AStarPosId> goals = a_star_pos_ids(goal); starts.clear(); // starts の更新 for (const AStarPosId& id : goals) { Vec2<double>& p = a_star_poses[id]; if (is_integer(p.y)) { // 内側へ寄せる if ((Meter)p.y == goal.y) p.y += EPS; else p.y -= EPS; } if (is_integer(p.x)) { if ((Meter)p.x == goal.x) p.x += EPS; else p.x -= EPS; } starts.emplace_back(a_star_dists[id], p); } // 道筋の記録 vector<vector<Vec2<double>>> paths; for (AStarPosId id : goals) { vector<Vec2<double>> path; if (a_star_dists[id] == 10000) { // 未到達 path.emplace_back(-1.0, -1.0); // ダミー } else { while (id < A_STAR_N_NORMAL) { id = a_star_froms[id]; path.push_back(a_star_poses[id]); } } reverse(path.begin(), path.end()); paths.push_back(path); } pathss.push_back(paths); int_start = goal; power *= 1.1; } // 復元 overall_path.clear(); Meter d = 10000; int argmin_starts = -1; for (int i = 0; i < (int)starts.size(); i++) { if (starts[i].first < d) { d = starts[i].first; argmin_starts = i; } } //HPC_ASSERT(-1 != argmin_starts); calculated_score += d; calculated_scr = d; overall_path.push_back(starts[argmin_starts].second); for (int idx_pathss = n_scrolls - 1; idx_pathss >= 0; idx_pathss--) { const vector<Vec2<double>>& path = pathss[idx_pathss][argmin_starts]; for (int idx_path = (int)path.size() - 1; idx_path >= 0; idx_path--) { overall_path.push_back(path[idx_path]); // 逆順 } starts = startss[idx_pathss]; argmin_starts = -1; for (int i = 0; i < (int)starts.size(); i++) { if (starts[i].second == path[0]) { argmin_starts = i; } } //HPC_ASSERT(-1 != argmin_starts); } reverse(overall_path.begin(), overall_path.end()); } // 浮動小数点の誤差を減らすように座標を修正 本当に誤差を減らせているかはよくわからない void fix_path() { for (Vec2<double>& p : overall_path) { Vec2<int> int_p(p); Vec2<double> frac_p = p - Vec2<double>(int_p); if (eq(frac_p.x, 0.0)) { if ((int)region_terrains[region_ids[int_p.y][int_p.x]] < (int)region_terrains[region_ids[int_p.y][int_p.x - 1]]) { p.x += 5e-5; } else { p.x -= 5e-5; } } else if (frac_p.x < 4e-5) { p.x += 4e-5; } if (frac_p.x > 1 - 4e-5) { p.x -= 4e-5; } if (eq(frac_p.y, 0.0)) { if ((int)region_terrains[region_ids[int_p.y][int_p.x]] < (int)region_terrains[region_ids[int_p.y - 1][int_p.x]]) { p.y += 5e-5; } else { p.y -= 5e-5; } } else if (frac_p.y < 4e-5) { p.y += 4e-5; } else if (frac_p.y > 1 - 4e-5) { p.y -= 4e-5; } } } //------------------------------------------------------------------------------ /// コンストラクタ /// @detail 最初のステージ開始前に実行したい処理があればここに書きます Answer::Answer() { init_sin_cos_table(); T0 = time(); stage_num = 0; fill_2d_array(tsp_dp, (int)1e9); } //------------------------------------------------------------------------------ /// デストラクタ /// @detail 最後のステージ終了後に実行したい処理があればここに書きます Answer::~Answer() { #ifdef PRINT_DEBUG cerr << "expected_score=" << expected_score << endl; cerr << "calculated_score=" << calculated_score << endl; cerr << "real_score=" << real_score << endl; int a; cin >> a; #endif } // >>> テスト >>> void test_go_straight() { for (Angle angle = 0; angle < 8; angle++) { const Vec2<double>& p = go_straight(Vec2<double>(0.5, 0.5), angle, n_scrolls); cerr << p << endl; } cerr << endl; for (Angle angle = 0; angle < 8; angle++) { const Vec2<double>& p = go_straight(Vec2<double>(49.5, 49.5), angle, region_ids[49][49]); cerr << p << endl; } } void test_get_boudary() { //auto bs = get_boudary(Vec2<double>(0.5, 0.5), region_ids[0][0], 1.0); auto bs = get_boudary<false>(Vec2<double>(14.0, 0.5), region_ids[0][14], 1.0); for (auto& b : bs) { cerr << b.first << " " << b.second << endl; } } void test_dijkstra() { cerr << "dijkstra start!" << endl; double t0 = time(); dijkstra(Vec2<double>(0.5, 0.5), 1.0, 999); for (const auto& dist : dijkstra_dists) { cerr << dist << " "; } cerr << endl; dijkstra(Vec2<double>(20.5, 0.5), 1.0, 999); dijkstra(Vec2<double>(20.5, 20.5), 1.0, 999); dijkstra(Vec2<double>(20.5, 30.5), 1.0, 999); dijkstra(Vec2<double>(20.5, 40.5), 1.0, 999); dijkstra(Vec2<double>(10.5, 40.5), 1.0, 999); dijkstra(Vec2<double>(30.5, 40.5), 1.0, 999); dijkstra(Vec2<double>(40.5, 40.5), 1.0, 999); double t = time() - t0; cerr << "dijkstra finished!" << endl; cerr << "time: " << t << " sec" << endl; } // <<< テスト <<< int next_scroll_idx; int next_path; //------------------------------------------------------------------------------ /// 各ステージ開始時に呼び出される処理 /// @detail 各ステージに対する初期化処理が必要ならここに書きます /// @param aStage 現在のステージ void Answer::initialize(const Stage& aStage) { next_scroll_idx = 0; next_path = 0; const auto& scrolls = aStage.scrolls(); n_scrolls = scrolls.count(); for (int i = 0; i < scrolls.count(); i++) { const auto& pos = scrolls[i].pos(); scroll_poses[i] = Vec2<Meter>((Meter)pos.x, (Meter)pos.y); } init_region(aStage); fill_2d_array(dijkstra_targets, false); double dijkstra_power = pow(1.1, (n_scrolls - 1.0) * 0.5); for (int idx_scrolls = 0; idx_scrolls < n_scrolls; idx_scrolls++) { const Vec2<Meter>& scroll = scroll_poses[idx_scrolls]; for (int i = 0; i < n_scrolls; i++) { const Vec2<Meter>& p = scroll_poses[i]; if (idx_scrolls != i) dijkstra_targets[p.y][p.x] = true; } const Vec2<double> start((double)scroll.x + 0.5, (double)scroll.y + 0.5); dijkstra(start, dijkstra_power, n_scrolls - 1); dijkstra_postprocess(idx_scrolls); } for (int i = 0; i < n_scrolls; i++) { const Vec2<Meter>& p = scroll_poses[i]; dijkstra_targets[p.y][p.x] = true; } dijkstra(aStage.rabbit().pos(), dijkstra_power, n_scrolls); dijkstra_postprocess(-1); if (n_scrolls == 1) tsp<1>(); else if (n_scrolls == 2) tsp<2>(); else if (n_scrolls == 3) tsp<3>(); else if (n_scrolls == 4) tsp<4>(); else if (n_scrolls == 5) tsp<5>(); else if (n_scrolls == 6) tsp<6>(); else if (n_scrolls == 7) tsp<7>(); else if (n_scrolls == 8) tsp<8>(); else if (n_scrolls == 9) tsp<9>(); else if (n_scrolls == 10) tsp<10>(); else if (n_scrolls == 11) tsp<11>(); else if (n_scrolls == 12) tsp<12>(); else if (n_scrolls == 13) tsp<13>(); else if (n_scrolls == 14) tsp<14>(); else if (n_scrolls == 15) tsp<15>(); else if (n_scrolls == 16) tsp<16>(); else if (n_scrolls == 17) tsp<17>(); else if (n_scrolls == 18) tsp<18>(); else if (n_scrolls == 19) tsp<19>(); else if (n_scrolls == 20) tsp<20>(); //else HPC_ASSERT(false); find_answer(aStage.rabbit().pos()); fix_path(); #ifdef PRINT_DEBUG cerr << "stage " << stage_num << ": " << time() - T0 << " sec" << endl; #endif stage_num++; } //------------------------------------------------------------------------------ /// 毎フレーム呼び出される処理 /// @detail 移動先を決定して返します /// @param aStage 現在のステージ /// @return 移動の目標座標 Vector2 Answer::getTargetPos(const Stage& aStage) { auto pos = aStage.rabbit().pos(); while (next_path < (int)overall_path.size() && (Vec2<double>(pos) - overall_path[next_path]).l2_norm() < 3e-4) { next_path++; } if (next_path < (int)overall_path.size()) { Vec2<double> p = overall_path[next_path]; return (Vector2)p; } return pos; } //------------------------------------------------------------------------------ /// 各ステージ終了時に呼び出される処理 /// @detail 各ステージに対する終了処理が必要ならここに書きます /// @param aStage 現在のステージ void Answer::finalize(const Stage& aStage) { real_score += aStage.turn(); #ifdef PRINT_DEBUG cerr << "calculated_score=" << calculated_scr << " actural_score=" << aStage.turn() << endl << endl; #endif } } // namespace #undef PRINT_DEBUG // EOF