//------------------------------------------------------------------------------
/// @file
/// @author ハル研究所プログラミングコンテスト実行委員会
///
/// @copyright (C)HAL Laboratory, Inc.
/// @attention このファイルの利用は、同梱のREADMEにある
/// 利用条件に従ってください。
//------------------------------------------------------------------------------
#include "Answer.hpp"
#include <iostream>
#include <algorithm>
#include <bitset>
#include <map>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <string>
#include <cstring>
#include <utility>
#include <vector>
#include <complex>
#include <valarray>
#include <fstream>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <numeric>
#include <climits>
#include <random>
#include <time.h>
#define InfL 2000000000
const float eps = 0.0001; // 0.0001, 0~99,101の特徴点で境界線から離す距離
const float eeps = 0.00001; // 0.00001, 小数部分がこれ以下の座標入力は禁止
using namespace std;
clock_t time_ini;
//------------------------------------------------------------------------------
namespace hpc {
// 時間計測
double time_diff() {
int time_tmp = clock();
const double time = static_cast<double>(time_tmp - (int)time_ini) / CLOCKS_PER_SEC * 1000.0;
return time;
}
// 乱数
int xor128() {
static int x = 123456789, y = 362436069, z = 521288629, w = 88675123;
int t = (x ^ (x << 11));
x = y; y = z; z = w;
return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
}
double RAND_() {
while (1) {
double rand_ = (double)(xor128() % InfL) / (double)InfL;
if (rand_ > 0 && rand_ < 1) return rand_;
}
}
Vector2 vec_init; // ウサギの初期位置
int N; // 巻物と初期位置の合計数
int turn_sum = 0; // 経過ターン数,出力時専用
vector<vector<bool>> x_wall(50); // x_wall[x][y] : 左上座標が(x,y)でx軸平行のマスの辺が、エリアの境界線であるかどうか
vector<vector<bool>> y_wall(50); // y_wall[x][y] : 左上座標が(x,y)でy軸平行のマスの辺が、エリアの境界線であるかどうか
vector<float> ter_to_sp = {1.0, 0.6, 0.3, 0.1}; // 地形->倍率
vector<float> ter_to_sp_inv = { 1.0, 1.0 / 0.6, 1.0 / 0.3, 1.0 / 0.1 }; // ter_to_spの逆数
vector<int> pow2; // 2のi乗
vector<float> pow1_1; // 1.1のi乗
vector<float> pow1_1_inv; // 1.1の-i乗
float modf_(float val) {
float tmp;
return(modf(val, &tmp)); // 小数部分
}
bool Vec_in(Vector2 v) { return(v.x > 0.0 && v.x < 50.0 && v.y > 0.0 && v.y < 50.0); } // vがフィールド内にあるか
bool Vec_eq(Vector2 v1, Vector2 v2) { return(v1.x == v2.x && v1.y == v2.y); }
float Vec_dist(Vector2 v1, Vector2 v2) { return(sqrt((v1.x - v2.x) * (v1.x - v2.x) + (v1.y - v2.y) * (v1.y - v2.y))); }
float Vec_dist_ter(Vector2 v1, Vector2 v2, int ter_new, int ter_old, int n) {
// v1からv2までの移動距離(単位 : ジャンプ回数)
// 高速区間->(v1)->低速区間->(v2)の場合、低速区間のジャンプ回数を一定まで少なくみなす
float dist = ter_to_sp_inv[ter_new] * pow1_1_inv[n] * Vec_dist(v1, v2);
if (ter_old != -1 && (ter_old < ter_new)) {
float sp_ratio = ter_to_sp[ter_old] / ter_to_sp[ter_new]; // >1
if (dist < sp_ratio)
dist = dist / sp_ratio; // 惰性では低速区間を飛び越えられない確率
else
dist -= (sp_ratio - (float)1.0); // 低速区間を踏む必要があるが、手前で止まることでジャンプ回数削減可能
}
return dist;
}
pair<int, int> Vec_to_xy(Vector2 vectmp) {
// マスのindexを返す
pair<int, int> xytmp = make_pair((int)vectmp.x, (int)vectmp.y);
return xytmp;
}
Vector2 xy_to_Vec(pair<int, int> xytmp) {
// 中心座標を返す
Vector2 vectmp;
vectmp.x = (float)xytmp.first + (float)0.5;
vectmp.y = (float)xytmp.second + (float)0.5;
return vectmp;
}
Vector2 scroll_or_init(const Stage& aStage, int i) {
// 巻物or初期位置座標を返す
Vector2 s = (i == N - 1) ? vec_init : aStage.scrolls()[i].pos();
return s;
}
vector<Vector2> bound_list(Vector2 vec_from, Vector2 vec_to, bool is_bool = false) {
// 両端がvec_fromとvec_toの線分がまたぐエリアの境界線のリスト
// is_bool : (true : 代表1つ, false : 全て)
vector<Vector2> bound_list_tmp;
// y軸と平行の境界線との衝突判定
int x_from = (int)(vec_from.x + (float)1.0 + eeps);
int x_to = (int)(vec_to.x - eeps);
Vector2 vec_diff(vec_to.x - vec_from.x, vec_to.y - vec_from.y);
for (int x_cross = x_from; x_cross <= x_to; x_cross++) {
float y_cross = vec_from.y + vec_diff.y * ((float)x_cross - vec_from.x) / vec_diff.x;
if (y_wall[x_cross][(int)y_cross]) {
Vector2 vectmp((float)x_cross, y_cross);
bound_list_tmp.push_back(vectmp);
if (is_bool) break;
}
}
if (is_bool && (int)bound_list_tmp.size() != 0)
return bound_list_tmp;
// x軸と平行の境界線との衝突判定
bool flag_swap = false;
if (vec_from.y > vec_to.y) {
swap(vec_from, vec_to);
flag_swap = true;
}
int y_from = (int)(vec_from.y + (float)1.0 + eeps);
int y_to = (int)(vec_to.y - eeps);
for (int y_cross = y_from; y_cross <= y_to; y_cross++) {
float x_cross = vec_from.x + vec_diff.x * ((float)y_cross - vec_from.y) / vec_diff.y;
if (x_wall[(int)x_cross][y_cross]) {
Vector2 vectmp(x_cross, (float)y_cross);
bound_list_tmp.push_back(vectmp);
if (is_bool) break;
}
}
if (flag_swap) swap(vec_from, vec_to);
return bound_list_tmp;
}
class UnionFind {
public:
vector<vector<pair<int, int>>> par;
int H, W;
void UnionFind_ini(int Harg, int Warg) {
H = Harg;
W = Warg;
par.resize(H);
for (int i = 0; i < H; i++) {
par[i].resize(W);
for (int j = 0; j < W; j++)
par[i][j] = make_pair(i, j);
}
}
pair<int, int> root(pair<int, int> x) {
if (par[x.first][x.second] == x) return x;
par[x.first][x.second] = root(par[x.first][x.second]);
return par[x.first][x.second];
}
void unite(pair<int, int> x, pair<int, int> y) {
pair<int, int> rx = root(x);
pair<int, int> ry = root(y);
if (rx == ry) return;
par[rx.first][rx.second] = ry;
return;
}
bool same(pair<int, int> x, pair<int, int> y) {
pair<int, int> rx = root(x);
pair<int, int> ry = root(y);
return rx == ry;
}
};
vector<Vector2> commands;
//------------------------------------------------------------------------------
/// コンストラクタ
/// @detail 最初のステージ開始前に実行したい処理があればここに書きます
Answer::Answer()
{
pow2.resize(30, 1);
pow1_1.resize(30, 1.0);
pow1_1_inv.resize(30, 1.0);
for (int i = 1; i < 30; i++) {
pow2[i] = pow2[i - 1] * 2;
pow1_1[i] = pow1_1[i - 1] * 1.1;
pow1_1_inv[i] = pow1_1_inv[i - 1] / 1.1;
}
for (int xtmp = 0; xtmp < 50; xtmp++) {
x_wall[xtmp].resize(50, false);
y_wall[xtmp].resize(50, false);
}
}
//------------------------------------------------------------------------------
/// デストラクタ
/// @detail 最後のステージ終了後に実行したい処理があればここに書きます
Answer::~Answer()
{
}
//------------------------------------------------------------------------------
/// 各ステージ開始時に呼び出される処理
/// @detail 各ステージに対する初期化処理が必要ならここに書きます
/// @param aStage 現在のステージ
void Answer::initialize(const Stage& aStage)
{
// 変数初期化など
turn_sum = 0;
N = 1;
vec_init = aStage.rabbit().pos();
for (auto scroll : aStage.scrolls()) {
auto tmp = scroll;
tmp = tmp;
N++;
}
// ---------- 0. 準備(境界線や特徴点の抽出など) ----------
// マスが互いにつながった地形が同じエリアに分割し、その境界線の場所を求める
UnionFind UF;
UF.UnionFind_ini(50, 50);
for (int xtmp = 0; xtmp < 50; xtmp++) {
for (int ytmp = 0; ytmp < 50; ytmp++) {
Vector2 vec0 = xy_to_Vec(make_pair(xtmp, ytmp));
auto ter0 = aStage.terrain(vec0);
Vector2 vec1 = vec0;
if (xtmp != 0) {
vec1.x -= (float)1.0;
auto ter1 = aStage.terrain(vec1);
if (ter0 == ter1)
UF.unite(make_pair(xtmp, ytmp), make_pair(xtmp - 1, ytmp));
y_wall[xtmp][ytmp] = (ter0 != ter1);
}
vec1 = vec0;
if (ytmp != 0) {
vec1.y -= (float)1.0;
auto ter1 = aStage.terrain(vec1);
if (ter0 == ter1)
UF.unite(make_pair(xtmp, ytmp), make_pair(xtmp, ytmp - 1));
x_wall[xtmp][ytmp] = (ter0 != ter1);
}
}
}
// エリアの整理
vector<vector<pair<int, int>>> UF_area; // エリア番号iに含まれるマス(xy0, ..., xyn)
vector<int> UF_ter; // エリア番号->地形
vector<vector<int>> UF_area_inv(50); // xy->エリア番号
set<pair<int, int>> root_set; // エリアの代表マスの集合
for (int xtmp = 0; xtmp < 50; xtmp++) {
for (int ytmp = 0; ytmp < 50; ytmp++) {
root_set.insert(UF.root(make_pair(xtmp, ytmp)));
UF_area_inv[xtmp].resize(50, -1);
}
}
int idx = 0;
for (auto it = root_set.begin(); it != root_set.end(); it++) {
UF_area_inv[it->first][it->second] = idx;
Vector2 vectmp = xy_to_Vec(*it);
auto tertmp = aStage.terrain(vectmp);
UF_ter.push_back((int)tertmp);
idx++;
}
int UF_area_size = idx + 1;
UF_area.resize(UF_area_size);
for (int xtmp = 0; xtmp < 50; xtmp++) {
for (int ytmp = 0; ytmp < 50; ytmp++) {
pair<int, int> r = UF.root(make_pair(xtmp, ytmp));
int root_idx = UF_area_inv[r.first][r.second];
UF_area_inv[xtmp][ytmp] = root_idx;
UF_area[root_idx].push_back(make_pair(xtmp, ytmp));
}
}
// 特徴点(i, j)の抽出 巻物or初期位置から巻物への移動は、特徴点を経由して行う 経由地間は直線移動する
// 特徴点の種類 : 0<=i<50 : x軸と平行の境界線上, 50<=i<100 : y軸と平行の境界線上
// , i=100 : 巻物or初期位置, i=101 : 格子点の周囲3/4マスが同じ地形のとき、eps外部に離れた点(L字外部点)
// i=0, i=50は左or上のフィールド境界なので使わない
int mesh_size = 1; // 1, 10 : メッシュ化(マスの辺の細分化)したときに1辺あたりに割り振られる特徴点の数(種類 : 0~99)
if (N < 7) mesh_size = 2; // 距離を求める計算量がN^2に比例するので、Nが小さいときに限りメッシュを細かくする
int mesh_num = mesh_size * 50; // 50
vector<vector<vector<int>>> v_to_root_idx(102);
vector<vector<Vector2>> v_to_vec(102);
for (int i = 0; i < 100; i++) {
v_to_root_idx[i].resize(mesh_num);
v_to_vec[i].resize(mesh_num);
for (int j = 0; j < mesh_num; j++) {
if (i < 50) {
v_to_vec[i][j].x = ((float)j + (float)0.5) / (float)mesh_size;
v_to_vec[i][j].y = (float)i;
}
else {
v_to_vec[i][j].x = (float)i - (float)50.0;
v_to_vec[i][j].y = ((float)j + (float)0.5) / (float)mesh_size;
}
}
}
v_to_root_idx[100].resize(N);
v_to_vec[100].resize(N);
for (int i = 0; i < N; i++)
v_to_vec[100][i] = scroll_or_init(aStage, i);
vector<vector<pair<int, int>>> UF_area_adjlist(UF_area_size);
// 0~99(境界線上の特徴点)を追加
for (int xtmp = 0; xtmp < 50; xtmp++) {
for (int ytmp = 0; ytmp < 50; ytmp++) {
int root_idx = UF_area_inv[xtmp][ytmp];
pair<int, int> xytmp = make_pair(xtmp, ytmp);
for (int p = 0; p < 4; p++) {
pair<int, int> xynew = xytmp;
switch (p) {
case 0:
xynew.first--;
break;
case 1:
xynew.first++;
break;
case 2:
xynew.second--;
break;
case 3:
xynew.second++;
break;
}
int xnew = xynew.first, ynew = xynew.second;
if (xnew < 0 || xnew >= 50 || ynew < 0 || ynew >= 50) continue;
if (root_idx != UF_area_inv[xnew][ynew]) {
// terの異なる境界線上
int xmax = max(xtmp, xnew); // 下
int ymax = max(ytmp, ynew); // 右
for (int mesh_tmp = 0; mesh_tmp < mesh_size; mesh_tmp++) {
pair<int, int> vnew;
if (p < 2)
vnew = make_pair(xmax + 50, ymax * mesh_size + mesh_tmp); // y軸と平行な境界線
else
vnew = make_pair(ymax, xmax * mesh_size + mesh_tmp); // x軸と平行な境界線
UF_area_adjlist[root_idx].push_back(vnew);
v_to_root_idx[vnew.first][vnew.second].push_back(root_idx);
}
}
}
}
}
// 100(巻物or初期位置の中心)を追加
for (int i = 0; i < N; i++) {
Vector2 s = scroll_or_init(aStage, i);
pair<int, int> xytmp = Vec_to_xy(s);
int root_idx = UF_area_inv[xytmp.first][xytmp.second];
UF_area_adjlist[root_idx].push_back(make_pair(100, i));
v_to_root_idx[100][i].push_back(root_idx);
}
// 101(L字外部点)を追加
int idx101 = 0;
for (int xtmp = 1; xtmp < 50; xtmp++) {
for (int ytmp = 1; ytmp < 50; ytmp++) {
vector<Vector2> vecs;
for (int i = -1; i <= 1; i+=2) {
for (int j = -1; j <= 1; j+=2) {
Vector2 vectmp((float)xtmp + (float)i * eps, (float)ytmp + (float)j * eps);
vecs.push_back(vectmp);
}
}
vector<int> ters(4, 0);
for (Vector2 vectmp : vecs) {
auto ter = aStage.terrain(vectmp);
ters[(int)ter]++;
}
for (int tertmp = 0; tertmp < 4; tertmp++) {
if (ters[tertmp] == 3) {
// L字型
for (int k = 0; k < 4; k++) {
Vector2 vecprev = vecs[k];
auto ter = aStage.terrain(vecprev);
if (ters[(int)ter] == 1) {
if (tertmp > (int)ter) continue; // L字型内部(1マス)の地形より、L字型外部(3マス)の地形の方が速くないと曲がる意味がない
int kinv = 3 - k;
Vector2 vectmp = vecs[kinv];
pair<int, int> xytmp = Vec_to_xy(vectmp);
int root_idx = UF_area_inv[xytmp.first][xytmp.second];
UF_area_adjlist[root_idx].push_back(make_pair(101, idx101));
vector<int> vv(1, root_idx);
v_to_root_idx[101].push_back(vv);
v_to_vec[101].push_back(vectmp);
idx101++;
break;
}
}
break;
}
}
}
}
// 特徴点間に張る辺を抽出 辺は異なるエリアをまたいではいけない
int M = idx101;
vector<vector<vector<pair<pair<int, int>, int>>>> v_adjlist(102);
for (int itmp = 0; itmp < 100; itmp++)
v_adjlist[itmp].resize(mesh_num);
v_adjlist[100].resize(N);
v_adjlist[101].resize(M);
int ii = 0;
for (vector<pair<int, int>> vlist : UF_area_adjlist) {
for (pair<int, int> v_from : vlist) {
Vector2 vec_from = v_to_vec[v_from.first][v_from.second];
for (pair<int, int> v_to : vlist) {
if (v_from == v_to) continue;
Vector2 vec_to = v_to_vec[v_to.first][v_to.second];
Vector2 vec_diff(vec_to.x - vec_from.x, vec_to.y - vec_from.y);
if (vec_from.x > vec_to.x) continue;
if (vec_from.x == vec_to.x && vec_from.y > vec_to.y) continue;
if (vec_from.x == vec_to.x) {
float frac_x = modf_(vec_from.x);
if (frac_x < eeps || frac_x >(float)1.0 - eeps) continue; // 境界線に沿う移動は禁止(バグ防止)
}
if (vec_from.y == vec_to.y) {
float frac_y = modf_(vec_from.y);
if (frac_y < eeps || frac_y > (float)1.0 - eeps) continue; // 境界線に沿う移動は禁止(バグ防止)
}
bool can = true;
// 境界線は経由しないが、移動全体が想定と別エリアに属す場合不可
Vector2 vec_half = vec_from;
vec_half.x += vec_diff.x * (float)0.5;
vec_half.y += vec_diff.y * (float)0.5;
pair<int, int> xy_half = Vec_to_xy(vec_half); // 中点
can = (UF_area_inv[xy_half.first][xy_half.second] == ii);
if (!can) continue;
vector<Vector2> bound_list_tmp = bound_list(vec_from, vec_to, true);
if ((int)bound_list_tmp.size() != 0) continue;
// 無向辺を追加
v_adjlist[v_from.first][v_from.second].push_back(make_pair(v_to, ii));
v_adjlist[v_to.first][v_to.second].push_back(make_pair(v_from, ii));
}
}
ii++;
}
// ---------- 1. まず、巻物間の最小の推定ジャンプ回数とその経路を求める(ダイクストラ法) ----------
vector<vector<vector<float>>> dist(N); // [巻物i][巻物j][取得済み巻物数]のときの最小ジャンプ回数
vector<vector<vector<vector<pair<int, int>>>>> dist_min_path(N); // [巻物i][巻物j][取得済み巻物数]のときジャンプ回数が最小となる特徴点順
for (int i = 0; i < N; i++) {
dist[i].resize(N - 1);
dist_min_path[i].resize(N - 1);
for (int j = 0; j < N - 1; j++) {
dist[i][j].resize(N);
dist_min_path[i][j].resize(N - 1);
for (int n = 0; n < N - 1; n++)
dist_min_path[i][j][n].clear();
}
}
for (int i = 0; i < N; i++) {
for (int n = 0; n < N - 1; n++) {
priority_queue<pair<float, pair<int, int>>, vector<pair<float, pair<int, int>>>, greater<pair<float, pair<int, int>>> > vdist_que;
vector<vector<float>> vdist(102);
vector<vector<pair<int, int>>> vfrom(102);
vector<vector<int>> area_from(102);
for (int itmp = 0; itmp < 100; itmp++) {
vdist[itmp].resize(mesh_num, (float)InfL);
vfrom[itmp].resize(mesh_num, make_pair(-1, -1));
area_from[itmp].resize(mesh_num, -1);
}
vdist[100].resize(N, (float)InfL);
vfrom[100].resize(N, make_pair(-1, -1));
area_from[100].resize(N, -1);
vdist[101].resize(M, (float)InfL);
vfrom[101].resize(M, make_pair(-1, -1));
area_from[101].resize(M, -1);
pair<int, int> vbegin = make_pair(100, i); // 探索開始の特徴点=初期位置
vdist[vbegin.first][vbegin.second] = (float)0.0;
vdist_que.push(make_pair((float)0.0, vbegin));
while (!vdist_que.empty()) {
pair<float, pair<int, int>> vdist_que_tmp = vdist_que.top();
vdist_que.pop();
float dist_tmp = vdist_que_tmp.first;
pair<int, int> vtmp = vdist_que_tmp.second;
if (vdist[vtmp.first][vtmp.second] < dist_tmp) continue;
if (vtmp.first == 100 && vtmp.second != i) continue; // 開始位置にない巻物からは移動しない
Vector2 vectmp = v_to_vec[vtmp.first][vtmp.second];
for (auto vnew_list : v_adjlist[vtmp.first][vtmp.second]) {
pair<int, int> vnew = vnew_list.first;
int idx = vnew_list.second;
if (area_from[vtmp.first][vtmp.second] == idx) continue; // 連続して同じエリアを経由する意味はないので刈る
Vector2 vecnew = v_to_vec[vnew.first][vnew.second];
if (vectmp.x == vecnew.x) {
float frac_x = modf_(vectmp.x);
if (frac_x < eeps || frac_x >(float)1.0 - eeps) continue; // 境界線に沿う移動は禁止
}
if (vectmp.y == vecnew.y) {
float frac_y = modf_(vectmp.y);
if (frac_y < eeps || frac_y >(float)1.0 - eeps) continue; // 境界線に沿う移動は禁止
}
int ter_old = -1;
if (area_from[vtmp.first][vtmp.second] != -1)
ter_old = UF_ter[area_from[vtmp.first][vtmp.second]];
float dist_new = dist_tmp + Vec_dist_ter(vectmp, vecnew, UF_ter[idx], ter_old, n);
if (vdist[vnew.first][vnew.second] > dist_new) {
vdist[vnew.first][vnew.second] = dist_new;
vfrom[vnew.first][vnew.second] = vtmp;
if (vnew.first == 101)
area_from[vnew.first][vnew.second] = -1; // L字外部点を移動している間は同じエリアでもよい
else
area_from[vnew.first][vnew.second] = idx;
vdist_que.push(make_pair(dist_new, vnew));
}
}
}
// 巻物間の最短経路のパスを整理
for (int j = 0; j < N - 1; j++) {
if (i == j) continue;
pair<int, int> vend = make_pair(100, j); // 巻物
dist[i][j][n] = vdist[vend.first][vend.second];
pair<int, int> vtmp = vend; // 開始位置の巻物除く
while (1) {
if (vtmp == vbegin) break;
dist_min_path[i][j][n].push_back(vtmp);
vtmp = vfrom[vtmp.first][vtmp.second];
}
reverse(dist_min_path[i][j][n].begin(), dist_min_path[i][j][n].end());
}
}
}
// ---------- 2. 次に、初期位置から全ての巻物を取る最短経路を求める ----------
// 巡回セールスマン問題
vector<int> dist_min_PATH; // 最短経路の場合の巻物順
if (N < 17) {
// 厳密解法 (計算量 : N^2*2^N)
int B = pow2[N];
vector<vector<float>> dist_min(B);
vector<vector<int>> dist_min_prev(B);
for (int b = 0; b < B; b++) {
dist_min[b].resize(N, (float)InfL);
dist_min_prev[b].resize(N);
}
dist_min[B / 2][N - 1] = (float)0.0;// 初期位置のみ
dist_min_prev[B / 2][N - 1] = -1;// 初期位置のみ
for (int b = B / 2; b < B; b++) {
vector<bool> in(N); // 追加前に経由したか(初期位置含む)
int n = 0;
for (int i = 0; i < N; i++) {
in[i] = (b >> i) % 2;
n += in[i];
}
for (int iprev = 0; iprev < N; iprev++) {
if (!in[iprev]) continue;
for (int inext = 0; inext < N; inext++) {
if (in[inext]) continue;
// [N-1 ?...? iprev] + [inext]
float dist_new = dist_min[b][iprev] + dist[iprev][inext][n - 1];
int b_new = b + pow2[inext];
if (dist_min[b_new][inext] > dist_new) {
dist_min[b_new][inext] = dist_new;
dist_min_prev[b_new][inext] = iprev;
}
}
}
}
float dist_min_all = (float)InfL;
int dist_min_i = 0;
for (int i = 0; i < N; i++) {
if (dist_min_all > dist_min[B - 1][i]) {
dist_min_all = dist_min[B - 1][i];
dist_min_i = i;
}
}
// 巻物の順序を整理
int itmp = dist_min_i;
int btmp = B - 1;
while (1) {
dist_min_PATH.push_back(itmp);
int itmptmp = itmp;
itmp = dist_min_prev[btmp][itmp];
if (itmp == -1) break;
btmp -= pow2[itmptmp];
}
reverse(dist_min_PATH.begin(), dist_min_PATH.end());
}
else {
// 近似解法, 焼きなましを利用
time_ini = clock();
vector<bool> n_visited(N, false);
n_visited[N - 1] = true;
dist_min_PATH.push_back(N - 1);
// 初期解生成
for (int n = 0; n < N - 1; n++) {
float dist_min_tmp = (float)InfL;
int dist_min_tmp_n = 0;
for (int ntmp = 0; ntmp < N - 1; ntmp++) {
if (n_visited[ntmp]) continue;
if (dist_min_tmp > dist[dist_min_PATH[n]][ntmp][n]) {
dist_min_tmp = dist[dist_min_PATH[n]][ntmp][n];
dist_min_tmp_n = ntmp;
}
}
dist_min_PATH.push_back(dist_min_tmp_n);
n_visited[dist_min_tmp_n] = true;
}
float dist_min = 0;
for (int n = 0; n < N - 1; n++) {
int i = dist_min_PATH[n];
int j = dist_min_PATH[n + 1];
dist_min += dist[i][j][n];
}
// 焼きなまし
double start_temp = 10.0;
double end_temp = 0.2;
double TIME_LIMIT = 150.0;
double time_now;
double temp;
while (1) {
time_now = time_diff();
if (time_now > TIME_LIMIT) break;
temp = start_temp + (end_temp - start_temp) * time_now / TIME_LIMIT;
for (int p = 0; p < 10000; p++) {
vector<int> dist_min_PATH_tmp = dist_min_PATH;
if (p % 4 == 0) {
// swap
int i_from = xor128() % (N - 1) + 1;
int i_to = xor128() % (N - 1) + 1;
if (i_from == i_to) continue;
swap(dist_min_PATH_tmp[i_from], dist_min_PATH_tmp[i_to]);
}
else if (p % 4 == 1) {
// insert
int i_from = xor128() % (N - 1) + 1;
int n = dist_min_PATH_tmp[i_from];
dist_min_PATH_tmp.erase(dist_min_PATH_tmp.begin() + i_from);
int i_to = xor128() % (N - 1) + 1;
dist_min_PATH_tmp.insert(dist_min_PATH_tmp.begin() + i_to, n);
}
else if (p % 4 == 2) {
// area swap
int i_from = xor128() % (N - 1) + 1;
int i_to = xor128() % (N - 1) + 1;
int len = xor128() % (N - 1) + 1;
if (i_from + len > i_to) continue;
if (i_to + len > N) continue;
for (int n = 0; n < len; n++)
swap(dist_min_PATH_tmp[i_from + n], dist_min_PATH_tmp[i_to + n]);
}
else if (p % 4 == 3) {
// reverse
int i_from = xor128() % (N - 1) + 1;
int i_to = xor128() % (N - 1) + 1;
if (i_from >= i_to) continue;
reverse(dist_min_PATH_tmp.begin() + i_from, dist_min_PATH_tmp.begin() + i_to + 1);
}
float dist_min_tmp = (float)0.0;
for (int n = 0; n < N - 1; n++) {
int i = dist_min_PATH_tmp[n];
int j = dist_min_PATH_tmp[n + 1];
dist_min_tmp += dist[i][j][n];
}
double prob = exp((double)(dist_min - dist_min_tmp) / temp);
if (prob > RAND_()) {
dist_min = dist_min_tmp;
dist_min_PATH = dist_min_PATH_tmp;
}
}
}
}
// ---------- 3. 最後に、巻物間の特徴点をずらすor削除することで移動回数を最小化する ----------
// 中継点(i, j)の抽出 1つの特徴点を、座標が微妙に異なる100個程度の中継点に分割(中継点のいずれか1つを経由orスキップ)
// 添字iが等しい場合,元の特徴点も同じである
// 特徴点間の移動のときと同様、中継点間の移動も直線である
int mesh_size_half = 5; // 5
mesh_size = mesh_size_half * 2 + 1; // 11(=奇数)
int idx_max = mesh_size_half * (mesh_size + 1);
float coef = (float)2.0 / (float)idx_max;
float jump_power = 1.0;
vector<float> jump_power_list;
vector<vector<Vector2>> vec_list;
vector<vector<int>> dist_min_list;
vector<vector<pair<int, int>>> v_from_list;
vector<pair<int, int>> v_list;
vector<Vector2> vec_list_tmp;
vec_list_tmp.push_back(vec_init);
vec_list.push_back(vec_list_tmp);
v_list.push_back(make_pair(100, N - 1));
float jump_power_prev = 1.0;
jump_power_list.push_back((float)1.0);
for (int n = 0; n < N - 1; n++) {
int i = dist_min_PATH[n];
int j = dist_min_PATH[n + 1];
vector<pair<int, int>> vlist = dist_min_path[i][j][n];
float jump_power_tmp = pow1_1[n];
for (pair<int, int> vtmp : vlist) {
vec_list_tmp.clear();
v_list.push_back(vtmp);
Vector2 vec0 = v_to_vec[vtmp.first][vtmp.second];
if (vtmp.first < 50) {
// x軸と平行の境界線上の特徴点 : y成分はわずかに高速の地形側に変動し、
// x成分は(-最大ジャンプ幅~最大ジャンプ幅)変動したものを中継点とする
// この場合、境界線からわずかに高速の地形側に動いた点で曲がるか、
// スキップするのが最適である
Vector2 vec_m = vec0, vec_p = vec0;
vec_m.y -= eps;
vec_p.y += eps;
auto ter_m = aStage.terrain(vec_m);
auto ter_p = aStage.terrain(vec_p);
Vector2 vec1 = ((int)ter_m < (int)ter_p) ? vec_m : vec_p;
Vector2 vec1_dual = ((int)ter_m < (int)ter_p) ? vec_p : vec_m;
auto ter1 = aStage.terrain(vec1);
auto ter1_dual = aStage.terrain(vec1_dual);
float jump_dist = jump_power_tmp * max(ter_to_sp[(int)ter1], ter_to_sp[(int)ter1_dual]);
for (int xdiff = -idx_max; xdiff <= idx_max; xdiff++) {
Vector2 vecnew = vec1;
Vector2 vecnew_dual = vec1_dual;
vecnew.x += (float)xdiff * jump_dist * coef;
vecnew_dual.x += (float)xdiff * jump_dist * coef;
// フィールド外になっていたり地形が変化していたりした場合は刈る
if (!Vec_in(vecnew) || !Vec_in(vecnew_dual)) continue;
if (ter1 != aStage.terrain(vecnew)) continue;
if (ter1_dual != aStage.terrain(vecnew_dual)) continue;
vec_list_tmp.push_back(vecnew);
}
}
else if (vtmp.first < 100) {
// y軸と平行の境界線上の特徴点 : x成分はわずかに高速の地形側に変動し、
// y成分は(-最大ジャンプ幅~最大ジャンプ幅)変動したものを中継点とする
Vector2 vec_m = vec0, vec_p = vec0;
vec_m.x -= eps;
vec_p.x += eps;
auto ter_m = aStage.terrain(vec_m);
auto ter_p = aStage.terrain(vec_p);
Vector2 vec1 = ((int)ter_m < (int)ter_p) ? vec_m : vec_p;
Vector2 vec1_dual = ((int)ter_m < (int)ter_p) ? vec_p : vec_m;
auto ter1 = aStage.terrain(vec1);
auto ter1_dual = aStage.terrain(vec1_dual);
float jump_dist = jump_power_tmp * max(ter_to_sp[(int)ter1], ter_to_sp[(int)ter1_dual]);
for (int ydiff = -idx_max; ydiff <= idx_max; ydiff++) {
Vector2 vecnew = vec1;
Vector2 vecnew_dual = vec1_dual;
vecnew.y += (float)ydiff * jump_dist * coef;
vecnew_dual.y += (float)ydiff * jump_dist * coef;
// フィールド外になっていたり地形が変化していたりした場合は刈る
if (!Vec_in(vecnew) || !Vec_in(vecnew_dual)) continue;
if (ter1 != aStage.terrain(vecnew)) continue;
if (ter1_dual != aStage.terrain(vecnew_dual)) continue;
vec_list_tmp.push_back(vecnew);
}
}
else if (vtmp.first == 100) {
mesh_size_half = 11; // 11
mesh_size = mesh_size_half * 2 + 1; // 23(=奇数)
// 巻物中心の特徴点 : 中心から絶対値(0.5,0.5)の範囲で変動するが、
// 特に隣マスの辺付近を経由するのが最短となるパターンが多いのでそのときだけ例外処理
for (int xdiff = -mesh_size_half; xdiff <= mesh_size_half; xdiff++) {
for (int ydiff = -mesh_size_half; ydiff <= mesh_size_half; ydiff++) {
// 辺付近に集中させる
if (abs(xdiff) != mesh_size_half && abs(ydiff) != mesh_size_half) {
if (abs(xdiff) % 2 || abs(ydiff) % 2) continue;
}
Vector2 vecnew = vec0;
// 辺付近なので例外処理
if (xdiff == -mesh_size_half) vecnew.x -= (float)0.4999;
else if (xdiff == mesh_size_half) vecnew.x += (float)0.4999;
else vecnew.x += (float)xdiff / (float)mesh_size;
// 辺付近なので例外処理
if (ydiff == -mesh_size_half) vecnew.y -= (float)0.4999;
else if (ydiff == mesh_size_half) vecnew.y += (float)0.4999;
else vecnew.y += (float)ydiff / (float)mesh_size;
if (!Vec_in(vecnew)) continue;
vec_list_tmp.push_back(vecnew);
}
}
mesh_size_half = 5; // 5
mesh_size = mesh_size_half * 2 + 1; // 11(=奇数)
}
else if (vtmp.first == 101) {
// L字外部点 : L字型に変動
// この場合、L字型を形成する境界線からわずかに高速の地形側に動いた点(x,y軸平行のうち片側or両側)で曲がるか、
// ともにスキップするのが最適である
// 元の特徴点と同じ座標
vec_list_tmp.push_back(vec0);
// 特徴点からx成分のみ変動した中継点
float frac_x = modf_(vec0.x);
float frac_y = modf_(vec0.y);
auto ter = aStage.terrain(vec0); // L字型(速い方)の地形
Vector2 vec1 = vec0;
if (frac_x > (float)0.5)
vec1.x += (float)0.5;
else
vec1.x -= (float)0.5;
if (frac_y > (float)0.5)
vec1.y += (float)0.5;
else
vec1.y -= (float)0.5;
auto ter_dual = aStage.terrain(vec1); // 間(遅い方)の地形
for (int xdiff = 1; xdiff <= idx_max / 2; xdiff++) {
Vector2 vecnew = vec0;
if (frac_x > (float)0.5)
vecnew.x += (float)xdiff / (float)mesh_size;
else
vecnew.x -= (float)xdiff / (float)mesh_size;
if (!Vec_in(vecnew)) continue;
Vector2 vecnew_dual = vecnew;
if (frac_y > (float)0.5)
vecnew_dual.y += (float)0.5;
else
vecnew_dual.y -= (float)0.5;
// 境界線上の特徴点のときと同様の処理
if (!Vec_in(vecnew_dual)) continue;
if (ter != aStage.terrain(vecnew)) continue;
if (ter_dual != aStage.terrain(vecnew_dual)) continue;
vec_list_tmp.push_back(vecnew);
}
// L字外部点に限り、2回曲がるパターンを考慮し中継点を二重化する
v_list.push_back(vtmp);
vec_list.push_back(vec_list_tmp);
jump_power_list.push_back(jump_power_prev);
vec_list_tmp.clear();
// 特徴点からy成分のみ変動した中継点
for (int ydiff = 1; ydiff <= idx_max / 2; ydiff++) {
Vector2 vecnew = vec0;
if (frac_y > (float)0.5)
vecnew.y += (float)ydiff / (float)mesh_size;
else
vecnew.y -= (float)ydiff / (float)mesh_size;
if (!Vec_in(vecnew)) continue;
Vector2 vecnew_dual = vecnew;
if (frac_x > (float)0.5)
vecnew_dual.x += (float)0.5;
else
vecnew_dual.x -= (float)0.5;
// 境界線上の特徴点のときと同様の処理
if (!Vec_in(vecnew_dual)) continue;
if (ter != aStage.terrain(vecnew)) continue;
if (ter_dual != aStage.terrain(vecnew_dual)) continue;
vec_list_tmp.push_back(vecnew);
}
}
vec_list.push_back(vec_list_tmp);
jump_power_list.push_back(jump_power_prev);
}
jump_power_list[(int)jump_power_list.size() - 1] *= (float)1.1;
jump_power_prev *= (float)1.1;
}
int point_len = (int)vec_list.size();
dist_min_list.resize(point_len);
v_from_list.resize(point_len);
for (int n = 0; n < point_len; n++) {
int m = (int)vec_list[n].size();
dist_min_list[n].resize(m, InfL);
v_from_list[n].resize(m, make_pair(-1, -1));
}
dist_min_list[0][0] = 1;
// 中継点間に張る有向辺(初期位置側->最終位置側)を抽出しながら、(ループがないのでダイクストラ法ではく)普通の動的計画法で初期位置から順に中継点(i, j)までの最小ジャンプ回数を求める
// 遷移元 : ある特徴点, 遷移先 : 1~4つ先の特徴点, 遷移式 : 遷移元のすべての中継点から遷移先のすべての中継点に直線移動し、ジャンプ回数の差分を求める
for (int n = 0; n < point_len - 1; n++) {
for (int path_skip = 1; path_skip <= 4; path_skip++) {
// path_skip : 中継点の最大スキップ数(ただしジャンプ元含む)
if (n + path_skip >= point_len) break;
int size_from = (int)vec_list[n].size();
int size_to = (int)vec_list[n + path_skip].size();
for (int n_from = 0; n_from < size_from; n_from++) {
Vector2 vec_from = vec_list[n][n_from];
int dist_min_from = dist_min_list[n][n_from];
for (int n_to = 0; n_to < size_to; n_to++) {
Vector2 vec_to = vec_list[n + path_skip][n_to];
// 中継点(n, n_from)から中継点(n+ path_skip, n_to)へ移動
Vector2 vec_tmp = vec_from;
int dist_tmp = 0; // ジャンプ回数
while (1) {
if (Vec_eq(vec_tmp, vec_to)) break;
Vector2 vec_next = aStage.getNextPos(vec_tmp, jump_power_list[n], vec_to);
dist_tmp++;
if (dist_min_list[n + path_skip][n_to] <= dist_min_from + dist_tmp) {
dist_tmp = InfL;
break;
}
vec_tmp = vec_next;
}
if (dist_min_list[n + path_skip][n_to] > dist_min_from + dist_tmp) {
dist_min_list[n + path_skip][n_to] = dist_min_from + dist_tmp;
v_from_list[n + path_skip][n_to] = make_pair(n, n_from);
}
}
}
if (v_list[n + path_skip].first == 100)
break; // 巻物はスキップ禁止
}
}
// ターン毎に出力するコマンドを求める
jump_power = 1.0;
vector<Vector2> dist_min_path_all;
vector<int> not_skip_list;
int dist_min_all = InfL;
Vector2 dist_min_vec;
int dist_min_k = 0;
for (int k = 0; k < (int)dist_min_list[point_len - 1].size(); k++) {
if (dist_min_all > dist_min_list[point_len - 1][k]) {
dist_min_all = dist_min_list[point_len - 1][k];
dist_min_vec = vec_list[point_len - 1][k];
dist_min_k = k;
}
}
Vector2 vec_joint = dist_min_vec;
pair<int, int> v_ij = make_pair(point_len - 1, dist_min_k);
not_skip_list.push_back(point_len - 1); // 例 : skipした経由地が2,5,6,8...のとき,not_skip_list[0]=0,[1]=1,[2]=3,[3]=4,[4]=7,[5]=9,...
while (1) {
// 最終位置から初期位置に向かって経由した中継点を遡る
if (v_ij.first == -1) break;
vec_joint = vec_list[v_ij.first][v_ij.second];
dist_min_path_all.push_back(vec_joint);
not_skip_list.push_back(v_ij.first);
v_ij = v_from_list[v_ij.first][v_ij.second];
}
reverse(dist_min_path_all.begin(), dist_min_path_all.end());
reverse(not_skip_list.begin(), not_skip_list.end());
jump_power = 1.0;
// 中継点間の経路を求める
for (int n = 0; n < (int)dist_min_path_all.size() - 1; n++) {
int n_without_skip = not_skip_list[n];
if (v_list[n_without_skip].first == 100 && v_list[n_without_skip].second != N - 1)
jump_power *= (float)1.1;
Vector2 vec_from = dist_min_path_all[n];
Vector2 vec_to = dist_min_path_all[n + 1];
Vector2 vectmp = vec_from;
while (1) {
if (Vec_eq(vectmp, vec_to)) break;
commands.push_back(vec_to);
vectmp = aStage.getNextPos(vectmp, jump_power, vec_to);
}
}
}
//------------------------------------------------------------------------------
/// 毎フレーム呼び出される処理
/// @detail 移動先を決定して返します
/// @param aStage 現在のステージ
/// @return 移動の目標座標
Vector2 Answer::getTargetPos(const Stage& aStage)
{
return commands[turn_sum++];
}
//------------------------------------------------------------------------------
/// 各ステージ終了時に呼び出される処理
/// @detail 各ステージに対する終了処理が必要ならここに書きます
/// @param aStage 現在のステージ
void Answer::finalize(const Stage& aStage)
{
commands.clear();
}
} // namespace
// EOF