//------------------------------------------------------------------------------
/// @file
/// @author ハル研究所プログラミングコンテスト実行委員会
///
/// @copyright (C)HAL Laboratory, Inc.
/// @attention このファイルの利用は、同梱のREADMEにある
/// 利用条件に従ってください。
//------------------------------------------------------------------------------
#include "Answer.hpp"
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <chrono>
#include <complex>
#include <limits>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <fstream>
#include <iostream>
#include <sstream>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
// #define NDEBUG
#include <cassert>
#ifdef _MSC_VER // ローカル環境
#define INLINE inline
bool debug = true;
#else // サーバー環境
#define INLINE inline __attribute__((always_inline))
bool debug = false;
#endif
using namespace std;
using ull = unsigned long long;
using ll = long long;
using pii = pair<int, int>;
using pdi = pair<double, int>;
using pfi = pair<float, int>;
#define len(c) (int) (c.size())
#define rep(i, from, until) for (int i = (from); i < (until); i++)
#define repr(i, from, until) for (int i = (until) - 1; i >= (from); i--)
#define rep0(i, until) rep(i, 0, until)
#define rep0r(i, until) repr(i, 0, until)
#define clamp(a, minimum, maximum) min(max(a, (minimum)), (maximum))
constexpr float PI = 3.14159265358979323846f;
constexpr float TWO_PI = 2.0f * PI;
constexpr float HALF_PI = 0.5f * PI;
class Rnd {
public:
Rnd() : y(135272729) {
}
void seed(int y) {
this->y = y;
}
int next() {
y = y ^ (y << 13); y = y ^ (y >> 17);
return (y = y ^ (y << 15)) & 0x7fffffff;
}
private:
int y;
};
Rnd rnd;
inline void seed(int y) {
rnd.seed(y);
}
inline int nextInt() {
return rnd.next();
}
inline int nextInt(int n) {
return rnd.next() % n;
}
inline float nextFloat() {
return (float) rnd.next() / 0x80000000;
}
inline float nextFloat(float min, float max) {
return min + nextFloat() * (max - min);
}
inline double nextDouble() {
return (double) rnd.next() / 0x80000000;
}
inline double nextDouble(double min, double max) {
return min + nextDouble() * (max - min);
}
void tracen() {
}
template <class Head, class... Tail>
void tracen(Head&& head, Tail&&... tail) {
if (!debug) return;
cerr << head;
tracen(forward<Tail>(tail)...);
}
template <class... Tail>
void trace(Tail&&... tail) {
if (!debug) return;
tracen(forward<Tail>(tail)...);
cerr << endl;
}
template <class Iter, class Map>
void tracein(Iter from, Iter until, Map f) {
if (!debug) return;
bool first = true;
while (from != until) {
if (first) {
first = false;
} else {
cerr << ", ";
}
cerr << f(*from);
from++;
}
}
template <class Iter, class Map>
void tracei(Iter from, Iter until, Map f) {
if (!debug) return;
tracein(from, until, f);
cerr << endl;
}
template <class Iter>
void tracein(Iter from, Iter until) {
tracein(from, until, [](decltype(*from) x) { return x; });
}
template <class Iter>
void tracei(Iter from, Iter until) {
tracei(from, until, [](decltype(*from) x) { return x; });
}
void segv() {
volatile int* a = nullptr;
*a = 0;
}
// return in ms
int timer(bool reset = false) {
static auto st = chrono::system_clock::now();
if (reset) {
st = chrono::system_clock::now();
return 0;
} else {
auto en = chrono::system_clock::now();
int elapsedTotal = (int) chrono::duration_cast<chrono::milliseconds>(en - st).count();
return elapsedTotal;
}
}
//------------------------------------------------------------------------------
namespace hpc {
constexpr int MAX_SCROLLS = Parameter::MaxScrollCount;
constexpr int FIELD_SIZE = Parameter::StageWidth;
constexpr float FIELD_SIZE_F = (float) FIELD_SIZE;
constexpr int MAX_OBJECTS = MAX_SCROLLS + 1;
constexpr int GRAPH_SIZE = FIELD_SIZE + 1;
constexpr int GRAPH_MAX_VERtICES = GRAPH_SIZE * GRAPH_SIZE + 100;
using vec2 = Vector2;
// 最終的に考慮する浮動小数点誤差
constexpr float EPS = 1e-6f;
// 誤差で消滅しないような小さい値
constexpr float DELTA = 1e-5f;
inline bool operator==(const vec2& a, const vec2& b) {
return a.x == b.x && a.y == b.y;
}
inline vec2 operator+(const vec2& a, const vec2& b) {
return vec2(a.x + b.x, a.y + b.y);
}
inline void operator+=(vec2& a, const vec2& b) {
a.x += b.x;
a.y += b.y;
}
inline void operator-=(vec2& a, const vec2& b) {
a.x -= b.x;
a.y -= b.y;
}
inline vec2 operator-(const vec2& a, const vec2& b) {
return vec2(a.x - b.x, a.y - b.y);
}
inline vec2 operator*(const vec2& a, const vec2& b) {
return vec2(a.x * b.x, a.y * b.y);
}
inline vec2 operator*(const vec2& a, float b) {
return vec2(a.x * b, a.y * b);
}
inline vec2 operator*(float a, const vec2& b) {
return vec2(a * b.x, a * b.y);
}
inline float length(const vec2& a) {
return sqrt(a.x * a.x + a.y * a.y);
}
inline float dot(const vec2& a, const vec2& b) {
return a.x * b.x + a.y * b.y;
}
inline float distance(const vec2& a, const vec2& b) {
return length(a - b);
}
// index を 0 以上 50 未満に射影する
constexpr int boundIndex(int index) {
return index < 0 ? 0 : index > FIELD_SIZE - 1 ? FIELD_SIZE - 1 : index;
}
// pos がステージ外を示さないようにする
vec2 boundPosition(const vec2& pos) {
return vec2(clamp(pos.x, DELTA, FIELD_SIZE_F - DELTA), clamp(pos.y, DELTA, FIELD_SIZE_F - DELTA));
}
// pos が cell と同じマス目から出ないようにする
vec2 boundPositionInCell(const vec2& pos, const vec2& cell) {
float cx = (float) (int) cell.x;
float cy = (float) (int) cell.y;
return vec2(clamp(pos.x, cx + DELTA, cx + 1.0f - DELTA), clamp(pos.y, cy + DELTA, cy + 1.0f - DELTA));
}
// 目標着地点をジャンプ可能範囲かつステージからはみ出ない範囲に射影する
vec2 limitTarget(const vec2& pos, vec2 target, float maxLength) {
target = boundPosition(target);
vec2 diff = target - pos;
float dist = length(diff);
if (dist > maxLength - EPS) {
target = pos + diff * ((maxLength - EPS) / dist);
}
return target;
}
// ステージに関する情報
class St {
public:
// ジャンプ距離にかかる係数
float jumpCoeffs[FIELD_SIZE][FIELD_SIZE] = {};
// ジャンプ距離にかかる係数の逆数
float invJumpCoeffs[FIELD_SIZE][FIELD_SIZE] = {};
// 巻物の位置
vec2 spos[MAX_SCROLLS];
// 巻物の個数
int n;
// ウサギの位置
vec2 rpos;
// ステージのインデックス
int index;
St() : n(0), index(-1) {
}
// 最もジャンプ効率の良い場所を返す
// 複数存在する場合は最初の場所を返す
vec2 selectBestPos(const vec2* poss, int n) const {
float best = jumpCoeffAt(poss[0]);
int bestI = 0;
rep(i, 1, n) {
float coeff = jumpCoeffAt(poss[i]);
if (coeff > best) {
best = coeff;
bestI = i;
}
}
return poss[bestI];
}
// 境界上の頂点を移動効率の良い側に摂動させる
// さらにジャンプ可能距離制限を考慮する
// 座標がチェビシェフ距離で最大 DELTA だけ変化する
vec2 pertubateLimitedTarget(const vec2& pos, const vec2& target, float maxLength) const {
// 0---1
// | |
// 3---2
vec2 ts[5] = {
boundPosition(target),
limitTarget(pos, target + vec2(-DELTA, -DELTA), maxLength),
limitTarget(pos, target + vec2(DELTA, -DELTA), maxLength),
limitTarget(pos, target + vec2(DELTA, DELTA), maxLength),
limitTarget(pos, target + vec2(-DELTA, DELTA), maxLength),
};
return selectBestPos(ts, 5);
}
// 境界上の頂点を移動効率の良い側に摂動させる
// 座標がチェビシェフ距離で最大 DELTA だけ変化する
vec2 pertubateUnlimitedTarget(const vec2& target) const {
// 0---1
// | |
// 3---2
vec2 ts[5] = {
boundPosition(target),
boundPosition(target + vec2(-DELTA, -DELTA)),
boundPosition(target + vec2(DELTA, -DELTA)),
boundPosition(target + vec2(DELTA, DELTA)),
boundPosition(target + vec2(-DELTA, DELTA)),
};
return selectBestPos(ts, 5);
}
// 同一のマスにあるか判定する
bool onSameCell(const vec2& p1, const vec2& p2) const {
return (int) p1.x == (int) p2.x && (int) p1.y == (int) p2.y;
}
// 始点から終点への移動が同一の地質内で完結するか判定する
// ただし、終点は始点と終点を結ぶ線分に含まれないものとする
bool onSameTerrain(const vec2& from, const vec2& to, bool pertubate) const {
int divs = (int) ceil(distance(from, to) / 0.2f + EPS);
float coeff = -1;
rep0(i, divs) {
float t = (float) i / divs;
vec2 p = from + t * (to - from);
if (pertubate) {
p = pertubateUnlimitedTarget(p);
}
float newCoeff = jumpCoeffAt(p);
if (coeff == -1) {
coeff = newCoeff; // 最初のジャンプ係数を記録
} else {
if (coeff != newCoeff) {
return false; // 異なる地質を跨いでいるので NG
}
}
}
return true;
}
// p1 から p2 へのジャンプ係数を考慮した距離を計算する
// ただし、p1 から p2 へと繋ぐ線分の内部は同一の地質に含まれているとする
float estimateEdgeWeight(const vec2& p1, const vec2& p2, float jumpPower) const {
float totalDist = distance(p1, p2);
if (totalDist < EPS) return 0.0f;
float jumpDistStart = jumpCoeffAt(p1) * jumpPower;
float jumpDistMid = jumpCoeffAt(pertubateUnlimitedTarget(p1 + (p2 - p1) * (0.5f / totalDist))) * jumpPower; // 始点から 0.5 マス進んだ点を摂動する
// 最初のジャンプだけ p1 地点の地質を用いる
float firstJumpDist = jumpDistStart;
float restJumpDist = totalDist - firstJumpDist;
if (restJumpDist < 0) {
firstJumpDist = totalDist;
restJumpDist = 0;
}
float count = firstJumpDist / jumpDistStart + restJumpDist / jumpDistMid;
return count;
}
inline float jumpCoeffAt(const vec2& pos) const {
return jumpCoeffs[(int) pos.x][(int) pos.y];
}
};
// 出力可能な解
class Solution {
public:
vector<vec2> targets;
// verify 後に利用可能
int numLandings;
vector<vec2> landPositions;
vector<bool> getScrollOnLand;
Solution() : numLandings(0) {
}
// 浮動小数点誤差によって実行不可能になっていないか調べる
bool verify(const St& s) {
bool scrollsMap[FIELD_SIZE][FIELD_SIZE] = {};
int scrollGotCount = 0;
landPositions.clear();
getScrollOnLand.clear();
numLandings = 0;
rep0(i, s.n) {
scrollsMap[(int) s.spos[i].x][(int) s.spos[i].y] = true;
}
// ジャッジプログラムと同じ方法で着地点列を生成する
vec2 pos = s.rpos;
int n = len(targets);
float jumpPower = 1.0f;
rep0(i, n) {
vec2 target = targets[i];
vec2 diff = target - pos;
float maxDist = jumpPower * s.jumpCoeffAt(pos);
float dist = length(diff);
if (dist > maxDist) {
target = pos + diff * (maxDist / dist);
}
pos = target;
landPositions.push_back(pos);
int ix = (int) pos.x;
int iy = (int) pos.y;
if (scrollsMap[ix][iy]) {
getScrollOnLand.push_back(true);
scrollGotCount++;
scrollsMap[ix][iy] = false;
jumpPower *= 1.1f;
} else {
getScrollOnLand.push_back(false);
}
}
numLandings = len(landPositions);
if (scrollGotCount < s.n) {
// 取った巻物の数が足りない
// 浮動小数点数
// ↓
// バコォッ (´･_･`)
// |∧ 从ノ (ミ＿（⌒＼ヽ
// （,,(≡￣￣￣￣三＼⌒ノノ）
// |(つWつ￣￣＼ ⌒彡) ノ
// |＼つ-つ ＼＿＿,ﾉノ
// || つ / ／
// || /ノ ＿─(´⌒(
return false;
}
return true;
}
};
// パス上の頂点の種類
enum class VType {
// 無効な点
Invalid,
// 開始点
Rabbit,
// 中間の転回ポイント
Intermediate,
// 巻物取得ポイント
Scroll
};
// ウサギまたはいずれかの巻物を表す型
class Obj {
public:
int index;
constexpr Obj() : index(-1) {
}
constexpr static Obj invalid() {
return Obj(-1);
}
constexpr static Obj rabbit() {
return Obj(0);
}
constexpr static Obj scroll(int scrollIndex) {
return Obj(scrollIndex + 1);
}
constexpr static Obj fromIndex(int index) {
return Obj(index);
}
private:
constexpr Obj(int index) : index(index) {
}
};
// ステージ上のオブジェクト（ウサギ or 巻物）を添え字とする配列
template<typename T>
class ObjArray {
public:
ObjArray() : array() {
}
T& operator[](Obj obj) {
return array[obj.index];
}
const T& operator[](Obj obj) const {
return array[obj.index];
}
private:
T array[MAX_OBJECTS];
};
// グラフの辺
class GraphE {
public:
int to;
float cost;
GraphE(int to, float cost) : to(to), cost(cost) {
}
};
bool operator<(const GraphE& lhs, const GraphE& rhs) {
return lhs.to < rhs.to;
}
// グラフの頂点
class GraphV {
public:
int index;
VType type;
vec2 pos;
vector<GraphE> edges;
GraphV() :index(-1), type(VType::Invalid) {
}
void init(VType type, const vec2& pos) {
this->type = type;
this->pos = pos;
edges.clear();
}
};
// 有向グラフ
class Graph {
public:
static constexpr int SIZE = FIELD_SIZE + 1;
static constexpr int MAX_VERTICES = SIZE * SIZE + 100;
GraphV vs[MAX_VERTICES];
int n;
Graph() : n(0) {
rep0(i, MAX_VERTICES) {
vs[i].index = i;
}
}
int addVertex(VType type, const vec2& pos) {
vs[n].init(type, pos);
return n++;
}
void addEdge(int from, int to, float cost, float costBack) {
// 順向き
vs[from].edges.push_back(GraphE(to, cost));
// 逆向き
vs[to].edges.push_back(GraphE(from, costBack));
}
void clear() {
rep0(i, n) {
auto& v = vs[i];
v.init(VType::Invalid, vec2());
}
n = 0;
}
// デバッグ用にSVG形式で出力する
void dumpSvg(const float* vertexColors) const {
float strokeWeight = 0.1f;
float pointRadius = 0.1f;
trace("\n\n\n\n<!-- begin dumping SVG -->");
trace("<svg viewBox=\"", -1, " ", -1, " ", FIELD_SIZE + 2, " ", FIELD_SIZE + 2, "\" xmlns=\"http://www.w3.org/2000/svg\">");
rep0(i, n) {
auto v1 = vs[i].pos;
for (auto& e : vs[i].edges) {
if (i > e.to) {
continue; // avoid duplications
}
auto v2 = vs[e.to].pos;
float actualDist = length(v2 - v1);
float edgeDist = e.cost;
float coeff = edgeDist / actualDist;
string color;
if (coeff < 1.1) color = "rgb(0,255,0)"; // plain
else if (coeff < 2.0) color = "rgb(0,128,0)"; // bush
else if (coeff < 4.0) color = "rgb(192,192,0)"; // sand
else color = "rgb(0,0,255)"; // pond
trace("<line x1=\"", v1.x, "\" y1=\"", v1.y, "\" x2=\"", v2.x, "\" y2=\"", v2.y, "\" stroke-width=\"", strokeWeight, "\" stroke=\"", color, "\" stroke-opacity=\"0.2\"/>");
}
int vr = 0;
int vg = 0;
int vb = 0;
if (vertexColors != nullptr) {
float ang = vertexColors[i] * 0.04f * TWO_PI;
vr = (int) ((sin(ang) * 0.5f + 0.5f) * 255.0f + 0.5f);
vg = (int) ((sin(ang - TWO_PI / 3.0f) * 0.5f + 0.5f) * 255.0f + 0.5f);
vb = (int) ((sin(ang + TWO_PI / 3.0f) * 0.5f + 0.5f) * 255.0f + 0.5f);
}
trace("<circle cx=\"", v1.x, "\" cy=\"", v1.y, "\" r=\"", pointRadius, "\" fill=\"rgb(", vr, ",", vg, ",", vb, ")\"/>");
}
trace("</svg>");
trace("<!-- end dumping SVG -->\n\n\n\n");
}
};
// ダイクストラ法の実行と結果格納
class Dijkstra {
public:
int prev[GRAPH_MAX_VERtICES];
float dists[GRAPH_MAX_VERtICES];
Dijkstra() : prev(), dists(), visited() {
}
// from からの距離を全頂点に対して計算する
void run(const Graph& g, int from) {
const int n = g.n;
const GraphV* vs = g.vs;
// 頂点の初期化
rep0(i, n) {
visited[i] = false;
dists[i] = 1e9;
prev[i] = -1;
}
dists[from] = 0;
// 全頂点をキューに追加
priority_queue<pfi, vector<pfi>, greater<pfi>> q;
rep0(i, n) {
if (len(vs[i].edges) == 0) {
// 使われていない頂点はスキップ
continue;
}
q.push(pfi(dists[i], i));
}
while (!q.empty()) {
// 距離が最小の頂点
auto top = q.top();
q.pop();
float d = top.first;
int from = top.second;
if (d > dists[from])
continue; // この要素の情報は古いのでスキップ
auto& v = vs[from];
for (auto e : v.edges) {
int to = e.to;
float d2 = d + e.cost;
if (dists[to] > d2) {
dists[to] = d2;
prev[to] = from;
q.push(pfi(d2, to)); // 要素を更新する代わりに新しい要素を入れる
}
}
}
}
private:
bool visited[GRAPH_MAX_VERtICES];
};
// パスの頂点
class PathV {
public:
vec2 pos;
VType type;
PathV() : pos(), type(VType::Invalid) {
}
PathV(const vec2& pos, VType type) : pos(pos), type(type) {
}
};
#define ONE_CASE_TEST -1 // 0 以上にすると特定のステージのみ実行する
#define DO_NOT_REFINE false // true にすると局所改善を行わない
#define DO_NOT_SIMPLIFY false // true にするとパスの頂点削減を行わない
#define MAX_TSP_ANSWERS 20 // 局所改善対象にする TSP の解の最大数
// 軌跡の折れ線による近似
class Path {
public:
vector<PathV> vs;
float estimatedDist;
int actualCount;
Path() : estimatedDist(0), actualCount(0) {
}
void clear() {
vs.clear();
estimatedDist = 0;
actualCount = 0;
}
void addVertex(const vec2& pos, VType type) {
vs.push_back(PathV(pos, type));
}
// 解を生成する
Solution generateSolution(const St& s) const {
Solution sol;
int n = len(vs);
float jumpPower = 1.0f;
int count = 0;
rep(i, 1, n) {
const vec2& ppos = vs[i - 1].pos;
const vec2& pos = vs[i].pos;
generatePoints(s, jumpPower, ppos, pos, sol.targets);
int c = measure(s, jumpPower, ppos, pos);
count += c;
if (vs[i].type == VType::Scroll) {
jumpPower *= 1.1f;
}
}
return sol;
}
// パスをSVG形式で書き出す
void dumpSvg(const St& s) const {
trace("\n\n\n<svg viewBox=\"", -1, " ", -1, " ", FIELD_SIZE + 2, " ", FIELD_SIZE + 2, "\" xmlns=\"http://www.w3.org/2000/svg\">");
rep0(i, FIELD_SIZE) {
rep0(j, FIELD_SIZE) {
string color;
float jc = s.jumpCoeffs[i][j];
if (jc < 0.2) color = "rgb(0,0,255)"; // pond
else if (jc < 0.4) color = "rgb(192,192,0)"; // sand
else if (jc < 0.7) color = "rgb(0,128,0)"; // bush
else color = "rgb(0,255,0)"; // plain
tracen("<rect x=\"", i, "\" y=\"", j, "\" width=\"1\" height=\"1\" fill=\"" + color + "\" stroke-width=\"0.02\" stroke=\"white\"/>");
}
}
trace();
for (auto& v : vs) {
trace("<circle cx=\"", v.pos.x, "\" cy=\"", v.pos.y, "\" r=\"", 0.2, "\" fill=\"white\"/>");
}
int nsol = len(vs);
rep(i, 0, nsol - 1) {
vec2 v1 = vs[i].pos;
vec2 v2 = vs[i + 1].pos;
trace("<line x1=\"", v1.x, "\" y1=\"", v1.y, "\" x2=\"", v2.x, "\" y2=\"", v2.y, "\" stroke-width=\"", 0.1, "\" stroke=\"white\"/>");
}
trace("</svg>\n\n\n");
}
// パスの頂点を削減する
void simplify(const St& s) {
vector<PathV> newVs;
float newDist = 0;
int index = 0;
int n = len(vs);
newVs.push_back(vs[0]);
// 可能な限りパスを直線で繋げる
while (index + 1 < n) {
int nextIndex = index + 1;
while (nextIndex + 1 < n) {
if (vs[nextIndex].type != VType::Intermediate) {
break; // 中間点以外はスキップしないようにする
}
if (s.jumpCoeffAt(vs[index].pos) != s.jumpCoeffAt(vs[nextIndex].pos)) {
break; // 地質を跨ぐ点はスキップしないようにする
}
nextIndex++;
if (!s.onSameTerrain(vs[index].pos, vs[nextIndex].pos, false)) {
nextIndex--;
break;
}
}
newDist += s.estimateEdgeWeight(vs[index].pos, vs[nextIndex].pos, 1.0f);
newVs.push_back(vs[nextIndex]);
index = nextIndex;
}
// 巻物のマスの移動コストを差し引く
if (vs[0].type == VType::Scroll) {
float coeff = s.jumpCoeffAt(vs[0].pos);
if (coeff < 0.2f) { // pond
newDist -= 0.5f / 0.1f - 1;
} else if (coeff < 0.4f) { // sand
newDist -= 0.5f / 0.3f - 1;
}
}
if (vs[n - 1].type == VType::Scroll) {
float coeff = s.jumpCoeffAt(vs[n - 1].pos);
if (coeff < 0.2f) { // pond
newDist -= 0.5f / 0.1f - 1;
} else if (coeff < 0.4f) { // sand
newDist -= 0.5f / 0.3f - 1;
}
}
// パスの更新
vs = newVs;
estimatedDist = newDist;
}
// 各着地点でパスを分断する
void splitAll(const St& s) {
Solution sol = generateSolution(s);
sol.verify(s);
vector<PathV> newVs;
// 開始点
newVs.push_back(PathV(s.rpos, VType::Rabbit));
// 全ての着地点をパスの頂点に追加
rep0(i, sol.numLandings) {
newVs.push_back(PathV(sol.landPositions[i], sol.getScrollOnLand[i] ? VType::Scroll : VType::Intermediate));
}
vs = newVs;
}
// 離散評価関数上でパスを最適化する
void refine(const St& s, float jumpPower, float deltaScale, bool shiftEnds, bool removeOnly) {
int n = len(vs);
vector<PathV> newVs;
newVs.reserve(n);
int actualCount = 0;
// 始点を追加する
PathV& begin = vs[0];
vec2 beginPos = begin.pos;
if (shiftEnds && begin.type == VType::Scroll) {
// 同じマス内で次の点が最も近くなる位置にずらす
beginPos = boundPositionInCell(vs[1].pos, beginPos);
}
newVs.push_back(PathV(beginPos, begin.type));
vec2 ppos = beginPos; // 一つ前の点、確定済み
rep(i, 1, n - 1) {
const VType type = vs[i].type;
const bool isIntermediate = type == VType::Intermediate;
const vec2& pos = vs[i].pos; // この点を変化させる
const vec2& npos = vs[i + 1].pos; // 一つ先の点、まだ変化させない
// 巻物を取ることが確定している場合に後半のジャンプ力を上げる
const float jumpPower2 = isIntermediate ? jumpPower : 1.1f * jumpPower;
// 現在の距離の総和を計測
vec2 lastBeforeEnd = ppos;
const int c1 = measure(s, jumpPower, ppos, pos, lastBeforeEnd);
const int c2 = measure(s, jumpPower2, pos, npos);
const int count = c1 + c2;
// pos を動かして距離を縮めようとする
constexpr int trials = 10;
// 動かす幅を一歩の大きさに合わせて決める
// --- 統計 ---
// 3.0: 24377
// 2.0: 24398
// 1.8: 24358
// 1.6: 24396
// 1.0: 24615
vec2 bestPos = pos;
int bestCount = count;
const float delta = 3.0f * jumpPower * s.jumpCoeffAt(pos) * deltaScale;
const float prevCoeff = s.jumpCoeffAt(lastBeforeEnd);
const float currentCoeff = s.jumpCoeffAt(pos);
const float radius = prevCoeff * jumpPower;
const bool shouldBound =
lastBeforeEnd.x - radius <= DELTA || lastBeforeEnd.x + radius >= FIELD_SIZE_F - DELTA ||
lastBeforeEnd.y - radius <= DELTA || lastBeforeEnd.y + radius >= FIELD_SIZE_F - DELTA;
// 縮退していたら優先的に消す
const bool forceDelete = c1 == 0 || c2 == 0;
if (isIntermediate) {
// 中間点を消してみる
int c = measure(s, jumpPower, ppos, npos, bestCount);
if (c <= bestCount) {
// 記録更新 or タイ
bestCount = c;
bestPos.x = -1; // 削除フラグ
}
} else {
// パスを一直線にできないか試してみる
vec2 p;
if (doesLandCell(s, jumpPower, ppos, npos, pos, p)) {
// パスの形状を
// ppos -> pos -> npos
// から
// ppos -> p -> npos
// に変える
int c = measure(s, jumpPower, ppos, p, bestCount);
c += measure(s, jumpPower2, p, npos, bestCount - c);
if (c <= bestCount) {
// 記録更新 or タイ
bestCount = c;
bestPos = p;
}
}
}
if (!removeOnly && !forceDelete) {
const int commonCount = measure(s, jumpPower, ppos, lastBeforeEnd, bestCount);
rep0(t, trials) {
// パスの形状を
// ppos -> pos -> npos
// から
// ppos -> lastBeforeEnd -> p -> npos
// に変える
vec2 p;
if (isIntermediate) {
p = pos + delta * vec2(nextFloat(-1, 1), nextFloat(-1, 1));
vec2 diff = p - lastBeforeEnd;
float d2 = dot(diff, diff);
// 不運にも縮退した場合
while (d2 == 0.0f) {
p = pos + delta * vec2(nextFloat(-1, 1), nextFloat(-1, 1));
diff = p - lastBeforeEnd;
d2 = dot(diff, diff);
}
float scale = radius / sqrt(d2);
p = lastBeforeEnd + diff * scale;
if (shouldBound) {
// ステージ外に出る可能性があるので制限する
p = boundPosition(p);
}
float newCoeff = s.jumpCoeffAt(p);
if (newCoeff < currentCoeff) {
// 移動することによって地質が悪化したら移動前と同じマスに制限する
p = boundPositionInCell(p, pos);
}
} else {
// このマスに巻物があるので、マスを出てはならない
p = boundPosition(pos + delta * vec2(nextFloat(-1, 1), nextFloat(-1, 1)));
p = boundPositionInCell(p, pos);
}
// パスを変化させた後のジャンプ回数
int c = commonCount;
c += measure(s, jumpPower, lastBeforeEnd, p); // どうせ 1 か 2 なので上限は設定しない
c += measure(s, jumpPower2, p, npos, bestCount - c);
if (c <= bestCount) {
// 記録更新 or タイ
bestCount = c;
bestPos = p;
}
}
}
if (bestPos == pos) {
// 変化なし
newVs.push_back(PathV(pos, type));
// pos を確定させる
ppos = pos;
actualCount += c1;
} else if (bestPos.x == -1) {
// 点をパスから消去、すなわち更新後のパスに頂点を追加しない
// 確定した一つ前の点は変わらない
} else {
// 実際のジャンプ回数の増加分
actualCount += measure(s, jumpPower, ppos, lastBeforeEnd) + measure(s, jumpPower, lastBeforeEnd, bestPos);
// 新たな中間点
newVs.push_back(PathV(lastBeforeEnd, VType::Intermediate));
// 移動後の点
newVs.push_back(PathV(bestPos, type));
// lastBeforeEnd, bestPos を確定させる
ppos = bestPos;
}
// 巻物を取ったらジャンプ力を上げる
if (!isIntermediate) {
jumpPower *= 1.1f;
}
}
// 終点を追加
PathV& end = vs[n - 1];
vec2 endPos = end.pos;
// 終点を動かして距離を縮めようとする
if (shiftEnds) {
vec2 pos = endPos;
int bestCount = measure(s, jumpPower, ppos, pos);
vec2 bestPos = pos;
int trials = 10;
rep0(t, trials) {
vec2 p;
if (t == 0) {
// 前の点に同じマス内で最も近付けるのを試す
p = boundPositionInCell(ppos, pos);
} else {
// ランダムに移動させる
float delta = 0.1f;
p = boundPositionInCell(pos + delta * vec2(nextFloat(-1, 1), nextFloat(-1, 1)), pos);
}
int c = measure(s, jumpPower, ppos, p, bestCount);
if (c <= bestCount) {
bestCount = c;
bestPos = p;
}
}
endPos = bestPos;
}
newVs.push_back(PathV(endPos, begin.type));
int lastCount = measure(s, jumpPower, ppos, endPos);
actualCount += lastCount;
vs = newVs;
this->actualCount = actualCount;
}
private:
bool doesLandCell(const St& s, float jumpPower, const vec2& begin, const vec2& end, const vec2& target, vec2& outPos) const {
constexpr float DIST_EPS = EPS * 2.0f;
constexpr float DIST_EPS_SQ = DIST_EPS * DIST_EPS;
vec2 diff = end - begin;
float l2 = dot(diff, diff);
if (l2 < DIST_EPS_SQ) {
return false;
}
float l = sqrt(l2);
float invL = 1 / l;
float leftDist = l;
vec2 n = diff * invL;
vec2 pos = begin;
do {
// 目的地に向かってジャンプする
float nextDist = jumpPower * s.jumpCoeffAt(pos);
leftDist -= nextDist;
// このジャンプで目的地に到達する
if (leftDist < DIST_EPS) {
return false;
}
// 次の位置へ
pos += nextDist * n;
// セルに到着したか？
if ((int) pos.x == (int) target.x && (int) pos.y == (int) target.y) {
outPos = pos;
return true;
}
} while (true);
}
// ジャンプ回数を数える
INLINE int measure(const St& s, float jumpPower, const vec2& begin, const vec2& end) const {
constexpr float DIST_EPS = EPS * 2.0f;
constexpr float DIST_EPS_SQ = DIST_EPS * DIST_EPS;
vec2 diff = end - begin;
float l2 = dot(diff, diff);
if (l2 < DIST_EPS_SQ) {
return 0;
}
float l = sqrt(l2);
float invL = 1 / l;
float leftDist = l;
vec2 n = diff * invL;
vec2 pos = begin;
int count = 0;
do {
count++;
// 目的地に向かってジャンプする
float nextDist = jumpPower * s.jumpCoeffAt(pos);
leftDist -= nextDist;
// このジャンプで目的地に到達する
if (leftDist < DIST_EPS) {
return count;
}
// 次の位置へ
pos += nextDist * n;
} while (true);
}
// ジャンプ回数を数える
// 最後の一つ前の着地点も出力する
INLINE int measure(const St& s, float jumpPower, const vec2& begin, const vec2& end, vec2& outLastBeforeEnd) const {
constexpr float DIST_EPS = EPS * 2.0f;
constexpr float DIST_EPS_SQ = DIST_EPS * DIST_EPS;
vec2 diff = end - begin;
float l2 = dot(diff, diff);
if (l2 < DIST_EPS_SQ) {
outLastBeforeEnd = begin;
return 0;
}
float l = sqrt(l2);
float invL = 1 / l;
float leftDist = l;
vec2 n = diff * invL;
vec2 pos = begin;
int count = 0;
do {
count++;
// 目的地に向かってジャンプする
float nextDist = jumpPower * s.jumpCoeffAt(pos);
leftDist -= nextDist;
// このジャンプで目的地に到達する
if (leftDist < DIST_EPS) {
outLastBeforeEnd = pos;
return count;
}
// 次の位置へ
pos += nextDist * n;
} while (true);
}
// 上限を設定してジャンプ回数を数える
INLINE int measure(const St& s, float jumpPower, const vec2& begin, const vec2& end, int rejectAt) const {
constexpr float DIST_EPS = EPS * 2.0f;
constexpr float DIST_EPS_SQ = DIST_EPS * DIST_EPS;
vec2 diff = end - begin;
float l2 = dot(diff, diff);
if (l2 < DIST_EPS_SQ) {
return 0;
}
float l = sqrt(l2);
float invL = 1 / l;
float leftDist = l;
vec2 n = diff * invL;
vec2 pos = begin;
int count = 0;
do {
if (++count > rejectAt) return 1000;
// 目的地に向かってジャンプする
float nextDist = jumpPower * s.jumpCoeffAt(pos);
leftDist -= nextDist;
// このジャンプで目的地に到達する
if (leftDist < DIST_EPS) {
return count;
}
// 次の位置へ
pos += nextDist * n;
} while (true);
}
// 上限を設定してジャンプ回数を数える
// 最後の一つ前の着地点も出力する
INLINE int measure(const St& s, float jumpPower, const vec2& begin, const vec2& end, int rejectAt, vec2& outLastBeforeEnd) const {
constexpr float DIST_EPS = EPS * 2.0f;
constexpr float DIST_EPS_SQ = DIST_EPS * DIST_EPS;
vec2 diff = end - begin;
float l2 = dot(diff, diff);
if (l2 < DIST_EPS_SQ) {
outLastBeforeEnd = begin;
return 0;
}
float l = sqrt(l2);
float invL = 1 / l;
float leftDist = l;
vec2 n = diff * invL;
vec2 pos = begin;
int count = 0;
do {
if (++count > rejectAt) return 1000;
// 目的地に向かってジャンプする
float nextDist = jumpPower * s.jumpCoeffAt(pos);
leftDist -= nextDist;
// このジャンプで目的地に到達する
if (leftDist < DIST_EPS) {
outLastBeforeEnd = pos;
return count;
}
// 次の位置へ
pos += nextDist * n;
} while (true);
}
// 着地点列を生成する
void generatePoints(const St& s, float jumpPower, const vec2& begin, const vec2& end, vector<vec2>& targets) const {
constexpr float DIST_EPS = EPS * 2.0f;
constexpr float DIST_EPS_SQ = DIST_EPS * DIST_EPS;
vec2 diff = end - begin;
float l2 = dot(diff, diff);
if (l2 < DIST_EPS_SQ) {
return;
}
float l = sqrt(l2);
float invL = 1 / l;
float leftDist = l;
vec2 n = diff * invL;
vec2 pos = begin;
int count = 0;
do {
count++;
// 目的地に向かってジャンプする
float nextDist = jumpPower * s.jumpCoeffAt(pos);
leftDist -= nextDist;
// このジャンプで目的地に到達する
if (leftDist < DIST_EPS) {
targets.push_back(end);
return;
}
// 次の位置へ
pos += nextDist * n;
targets.push_back(pos);
} while (true);
}
};
// 頂点 0 から始まり他の全ての頂点を辿るパスの最短経路を求める
class TSP {
public:
const St& s;
ObjArray<ObjArray<Path>>& paths;
ObjArray<ObjArray<int[MAX_SCROLLS]>> dists;
int answers[MAX_TSP_ANSWERS][MAX_SCROLLS];
int numAnswers;
TSP(const St& s, ObjArray<ObjArray<Path>>& paths) :s(s), paths(paths), answers(), numAnswers(0), dp(), prev() {
}
void setup() {
int n = s.n + 1;
rep0(i, n) {
const Obj oi = Obj::fromIndex(i);
rep0(j, n) {
const Obj oj = Obj::fromIndex(j);
if (i == j) {
rep0(s, MAX_SCROLLS) {
dists[oi][oj][s] = 0;
}
} else {
float dist = paths[oi][oj].estimatedDist;
distBase[oi][oj] = dist;
rep0(s, MAX_SCROLLS) {
// s 個巻物を取ったときの距離
dists[oi][oj][s] = (int) (dist * 65536.0f);
dist /= 1.1f;
}
}
}
}
}
void pertubateDists() {
int n = s.n + 1;
rep0(i, n) {
const Obj oi = Obj::fromIndex(i);
rep0(j, n) {
const Obj oj = Obj::fromIndex(j);
if (i == j) {
rep0(s, MAX_SCROLLS) {
dists[oi][oj][s] = 0;
}
} else {
float dist = distBase[oi][oj];
// 距離を僅かに変化させる
dist *= nextFloat(0.92f, 1.08f);
rep0(s, MAX_SCROLLS) {
// s 個巻物を取ったときの距離
dists[oi][oj][s] = (int) (dist * 65536.0f);
dist /= 1.1f;
}
}
}
}
}
void solve() {
set<vector<int>> as;
timer(true);
rep0(t, MAX_TSP_ANSWERS) {
int l1 = len(as);
solveHeuristicSingle(as);
int l2 = len(as);
trace("answers: ", l1, " -> ", l2);
if (len(as) >= MAX_TSP_ANSWERS) break;
pertubateDists();
}
trace("TSP heuristics: ", timer(), "ms");
numAnswers = 0;
trace("TSP answers: ", len(as));
for (auto& a : as) {
tracen(" ");
tracei(a.begin(), a.end());
rep0(i, s.n) {
answers[numAnswers][i] = a[i];
}
numAnswers++;
if (numAnswers >= MAX_TSP_ANSWERS) break;
}
//solveDP();
}
int computeDist(const vector<int>& scrollVisitOrder) const {
int res = 0;
int n = s.n;
Obj p = Obj::rabbit();
rep0(i, n) {
Obj s = Obj::scroll(scrollVisitOrder[i]);
res += dists[p][s][i];
p = s;
}
return res;
}
// 発見的手法で解を求める
void solveHeuristicSingle(set<vector<int>>& as) const {
vector<int> vs;
int n = s.n;
rep0(i, n) {
vs.push_back(i);
}
int best = computeDist(vs);
int globalBest = best;
vector<int> bestVs = vs;
int trial = 20;
bool reset = false;
rep0(t, trial) {
if (reset) {
as.insert(vs); // add optimum
vs.clear();
rep0(i, n) {
vs.insert(vs.begin() + nextInt(i + 1), i);
}
best = computeDist(vs);
}
reset = true;
// vertex swap
{
rep0(i, n) {
rep0(j, i) {
swap(vs[i], vs[j]);
int dist = computeDist(vs);
if (dist < best) {
best = dist;
reset = false;
} else {
swap(vs[i], vs[j]);
}
}
}
}
// 2-opt
{
rep0(i, n - 3) {
rep(j, i + 3, n) {
reverse(vs.begin() + i, vs.begin() + (j + 1));
int dist = computeDist(vs);
if (dist < best) {
best = dist;
reset = false;
} else {
reverse(vs.begin() + i, vs.begin() + (j + 1));
}
}
}
}
// 1.5-opt
{
rep0(i, n) {
rep0(j, n) {
if (abs(i - j) <= 1) continue;
int vi = vs[i];
vs.erase(vs.begin() + i);
vs.insert(vs.begin() + j, vi);
int dist = computeDist(vs);
if (dist < best) {
best = dist;
reset = false;
} else {
vs.erase(vs.begin() + j);
vs.insert(vs.begin() + i, vi);
}
}
}
}
if (best < globalBest) {
globalBest = best;
bestVs = vs;
}
}
as.insert(bestVs);
trace("best: ", globalBest / 65536.0f);
}
// 最適解を動的計画法で求める
void solveDP() {
int n = s.n + 1;
int ns = s.n; // 巻物の個数
const int max = 1 << ns; // 取得済み巻物の状態数
trace("solving TSP of N=", n - 1, "...");
timer(true);
constexpr int INF = 1000 * 65536;
// DP配列の初期化
rep0(s, max) {
rep0(i, ns) {
dp[s][i] = INF;
prev[s][i] = -1;
}
}
// 最初の巻物を取る
rep0(i, ns) {
dp[1 << i][i] = dists[Obj::rabbit()][Obj::scroll(i)][0];
}
rep(s, 1, max) {
// s に含まれている巻物を列挙
int iList[MAX_SCROLLS];
int iCount = 0;
// s に含まれていない巻物を列挙
int nextStateList[MAX_SCROLLS];
int jList[MAX_SCROLLS];
int jCount = 0;
rep0(i, ns) {
int nextState = s | 1 << i;
if (s == nextState) {
// 巻物 i は s に含まれる
iList[iCount] = i;
iCount++;
} else {
// 巻物 i は s に含まれない
nextStateList[jCount] = nextState;
jList[jCount] = i;
jCount++;
}
}
rep0(iidx, iCount) {
// s に含まれる巻物を全て取り、現在巻物 i の地点にいる状態
int i = iList[iidx];
int currentDist = dp[s][i];
rep0(jidx, jCount) {
int j = jList[jidx];
int nextState = nextStateList[jidx];
// この状態で巻物 j を取るのにかかるジャンプ回数
int deltaDist = dists[Obj::scroll(i)][Obj::scroll(j)][iCount];
// ここで巻物 j を取った場合の距離と判明している最短距離を比較
int newDist = currentDist + deltaDist;
if (newDist < dp[nextState][j]) {
// 記録を更新し、巻物 i から移動したことを記す
dp[nextState][j] = newDist;
prev[nextState][j] = i;
}
}
}
}
int lastScroll = -1;
int best = INF;
int state = max - 1;
rep0(i, ns) {
if (dp[state][i] < best) {
best = dp[state][i];
lastScroll = i;
}
}
int(&answer)[MAX_SCROLLS] = answers[0];
numAnswers = 1;
int count = 0;
while (state != 0) {
answer[count++] = lastScroll;
int nextState = state & ~(1 << lastScroll);
lastScroll = prev[state][lastScroll];
state = nextState;
}
reverse(answer, answer + s.n);
tracen("TSP sol: ");
tracei(answer, answer + s.n);
trace(" best = ", best / 65536.0f);
Obj pos = Obj::rabbit();
rep0(i, s.n) {
Obj npos = Obj::scroll(answer[i]);
trace(" ", dists[pos][npos][i] / 65536.0f);
pos = npos;
}
trace("TSP DP: ", timer(), "ms");
}
private:
int dp[1 << MAX_SCROLLS][MAX_SCROLLS];
int prev[1 << MAX_SCROLLS][MAX_SCROLLS];
ObjArray<ObjArray<float>> distBase;
};
class Solver {
public:
Solution solution;
Solver() :stageIndex(0), tsp(s, paths) {
}
void solveNextStage(const Stage& stage) {
setupStage(stage);
solve();
stageIndex++;
}
private:
int stageIndex;
// 現在のステージ
St s;
// 初期のパスを構築するためのグラフ
Graph g;
// ダイクストラ法
Dijkstra dijkstra;
// オブジェクト間の2点を結ぶ最短パスをまとめた行列
ObjArray<ObjArray<Path>> paths;
// 全体の最短パス
Path globalPath;
// TSPソルバ
TSP tsp;
// ステージ情報をコピーする
void setupStage(const Stage& stage) {
auto ss = stage.scrolls();
s.index = stageIndex;
s.rpos = stage.rabbit().pos();
s.n = ss.count();
rep0(i, s.n) {
s.spos[i] = ss[i].pos();
}
rep0(i, FIELD_SIZE) {
rep0(j, FIELD_SIZE) {
int x = i;
int y = j;
int terrainIndex = (int) stage.terrain(vec2(x + 0.5f, y + 0.5f));
s.jumpCoeffs[x][y] = Parameter::JumpTerrianCoefficient[terrainIndex];
s.invJumpCoeffs[x][y] = 1 / s.jumpCoeffs[x][y];
}
}
// 処理順の依存性を消す
seed(1000012 + s.index * 100);
}
// 頂点間に双方向の辺を張る
void connectVertices(int v1, int v2) {
const vec2& p1 = g.vs[v1].pos;
const vec2& p2 = g.vs[v2].pos;
g.addEdge(v1, v2, s.estimateEdgeWeight(p1, p2, 1.0f), s.estimateEdgeWeight(p2, p1, 1.0f));
}
// グラフを構築し初期のパスを生成する
void computePairwisePaths() {
g.clear();
// build a king's + knight's graph
static int vs[GRAPH_SIZE][GRAPH_SIZE];
rep0(i, GRAPH_SIZE) {
rep0(j, GRAPH_SIZE) {
vs[i][j] = g.addVertex(VType::Intermediate, s.pertubateUnlimitedTarget(vec2(i, j)));
}
}
ObjArray<int> objvs;
objvs[Obj::rabbit()] = g.addVertex(VType::Rabbit, s.rpos);
rep0(i, s.n) {
objvs[Obj::scroll(i)] = g.addVertex(VType::Scroll, s.spos[i]);
}
static int objs[FIELD_SIZE][FIELD_SIZE]; // -1: none, 0+: center's index
rep0(i, FIELD_SIZE) {
rep0(j, FIELD_SIZE) {
objs[i][j] = -1;
}
}
objs[(int) s.rpos.x][(int) s.rpos.y] = objvs[Obj::rabbit()];
rep0(i, s.n) {
objs[(int) s.spos[i].x][(int) s.spos[i].y] = objvs[Obj::scroll(i)];
}
// vertical / horizontal
rep0(i, GRAPH_SIZE) {
rep0(j, GRAPH_SIZE) {
if (i < GRAPH_SIZE - 1) {
connectVertices(vs[i][j], vs[i + 1][j]);
}
if (j < GRAPH_SIZE - 1) {
connectVertices(vs[i][j], vs[i][j + 1]);
}
}
}
// diagonal
rep0(i, FIELD_SIZE) {
rep0(j, FIELD_SIZE) {
// 対角線を接続
connectVertices(vs[i][j], vs[i + 1][j + 1]);
connectVertices(vs[i + 1][j], vs[i][j + 1]);
int center = objs[i][j];
if (center != -1) {
// 中央に点がある場合、そことも接続する
connectVertices(center, vs[i][j]);
connectVertices(center, vs[i][j + 1]);
connectVertices(center, vs[i + 1][j]);
connectVertices(center, vs[i + 1][j + 1]);
}
}
}
// knight
rep0(i, FIELD_SIZE) {
rep0(j, FIELD_SIZE) {
// (-2, 1)
if (i - 2 >= 0 && j + 1 < GRAPH_SIZE) {
int i1 = i - 2;
int j1 = j;
int i2 = i - 1;
int j2 = j;
float coeff1 = s.invJumpCoeffs[i1][j1];
float coeff2 = s.invJumpCoeffs[i2][j2];
if (coeff1 == coeff2) {
connectVertices(vs[i][j], vs[i - 2][j + 1]);
}
}
// (-1, 2)
if (i - 1 >= 0 && j + 2 < GRAPH_SIZE) {
int i1 = i - 1;
int j1 = j;
int i2 = i - 1;
int j2 = j + 1;
float coeff1 = s.invJumpCoeffs[i1][j1];
float coeff2 = s.invJumpCoeffs[i2][j2];
if (coeff1 == coeff2) {
connectVertices(vs[i][j], vs[i - 1][j + 2]);
}
}
// (1, 2)
if (i + 1 < GRAPH_SIZE && j + 2 < GRAPH_SIZE) {
int i1 = i;
int j1 = j;
int i2 = i;
int j2 = j + 1;
float coeff1 = s.invJumpCoeffs[i1][j1];
float coeff2 = s.invJumpCoeffs[i2][j2];
if (coeff1 == coeff2) {
connectVertices(vs[i][j], vs[i + 1][j + 2]);
}
}
// (2, 1)
if (i + 2 < GRAPH_SIZE && j + 1 < GRAPH_SIZE) {
int i1 = i;
int j1 = j;
int i2 = i + 1;
int j2 = j;
float coeff1 = s.invJumpCoeffs[i1][j1];
float coeff2 = s.invJumpCoeffs[i2][j2];
if (coeff1 == coeff2) {
connectVertices(vs[i][j], vs[i + 2][j + 1]);
}
}
}
}
computePairwisePathsFromGraph(objvs);
int edgeCount = 0;
for (GraphV& v : g.vs) {
edgeCount += len(v.edges);
}
trace("graph vertex count: ", g.n);
trace("graph edge count: ", edgeCount);
// デバッグ用にグラフを出力
//if (s.index == 100)
// g.dumpSvg(dijkstra.dists);
}
// 構築されたグラフの情報に従い2点間のパスを生成する
void computePairwisePathsFromGraph(const ObjArray<int>& indices) {
// パスを計算
int n = s.n + 1;
rep0(i, n) {
Obj oi = Obj::fromIndex(i);
// 頂点 from からのダイクストラ法を実行
int from = indices[oi];
dijkstra.run(g, from);
rep0(j, n) {
Obj oj = Obj::fromIndex(j);
int to = indices[oj];
// パスの初期化
Path& path = paths[oi][oj];
path.clear();
if (i == j) continue; // 同じ頂点をスキップ
// 距離を格納
float dist = dijkstra.dists[to];
path.estimatedDist = dist;
// バックトラックでパスを復元
vector<int> indices;
int pos = to;
indices.push_back(pos);
while (pos != from) {
pos = dijkstra.prev[pos];
indices.push_back(pos);
}
reverse(indices.begin(), indices.end());
// パスを設定
for (auto index : indices) {
// パスの中間では巻物を取らないことにする（でないと偶然同じ頂点を2回通ったときに重複する）
int forceIntermediate = index != indices.front() && index != indices.back();
path.addVertex(g.vs[index].pos, forceIntermediate ? VType::Intermediate : g.vs[index].type);
}
#if !DO_NOT_SIMPLIFY
// パスを単純化
int pass = 2;
rep0(k, pass) {
path.simplify(s);
}
#endif
}
}
}
void solveTSP() {
tsp.setup();
tsp.solve();
}
void initGlobalPath(int ansIndex) {
// パスを初期化
globalPath.clear();
// 初期位置はウサギ
Obj pos = Obj::rabbit();
globalPath.addVertex(s.rpos, VType::Rabbit);
rep0(i, s.n) {
// 次の巻物
Obj nextPos = Obj::scroll(tsp.answers[ansIndex][i]);
auto& nextPath = paths[pos][nextPos];
// パスを繋げる
bool firstVertexInPath = true;
for (auto& v : nextPath.vs) {
if (firstVertexInPath) {
// パス内の最初の頂点は飛ばす
firstVertexInPath = false;
continue;
}
globalPath.addVertex(v.pos, v.type);
}
pos = nextPos;
}
}
void computeGlobalPath() {
// パスを初期化
initGlobalPath(0);
#if DO_NOT_REFINE
return;
#endif
timer(true);
Path bestPath = globalPath;
int bestCount = 1000;
// TSP の計算で得た最適解とそれに近い解を初期解として局所改善を行う
{
constexpr int refineMul = 7200;
int refineTrials = min(MAX_TSP_ANSWERS, tsp.numAnswers * 2); // 2巡以上しない
int refinePass = refineMul / refineTrials;
rep0(i, refineTrials) {
initGlobalPath(i % tsp.numAnswers);
Path path = globalPath;
rep0(k, refinePass) {
float t = (float) k / refinePass;
float from = 1.0f;
float to = DELTA;
path.refine(s, 1.0f, from + t * (to - from), true, false);
if (k > 0 && k % 10 == 0) {
// 削除のみの refine を実行する
path.refine(s, 1.0f, 0, true, true);
}
int count = path.actualCount;
if (count < bestCount) {
Solution sol = path.generateSolution(s);
if (sol.verify(s)) {
bestCount = count;
bestPath = path;
trace("best updated! ", bestCount, " i=", i, " k=", k);
} else {
trace("best updated, but verification failed. ", bestCount, " -> ", count, " reverting...");
path = bestPath;
}
}
// 前向き枝刈りを行う
if (k == 20) {
if (count >= bestCount + 10) {
trace("no hope, break (k=", k, " count=", count, ")");
break;
}
}
if (k == 200) {
if (count >= bestCount + 3) {
trace("no hope, break (k=", k, " count=", count, ")");
break;
}
}
if (k == 400) {
if (count >= bestCount + 2) {
trace("no hope, break (k=", k, " count=", count, ")");
break;
}
}
if (k > 0 && k % 50 == 0) {
// パスを細かくする
path.splitAll(s);
}
}
}
}
seed(nextInt() ^ 10);
// 最もよかったパスに対してさらに改善を行う
globalPath = bestPath;
globalPath.splitAll(s);
trace("refinement phase 2 begin...");
{
int refineTrials = 5; // mul 5000
rep0(i, refineTrials) {
Path path = globalPath;
int refinePass = 1000;
rep0(k, refinePass) {
float t = (float) k / refinePass;
float from = 1.0f;
float to = DELTA;
path.refine(s, 1.0f, from + t * (to - from), true, false);
if (k > 0 && k % 10 == 0) {
// 削除のみの refine を実行する
path.refine(s, 1.0f, 0, true, true);
}
int count = path.actualCount;
if (count < bestCount) {
Solution sol = path.generateSolution(s);
if (sol.verify(s)) {
bestCount = count;
bestPath = path;
trace("best updated! ", bestCount, " i=", i, " k=", k);
} else {
trace("best updated, but verification failed. ", bestCount, " -> ", count, " reverting...");
path = bestPath;
}
}
if (k > 0 && k % 50 == 0) {
// パスを細かくする
path.splitAll(s);
}
}
}
}
globalPath = bestPath;
trace("refining time: ", timer(), "ms");
}
void solve() {
#if ONE_CASE_TEST != -1
if (stageIndex != ONE_CASE_TEST) {
// 特定のステージ以外をとりあえずスキップ
solution.targets.clear();
return;
}
#endif
#if SUBMARINE
if (stageIndex == 0) {
// 最初のステージのスコアを 1000 にする
solution.targets.clear();
return;
}
#endif
computePairwisePaths();
solveTSP();
computeGlobalPath();
solution = globalPath.generateSolution(s);
trace("-----------------------------------");
trace("stage ", stageIndex, ": ", len(solution.targets));
trace("-----------------------------------\n\n");
}
};
Solver solver;
int targetIndex;
int errorIndex;
int stageIndex;
int errorCount;
int totalExpectedCount;
int totalActualCount;
Answer::Answer() {
errorIndex = -1;
stageIndex = -1;
totalExpectedCount = 0;
totalActualCount = 0;
}
Answer::~Answer() {
trace("TOTAL:");
trace(" ", totalExpectedCount, " - expected");
trace(" ", totalActualCount, " - actual");
}
void Answer::initialize(const Stage& aStage) {
stageIndex++;
targetIndex = 0;
solver.solveNextStage(aStage);
}
vec2 Answer::getTargetPos(const Stage& aStage) {
totalActualCount++;
if (len(solver.solution.targets) <= targetIndex) {
if (errorIndex != stageIndex) {
if (errorCount < 10) {
cerr << "ERROR! not enough points (stage " << stageIndex << ")" << endl;
}
errorCount++;
errorIndex = stageIndex;
}
return aStage.rabbit().pos();
}
return solver.solution.targets[targetIndex++];
}
void Answer::finalize(const Stage& aStage) {
if (errorIndex == stageIndex) {
totalExpectedCount += 1000;
} else {
totalExpectedCount += len(solver.solution.targets);
}
}
} // namespace
// EOF