//------------------------------------------------------------------------------
/// @file
/// @author ハル研究所プログラミングコンテスト実行委員会
///
/// @copyright Copyright (c) 2019 HAL Laboratory, Inc.
/// @attention このファイルの利用は、同梱のREADMEにある
/// 利用条件に従ってください。
//------------------------------------------------------------------------------
#include "Answer.hpp"
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <functional>
#include <random>
#include <chrono>
#include <cassert>
//------------------------------------------------------------------------------
namespace hpc {
using namespace std;
using ll = long long;
class timer {
private:
chrono::system_clock::time_point start;
public:
void set_time() {
start = chrono::system_clock::now();
}
ll get_time() {
auto end = chrono::system_clock::now();
return chrono::duration_cast<chrono::milliseconds>(end - start).count();
}
};
timer total_time;
unsigned int xor128() {
static unsigned int x = 123456789, y = 362436069, z = 521288629, w = 982650321;
unsigned int t;
t = (x ^ (x << 11)); x = y; y = z; z = w;
return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
}
inline double prob() {
static const double P = (1. - 1e-5) / (unsigned)-1;
return xor128()*P;
}
int stage_cnt;
int cnt_update;
vector<int> idx(Parameter::MaxFoodCount);
bool flag_store;
// l1
inline int distance(const Point &a, const Point &b) {
return abs(a.x - b.x) + abs(a.y - b.y);
}
Action move_command(const Point &tpos, const Point &fpos) {
int dx = fpos.x - tpos.x;
int dy = fpos.y - tpos.y;
if (dx == 0 && dy == 0) return Action_Wait;
if (abs(dx) > abs(dy)) {
return dx > 0 ? Action_MoveRight : Action_MoveLeft;
}
else {
return dy > 0 ? Action_MoveDown : Action_MoveUp;
}
}
#ifdef LOCAL
constexpr int KSIZE = 6 * (1 << 5);
vector<int> cnt_bestk(KSIZE);
#endif
vector<int> cand = {
0, 8, 12, 18, 22,
26, 30, 32, 33, 35,
36, 40, 41, 43, 44,
49, 50, 51, 54, 57,
58, 59, 62, 63, 64,
67, 68, 72, 73, 74,
76, 82, 86, 89, 90,
94, 96, 97, 99, 100,
101, 104, 105, 107, 108,
111, 113, 114, 115, 117,
118, 120, 121, 122, 123,
125, 126, 129, 130, 131,
134, 135, 137, 138, 139,
141, 142, 143, 144, 145,
147, 148, 152, 153, 156,
159, 161, 162, 165, 166,
169, 170, 171, 174, 175,
176, 177, 180, 184, 187,
188, 191
};
using RankType = int;
using Rank = pair<RankType, RankType>;
RankType pat1[6][3][6] = {
{
{ 0, 1, 2, 3, 4, 5 },
{ 11, 10, 9, 8, 7, 6 },
{ 12, 13, 14, 15, 16, 17 }
},
{
{ 0, 5, 6, 11, 12, 17 },
{ 1, 4, 7, 10, 13, 16 },
{ 2, 3, 8, 9, 14, 15 }
},
{
{ 0, 1, 2, 15, 16, 17 },
{ 5, 4, 3, 14, 13, 12 },
{ 6, 7, 8, 9, 10, 11 }
},
{
{ 6, 7, 8, 9, 16, 15 },
{ 5, 0, 1, 10, 17, 14 },
{ 4, 3, 2, 11, 12, 13 }
},
{
{ 15, 16, 17, 0, 1, 2 },
{ 14, 11, 10, 7, 6, 3 },
{ 13, 12, 9, 8, 5, 4 }
},
{
{ 15, 14, 13, 0, 1, 2 },
{ 16, 11, 12, 7, 6, 3 },
{ 17, 10, 9, 8, 5, 4 }
}
};
RankType pat2[2][10] = {
{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 },
{ 0, 0, 1, 1, 2, 2, 3, 3, 4, 4 }
};
Rank calc_rank(const Food &food, int mode) {
static const int px = Parameter::StageWidth / 6;
static const int py = Parameter::StageHeight / 3;
const auto &pos = food.pos();
int t1 = mode >> 3, t2 = mode & 7;
int yy = t1 & 1 ? 2 - pos.y / py : pos.y / py;
int xx = (t1 >> 1) & 1 ? 5 - pos.x / px : pos.x / px;
int r1 = pat1[t1 >> 2][yy][xx];
int pp = t2 & 1 ? pos.y % 10 : pos.x % 10;
int r2 = pat2[(t2 >> 2) & 1][pp];
if ((t2 >> 1) & 1) r2 *= -1;
return { r1, r2 };
}
int simulate(const Stage &stage) {
static vector<pair<int, int>> rank(Parameter::MaxTurtleCount);
static vector<int> elpt(Parameter::MaxTurtleCount);
static vector<Point> lastpos(Parameter::MaxTurtleCount);
const Foods &foods = stage.foods();
const int nfoods = foods.count();
const TurtlePositions &turtles = stage.turtlePositions();
const int nturtles = turtles.count();
for (int i = 0; i < nturtles; i++) elpt[i] = 0;
for (int i = 0; i < nturtles; i++) lastpos[i] = turtles[i];
for (int dm = 0; dm < nfoods; dm++) {
const int foodid = idx[dm];
const auto &food = foods[foodid];
const auto &fpos = food.pos();
const int n = food.height();
int cnt = 0, cm = 0;
for (int i = 0; i < nturtles; i++) {
int v = distance(fpos, lastpos[i]);
if (cnt >= n && v + elpt[i] >= cm) continue;
cm = max(cm, v + elpt[i]);
rank[cnt++] = { v + elpt[i], i };
}
nth_element(rank.begin(), rank.begin() + (n - 1), rank.begin() + cnt);
int t = rank[n - 1].first;
for (int i = 0; i < n; i++) {
int tid = rank[i].second;
lastpos[tid] = food.pos();
elpt[tid] = t;
}
}
int ret = 0;
for (int i = 0; i < nturtles; i++) ret = max(ret, elpt[i]);
return ret;
}
bool check_move(int score, int cur_score, int iter, int maxiter) {
static const double MAXT = 3.;
static const double MINT = 1e-9;
if (score <= cur_score) return true;
if (iter > maxiter) iter = maxiter;
double T = MAXT + (MINT - MAXT) * iter / maxiter;
double p = exp((cur_score - score) / T);
//cerr << iter << " " << p << endl;
return prob() < p;
}
void simulated_annealing(const Stage &stage, const int maxiter, const int dmiter) {
// USAGE: idx_inv[rank[idx[i]][j]]
static vector<vector<pair<int, int>>>
rank(Parameter::MaxFoodCount, vector<pair<int, int>>(Parameter::MaxFoodCount - 1));
static vector<int> idx_inv(Parameter::MaxFoodCount);
const Foods &foods = stage.foods();
const int size = foods.count();
const double cfsize = (size - 1e-5) / (unsigned)-1;
int minv = simulate(stage);
int gminv = minv;
// idx: ord |-> foodid
// idx_inv: foodid |-> ord
for (int i = 0; i < size; i++) idx_inv[idx[i]] = i;
for (int i = 0; i < size; i++) {
for (int p = 0; p < size; p++) {
if (i == p) continue;
int d = distance(foods[i].pos(), foods[p].pos());
rank[i][p - (i < p)] = { d, p };
}
sort(rank[i].begin(), rank[i].begin() + size - 1);
}
for (int iter = 0; iter < maxiter; iter++) {
if (xor128() & 1) {
int e1 = (int)(xor128() * cfsize);
int ng = max(0, e1 - 1);
int e2, sss = xor128() & 3;
for (int i = 0; i <= sss; i++) {
e2 = idx_inv[rank[idx[e1]][i].second];
if (e2 == ng) sss++;
if (i != sss && e1 != 0 && e2 == 0) {
e2 = -1;
i++;
}
}
const int sv = idx[e1];
if (e1 < e2) {
for (int i = e1; i < e2; i++) idx[i] = idx[i + 1];
idx[e2] = sv;
}
else {
for (int i = e1; i > e2 + 1; i--) idx[i] = idx[i - 1];
idx[e2 + 1] = sv;
}
int v = simulate(stage);
if (check_move(v, minv, iter, dmiter)) {
cnt_update += v < gminv;
minv = v;
gminv = min(gminv, v);
if (e1 < e2) {
for (int i = e1; i <= e2; i++) idx_inv[idx[i]] = i;
}
else {
for (int i = e2 + 1; i <= e1; i++) idx_inv[idx[i]] = i;
}
}
else {
if (e1 < e2) {
for (int i = e2; i > e1; i--) idx[i] = idx[i - 1];
idx[e1] = sv;
}
else {
for (int i = e2 + 1; i < e1; i++) idx[i] = idx[i + 1];
idx[e1] = sv;
}
}
}
else {
int e1 = (int)(xor128() * cfsize);
int ng1 = max(0, e1 - 1), ng2 = min(size - 1, e1 + 1);
int e2, sss = xor128() & 3;
for (int i = 0; i <= sss; i++) {
e2 = idx_inv[rank[idx[e1]][i].second];
if (e2 == ng1 || e2 == ng2) sss++;
}
if (e1 > e2) swap(e1, e2);
reverse(idx.begin() + e1 + 1, idx.begin() + e2 + 1);
int v = simulate(stage);
if (check_move(v, minv, iter, dmiter)) {
cnt_update += v < gminv;
minv = v;
gminv = min(gminv, v);
for (int i = e1 + 1; i < e2 + 1; i++) idx_inv[idx[i]] = i;
}
else {
reverse(idx.begin() + e1 + 1, idx.begin() + e2 + 1);
}
}
}
}
//------------------------------------------------------------------------------
/// コンストラクタ。
/// @detail 最初のステージ開始前に実行したい処理があればここに書きます。
Answer::Answer() {
total_time.set_time();
}
//------------------------------------------------------------------------------
/// デストラクタ。
/// @detail 最後のステージ終了後に実行したい処理があればここに書きます。
Answer::~Answer() {
cerr << "total time " << total_time.get_time() << "ms" << endl;
cerr << "total update " << cnt_update << endl;
#ifdef LOCAL
cerr << "bestk" << endl;
for (int i = 0; i < (int)cnt_bestk.size(); i++) {
cerr << "(" << i << "," << cnt_bestk[i] << ") ";
if ((i & 7) == 7) cerr << endl;
if ((i & 31) == 31) cerr << endl;
}
#endif
}
//------------------------------------------------------------------------------
/// 各ステージ開始時に呼び出される処理。
/// @detail 各ステージに対する初期化処理が必要ならここに書きます。
/// @param aStage 現在のステージ。
void Answer::initialize(const Stage& aStage) {
const Foods &foods = aStage.foods();
const int size = foods.count();
cerr << "stage " << stage_cnt << endl;
vector<pair<Rank, int>> rank(size);
int minv = (int)1e9, bestk = 0;
for (int k : cand) {
for (int i = 0; i < size; i++) rank[i] = { calc_rank(foods[i], k), i };
sort(rank.begin(), rank.end());
for (int i = 0; i < size; i++) idx[i] = rank[i].second;
int v = simulate(aStage);
if (v < minv) minv = v, bestk = k;
}
for (int i = 0; i < size; i++) {
rank[i] = { calc_rank(foods[i], bestk), i };
}
sort(rank.begin(), rank.end());
for (int i = 0; i < size; i++) idx[i] = rank[i].second;
#ifdef LOCAL
cnt_bestk.at(bestk)++;
#endif
int nturtles = aStage.turtlePositions().count();
if (nturtles <= 12) simulated_annealing(aStage, 40000, 35000);
else simulated_annealing(aStage, 20000, 15000);
flag_store = true;
}
//------------------------------------------------------------------------------
/// 各ターンのカメの行動を指定する。
/// @detail 各カメの行動を指定し、aActionsの要素に追加してください。
/// aActions[i]がi番目のカメの行動になります。
/// aActionsの要素数がaStage.turtlePositions()の要素数と異なる場合、アサートに失敗します。
/// @param[in] aStage 現在のステージ。
/// @param[out] aActions 各カメの行動を指定する配列。
void Answer::setActions(const Stage& aStage, Actions& aActions) {
static vector<pair<int, int>> rank(Parameter::MaxTurtleCount);
static vector<Action> actions(Parameter::MaxTurtleCount, Action_Wait);
static vector<int> elpt(Parameter::MaxTurtleCount);
static vector<deque<int>> targetid(Parameter::MaxTurtleCount);
static vector<Point> lastpos(Parameter::MaxTurtleCount);
const Foods &foods = aStage.foods();
const TurtlePositions &turtles = aStage.turtlePositions();
const int nturtles = turtles.count();
if (flag_store) {
for (int i = 0; i < nturtles; i++) elpt[i] = 0;
for (int i = 0; i < nturtles; i++) targetid[i].clear();
for (int i = 0; i < nturtles; i++) lastpos[i] = turtles[i];
const int nfoods = foods.count();
for (int dm = 0; dm < nfoods; dm++) {
const int foodid = idx[dm];
const auto &food = foods[foodid];
if (food.isEaten()) continue;
const auto &fpos = food.pos();
int n = food.height();
int cnt = 0, cm = 0;
for (int i = 0; i < nturtles; i++) {
int v = distance(fpos, lastpos[i]);
if (cnt >= n && v + elpt[i] >= cm) continue;
cm = max(cm, v + elpt[i]);
rank[cnt++] = { v + elpt[i], i };
}
nth_element(rank.begin(), rank.begin() + (n - 1), rank.begin() + cnt);
int t = rank[n - 1].first;
for (int i = 0; i < n; i++) {
int tid = rank[i].second;
targetid[tid].push_back(foodid);
lastpos[tid] = food.pos();
elpt[tid] = t;
}
}
flag_store = false;
}
for (int i = 0; i < nturtles; i++) {
while (true) {
if (targetid[i].empty()) break;
if (!foods[targetid[i].front()].isEaten()) break;
targetid[i].pop_front();
}
}
for (int i = 0; i < nturtles; i++) {
if (targetid[i].empty()) continue;
const auto &food = foods[targetid[i].front()];
actions[i] = move_command(turtles[i], food.pos());
}
for (int i = 0; i < nturtles; i++) aActions.add(actions[i]);
}
//------------------------------------------------------------------------------
/// 各ステージ終了時に呼び出される処理。
/// @detail 各ステージに対する終了処理が必要ならここに書きます。
/// @param aStage 現在のステージ。
void Answer::finalize(const Stage& aStage) {
stage_cnt++;
}
} // namespace
// EOF