//------------------------------------------------------------------------------
/// @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