この記事はKMCアドベントカレンダー18日目の記事です。
皆様こんにちは。zekeと申します。寒いですね、自転車を手袋なしで乗っていると手先が凍ってしまいました。今回はハル研究所が主催するプログラミングコンテストに参加しましたので雑に振り返っていきたいと思います。
さてハル研プロコンは2020年の11/4~11/18に開催されました。ハル研プロコンは2003年ごろから開催されているマラソン型プログラミンコンテスト*1で有名らしいですね。サークルの中で話に出ていたので気になって参加を決めました。最終順位は43位でした。*230位以内でもらえるトートバックほしかった…
問題
昔むかし、かけっこでカメに負けてしまったウサギがいました。 悔しさを胸にウサギは修行の旅にでます。 次こそ勝つために、修行の地に散らばる秘伝の巻物を集めてください。
はい、まあこれだけではわからないので簡単に説明しますと、
二次元平面上に「巻物」が散らばっている、目標はそれらをできるだけ早く回収することである。
参加者は巻物を回収する「ウサギ」が次にどこに向かうかを座標で指定しなくてはならない。
「ウサギ」の飛ぶ距離は、「巻物」を取るたびに長くなるが、「地形」によっては短くなってしまう。*3
ステージに関する全情報が開示されており、乱数依存。*4
こんな感じでしょうか。問題を見たときTSP*5みたいだなと記憶しています。
この問題特有の設定として
がありました。個人的に一つ目に関する考察が大変だったように思われます。
可視化ツールと確認用コードがありましたので実行してみると…
確認用コードを読んでみると、どうやらまだとっていない巻物に一直線に向かうような行動を指示しているようです。これでは途中に「池」があっても迂回しないので時間がかかってしまいますね…
実装方針
ここで今後のおおまかな実装方針を決めました。
最適な巡回順を見つける
最短の経路を探索する
一つ目ではどの巻物からとっていくか？というのを考えていて、二つ目ではある地点からある地点まで移動するときに、地形などを考慮してどのように進んでいくか？というのを考えようとしています。
経路探索
まず取り掛かったのは二つ目です。これは実装方針が立ちやすかったからです。二次元グリッド上の最短経路探索は重みありグラフの最短経路問題に帰着できることが多いです。今回の場合だと地形によって重みを付けた有向グラフの構築をした後、ダイクストラ法*10というアルゴリズムを適用することで簡単に実装することができます。(一つの座標に対して8方向へ有向辺を張りました、ステージが50*50=2500の大きさで *11 と考えると計算量
オーダーになることもわかります。)
実行してみると…
総ターン数が劇的に改良されているのもわかります*13
次に一つ目の巡回順について考えてみましょう。TSP問題はNP困難ですので多項式時間で解くことができません。そこでTSP問題で最もよく使われる2-opt法*14を実装しました。これはTSPの近似解を求めるもので、局所改善法の一つでもあります。貪欲解*15から局所改善を行いました。
わかりやすいように二つ並べました。左が改善前(貪欲解)で右が改善後(局所改善適用後)です。264ターンから194ターンに改善されてます。いい感じですね。
またこれを実装した後に制約をにらんでいると巻物の最大数が20個であることに気づきました*16。それならばbitDP*17による完全解を求めることができます！先ほどTSPはNP困難と紹介したのですが、指数時間で間に合う制約なら完全解を出すことができます。といっても愚直にやると巻物の数をNとするとかかってしまい計算量
？ぐらいかかってしまいます。富岳だと60sec以内で実行できるかもしれませんが、一般的なパソコンなら無理です*18。しかし動的計画法を用いると
まで落とすことが可能です。これを実装してやることで時間内で(20secほどかかる)巡回順の完全解を求めることが可能です。*19
微調整
ここまでで30000の大台を切ることに成功しました*20。ここからは巡回順は最善であることが証明されているので、経路最適化に注力していくことになります。ここではウサギの座標が浮動小数点で表記されていることがポイントです。単純な経路探索では大体の経路しかわからないため、細かいところは別に実装する必要があります。以下は細かい修正を比較したものです。
あとは光学的距離をヒントに幾何的なアプローチをしていたのですが、時間切れになってしまいました…
最終的には27567を達成することができました！
感想
とても楽しかったです！マラソンの醍醐味を味わえた問題でした。ある程度こうすればうまくいくんじゃないかと仮説を立てて、実装＆デバッグした後にうまく動いているのを見ると感激してしまいますね。
個人的に大変だったのは膨大なコードファイルの数ですね。
またこれはマラソン競技全般に言えるのですがデバッグがしんどいです…振り返りでは簡単と書いてある場所でも実際の実装には二日かかっているものもあります。ひとえに能力不足ですね、精進します。大体全体で30時間ぐらいかかったんじゃないかなと思います。実は自動車免許合宿中にやっていたこともあって大学の課題とともにやる必要があり、時間があまりとれなかったのが反省点です。ちゃんと計画して生きていきたいですね。
それでもマラソンは楽しい！みんなもやろう！
最後に
明日のKMC のアドベントカレンダーはpastakさんです。
おまけ
誰も見ないと思いますが、最終提出コードを貼っておきます…
//------------------------------------------------------------------------------
/// @file
/// @author ハル研究所プログラミングコンテスト実行委員会
///
/// @copyright (C)HAL Laboratory, Inc.
/// @attention このファイルの利用は、同梱のREADMEにある
/// 利用条件に従ってください。
//------------------------------------------------------------------------------
#include "Answer.hpp"
#include <bits/stdc++.h>
//------------------------------------------------------------------------------
namespace hpc {
typedef long double Weight;
struct Edge { // src:辺の始点,dst:辺の終点,weight:辺の重さ
int src, dst;
Weight weight;
Edge(int Src, int Dst, Weight weeight) {
src = Src;
dst = Dst;
weight = weeight;
}
};
using Edges = std::vector<Edge>;
using Graph = std::vector<Edges>;
const long long INF = 1e18;
const double DINF = 1e15;
bool operator<(const Edge& e, const Edge& f) {
return e.weight != f.weight ? e.weight > f.weight
: //辺は重さが重いものを"小さい"と定義する
e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
// Global
template <class T>
bool chmax(T& a, const T& b) {
if (a < b) {
a = b;
return 1;
}
return 0;
}
template <class T>
bool chmin(T& a, const T& b) {
if (b < a) {
a = b;
return 1;
}
return 0;
}
Vector2 OUTPUT(Vector2 pos, Vector2 target) {
float xres = 0;
float yres = 0;
if (pos.x > target.x && pos.x < target.x + 1) {
xres = pos.x;
} else {
xres = target.x + 0.5;
}
if (pos.y > target.y && pos.y < target.y + 1) {
yres = pos.y;
} else {
yres = target.y + 0.5;
}
return Vector2(xres, yres);
}
Graph StageGraph(Parameter::StageWidth* Parameter::StageHeight);
std::vector<int> scrolls_order;
std::vector<int> scroll_grid;
std::vector<std::vector<int>> state_type(
Parameter::StageHeight, std::vector<int>(Parameter::StageWidth));
int scroll_index = 0;
double distance(double sy, double gy, double sx, double gx) {
return sqrt(pow(sy - gy, 2) + pow(sx - gx, 2));
}
//
//------------------------------------------------------------------------------
/// コンストラクタ
/// @detail 最初のステージ開始前に実行したい処理があればここに書きます
Answer::Answer() {}
//------------------------------------------------------------------------------
/// デストラクタ
/// @detail 最後のステージ終了後に実行したい処理があればここに書きます
Answer::~Answer() {}
void shortestPath(const Graph& g, int s, std::vector<Weight>& dist,
std::vector<int>& prev) {
int n = g.size();
dist.assign(n, INF);
dist[s] = 0;
prev.assign(n, -1);
std::priority_queue<Edge> Q;
Q.push(Edge(-2, s, 0));
while (!Q.empty()) {
Edge e = Q.top();
Q.pop();
if (prev[e.dst] != -1) continue;
prev[e.dst] = e.src;
for (auto f = g[e.dst].begin(); f != g[e.dst].end(); f++) {
if (dist[f->dst] > e.weight + f->weight) {
dist[f->dst] = e.weight + f->weight;
Q.push(Edge(f->src, f->dst, e.weight + f->weight));
}
}
}
}
std::vector<int> buildPath(const std::vector<int>& prev, int goal, int start) {
std::vector<int> path;
for (int u = goal; u != start; u = prev[u]) path.push_back(u);
// reverse(path.begin(), path.end());
return path;
}
int Two2One(const int y, const int x) { return y * Parameter::StageWidth + x; }
std::pair<int, int> One2Two(const int state) {
return {state / Parameter::StageWidth, state % Parameter::StageWidth};
}
//------------------------------------------------------------------------------
/// 各ステージ開始時に呼び出される処理
/// @detail 各ステージに対する初期化処理が必要ならここに書きます
/// @param aStage 現在のステージ
void Answer::initialize(const Stage& aStage) {
//初手グラフ構築
// Timer::timer time();
scroll_index = 0;
Graph tempGraph(Parameter::StageWidth * Parameter::StageHeight);
StageGraph = tempGraph;
scrolls_order = {};
scroll_grid = {};
// std::cerr << "start" << std::endl;
int dx[] = {-1, 0, 1, 0, 1, -1, 1, -1, 1, 2, 1, 2, -1, -2, -1, -2};
int dy[] = {0, 1, 0, -1, 1, -1, -1, 1, 2, 1, -2, -1, 2, 1, -2, -1};
for (int height = 0; height < Parameter::StageHeight; height++) {
for (int width = 0; width < Parameter::StageWidth; width++) {
int end = Two2One(height, width);
Terrain type = aStage.terrain(Vector2(width, height));
Weight poswei = 0;
int TYPE = 0;
if (type == Terrain::Plain) {
poswei = 3;
TYPE = 0;
// std::cerr<<"P";
}
if (type == Terrain::Bush) {
poswei = 5;
TYPE = 1;
// std::cer
// std::cerr << "B";
}
if (type == Terrain::Sand) {
poswei = 10;
TYPE = 2;
// std::cerr << "S";
}
if (type == Terrain::Pond) {
TYPE = 3;
// continue;
// std::cerr << width<<" "<<height<<std::endl;
poswei = 30;
}
state_type[height][width] = TYPE;
for (int way = 0; way < 8; way++) {
int starty = height + dy[way];
int startx = width + dx[way];
if (startx >= Parameter::StageWidth || startx < 0 ||
starty >= Parameter::StageHeight || starty < 0) {
continue;
}
if (way >= 8) {
poswei *= 2.236;
} else if (way >= 4) {
poswei *= 1.414;
}
int start = Two2One(starty, startx);
StageGraph[end].push_back(Edge(end, start, poswei));
}
}
// std::cerr<<std::endl;
}
// std::cerr<<"initialize finished"<<std::endl;
////////////////////////////////////////////////////////////////////////////////
// bitDP
for (auto scroll : aStage.scrolls()) {
scroll_grid.push_back(Two2One(scroll.pos().y, scroll.pos().x));
}
int scrolls_num = scroll_grid.size();
std::vector<std::vector<Weight>> scrolls_dist(
scrolls_num, std::vector<Weight>(scrolls_num));
for (int i = 0; i < scrolls_num; i++) {
std::vector<Weight> dist;
std::vector<int> prev;
// std::pair<int,int> tempnow=One2Two(scroll_grid[i]);
// int nowh=tempnow.first;
// int noww=tempnow.second;
shortestPath(StageGraph, scroll_grid[i], dist, prev);
for (int j = 0; j < scrolls_num; j++) {
if (scrolls_dist[j][i] != 0) {
scrolls_dist[i][j] = scrolls_dist[j][i];
} else {
scrolls_dist[i][j] = dist[scroll_grid[j]];
}
}
}
auto pos = aStage.rabbit().pos();
int rabbit_posx = static_cast<int>(pos.x);
int rabbit_posy = static_cast<int>(pos.y);
std::vector<Weight> dist_fromrabbit;
std::vector<int> prev_fromrabbit;
shortestPath(StageGraph, Two2One(rabbit_posy, rabbit_posx), dist_fromrabbit,
prev_fromrabbit);
int nearest_scroll = 0;
Weight nearest_reg = INF;
for (int i = 0; i < scrolls_num; i++) {
if (nearest_reg > dist_fromrabbit[scroll_grid[i]]) {
nearest_reg = dist_fromrabbit[scroll_grid[i]];
nearest_scroll = i;
}
// std::cerr<<dist_fromrabbit[scroll_grid[i]]<<std::endl;
}
if (scrolls_num <= 2) {
std::vector<bool> have_seen(scrolls_num, false);
scrolls_order = {};
for (int i = 0; i < scrolls_num; i++) {
scrolls_order.push_back(nearest_scroll);
Weight tempreg = INF;
int next_order = 0;
have_seen[nearest_scroll] = true;
for (int j = 0; j < scrolls_num; j++) {
if (have_seen[j]) {
continue;
}
if (tempreg > scrolls_dist[nearest_scroll][j]) {
tempreg = scrolls_dist[nearest_scroll][j];
next_order = j;
}
}
nearest_scroll = next_order;
}
return;
}
/////////////////////////////////////////////////////////////////////////////////////
std::vector<std::vector<Weight>> bitDP(
std::pow(2, scrolls_num), std::vector<Weight>(scrolls_num, 1e9));
std::vector<double> bias(scrolls_num - 1);
bias[0] = 1.00;
for (int i = 1; i < scrolls_num - 1; i++) {
bias[i] = bias[i - 1] / 1.1;
}
bitDP[(1 << nearest_scroll)][nearest_scroll] = 0;
for (int bit = 1; bit < std::pow(2, scrolls_num); bit++) {
for (int j = 0; j < scrolls_num; j++) {
if (!(bit & (1 << j))) {
continue;
}
if (__builtin_popcount(bit) == 1) {
continue;
}
int beforebit = bit & ~(1 << j);
int befotebitcount = __builtin_popcount(beforebit);
for (int k = 0; k < scrolls_num; k++) {
chmin(bitDP[bit][j],
bitDP[beforebit][k] + ((Weight)scrolls_dist[k][j] *
(Weight)bias[befotebitcount - 1]));
}
}
}
Weight bitres = DINF;
int hogehoge = 0;
for (int i = 0; i < scrolls_num; i++) {
if (chmin(bitres, bitDP[std::pow(2, scrolls_num) - 1][i])) {
hogehoge = i;
}
}
int invbit = std::pow(2, scrolls_num) - 1;
int invtop = hogehoge;
std::vector<int> bitDPinv_path;
bitDPinv_path.push_back(invtop);
while (1) {
if (invbit == (1 << (nearest_scroll))) {
break;
}
int beforebit = invbit & ~(1 << invtop);
int bitCount = __builtin_popcount(beforebit);
for (int i = 0; i < scrolls_num; i++) {
if (abs((bitDP[beforebit][i] +
(scrolls_dist[i][invtop] * bias[bitCount - 1])) -
bitDP[invbit][invtop]) < 0.0001) {
bitDPinv_path.push_back(i);
invbit = beforebit;
invtop = i;
break;
}
}
}
reverse(bitDPinv_path.begin(), bitDPinv_path.end());
scrolls_order = bitDPinv_path;
std::cerr << "bitDP score" << bitDP[(1 << scrolls_num) - 1][hogehoge]
<< std::endl;
return;
/////////////////////////////////////////////////////////////////////////////////////
}
Vector2 remote_jump(Vector2 pos, Vector2 goal, Weight power,
const Stage& aStage) {
Vector2 res;
double disreg = 0;
for (double i = power; i >= 0.01; i -= 0.01) {
Vector2 res1 = aStage.getNextPos(pos, i, goal);
Vector2 res2 = aStage.getNextPos(res1, power, goal);
if (chmax(disreg, distance(res2.y, pos.y, res2.x, pos.x))) {
res = res1;
}
}
return res;
}
//------------------------------------------------------------------------------
/// 毎フレーム呼び出される処理
/// @detail 移動先を決定して返します
/// @param aStage 現在のステージ
/// @return 移動の目標座標
///////////////////////////MAIN///////////////////////////////////////
Vector2 Answer::getTargetPos(const Stage& aStage) {
while (1) {
// std::cerr<<scroll_index<<std::endl;
auto const pos = aStage.rabbit().pos();
int rabbit_posx = static_cast<int>(pos.x);
int rabbit_posy = static_cast<int>(pos.y);
std::pair<int, int> goal =
One2Two(scroll_grid[scrolls_order[scroll_index]]);
for (auto scroll : aStage.scrolls()) {
if (static_cast<int>(scroll.pos().x) == goal.second &&
static_cast<int>(scroll.pos().y) == goal.first) {
if (scroll.isGotten()) {
// std::cerr<<"get"<<std::endl;
scroll_index++;
goal = One2Two(scroll_grid[scrolls_order[scroll_index]]);
}
break;
}
}
int rabbit_pos = Two2One(rabbit_posy, rabbit_posx);
std::vector<Weight> dist;
std::vector<int> prev;
shortestPath(StageGraph, rabbit_pos, dist, prev);
std::vector<int> temp_path = buildPath(
prev, scroll_grid[scrolls_order[scroll_index]], rabbit_pos);
bool is_sea = true;
for (int i = 1; i < static_cast<int>(temp_path.size()); i++) {
std::pair<int, int> now = One2Two(temp_path[i]);
std::pair<int, int> tempgoal;
if (i != 0) {
tempgoal = One2Two(temp_path[i - 1]);
} else {
tempgoal = One2Two(temp_path[i]);
}
if (state_type[static_cast<int>(now.first)]
[static_cast<int>(now.second)] != 3) {
is_sea = false;
}
bool land2sea =
(state_type[pos.y][pos.x] == 0) &&
(state_type[static_cast<int>(tempgoal.first)]
[static_cast<int>(tempgoal.second)] == 3);
if (!land2sea) {
land2sea = (state_type[pos.y][pos.x] == 0) &&
(state_type[static_cast<int>(tempgoal.first)]
[static_cast<int>(tempgoal.second)] == 2);
}
double power =
aStage.rabbit().power() *
Parameter::JumpTerrianCoefficient[state_type[static_cast<int>(pos.y)][static_cast<int>(pos.x)]];
double purepower = aStage.rabbit().power();
Vector2 nownext = aStage.getNextPos(pos, purepower, Vector2(now.second + 0.5, now.first + 0.5));
Vector2 tempnext = aStage.getNextPos(pos,purepower,Vector2(tempgoal.second + 0.5, tempgoal.first + 0.5));
if (state_type[(int)tempnext.y][(int)tempnext.x]>state_type[(int)nownext.y][(int)nownext.x]) {
continue;
}
if (state_type[(int)tempnext.y][(int)tempnext.x]>state_type[(int)nownext.y][(int)nownext.x]) {
continue;
}
if(state_type[pos.y][pos.x]==0&&state_type[(int)tempnext.y][(int)tempnext.x]==3&&state_type[(int)nownext.y][(int)nownext.x]==3&&state_type[(int)tempgoal.first][(int)tempgoal.second]==0){
continue;
}
Vector2 now_state = pos;
Vector2 goal_vector =
Vector2(tempgoal.second + 0.5, tempgoal.first + 0.5);
while (1) {
if ((state_type[static_cast<int>(pos.y)]
[static_cast<int>(pos.x)] == 2 ||
state_type[static_cast<int>(pos.y)]
[static_cast<int>(pos.x)] == 3)) {
break;
}
if (state_type[static_cast<int>(pos.y)]
[static_cast<int>(pos.x)] !=
state_type[static_cast<int>(goal_vector.y)]
[static_cast<int>(goal_vector.x)]) {
break;
}
if (state_type[static_cast<int>(now_state.y)]
[static_cast<int>(now_state.x)] >
state_type[static_cast<int>(pos.y)]
[static_cast<int>(pos.x)]) {
break;
}
if (now_state.x == goal_vector.x &&
now_state.y == goal_vector.y) {
// break;
return Vector2(goal_vector.x, goal_vector.y);
}
now_state =
aStage.getNextPos(now_state, purepower, goal_vector);
}
if (distance(pos.y, now.first, pos.x, now.second) < power) {
if (land2sea) {
// return Vector2(tempgoal.second + 0.5, tempgoal.first +
// 0.5);///////////////////////////
return remote_jump(
pos,
Vector2(tempgoal.second + 0.5, tempgoal.first + 0.5),
purepower, aStage);
}
return Vector2(tempgoal.second + 0.5, tempgoal.first + 0.5);
}
if (distance(pos.y, now.first, pos.x, now.second + 1) < power) {
if (land2sea) {
// return Vector2(tempgoal.second + 0.5, tempgoal.first +
// 0.5);///////////////////////////
return remote_jump(
pos,
Vector2(tempgoal.second + 0.5, tempgoal.first + 0.5),
purepower, aStage);
}
return Vector2(tempgoal.second + 0.5, tempgoal.first + 0.5);
}
if (distance(pos.y, now.first + 1, pos.x, now.second) < power) {
if (land2sea) {
// return Vector2(tempgoal.second + 0.5, tempgoal.first +
// 0.5);///////////////////////////
return remote_jump(
pos,
Vector2(tempgoal.second + 0.5, tempgoal.first + 0.5),
purepower, aStage);
}
return Vector2(tempgoal.second + 0.5, tempgoal.first + 0.5);
// std::cerr << "hoge" << std::endl;
}
if (distance(pos.y, now.first + 1, pos.x, now.second + 1) < power) {
if (land2sea) {
// return Vector2(tempgoal.second + 0.5, tempgoal.first +
// 0.5);///////////////////////////
return remote_jump(
pos,
Vector2(tempgoal.second + 0.5, tempgoal.first + 0.5),
purepower, aStage);
}
return Vector2(tempgoal.second + 0.5, tempgoal.first + 0.5);
// std::cerr << "hoge" << std::endl;
}
}
reverse(temp_path.begin(), temp_path.end());
std::pair<int, int> Tempres = One2Two(temp_path[0]);
if ((abs(goal.first - rabbit_posy) + abs(goal.second - rabbit_posx) <
3) |
is_sea) {
return Vector2(goal.second + 0.5, goal.first + 0.5);
}
if (state_type[static_cast<int>(pos.y)][static_cast<int>(pos.x)] == 3) {
for (int i = 0; i < static_cast<int>(temp_path.size()); i++) {
std::pair<int, int> tempres = One2Two(temp_path[i]);
if (state_type[static_cast<int>(tempres.first)]
[static_cast<int>(tempres.second)] != 3) {
return Vector2(tempres.second + 0.5, tempres.first + 0.5);
}
}
}
reverse(temp_path.begin(), temp_path.end());
return Vector2(Tempres.second + 0.5, Tempres.first + 0.5);
}
}
///////////////////////////MAIN///////////////////////////////////////
//------------------------------------------------------------------------------
/// 各ステージ終了時に呼び出される処理
/// @detail 各ステージに対する終了処理が必要ならここに書きます
/// @param aStage 現在のステージ
void Answer::finalize(const Stage& aStage) {}
} // namespace hpc
// EOF
*1:競技プログラミングの中で比較的長期間で開催されるコンテストのこと。なにかしらのスコアで競うものが多い。今回は約2週間。
*2:最高順位は28位でした。
*3:巻物をとるたびに1.1倍、地形に関しては後述
*4:手元と本番ではステージが異なる
*5:巡回セールスマン問題
*6:平地:1.0,茂み:0.6,砂地:0.3,池:0.1の補正
*7:マルチスレッド不可
*9:見にくくてすみません…
*10:辺が非負であるときに単一始点最短距離を解くためのアルゴリズム
*11:E:辺数,V:頂点数
*12:巡回順が変わっているのは重み付きで一番近くの巻物をとるように改良したため
*13:70%改善！
*14:2辺をランダムに選び、コストが低くなる方につなぎかえるアルゴリズム
*15:近い巻物から回収する
*16:先に読んどくべきだった…
*18:競プロでよく言ってる
*19:もちろん巻物をとったら飛距離が1.1倍になることを考慮しています
*20:ちなみに33333を切るとチャレンジスコア達成ということでハル研から褒められます
*21:かかりすぎ
