//------------------------------------------------------------------------------
/// @file
/// @author ハル研究所プログラミングコンテスト実行委員会
///
/// @copyright Copyright (c) 2019 HAL Laboratory, Inc.
/// @attention このファイルの利用は、同梱のREADMEにある
/// 利用条件に従ってください。
//------------------------------------------------------------------------------
// 学習を行う場合は1
#define LEARNING 0
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <array>
#include <algorithm>
#include <bitset>
#include <chrono>
#include <complex>
#include <functional>
#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>
#if LEARNING
// 学習はマルチスレッドで行う
#include <thread>
#include <mutex>
#else
#include "Answer.hpp"
#endif
// #define NDEBUG
#include <cassert>
#define ull unsigned long long
#define ll long long
#define pii pair<int, int>
#define pdi pair<double, 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))
using namespace std;
// 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;
}
}
bool debug = true;
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;
}
#if LEARNING
mutex traceMutex;
template <class... Tail>
void tracex(Tail&&... tail) {
lock_guard<mutex> lock(traceMutex);
if (!debug) return;
tracen(forward<Tail>(tail)...);
cerr << endl;
}
#endif
template <class Iter>
void tracein(Iter from, Iter until) {
if (!debug) return;
bool first = true;
while (from != until) {
if (first) {
first = false;
} else {
cerr << ", ";
}
cerr << *from;
from++;
}
}
template <class Iter>
void tracei(Iter from, Iter until) {
if (!debug) return;
tracein(from, until);
cerr << endl;
}
void sleepUntil(int until) {
volatile unsigned int a = 0;
while (timer() < until) a++;
}
void segv() {
volatile int *a = nullptr;
*a = 0;
}
void waitForever() {
while (true) getchar();
}
#if !LEARNING
namespace hpc {
#endif
template <class T>
string str(T a) {
stringstream ss;
ss << a;
return ss.str();
}
// エサの最大数
const int MAX_F = 100;
// カメの最大数
const int MAX_T = 25;
// 実質無限
const int INF = 1000000;
// エサ
class F {
public:
// 位置
int x;
int y;
// 高さ
int height;
// 優先度、低いほど先に食べられる
double priority;
// ターン開始時にエサが食べられるとするときの、このエサが食べられるターン
int time;
void init(int _x, int _y, int _height) {
x = _x;
y = _y;
height = _height;
priority = 0;
time = 0;
}
};
// カメ
class T {
public:
// 位置
int x;
int y;
// 初期位置
int initialX;
int initialY;
// 訪れる予定のエサ
vector<int> fs;
// 食べたエサの数
int numEaten;
// 次の行動可能時刻
int time;
// 0～numF-1: エサの上, numF～numF+numT-1: 初期座標
int position;
void init(int _x, int _y) {
x = _x;
y = _y;
initialX = _x;
initialY = _y;
fs = vector<int>();
numEaten = 0;
time = 0;
position = 0;
}
private:
};
// ステージの状態を表す
class Field {
public:
int numT;
int numF;
int ts[MAX_T][2]; // x, y
int fs[MAX_F][3]; // x, y, h
};
// 進行中のゲームの一意な場面を表す置換表のキー
class TableKey {
public:
int numT;
int numF;
int ts[MAX_T][2]; // position, time
bool eaten[MAX_F];
int padding;
void clear() {
memset(this, 0, sizeof(TableKey));
}
int hash() {
ull res = 13;
ull *p = (ull*) this;
// sizeof(TableKey) / 8 = 312 / 8 = 39
rep0(i, 39) {
res = (res << 5) - res + *p++;
}
return (int) (res & 0xfff);
}
};
// 置換表のサイズ
const int TABLE_SIZE = 0x1000;
// 置換表
class Table {
public:
int stage;
int vals[TABLE_SIZE];
TableKey keys[TABLE_SIZE];
Table() {
clear();
}
void clear() {
stage = 0;
memset(vals, 0, sizeof(vals));
memset(keys, 0, sizeof(keys));
}
// 置換表に格納された値を読みだす
// 存在しない場合は -1
int getVal(TableKey &key2, int hash) {
TableKey &key1 = keys[hash];
if (memcmp(&key1, &key2, sizeof(TableKey)) != 0) {
return -1;
}
return vals[hash];
}
// 置換表の対応するキーの値を上書きする
void set(TableKey &key2, int hash, int value) {
keys[hash] = key2;
vals[hash] = value;
}
};
Table table;
// 評価関数のパラメータの数
const int NUM_FOOD_PARAMS = 20;
// パラメータの難易度方向の分割数
const int NUM_FOOD_PARAMS_DIFFICULTY_DIVS = 3;
// パラメータのエサの個数方向の分割数
const int NUM_FOOD_PARAMS_FOOD_COUNT_DIVS = 4;
// 特定の分類のステージのみ実行する場合は 0～12
int targetId = -1;
class FoodParam {
public:
// 現在のステージに対し読み込まれているパラメータ
double activeParams[NUM_FOOD_PARAMS];
// 全てのパラメータ
double allParams[NUM_FOOD_PARAMS_DIFFICULTY_DIVS][NUM_FOOD_PARAMS_FOOD_COUNT_DIVS][NUM_FOOD_PARAMS];
FoodParam() {
rep0(i, NUM_FOOD_PARAMS) {
activeParams[i] = 0;
}
allParams[0][0][0] = -0.2764549103792215;
allParams[0][0][1] = -0.218341;
allParams[0][0][2] = -0.345481;
allParams[0][0][3] = 0.3250616361476487;
allParams[0][0][4] = 1.5349;
allParams[0][0][5] = -0.415629;
allParams[0][0][6] = 0.0357089;
allParams[0][0][7] = -0.008793189841302961;
allParams[0][0][8] = -0.82469;
allParams[0][0][9] = -0.32219865582390156;
allParams[0][0][10] = -0.0712338;
allParams[0][0][11] = -0.2060817044892388;
allParams[0][0][12] = -0.10061676368411136;
allParams[0][0][13] = -0.6072727648619561;
allParams[0][0][14] = 0.19726642703514244;
allParams[0][0][15] = -0.16820569783598605;
allParams[0][0][16] = -0.011458099999999999;
allParams[0][0][17] = 0.048576576794481;
allParams[0][0][18] = 0.09543369432512276;
allParams[0][0][19] = -0.11560788764791761;
allParams[1][0][0] = -0.16121122913921232;
allParams[1][0][1] = -0.13937220898283473;
allParams[1][0][2] = -0.9671217744389435;
allParams[1][0][3] = 0.388216;
allParams[1][0][4] = 2.76744;
allParams[1][0][5] = -0.20384;
allParams[1][0][6] = -0.222068;
allParams[1][0][7] = 0.082516;
allParams[1][0][8] = -0.691287;
allParams[1][0][9] = -0.54687;
allParams[1][0][10] = -0.27715764735015286;
allParams[1][0][11] = -0.17398070234360766;
allParams[1][0][12] = -0.597946;
allParams[1][0][13] = 0.032218;
allParams[1][0][14] = 0.255598737768295;
allParams[1][0][15] = -0.018165021026667595;
allParams[1][0][16] = -0.19517300583676114;
allParams[1][0][17] = -0.08321570223415135;
allParams[1][0][18] = -0.126326;
allParams[1][0][19] = -0.1473684732598109;
allParams[2][0][0] = -0.5413639670202458;
allParams[2][0][1] = -0.442426;
allParams[2][0][2] = -0.919612020887568;
allParams[2][0][3] = 0.6569907777487177;
allParams[2][0][4] = 2.1744;
allParams[2][0][5] = -0.0961374;
allParams[2][0][6] = -0.030716125155326485;
allParams[2][0][7] = -0.05478864059217411;
allParams[2][0][8] = -0.299535;
allParams[2][0][9] = -0.1475015210837453;
allParams[2][0][10] = -0.16793091379408348;
allParams[2][0][11] = -0.4158103670175602;
allParams[2][0][12] = -0.8304605833245695;
allParams[2][0][13] = 0.135426;
allParams[2][0][14] = 0.47153575791567887;
allParams[2][0][15] = 0.006964110036191894;
allParams[2][0][16] = -0.05947875760008918;
allParams[2][0][17] = -0.02261481203135105;
allParams[2][0][18] = -0.29747860174448626;
allParams[2][0][19] = -0.30663557131294156;
allParams[0][1][0] = -0.24302594528778676;
allParams[0][1][1] = -0.237334;
allParams[0][1][2] = -0.453821;
allParams[0][1][3] = 0.334692;
allParams[0][1][4] = 2.18055;
allParams[0][1][5] = -0.3152990859979627;
allParams[0][1][6] = -0.0570399;
allParams[0][1][7] = 0.0191401;
allParams[0][1][8] = -0.811158;
allParams[0][1][9] = -0.49438046620676696;
allParams[0][1][10] = -0.08873416921724019;
allParams[0][1][11] = -0.204439;
allParams[0][1][12] = -0.321087;
allParams[0][1][13] = -0.175645;
allParams[0][1][14] = 0.279724;
allParams[0][1][15] = -0.121709;
allParams[0][1][16] = 0.08307183679684717;
allParams[0][1][17] = -0.037977;
allParams[0][1][18] = -0.0780841;
allParams[0][1][19] = -0.221995;
allParams[1][1][0] = -0.27806691322262955;
allParams[1][1][1] = -0.316041;
allParams[1][1][2] = -0.8098874022002027;
allParams[1][1][3] = 0.255111;
allParams[1][1][4] = 4.078891878449788;
allParams[1][1][5] = -0.136524903579275;
allParams[1][1][6] = 0.397488;
allParams[1][1][7] = -0.145285;
allParams[1][1][8] = -0.3664983568887598;
allParams[1][1][9] = -0.544941;
allParams[1][1][10] = -0.1064996654191761;
allParams[1][1][11] = -0.12434778064779714;
allParams[1][1][12] = -0.576247858917687;
allParams[1][1][13] = 0.16767755734948528;
allParams[1][1][14] = 0.22220499999999999;
allParams[1][1][15] = -0.0412346;
allParams[1][1][16] = 0.209129;
allParams[1][1][17] = -0.012108377108781421;
allParams[1][1][18] = -0.3251052757518553;
allParams[1][1][19] = -0.247708;
allParams[2][1][0] = -0.4280363923208305;
allParams[2][1][1] = -0.5159913119965798;
allParams[2][1][2] = -0.890193;
allParams[2][1][3] = 0.565231;
allParams[2][1][4] = 2.20745;
allParams[2][1][5] = -0.0583021;
allParams[2][1][6] = -0.0467745;
allParams[2][1][7] = 0.019219573735224055;
allParams[2][1][8] = -0.18529241630177168;
allParams[2][1][9] = -0.16079859417986309;
allParams[2][1][10] = -0.1662309371599068;
allParams[2][1][11] = -0.24466363156678933;
allParams[2][1][12] = -0.941397;
allParams[2][1][13] = 0.09759291505800816;
allParams[2][1][14] = 0.6226019967193879;
allParams[2][1][15] = -0.0215193;
allParams[2][1][16] = -0.01995955823676387;
allParams[2][1][17] = -0.050926492991717295;
allParams[2][1][18] = -0.3628862784020083;
allParams[2][1][19] = -0.18741896702694072;
allParams[0][2][0] = -0.314937;
allParams[0][2][1] = -0.199003;
allParams[0][2][2] = -0.515034;
allParams[0][2][3] = 0.472974;
allParams[0][2][4] = 2.43328;
allParams[0][2][5] = -0.262923;
allParams[0][2][6] = 0.00955827;
allParams[0][2][7] = 0.107467;
allParams[0][2][8] = -0.833502;
allParams[0][2][9] = -0.604242;
allParams[0][2][10] = -0.144739;
allParams[0][2][11] = -0.203522;
allParams[0][2][12] = -0.420787;
allParams[0][2][13] = -0.095368;
allParams[0][2][14] = 0.22479293561313088;
allParams[0][2][15] = -0.0864083;
allParams[0][2][16] = -0.00248608;
allParams[0][2][17] = -0.0736316;
allParams[0][2][18] = -0.134835;
allParams[0][2][19] = -0.17637;
allParams[1][2][0] = -0.18648;
allParams[1][2][1] = -0.2602943230796714;
allParams[1][2][2] = -0.87447;
allParams[1][2][3] = 0.650999;
allParams[1][2][4] = 5.21872;
allParams[1][2][5] = -0.133718;
allParams[1][2][6] = 0.14492;
allParams[1][2][7] = -0.0129632;
allParams[1][2][8] = -0.366917;
allParams[1][2][9] = -0.402998;
allParams[1][2][10] = -0.20098320017165652;
allParams[1][2][11] = 0.013809933272247797;
allParams[1][2][12] = -0.928954;
allParams[1][2][13] = 0.09514025333561821;
allParams[1][2][14] = 0.48350733014154684;
allParams[1][2][15] = -0.0324224;
allParams[1][2][16] = 0.229653;
allParams[1][2][17] = 0.0135226;
allParams[1][2][18] = -0.506027;
allParams[1][2][19] = -0.1603661630579445;
allParams[2][2][0] = -0.4055938983360103;
allParams[2][2][1] = -0.32308681275513706;
allParams[2][2][2] = -1.0574602622064604;
allParams[2][2][3] = 0.52568505880768;
allParams[2][2][4] = 2.6737567220005216;
allParams[2][2][5] = -0.0279855;
allParams[2][2][6] = -0.0458863;
allParams[2][2][7] = -0.06771419571103021;
allParams[2][2][8] = -0.22026193526354124;
allParams[2][2][9] = -0.179013;
allParams[2][2][10] = -0.11930866859280455;
allParams[2][2][11] = -0.3804336732973919;
allParams[2][2][12] = -0.8128830447984993;
allParams[2][2][13] = 0.11867986293711169;
allParams[2][2][14] = 0.5133366884875455;
allParams[2][2][15] = -0.0327879;
allParams[2][2][16] = 0.020334425043494996;
allParams[2][2][17] = 0.003327295971437479;
allParams[2][2][18] = -0.3714873770917999;
allParams[2][2][19] = -0.39116;
allParams[0][3][0] = -0.2537428811221776;
allParams[0][3][1] = -0.25578603925374616;
allParams[0][3][2] = -0.453291;
allParams[0][3][3] = 0.452165;
allParams[0][3][4] = 3.20284;
allParams[0][3][5] = -0.317276;
allParams[0][3][6] = -0.13605154236739483;
allParams[0][3][7] = -0.212365;
allParams[0][3][8] = -0.558361;
allParams[0][3][9] = -0.595984;
allParams[0][3][10] = -0.0519101;
allParams[0][3][11] = -0.303806;
allParams[0][3][12] = -0.4608544270185508;
allParams[0][3][13] = -0.06489905312141754;
allParams[0][3][14] = 0.205226;
allParams[0][3][15] = -0.0687293;
allParams[0][3][16] = -0.12010900000000001;
allParams[0][3][17] = -0.0584111;
allParams[0][3][18] = -0.155823;
allParams[0][3][19] = -0.24391746102092077;
allParams[1][3][0] = -0.248926;
allParams[1][3][1] = -0.30109;
allParams[1][3][2] = -0.8459904121886247;
allParams[1][3][3] = 0.716237;
allParams[1][3][4] = 3.666464240117089;
allParams[1][3][5] = -0.0800026;
allParams[1][3][6] = 0.150834;
allParams[1][3][7] = 0.11743288504680259;
allParams[1][3][8] = -0.236662;
allParams[1][3][9] = -0.416972;
allParams[1][3][10] = -0.1255486645843111;
allParams[1][3][11] = -0.137307;
allParams[1][3][12] = -0.930462;
allParams[1][3][13] = 0.2269574738699019;
allParams[1][3][14] = 0.443099;
allParams[1][3][15] = -0.0715643;
allParams[1][3][16] = 0.168586;
allParams[1][3][17] = 0.005488230542337585;
allParams[1][3][18] = -0.46755417125167137;
allParams[1][3][19] = -0.23302556632918958;
allParams[2][3][0] = -0.2768781381518962;
allParams[2][3][1] = -0.547606;
allParams[2][3][2] = -1.0584804701140633;
allParams[2][3][3] = 0.672736;
allParams[2][3][4] = 1.95729;
allParams[2][3][5] = -0.0245541;
allParams[2][3][6] = -0.00456571;
allParams[2][3][7] = 0.0552016;
allParams[2][3][8] = -0.195892;
allParams[2][3][9] = -0.142709;
allParams[2][3][10] = 0.008768192573337795;
allParams[2][3][11] = -0.288716;
allParams[2][3][12] = -0.920159;
allParams[2][3][13] = 0.187212;
allParams[2][3][14] = 0.35059144398418624;
allParams[2][3][15] = -0.0245739;
allParams[2][3][16] = 0.0144374;
allParams[2][3][17] = -0.06366998116687442;
allParams[2][3][18] = -0.359912;
allParams[2][3][19] = -0.2922522729487392;
}
void copyParam(double *src) {
rep0(i, NUM_FOOD_PARAMS) {
activeParams[i] = src[i];
}
}
// ステージ番号から対応する分類のパラメータを読み込む
void loadParam(int stageId) {
copyParam(allParams[stageId % 3][stageId / 60]);
}
// ファイルに保存したパラメータを読み込む (学習時専用)
void readAllParams() {
int num = 243;
rep0(j, NUM_FOOD_PARAMS_FOOD_COUNT_DIVS) {
rep0(i, NUM_FOOD_PARAMS_DIFFICULTY_DIVS) {
readParamByName("./params_" + str(num), allParams[i][j]);
rep0(k, NUM_FOOD_PARAMS) {
cout << "allParams[" << i << "][" << j << "][" << k << "] = " << allParams[i][j][k] << ";" << endl;
}
num++;
}
}
}
// ファイルに保存したパラメータを読み込む (学習時専用)
bool readParamByName(string name, double *readTo = nullptr) {
if (readTo == nullptr) {
readTo = activeParams;
}
ifstream fin;
fin.open(name, ios::in | ios::binary);
if (!fin) {
trace("read failed: ", name);
return false;
}
fin.read((char*) readTo, sizeof(double) * NUM_FOOD_PARAMS);
fin.close();
trace("read succeeded: ", name);
return true;
}
};
// 実行コンテキスト
class Context {
public:
int id;
// 乱数
class Rnd {
public:
Rnd(): y(135272729) {
}
void seed(int s) {
y = s;
}
int getSeed() {
return y;
}
int next() {
y = y ^ (y << 13); y = y ^ (y >> 17);
return (y = y ^ (y << 15)) & 0x7fffffff;
}
private:
int y;
};
Rnd rnd;
void seed(int y) {
rnd.seed(y);
}
int seed() {
return rnd.getSeed();
}
int nextInt() {
return rnd.next();
}
int nextInt(int n) {
return rnd.next() % n;
}
float nextFloat() {
return (float) rnd.next() / 0x80000000;
}
// エサ
F fs[MAX_F];
// エサの数
int numF;
// カメ
T ts[MAX_T];
// カメの数
int numT;
// エサ/カメ ～ エサ の距離
int dists[MAX_F + MAX_T][MAX_F];
// 各エサから他のエサへの近い順の距離
int nn[MAX_F][MAX_F - 1];
// 残りのエサの個数
int numLeftFoods;
// 残りのエサの高さの和
int leftFoodHeightSum;
// 現在のステージ
int stage;
// 評価関数のパラメータ
FoodParam foodp;
Context() {
stage = 0;
}
int dist(int x1, int y1, int x2, int y2) {
return abs(x1 - x2) + abs(y1 - y2);
}
void setupDists() {
// 距離行列を計算
rep0(i, numF + numT) {
int x1 = i >= numF ? ts[i - numF].initialX : fs[i].x;
int y1 = i >= numF ? ts[i - numF].initialY : fs[i].y;
rep0(j, numF) {
int x2 = fs[j].x;
int y2 = fs[j].y;
int d = dist(x1, y1, x2, y2);
dists[i][j] = d;
}
}
// kNN を構築
rep0(i, numF) {
vector<pii> pairs;
rep0(j, numF) {
if (i == j) continue;
pairs.push_back(pii(dists[i][j], j));
}
sort(pairs.begin(), pairs.end());
rep0(j, numF - 1) {
nn[i][j] = pairs[j].second;
}
}
}
// 全体のうち k 番目に小さい要素を返す
// 計算量 O(kn)
int kthElement2(int a[], int n, int k) {
int count = 0;
int min = 0;
while (true) {
int min2 = INF;
int count2 = 0;
rep0(i, n) {
int ai = a[i];
if (ai > min) {
if (ai < min2) {
min2 = ai;
count2 = 1;
} else if (ai == min2) {
count2++;
}
}
}
min = min2;
count += count2;
if (count >= k) {
return min;
}
}
}
// 全体のうち k 番目に小さい要素を返す
// 計算量 O(n+m), m≦300
int kthElement(int a[], int n, int k) {
int max = 0;
int min = INF;
rep0(i, n) {
if (a[i] > max) max = a[i];
if (a[i] < min) min = a[i];
}
int counts[300];
int num = max - min + 1;
// O(kn) の方が早く終わりそうな見込みがある場合別のアルゴリズムを実行
if (n * k < num * 2) {
return kthElement2(a, n, k);
}
rep0(i, num) {
counts[i] = 0;
}
rep0(i, n) {
counts[a[i] - min]++;
}
int count = 0;
rep0(i, num) {
count += counts[i];
if (count >= k) {
return min + i;
}
}
return -1;
}
// パラメータ無次元化させるための正規化定数
const double TIME_SCALE = 1.0 / 100;
// エサの評価関数
inline double evaluationFunction(double time, double knn1, double knn3, double knn5, double turtleDistMean, double heightMean, double height, double x, double y, double t, double p[]) {
double ax = x < 0 ? -x : x;
double ay = y < 0 ? -y : y;
double v1;
double v2;
v1 = knn1 * *p++;
v1 += knn3 * *p++;
v1 += knn5 * *p++;
v1 += turtleDistMean * *p++;
v1 += turtleDistMean * heightMean * *p++;
v1 += height * *p++;
v1 += x * *p++;
v1 += y * *p++;
v1 += ax * *p++;
v1 += ay * *p++;
v2 = knn1 * *p++;
v2 += knn3 * *p++;
v2 += knn5 * *p++;
v2 += turtleDistMean * *p++;
v2 += turtleDistMean * heightMean * *p++;
v2 += height * *p++;
v2 += x * *p++;
v2 += y * *p++;
v2 += ax * *p++;
v2 += ay * *p++;
return time + v1 + t * (v2 - v1);
}
// エサ f を食べるコストを計算する
inline double foodCost(int f) {
// カメがエサに辿り着く時刻
int times[MAX_T];
// エサの高さ
int h = fs[f].height;
// エサの高さとカメの数の比
double normalizedHeight = (double) h / numT;
int turtleDistMean = 0;
rep0(i, numT) {
T &t = ts[i];
int d = dists[t.position][f];
turtleDistMean += d;
times[i] = t.time + d;
}
turtleDistMean /= numT;
// 実際にエサが食べられる時刻
int time = kthElement(times, numT, h);
// 残っているエサの高さの平均から「カメがどれだけ凝集するべきか」を計算する
// 多くのカメがいる周辺のエサを優先して食べるようにする
double normalizedHeightMean = (double) leftFoodHeightSum / (numLeftFoods * numT);
// n番目に近いエサの距離
int cnt = 0;
int knnDist1 = 0;
int knnDist3 = 0;
int knnDist5 = 0;
rep0(i, numF - 1) {
int f2 = nn[f][i];
if (fs[f2].time == INF) {
int dist = dists[f][f2];
switch (++cnt) {
case 1:
knnDist1 = dist;
knnDist3 = dist;
knnDist5 = dist;
break;
case 2:
case 3:
knnDist3 = dist;
knnDist5 = dist;
break;
case 4:
case 5:
knnDist5 = dist;
break;
}
if (cnt == 5 || cnt == numLeftFoods - 1) break;
}
}
return evaluationFunction(
time * TIME_SCALE,
knnDist1 * TIME_SCALE,
knnDist3 * TIME_SCALE,
knnDist5 * TIME_SCALE,
turtleDistMean * TIME_SCALE,
normalizedHeightMean,
normalizedHeight,
(fs[f].x - 30) * TIME_SCALE,
(fs[f].y - 15) * TIME_SCALE,
(double) (numF - numLeftFoods) / numF,
foodp.activeParams
);
}
// 最後に食べられたエサの時刻を計算
int computeMaxTime() {
int maxTime = 0;
rep0(i, numF) {
maxTime = max(maxTime, fs[i].time);
}
return maxTime;
}
// 現状から貪欲にエサを食べていった場合の合計ターン数を返す
// ステージの情報を復元しないため、再帰的処理には使えない
int evaluateGreedyFast() {
// 残りのエサ
set<int> left;
rep0(i, numF) {
if (fs[i].time == INF) {
left.insert(i);
}
}
while (numLeftFoods > 0) {
// コストが最小のエサを選ぶ
double minC = 1e9;
int f = -1;
for (int i : left) {
double c = foodCost(i);
if (c < minC) {
f = i;
minC = c;
}
}
// 食べられる時刻を計算
pii times[MAX_T];
rep0(i, numT) {
T &t = ts[i];
times[i] = pii(t.time + dists[t.position][f], i);
}
sort(times, times + numT);
int h = fs[f].height;
int time = times[h - 1].first;
rep0(i, h) {
T &t = ts[times[i].second];
t.time = time;
t.position = f;
}
F &food = fs[f];
food.time = time;
leftFoodHeightSum -= food.height;
numLeftFoods--;
left.erase(f);
}
return computeMaxTime();
}
void getTableKey(TableKey &key) {
key.clear();
key.numT = numT;
key.numF = numF;
rep0(i, numT) {
key.ts[i][0] = ts[i].position;
key.ts[i][1] = ts[i].time;
}
rep0(i, numF) {
key.eaten[i] = fs[i].time < INF;
}
}
// (debug) 置換表のヒット数
int numHit = 0;
// (debug) 置換表のアクセス数
int numTotal = 0;
// 現状から貪欲にエサを食べていった場合の合計ターン数を返す
int evaluateGreedy() {
// テーブルを見る
TableKey key;
getTableKey(key);
int hash = key.hash();
int tableVal = table.getVal(key, hash);
if (tableVal != -1) {
numHit++;
return tableVal;
}
numTotal++;
int positions[MAX_T];
int turtleTimes[MAX_T];
int foodTimes[MAX_F];
pdi saved[MAX_F];
rep0(i, numT) {
positions[i] = ts[i].position;
turtleTimes[i] = ts[i].time;
}
rep0(i, numF) {
foodTimes[i] = fs[i].time;
}
int score = evaluateGreedyFast();
rep0(i, numT) {
ts[i].position = positions[i];
ts[i].time = turtleTimes[i];
}
numLeftFoods = 0;
leftFoodHeightSum = 0;
rep0(i, numF) {
fs[i].time = foodTimes[i];
if (fs[i].time == INF) {
numLeftFoods++;
leftFoodHeightSum += fs[i].height;
}
}
table.set(key, hash, score);
return score;
}
// 現状から辿り着ける最良の評価と次に食べるべきエサのインデックスを返す
pii searchRecursive(int lookahead) {
// 全てのエサが食べられた
if (numLeftFoods == 0) {
return pii(computeMaxTime(), -1);
}
// エサのコストを更新する
pdi costs[MAX_F];
int numCandidates = 0;
rep0(i, numF) {
if (fs[i].time < INF) {
continue;
}
costs[numCandidates++] = pdi(foodCost(i), i);
}
sort(costs, costs + numCandidates);
// 次に食べるエサの候補を絞る
const int MAX_CANDIDATES = 6;
int candidates[MAX_CANDIDATES];
int n;
n = min((int) (sqrt(2560.0 / (numF + numT * 0.2))), min(MAX_CANDIDATES, numCandidates));
if (lookahead == 0) n = 1;
// エサの更新間隔を決定する
rep0(i, n) {
candidates[i] = costs[i].second;
}
// DFS
int minCost = INF;
int minF = -1;
rep0(idx, n) {
int f = candidates[idx];
// 各カメが該当するエサに辿り着く時刻
pii times[MAX_T];
rep0(i, numT) {
T &t = ts[i];
int d = dists[t.position][f];
times[i] = pii(t.time + d, i);
}
sort(times, times + numT);
// エサの高さ
int h = fs[f].height;
// エサが食べられる時刻
int time = times[h - 1].first;
// 後で戻す用: 位置
int prevPositions[MAX_T];
// 後で戻す用: 移動可能時刻
int prevTimes[MAX_T];
// カメを動かしエサを食べる
rep0(i, h) {
T &t = ts[times[i].second];
prevPositions[i] = t.position;
prevTimes[i] = t.time;
t.time = time;
t.position = f;
}
fs[f].time = time;
leftFoodHeightSum -= h;
numLeftFoods--;
// 最小コストを計算
int cost;
if (numLeftFoods == 0) {
cost = computeMaxTime();
} else {
if (lookahead <= 1) {
cost = evaluateGreedy();
} else {
cost = searchRecursive(lookahead - 1).first;
}
}
if (cost < minCost) {
minCost = cost;
minF = f;
}
// カメとエサを戻す
rep0(i, h) {
T &t = ts[times[i].second];
t.position = prevPositions[i];
t.time = prevTimes[i];
}
fs[f].time = INF;
leftFoodHeightSum += h;
numLeftFoods++;
}
return pii(minCost, minF);
}
// 再帰探索の根
void searchRecursiveBase() {
numLeftFoods = numF;
leftFoodHeightSum = 0;
rep0(i, numF) {
fs[i].time = INF;
leftFoodHeightSum += fs[i].height;
}
rep0(i, numT) {
ts[i].position = numF + i;
}
// 残りのエサ
set<int> left;
rep0(i, numF) {
left.emplace(i);
}
int cnt = 0;
// 全部食べる
while (numLeftFoods > 0) {
// 再帰深さ2で探索を実行
pdi res = searchRecursive(2);
int f = res.second;
// 食べられる時刻を計算
pii times[MAX_T];
rep0(i, numT) {
T &t = ts[i];
times[i] = pii(t.time + dists[t.position][f], i);
}
sort(times, times + numT);
int h = fs[f].height;
int time = times[h - 1].first;
rep0(i, h) {
T &t = ts[times[i].second];
t.fs.emplace_back(f);
t.time = time;
t.position = f;
}
trace("food ", f, " is eaten at ", time);
F &food = fs[f];
food.time = time;
food.priority = cnt++;
leftFoodHeightSum -= food.height;
numLeftFoods--;
left.erase(f);
}
}
// 実際と同じ確率分布からステージを生成する
void generateStage(int stageId, Field &f) {
f.numT = stageId / 3 % 20 + 6;
f.numF = stageId / 60 % 4 * 20 + 40;
int distribution = 2 - stageId % 3;
const int WIDTH = 60;
const int HEIGHT = 30;
bool used[HEIGHT][WIDTH];
rep0(y, HEIGHT) {
rep0(x, WIDTH) {
used[y][x] = false;
}
}
int turtleCount = 0;
while (turtleCount < f.numT) {
int x = nextInt(WIDTH);
int y = nextInt(HEIGHT);
if (used[y][x]) continue;
used[y][x] = true;
f.ts[turtleCount][0] = x;
f.ts[turtleCount][1] = y;
turtleCount++;
}
int foodCount = 0;
while (foodCount < f.numF) {
int x = nextInt(WIDTH);
int y = nextInt(HEIGHT);
if (used[y][x]) continue;
used[y][x] = true;
f.fs[foodCount][0] = x;
f.fs[foodCount][1] = y;
int h = nextInt(f.numT) + 1;
rep0(i, distribution) {
h = nextInt(h) + 1;
}
f.fs[foodCount][2] = h;
foodCount++;
}
}
void setField(Field &f) {
numT = f.numT;
numF = f.numF;
rep0(i, numT) {
ts[i].init(f.ts[i][0], f.ts[i][1]);
}
rep0(i, numF) {
fs[i].init(f.fs[i][0], f.fs[i][1], f.fs[i][2]);
}
setupDists();
numLeftFoods = numF;
leftFoodHeightSum = 0;
rep0(i, numF) {
fs[i].time = INF;
leftFoodHeightSum += fs[i].height;
}
rep0(i, numT) {
ts[i].position = numF + i;
}
}
void getField(Field &f) {
f.numT = numT;
f.numF = 0;
rep0(i, numT) {
int pos = ts[i].position;
f.ts[i][0] = pos < numF ? fs[pos].x : ts[pos - numF].x;
f.ts[i][1] = pos < numF ? fs[pos].y : ts[pos - numF].y;
}
rep0(i, numF) {
if (fs[i].time == INF) {
f.fs[f.numF][0] = fs[i].x;
f.fs[f.numF][1] = fs[i].y;
f.fs[f.numF][2] = fs[i].height;
f.numF++;
}
}
}
int stageSeed = 345784967;
// 現在の評価関数で一度だけ貪欲に探索したときのターン数を返す
// パラメータの学習用
//
// -1: 全部
//
// 0～239: 個別ステージ
//
// 240: 分散2のステージのみでスコアを3倍する
// 241: 分散1〃
// 242: 分散0〃
//
// 243: 分散2、エサ40個のステージのみでスコアを12倍する
// 244: 分散1、エサ40個〃
// 245: 分散0、エサ40個〃
// 246: 分散2、エサ60個〃
// 247: 分散1、エサ60個〃
// 248: 分散0、エサ60個〃
// 249: 分散2、エサ80個〃
// 250: 分散1、エサ80個〃
// 251: 分散0、エサ80個〃
// 252: 分散2、エサ100個〃
// 253: 分散1、エサ100個〃
// 254: 分散0、エサ100個〃
int evaluateCurrentParamRaw(int stageNumber) {
int oldSeed = seed();
int scoreSum = 0;
seed(stageSeed);
rep0(t, 240) {
int id = t;
if (stageNumber >= 0 && stageNumber < 240) id = stageNumber;
int mod3 = -1;
int div60 = -1;
if (stageNumber >= 240) {
mod3 = (stageNumber - 240) % 3;
}
if (stageNumber >= 243) {
div60 = (stageNumber - 243) / 3;
}
if (mod3 != -1 && t % 3 != mod3) {
continue;
}
if (div60 != -1 && t / 60 != div60) {
continue;
}
Field f;
generateStage(id, f);
setField(f);
int score = evaluateGreedyFast();
scoreSum += score;
}
seed(oldSeed);
if (stageNumber >= 240) scoreSum *= 3;
if (stageNumber >= 243) scoreSum *= 4;
return scoreSum;
}
#if !LEARNING
// ステージ開始時の処理
void beginStage(const Stage& st) {
trace("\nstage ", stage, " begin ----------------------------\n");
numF = st.foods().count();
numT = st.turtlePositions().count();
if (targetId != -1 && stage % 3 + stage / 60 * 3 != targetId) {
return;
}
// エサの初期化
rep0(i, numF) {
auto &f = st.foods()[i];
auto &p = f.pos();
fs[i].init(p.x, p.y, f.height());
}
// カメの初期化
rep0(i, numT) {
auto &p = st.turtlePositions()[i];
ts[i].init(p.x, p.y);
}
// パラメータ設定
foodp.loadParam(stage);
// テーブル初期化
table.clear();
// 解く
setupDists();
searchRecursiveBase();
}
void nextActions(const Stage &st, Actions& ac) {
if (targetId != -1 && stage % 3 + stage / 60 * 3 != targetId) {
rep0(i, numT) {
ac.add(Action_Wait);
}
return;
}
auto &poss = st.turtlePositions();
struct {
Action operator()(int x, int y, int tx, int ty) {
if (x < tx) return Action_MoveRight;
if (x > tx) return Action_MoveLeft;
if (y < ty) return Action_MoveDown;
if (y > ty) return Action_MoveUp;
return Action_Wait;
}
} go;
rep0(i, numT) {
T &t = ts[i];
t.x = poss[i].x;
t.y = poss[i].y;
int n = len(t.fs);
int &numEaten = t.numEaten;
vector<int> &tfs = t.fs;
// エサを食べ終えたら次のエサへ向かう
if (numEaten < n && st.turn() == fs[tfs[numEaten]].time) numEaten++;
// 全てのエサを食べ終わったか？
if (numEaten == n) {
ac.add(Action_Wait);
continue;
}
// 次のエサへ進む
F &f = fs[tfs[numEaten]];
ac.add(go(t.x, t.y, f.x, f.y));
}
}
// ステージ終了時の処理
void endStage(const Stage& st) {
trace("\nstage ", stage, " end ----------------------------\n");
numF = 0;
numT = 0;
stage++;
}
#endif
};
#if LEARNING
// パラメータの学習モードが有効になっている場合
// 個別スレッドが実行するジョブ
class Job {
public:
function<void()> main;
bool ready;
bool finished;
Job(): ready(false), finished(true) {
}
// ジョブを設定
void set(function<void()> _main) {
main = _main;
ready = true;
finished = false;
}
// ジョブを実行
void run() {
if (!ready) return;
ready = false;
main();
main = nullptr;
finished = true;
}
};
// ワーカーの数
const int NUM_WORKERS = 256;
// ワーカー全体のマネージャー
class Workers {
public:
bool workersRunning = false;
thread *threads[NUM_WORKERS];
Job jobs[NUM_WORKERS];
mutex jobMutices[NUM_WORKERS];
Workers() {
}
~Workers() {
}
void workerMain(int id) {
//tracex("worker ", id, " started.");
while (true) {
if (!workersRunning) break;
{
lock_guard<mutex> lock(jobMutices[id]);
Job &job = jobs[id];
if (job.ready) {
//tracex(id, " new job found!");
job.run();
//tracex(id, " job finished.");
}
}
this_thread::sleep_for(chrono::milliseconds(5));
}
//tracex("worker ", id, " finished.");
}
// 全ワーカーを開始
void start() {
if (workersRunning) {
tracex("workers already running");
return;
}
tracex("starting workers...");
workersRunning = true;
rep0(i, NUM_WORKERS) {
threads[i] = new thread([&, i] {
workerMain(i);
});
}
}
// 全ワーカーを停止
void stop() {
if (!workersRunning) {
tracex("workers not running");
return;
}
tracex("stopping workers...");
workersRunning = false;
rep0(i, NUM_WORKERS) {
threads[i]->join();
}
rep0(i, NUM_WORKERS) {
delete threads[i];
}
}
template <typename func>
void setJob(int jobId, func main) {
lock_guard<mutex> lock(jobMutices[jobId]);
jobs[jobId].set(main);
}
bool finished(int jobId) {
return jobs[jobId].finished;
}
bool finishedAll() {
rep0(i, NUM_WORKERS) {
if (!finished(i)) return false;
}
return true;
}
private:
};
Workers workers;
class FoodParamLearner {
public:
int stageNumber;
FoodParam foodpBest;
FoodParam foodpDefault;
FoodParam foodp;
double bestScore;
double score;
int stageSeed;
Context rnd;
string fileId;
FoodParamLearner() {
stageNumber = 0;
bestScore = 1e9;
score = bestScore;
stageSeed = 12345678;
}
double evalParams(int stageSeed, double *params, int stageNumber) {
// 全体の計算実行数
const int TOTAL_NUM = 64;
// 処理の分割数
const int NUM_THREADS = 8;
int batch = TOTAL_NUM / NUM_THREADS;
int scores[TOTAL_NUM];
if (TOTAL_NUM % NUM_THREADS) trace("TOTAL_NUM % NUM_THREADS must be zero");
mutex rndMutex;
Context rnd;
rnd.seed(stageSeed);
// 個別ジョブを生成
rep0(id, NUM_THREADS) {
workers.setJob(id, [id, ¶ms, &stageNumber, &batch, &scores, &rnd, &rndMutex]() {
Context c;
int *res = scores + id * batch;
c.foodp.copyParam(params);
rep0(i, batch) {
int nextSeed;
{
lock_guard<mutex> lock(rndMutex);
nextSeed = rnd.nextInt();
}
c.stageSeed = nextSeed;
res[i] = c.evaluateCurrentParamRaw(stageNumber);
}
});
}
// 全てのジョブが終わるまで待つ
while (!workers.finishedAll()) {
this_thread::sleep_for(chrono::milliseconds(5));
}
double mean = 0;
rep0(i, TOTAL_NUM) {
mean += scores[i];
}
mean /= TOTAL_NUM;
return mean;
}
// パラメータ読み込み
bool readParam() {
if (foodp.readParamByName("params_" + str(stageNumber))) return true;
if (stageNumber >= 243) {
rep(i, 1, 10) {
if (stageNumber - i * 3 < 240) break;
if (foodp.readParamByName("params_" + str(stageNumber - i * 3))) return true;
}
}
return false;
}
// パラメータ書き出し
bool writeParam() {
ofstream fout;
fout.open("params_" + str(stageNumber) + fileId, ios::out | ios::binary | ios::trunc);
if (!fout) {
return false;
}
fout.write((char*) foodp.activeParams, sizeof(double) * NUM_FOOD_PARAMS);
fout.close();
return true;
}
void saveBest() {
foodpBest = foodp;
bestScore = score;
}
void loadBest() {
foodp = foodpBest;
score = bestScore;
}
// ステージのシードを更新
void updateStageSeed() {
loadBest();
stageSeed = rnd.nextInt();
double targetScore = evalParams(stageSeed, foodpDefault.activeParams, stageNumber);
double currentScore = evalParams(stageSeed, foodp.activeParams, stageNumber);
trace("stage: ", stageNumber);
trace("target score: ", targetScore);
trace("current score: ", currentScore);
trace("diff: ", currentScore - targetScore);
score = currentScore;
bestScore = currentScore;
}
// 規定回数学習を行う
void learn(int _stageNumber, int repeat) {
stageNumber = _stageNumber;
foodpDefault.loadParam((stageNumber - 243) % 3 + (stageNumber - 243) / 3 * 60);
foodp.loadParam((stageNumber - 243) % 3 + (stageNumber - 243) / 3 * 60);
fileId = "_" + str(rnd.nextInt() % 65536);
double initialTemp = 10;
score = 1e9;
readParam();
rep0(i, NUM_FOOD_PARAMS) {
foodp.activeParams[i] *= 1.0 + (rnd.nextFloat() * 2 - 1) * 0.1;
}
int signx = rnd.nextInt(2) * 2 - 1;
int signy = rnd.nextInt(2) * 2 - 1;
foodp.activeParams[6] *= signx;
foodp.activeParams[7] *= signy;
foodp.activeParams[16] *= signx;
foodp.activeParams[17] *= signy;
saveBest();
rep0(stageIter, repeat) {
updateStageSeed();
double temp = initialTemp;
double beta = 0.99;
rep0(t, 100) {
temp *= beta;
int paramIndex = rnd.nextInt(NUM_FOOD_PARAMS);
double prevParam = foodp.activeParams[paramIndex];
double maxDiff = max(abs(prevParam) * 0.05, 0.01);
double minDiff = 0.005;
double paramDiff = (rnd.nextFloat() * 2 - 1) * maxDiff;
if (abs(paramDiff) < minDiff) {
paramDiff = minDiff * (rnd.nextInt(2) * 2 - 1);
}
foodp.activeParams[paramIndex] += paramDiff;
double newScore = evalParams(stageSeed, foodp.activeParams, stageNumber);
bool pass = false;
if (newScore < score) {
pass = true;
} else {
double diff = newScore - score;
double prob = exp(-diff / temp);
if (rnd.nextFloat() < prob) {
pass = true;
}
}
if (!pass) {
foodp.activeParams[paramIndex] = prevParam;
continue;
}
//tracex("score: ", newScore, " (trial = ", t, ", T = ", temp, ")");
score = newScore;
if (score < bestScore) {
saveBest();
writeParam();
//tracex("updated! score = ", score, " (trial = ", t, ", T = ", temp, ")");
}
}
}
}
};
void learnFoodParam() {
workers.start();
// 12分割されたパラメータを学習し続ける
FoodParamLearner l;
while (true) rep0(i, 12) l.learn(243 + i, 10);
workers.stop();
}
int main() {
debug = true;
learnFoodParam();
return 0;
}
#else
// 本番環境の場合
Context globalContext;
// ステージ開始時の処理
void Answer::initialize(const Stage& st) {
globalContext.beginStage(st);
}
// ステージ終了時の処理
void Answer::finalize(const Stage& st) {
globalContext.endStage(st);
}
//------------------------------------------------------------------------------
/// 各ターンのカメの行動を指定する。
/// @detail 各カメの行動を指定し、aActionsの要素に追加してください。
/// aActions[i]がi番目のカメの行動になります。
/// aActionsの要素数がaStage.turtlePositions()の要素数と異なる場合、アサートに失敗します。
/// @param[in] aStage 現在のステージ。
/// @param[out] aActions 各カメの行動を指定する配列。
void Answer::setActions(const Stage& st, Actions& ac) {
globalContext.nextActions(st, ac);
}
Answer::Answer() {
// デバッグ出力を切る
debug = false;
}
Answer::~Answer() {
}
} // namespace
#endif
// EOF