#include "Answer.hpp"
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <set>
#include <functional>
#include <random>
#include <chrono>
#include <cstring>
using namespace std;
double params[100] =
{
//評価値計算用のパラメータ
0.44,
0.05,
2.7,
0.35,
3.7,
4,
13,
0.16,
0.84,
11, //chokudai幅に関するパラメータ
3, //巡回セールスマン距離を計算するとき高さの低い餌を無視するようのパラメータ
//餌の数、カメの数、distributionによる探索時間を配分するパラメータ
0.9,
1,
3.7,
0.3,
0.8,
0.3,
3.4,
0.8,
10, //chokudaiサーチにかける時間
45, //山登りにかける時間
25, //山登りするときに選ぶ餌のペアの距離の最大値
5 //山登りするときに選ぶ餌のペアの距離の最小値
};
//タイマー
class MyTimer
{
chrono::high_resolution_clock::time_point start, end;
double limit;
public:
MyTimer()
{
start = chrono::high_resolution_clock::now();
}
MyTimer(double l)
{
start = chrono::high_resolution_clock::now();
limit = l;
}
double getTime()
{
end = chrono::high_resolution_clock::now();
return chrono::duration<double>(end - start).count();
}
bool Over()
{
if (getTime() > limit)
{
return true;
}
return false;
}
void setLimit(double l)
{
limit = l;
}
void setStart() { start = chrono::high_resolution_clock::now(); }
double getLimit() { return limit; }
};
//疑似乱数
class XorShift
{
unsigned static int x, y, z, w;
public:
XorShift()
{
x = 31103110, y = 123456789, z = 521288629, w = 88675123;
}
unsigned int nextInt()
{
unsigned int t;
t = (x ^ (x << 11)); x = y; y = z; z = w;
return(w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
}
};
unsigned int XorShift::x, XorShift::y, XorShift::z, XorShift::w;
struct MyPair
{
int dist; //評価値
char id; //番号
MyPair(int dist = 0, char id = 0) :dist(dist), id(id) {}
bool operator<(const MyPair& r)const
{
return dist < r.dist;
}
};
//カメの集団
struct GroupInfo
{
int turn, id, num; //移動ターン数、番号、カメの数
GroupInfo(int turn = 0, int id = 0, int num = 0) :turn(turn), id(id), num(num) {}
bool operator<(const GroupInfo& r)const
{
return turn < r.turn;
}
};
//カメの集団(メモリ節約用)
struct GroupInfo_small
{
unsigned char turn; //移動ターン数の差分
char id, num; //番号、カメの数
GroupInfo_small(unsigned char turn = 0, char id = 0, char num = 0) :turn(turn), id(id), num(num) {}
bool operator<(const GroupInfo_small& r)const
{
return turn < r.turn;
}
};
//座標
struct MyPoint
{
char x, y;
MyPoint(char x = 0, char y = 0) :x(x), y(y) {}
bool operator<(const MyPoint& r)const
{
if (x != r.x)return x < r.x;
return y < r.y;
}
};
namespace hpc
{
MyTimer stage_tmr, game_tmr;
XorShift rnd;
int stage_num = 0; //ステージ番号
int turtleCount; //カメの数
int foodCount; //餌の数
int distribution;
int total_score = 0; //トータルスコア
int best_score; //ベストスコア
double revfoodCount; //foodCountの逆数
double revturtleCount; //turtleCountの逆数
vector<int>orders[25]; //各カメが食べる餌
int foods_order[100]; //食べる餌の順番
int foods_index[100];
MyPoint food_pos[125]; //餌の座標
int food_height[100]; //餌の高さ
int remain_pair;
MyPoint foods_pair[10000]; //山登りするときの餌の選び方のペア
int turtle_turn_1d[125]; //移動ターン数
int turtle_turn_2d[101][25]; //各餌を食べたときのカメの移動ターン数
int turtle_turns_max[101]; //各餌を食べたときのカメの移動ターン数の最大
int objects_id[25]; //カメがいる位置
int objects_id_2d[101][25]; //各餌を食べたときのカメがいる位置
int calced_mht_dist[100][125]; //マンハッタン距離
int tmp_gr_n[101];
int gr_n[101]; //カメの集団の数
GroupInfo groups_2d[101][25]; //各餌を食べたときのカメの集団の情報
GroupInfo tmp_groups_2d[101][25];
GroupInfo groups[25]; //カメの集団の情報
int gr_index[125]; //カメの集団の添え字
int gr_index_2d[101][125];
int gr_t_n[125];
int gr_turtles_id[125][25];
//何かに使える情報
struct Info
{
int t_n; //カメの数
int turtle_id[25]; //カメの番号
int turn; //移動ターン数
};
Info infos[101];
//chokudaiサーチに必要なデータ
struct STATUS
{
int g_n; //カメの集団の数
int min_turn; //最小移動ターン数
GroupInfo_small groups[25]; //カメの集団の情報
int prev; //ひとつ前のSTATUS
char prev_food; //ひとつ前に食べた餌
STATUS(int t = 0)
{
g_n = t;
min_turn = 0;
for (int i = 0; i < t; i++)
{
groups[i].turn = 0;
groups[i].id = foodCount + i;
groups[i].num = 1;
}
prev = -1;
prev_food = -1;
}
};
STATUS Q[2000000];
//STATUSをpriority_queueに入れてたら遅いので
struct ScoreInfo
{
double score; //評価値
int id; //Qの添え字
ScoreInfo(double score, int id) :score(score), id(id) {}
bool operator<(const ScoreInfo& r)const
{
return score < r.score;
}
bool operator>(const ScoreInfo& r)const
{
return score > r.score;
}
};
//マンハッタン距離
int mht_dist(MyPoint p1, MyPoint p2)
{
return abs(p1.x - p2.x) + abs(p1.y - p2.y);
}
void nth_element1(MyPair * v, int n, int l, int r)
{
if (l >= r - 1)return;
int pivot = v[l].dist;
int m = l;
for (int i = l + 1; i < r; i++)
{
if (v[i].dist < pivot)
{
swap(v[i], v[++m]);
}
}
swap(v[l], v[m]);
if (m < n)
{
for (int i = m + 1; i < r; i++)
{
if (v[i].dist == pivot)
{
swap(v[i], v[++m]);
if (m >= n)return;
}
}
nth_element1(v, n, m + 1, r);
}
else if (m > n)
{
nth_element1(v, n, l, m);
}
return;
}
int nth_element2(GroupInfo * v, int n, int l, int r)
{
int m;
while (1)
{
int pivot = v[r - 1].turn;
m = r - 1;
int cnt = 0;
for (int i = r - 2; i >= l; i--)
{
if (v[i].turn < pivot)
{
cnt += v[i].num;
swap(v[i], v[--m]);
}
}
swap(v[r - 1], v[m]);
if (cnt + v[m].num < n)
{
r = m;
n -= cnt + v[m].num;
}
else if (cnt >= n)
{
l = m + 1;
}
else
{
v[m].num -= n - cnt;
break;
}
}
return m;
}
int nth_element3(GroupInfo_small * v, int n, int l, int r)
{
int m;
while (1)
{
int pivot = v[r - 1].turn;
m = r - 1;
int cnt = 0;
for (int i = r - 2; i >= l; i--)
{
if (v[i].turn < pivot)
{
cnt += v[i].num;
swap(v[i], v[--m]);
}
}
swap(v[r - 1], v[m]);
if (cnt + v[m].num < n)
{
r = m;
n -= cnt + v[m].num;
}
else if (cnt >= n)
{
l = m + 1;
}
else
{
v[m].num -= n - cnt;
break;
}
}
return m;
}
//各カメの食べる餌の順番決定
void set_orders()
{
for (int i = 0; i < turtleCount; i++)
{
orders[i].clear();
}
for (int i = 0; i < foodCount; i++)
{
int fid = foods_order[i];
for (int j = 0; j < turtleCount; j++)
{
if (objects_id_2d[i + 1][j] != fid)continue;
orders[j].push_back(fid);
}
}
for (int i = 0; i < turtleCount; i++)
{
reverse(orders[i].begin(), orders[i].end());
}
}
int update_groups_2d(int s)
{
int max_turn = turtle_turns_max[s];
for (int i = s; i < foodCount; i++)
{
gr_n[i + 1] = tmp_gr_n[i + 1];
memcpy(groups_2d[i + 1], tmp_groups_2d[i + 1], sizeof(tmp_groups_2d[i + 1]));
if (infos[i].turn > max_turn)max_turn = infos[i].turn;
turtle_turns_max[i + 1] = max_turn;
}
return turtle_turns_max[foodCount];
}
void init_groups_2d()
{
for (int i = 0; i < foodCount; i++)
{
gr_n[i + 1] = 0;
for (int j = 0; j < turtleCount; j++)
{
int object_id = objects_id_2d[i + 1][j];
if (gr_index[object_id] == -1)
{
gr_index[object_id] = gr_n[i + 1];
groups_2d[i + 1][gr_n[i + 1]].turn = turtle_turn_2d[i + 1][j];
groups_2d[i + 1][gr_n[i + 1]].id = object_id;
groups_2d[i + 1][gr_n[i + 1]].num = 0;
gr_n[i + 1]++;
}
int gid = gr_index[object_id];
groups_2d[i + 1][gid].num++;
}
int max_turn = 0;
for (int j = 0; j < turtleCount; j++)max_turn = max(max_turn, turtle_turn_2d[i + 1][j]);
turtle_turns_max[i + 1] = max_turn;
for (int j = 0; j < turtleCount; j++)
{
int object_id = objects_id_2d[i + 1][j];
if (gr_index[object_id] != -1)gr_index[object_id] = -1;
}
}
}
//集団の動き方から各カメの動き方に変換
void finalize_turtles()
{
int max_turn = 0;
for (int i = 0; i < turtleCount; i++)
{
int object_id = foodCount + i;
gr_t_n[object_id] = 1;
gr_turtles_id[object_id][0] = i;
}
for (int i = 0; i < foodCount; i++)
{
int fid = foods_order[i];
int height = food_height[fid];
for (int j = 0; j < turtleCount; j++)
{
turtle_turn_2d[i + 1][j] = turtle_turn_2d[i][j];
objects_id_2d[i + 1][j] = objects_id_2d[i][j];
}
vector<char>used(foodCount + turtleCount);
for (int j = 0; j < gr_n[i + 1]; j++)used[groups_2d[i + 1][j].id] = groups_2d[i + 1][j].num;
int last = -1;
infos[i].t_n = 0;
for (int j = 0; j < gr_n[i]; j++)
{
int sub = groups_2d[i][j].num - used[groups_2d[i][j].id];
if (sub > 0)
{
if (used[groups_2d[i][j].id] > 0)last = infos[i].t_n;
infos[i].turtle_id[infos[i].t_n++] = groups_2d[i][j].id;
}
}
if (last != -1)swap(infos[i].turtle_id[last], infos[i].turtle_id[infos[i].t_n - 1]);
infos[i].turn = 0;
for (int j = 0; j < gr_n[i + 1]; j++)infos[i].turn = max<int>(infos[i].turn, groups_2d[i + 1][j].turn);
int h = 0;
for (int j = 0; j < infos[i].t_n; j++)
{
int object_id = infos[i].turtle_id[j];
int remain = gr_t_n[object_id];
while (remain > 0)
{
int tid = gr_turtles_id[object_id][--remain];
gr_turtles_id[fid][h++] = tid;
turtle_turn_2d[i + 1][tid] = infos[i].turn;
objects_id_2d[i + 1][tid] = fid;
if (h == height)break;
}
gr_t_n[object_id] = remain;
}
gr_t_n[fid] = height;
if (infos[i].turn > max_turn)max_turn = infos[i].turn;
turtle_turns_max[i] = max_turn;
}
}
//貪欲な巡回セールスマン距離の計算
double calc_so_rough_dist(int remain, int* remain_foods, int* remain_foods_index, int prev_food)
{
double res = 0;
if (prev_food == -1)return res;
int si, sj = -1;
si = remain_foods_index[prev_food];
//高さの低い餌は無視する
for (int j = 0; j < remain; j++)
{
if (food_height[remain_foods[j]] * params[10] < turtleCount)
{
swap(remain_foods_index[remain_foods[j]], remain_foods_index[remain_foods[remain - 1]]);
swap(remain_foods[j], remain_foods[--remain]);
j--;
}
}
while (remain > 0)
{
//距離が一番近い餌から貪欲に選んでいく
int min_dist = 1e9;
for (int j = 0; j < remain; j++)
{
int dist = calced_mht_dist[remain_foods[si]][remain_foods[j]];
if (dist < min_dist)
{
min_dist = dist;
sj = j;
}
}
res += min_dist;
swap(remain_foods_index[remain_foods[sj]], remain_foods_index[remain_foods[remain - 1]]);
swap(remain_foods[sj], remain_foods[--remain]);
si = remain;
}
return res;
}
//近傍の移動ターン数を計算
int partial_simulation(int l, int r)
{
int max_turn = turtle_turns_max[l];
int gn = gr_n[l];
for (int i = 0; i < gn; i++)
{
int object_id = groups[i].id = groups_2d[l][i].id;
groups[i].num = groups_2d[l][i].num;
turtle_turn_1d[object_id] = groups_2d[l][i].turn;
}
for (int i = l; i < foodCount; i++)
{
int fid = foods_order[i];
int* cmd = calced_mht_dist[fid];
for (int j = gn - 1; j >= 0; j--)
{
int object_id = groups[j].id;
groups[j].turn = turtle_turn_1d[object_id] + cmd[object_id];
}
//餌に近いカメを貪欲に向かわせる
int m = nth_element2(groups, food_height[fid], 0, gn);
int next_turn = groups[m].turn;
//集団情報の更新
if (groups[m].num == 0)gn = m;
else gn = m + 1;
turtle_turn_1d[fid] = next_turn;
groups[gn].id = fid;
groups[gn].num = food_height[fid];
gn++;
//遷移した時に必要な情報を保存
tmp_gr_n[i + 1] = gn;
GroupInfo * mt_i = tmp_groups_2d[i + 1];
for (int j = 0; j < gn; j++)
{
int object_id = groups[j].id;
mt_i[j].turn = turtle_turn_1d[object_id];
mt_i[j].id = object_id;
mt_i[j].num = groups[j].num;
}
infos[i].turn = next_turn;
if (next_turn > max_turn)max_turn = next_turn;
if (max_turn - turtle_turns_max[i + 1] > 20) //前の解とのターン数の差が20ターンより大きくなったら遷移しない
{
max_turn = 1e8;
break;
}
if (max_turn > best_score) //ターン数がベストターン数より大きくなったら遷移しない
{
max_turn = 1e8;
break;
}
}
return max_turn;
}
//食べる餌の順番を直大サーチ
void chokudai_search()
{
MyTimer tmr;
double order_sum = 0;
for (int i = 0; i < 4; i++)
{
int foodCount = i * 20 + 40;
order_sum += pow(foodCount, params[11]);
}
double order_sum2 = 0;
for (int i = 0; i < 20; i++)
{
int turtleCount = i + 6;
order_sum2 += pow(turtleCount, params[12]);
}
double order_sum3 = 0;
for (int i = 0; i < 3; i++)
{
int distribution = 2 - i % 3;
order_sum3 += params[13] + params[14] * distribution;
}
tmr.setLimit(params[19] * pow(foodCount, params[11]) / order_sum * pow(turtleCount, params[12]) / order_sum2 * (params[13] + params[14] * distribution) / order_sum3);
int remain_foods_index[100];
int remain_foods[100];
for (int i = 0; i < foodCount; i++)
{
remain_foods[i] = i;
remain_foods_index[i] = i;
}
MyPair dist_sorted[100];
int Qsize = 0;
priority_queue<ScoreInfo, vector<ScoreInfo>, greater<ScoreInfo>>Q_indices[101];
ScoreInfo tmp_si(0, Qsize);
Q_indices[0].push(tmp_si);
Q[Qsize++] = STATUS(turtleCount);
int best_turn = 1e9;
int loop = 0;
while (1)
{
if (loop && tmr.Over())break;
for (int t = 0; t < foodCount; t++)
{
int t2n = max<int>(1, params[9] - (foodCount - t - 1)); //chokudai幅は基本1、終盤のchokudai幅を増やした
for (int t2 = 0; t2 < t2n; t2++)
{
if (Q_indices[t].size() == 0)continue;
ScoreInfo si = Q_indices[t].top();
int q_ind = si.id;
STATUS st = Q[q_ind];
Q_indices[t].pop();
int minturn = 1e9;
for (int j = 0; j < st.g_n; j++)
{
if (st.groups[j].turn < minturn)minturn = st.groups[j].turn;
}
int maxturn = 0;
for (int j = 0; j < st.g_n; j++)
{
st.groups[j].turn -= minturn;
if (st.groups[j].turn > maxturn)maxturn = st.groups[j].turn;
}
st.min_turn += minturn;
int tmp_turn = 0;
for (int j = 0; j < st.g_n; j++)
{
if (st.min_turn + st.groups[j].turn > tmp_turn)tmp_turn = st.min_turn + st.groups[j].turn;
}
//まだ食べてない餌の確認
int s = q_ind;
int remain_foods_num = foodCount;
while (s != 0)
{
swap(remain_foods_index[(int)Q[s].prev_food], remain_foods_index[remain_foods[remain_foods_num - 1]]);
swap(remain_foods[remain_foods_index[remain_foods[remain_foods_num - 1]]], remain_foods[remain_foods_num - 1]);
remain_foods_num--;
s = Q[s].prev;
}
//残りの餌の、高さの最大値、x座標とy座標の最小最大と平均、の計算
int max_height = 0;
int minfx = 1e9, maxfx = 0;
int minfy = 1e9, maxfy = 0;
double avefx = 0, avefy = 0;
for (int i = 0; i < remain_foods_num; i++)
{
int fid = remain_foods[i];
MyPoint p = food_pos[fid];
if (p.x < minfx)minfx = p.x;
if (p.x > maxfx)maxfx = p.x;
if (p.y < minfy)minfy = p.y;
if (p.y > maxfy)maxfy = p.y;
avefx += p.x;
avefy += p.y;
max_height = max(max_height, food_height[fid]);
}
avefx /= (foodCount - t);
avefy /= (foodCount - t);
//カメの平均のx座標とy座標の計算
double avetx = 0, avety = 0;
for (int j = 0; j < st.g_n; j++)
{
MyPoint p = food_pos[(int)st.groups[j].id];
avetx += p.x * st.groups[j].num;
avety += p.y * st.groups[j].num;
}
avetx *= revturtleCount;
avety *= revturtleCount;
//カメの密集度の計算
double turtle_density = 0;
for (int j = 0; j < st.g_n; j++)
{
MyPoint p = food_pos[(int)st.groups[j].id];
turtle_density += st.groups[j].num * (abs(p.x - avetx) + abs(p.y - avety));
}
turtle_density *= revturtleCount;
//残りの餌の巡回セールスマン距離の計算
double remain_dist = calc_so_rough_dist(remain_foods_num, remain_foods, remain_foods_index, st.prev_food);
//盤面評価
si.score += params[1] * ((maxfx - minfx + 1) * (maxfy - minfy + 1)); //残りの餌を含む面積は小さいほうが良い
si.score += params[2] * pow(1. * (foodCount - t) * revfoodCount, params[4]) * turtle_density; //カメはまず最初に集まったほうが良い
si.score += params[3] * remain_dist; //残りの餌の巡回セールスマン距離は小さいほうが良い
//距離が近い順にソート
for (int i = 0; i < remain_foods_num; i++)
{
if (st.prev_food != -1)dist_sorted[i].dist = calced_mht_dist[(int)st.prev_food][remain_foods[i]];
else dist_sorted[i].dist = 0;
dist_sorted[i].id = remain_foods[i];
}
partial_sort(dist_sorted, dist_sorted + min(remain_foods_num, (int)(remain_foods_num / params[5]) + 1), dist_sorted + remain_foods_num);
for (int i = 0; i < remain_foods_num; i++)
{
if (t && (i >= remain_foods_num / params[5] + 1))break; //ひとつ前に食べた餌と距離が遠い餌は選ばない
int fid = dist_sorted[i].id;
Q[Qsize] = st;
STATUS * next_st = &Q[Qsize];
MyPoint fpos = food_pos[fid];
int height = food_height[fid];
int* cmd = calced_mht_dist[fid];
//餌に近いカメを貪欲に向かわせる
for (int j = 0; j < st.g_n; j++)next_st->groups[j].turn = st.groups[j].turn + cmd[(int)st.groups[j].id];
int m = nth_element3(next_st->groups, height, 0, st.g_n);
int next_turn = next_st->groups[m].turn;
//集団情報の更新
if (next_st->groups[m].num == 0)next_st->g_n = m;
else next_st->g_n = m + 1;
for (int j = 0; j < next_st->g_n; j++)next_st->groups[j].turn -= cmd[(int)next_st->groups[j].id];
next_st->groups[next_st->g_n].turn = next_turn;
next_st->groups[next_st->g_n].id = fid;
next_st->groups[next_st->g_n].num = height;
next_st->g_n++;
next_turn += st.min_turn;
int turn = tmp_turn;
if (next_turn > turn)turn = next_turn;
if (turn >= best_turn)continue;
//評価値の計算
double score = si.score; //評価値は今までの累積
score += 1. * turn; //餌を食べた後の移動ターン数は小さいほうが良い
score -= (params[7] + params[8] * t / foodCount) * (params[6] * height / max_height); //高さの大きい餌を食べたほうが良い
score -= params[0] * (abs(fpos.x - avefx) + abs(fpos.y - avefy)); //残りの餌の平均座標から離れてる餌を食べたほうが良い
if (t == foodCount - 1)
{
score = turn;
if (turn < best_turn)best_turn = turn;
}
next_st->prev = q_ind;
next_st->prev_food = fid;
tmp_si.score = score;
tmp_si.id = Qsize;
Q_indices[t + 1].emplace(tmp_si);
Qsize++;
}
}
}
loop++;
}
int s = Q_indices[foodCount].top().id;
int index = foodCount - 1;
while (index != -1)
{
STATUS st = Q[s];
foods_order[index] = st.prev_food;
gr_n[index + 1] = st.g_n;
for (int i = 0; i < st.g_n; i++)
{
groups_2d[index + 1][i].turn = st.min_turn + st.groups[i].turn;
groups_2d[index + 1][i].id = st.groups[i].id;
groups_2d[index + 1][i].num = st.groups[i].num;
}
s = st.prev;
index--;
}
finalize_turtles();
best_score = best_turn;
}
//食べる餌の順番を山登り
void climbing()
{
init_groups_2d();
MyTimer tmr;
double order_sum = 0;
for (int i = 0; i < 4; i++)
{
int foodCount = i * 20 + 40;
order_sum += pow(foodCount, params[15]);
}
double order_sum2 = 0;
for (int i = 0; i < 20; i++)
{
int turtleCount = i + 6;
order_sum2 += pow(turtleCount, params[16]);
}
double order_sum3 = 0;
for (int i = 0; i < 3; i++)
{
int distribution = 2 - i % 3;
order_sum3 += (params[17] + params[18] * distribution);
}
tmr.setLimit(params[20] * pow(foodCount, params[15]) / order_sum * pow(turtleCount, params[16]) / order_sum2 * (params[17] + params[18] * distribution) / order_sum3);
tmr.setStart();
int score = best_score;
const int MAX_DIST = (int)params[21];
remain_pair = 0;
for (int i = 0; i < foodCount; i++)
{
for (int j = i + 1; j < foodCount; j++)
{
if (calced_mht_dist[i][j] > MAX_DIST)continue;
foods_pair[remain_pair++] = MyPoint(i, j);
}
}
for (int i = 0; i < foodCount; i++)foods_index[foods_order[i]] = i;
int dist_border = MAX_DIST; //餌のペアの距離の閾値
int loop = 0;
while (1)
{
loop++;
if (loop % 1000 == 0)
{
//時間の計算は遅いのでループ1000回に1回
if (tmr.getLimit() < tmr.getTime())break;
//距離の閾値を超えたペアの除去
int pre = dist_border;
dist_border = params[22] + (MAX_DIST - params[22]) * (tmr.getLimit() - tmr.getTime()) / tmr.getLimit();
if (dist_border != pre)
{
for (int i = 0; i < remain_pair; i++)
{
if (calced_mht_dist[(int)foods_pair[i].x][(int)foods_pair[i].y] > dist_border)
{
swap(foods_pair[i], foods_pair[--remain_pair]);
i--;
}
}
if (remain_pair == 0)break;
}
}
//距離の近い餌のペアを選ぶ
int r = rnd.nextInt() % remain_pair;
int r1 = foods_index[(int)foods_pair[r].x];
int r2 = foods_index[(int)foods_pair[r].y];
if (r1 > r2)swap(r1, r2);
//0:insert, 1:swap, 2:reverse
int mode = loop % 3;
if (mode == 0)
{
if (loop % 2)for (int i = r1; i < r2; i++)swap(foods_order[i], foods_order[i + 1]);
else for (int i = r2; i > r1; i--)swap(foods_order[i], foods_order[i - 1]);
}
else if (mode == 1)
{
swap(foods_order[r1], foods_order[r2]);
}
else if (mode == 2)
{
for (int i = 0; i < (r2 - r1) / 2; i++)swap(foods_order[r1 + i], foods_order[r2 - i]);
}
//近傍のスコア計算
int next_score = partial_simulation(r1, r2);
if (next_score <= score)
{
for (int i = r1; i <= r2; i++)foods_index[foods_order[i]] = i;
score = next_score;
update_groups_2d(r1);
if (score < best_score)
{
best_score = score;
}
}
else
{
if (mode == 0)
{
if (loop % 2)for (int i = r2; i > r1; i--)swap(foods_order[i], foods_order[i - 1]);
else for (int i = r1; i < r2; i++)swap(foods_order[i], foods_order[i + 1]);
}
else if (mode == 1)
{
swap(foods_order[r1], foods_order[r2]);
}
else if (mode == 2)
{
for (int i = 0; i < (r2 - r1) / 2; i++)swap(foods_order[r1 + i], foods_order[r2 - i]);
}
}
}
finalize_turtles();
}
void init(const Stage & aStage)
{
stage_tmr.setStart();
foodCount = stage_num / 60 % 4 * 20 + 40;
turtleCount = stage_num / 3 % 20 + 6;
distribution = 2 - stage_num % 3;
revfoodCount = 1. / foodCount;
revturtleCount = 1. / turtleCount;
best_score = 1e9;
for (int i = 0; i < turtleCount; i++)objects_id_2d[0][i] = foodCount + i;
TurtlePositions tps = aStage.turtlePositions();
Foods foods = aStage.foods();
for (int i = 0; i < foodCount; i++)food_pos[i] = MyPoint(foods[i].pos().x, foods[i].pos().y);
for (int i = 0; i < foodCount; i++)food_height[i] = foods[i].height();
for (int i = 0; i < turtleCount; i++)food_pos[foodCount + i] = MyPoint(tps[i].x, tps[i].y);
for (int i = 0; i < foodCount; i++)for (int j = 0; j < foodCount; j++)calced_mht_dist[i][j] = mht_dist(food_pos[i], food_pos[j]);
for (int i = 0; i < turtleCount; i++)for (int j = 0; j < foodCount; j++)calced_mht_dist[j][foodCount + i] = mht_dist(food_pos[objects_id_2d[0][i]], food_pos[j]);
gr_n[0] = turtleCount;
for (int i = 0; i < turtleCount; i++)
{
groups_2d[0][i].turn = 0;
groups_2d[0][i].id = foodCount + i;
groups_2d[0][i].num = 1;
}
for (int i = 0; i < turtleCount + foodCount; i++)gr_index[i] = -1;
}
void Answer::initialize(const Stage & aStage)
{
init(aStage);
chokudai_search();
climbing();
set_orders();
}
Action move_dir(Point from, Point to)
{
if (from.x < to.x)
{
return Action_MoveRight;
}
else if (from.x > to.x)
{
return Action_MoveLeft;
}
else if (from.y < to.y)
{
return Action_MoveDown;
}
else if (from.y > to.y)
{
return Action_MoveUp;
}
else
{
return Action_Wait;
}
}
void Answer::setActions(const Stage & aStage, Actions & aActions)
{
Foods foods = aStage.foods();
TurtlePositions tps = aStage.turtlePositions();
for (int i = 0; i < turtleCount; i++)
{
int fid = -1;
while (orders[i].size())
{
fid = orders[i].back();
if (foods[fid].isEaten())orders[i].pop_back();
else break;
}
if (orders[i].size() == 0)
{
aActions.add(Action_Wait);
continue;
}
aActions.add(move_dir(tps[i], foods[fid].pos()));
}
}
void Answer::finalize(const Stage & aStage)
{
total_score += best_score;
stage_num++;
cout << "Score : " << best_score << endl;
}
Answer::Answer()
{
for (int i = 0; i < 23; i++)
{
cerr << i << " " << params[i] << endl;
}
game_tmr.setLimit(59.);
game_tmr.setStart();
}
Answer::~Answer()
{
cerr << "TotalScore : " << total_score << endl;
}
}