結果
| 問題 | No.5019 Hakai Project |
| ユーザー |
 Jiro_tech15
|
| 提出日時 | 2023-11-19 19:59:58 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 2,964 ms / 3,000 ms |
| コード長 | 26,493 bytes |
| コンパイル時間 | 5,522 ms |
| コンパイル使用メモリ | 235,604 KB |
| 実行使用メモリ | 136,044 KB |
| スコア | 2,554,096,188 |
| 最終ジャッジ日時 | 2023-11-19 20:03:39 |
| 合計ジャッジ時間 | 162,511 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge11 |
| 純コード判定しない問題か言語 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2,961 ms
116,712 KB |
| testcase_01 | AC | 2,962 ms
112,872 KB |
| testcase_02 | AC | 2,960 ms
123,372 KB |
| testcase_03 | AC | 2,960 ms
113,000 KB |
| testcase_04 | AC | 2,961 ms
115,560 KB |
| testcase_05 | AC | 2,962 ms
123,244 KB |
| testcase_06 | AC | 2,960 ms
104,932 KB |
| testcase_07 | AC | 2,962 ms
117,224 KB |
| testcase_08 | AC | 2,960 ms
108,776 KB |
| testcase_09 | AC | 2,961 ms
116,584 KB |
| testcase_10 | AC | 2,961 ms
115,048 KB |
| testcase_11 | AC | 2,962 ms
117,352 KB |
| testcase_12 | AC | 2,962 ms
118,632 KB |
| testcase_13 | AC | 2,961 ms
111,208 KB |
| testcase_14 | AC | 2,961 ms
126,572 KB |
| testcase_15 | AC | 2,960 ms
108,260 KB |
| testcase_16 | AC | 2,960 ms
110,952 KB |
| testcase_17 | AC | 2,962 ms
126,956 KB |
| testcase_18 | AC | 2,960 ms
105,316 KB |
| testcase_19 | AC | 2,963 ms
117,480 KB |
| testcase_20 | AC | 2,960 ms
115,560 KB |
| testcase_21 | AC | 2,964 ms
117,096 KB |
| testcase_22 | AC | 2,962 ms
124,908 KB |
| testcase_23 | AC | 2,962 ms
121,448 KB |
| testcase_24 | AC | 2,961 ms
123,752 KB |
| testcase_25 | AC | 2,961 ms
120,168 KB |
| testcase_26 | AC | 2,960 ms
108,264 KB |
| testcase_27 | AC | 2,962 ms
130,028 KB |
| testcase_28 | AC | 2,961 ms
118,504 KB |
| testcase_29 | AC | 2,960 ms
126,312 KB |
| testcase_30 | AC | 2,962 ms
100,964 KB |
| testcase_31 | AC | 2,961 ms
104,420 KB |
| testcase_32 | AC | 2,961 ms
109,672 KB |
| testcase_33 | AC | 2,962 ms
119,016 KB |
| testcase_34 | AC | 2,959 ms
106,084 KB |
| testcase_35 | AC | 2,961 ms
115,560 KB |
| testcase_36 | AC | 2,960 ms
101,348 KB |
| testcase_37 | AC | 2,959 ms
107,492 KB |
| testcase_38 | AC | 2,960 ms
92,900 KB |
| testcase_39 | AC | 2,962 ms
136,044 KB |
| testcase_40 | AC | 2,962 ms
104,804 KB |
| testcase_41 | AC | 2,963 ms
117,992 KB |
| testcase_42 | AC | 2,962 ms
114,920 KB |
| testcase_43 | AC | 2,962 ms
126,956 KB |
| testcase_44 | AC | 2,964 ms
121,324 KB |
| testcase_45 | AC | 2,960 ms
110,824 KB |
| testcase_46 | AC | 2,961 ms
129,132 KB |
| testcase_47 | AC | 2,962 ms
109,160 KB |
| testcase_48 | AC | 2,962 ms
118,124 KB |
| testcase_49 | AC | 2,962 ms
124,524 KB |
コンパイルメッセージ
main.cpp: In member function 'NBD* NBDGenerator::Generate(Solution*, int, double)':
main.cpp:992:3: warning: control reaches end of non-void function [-Wreturn-type]
992 | }
| ^
main.cpp: In static member function 'static void Pos::StaticInit(int)':
main.cpp:350:24: warning: 'dir' may be used uninitialized [-Wmaybe-uninitialized]
350 | move_to[dir][p] = {adj_x, adj_y};
| ^
main.cpp:337:17: note: 'dir' declared here
337 | Dir dir;
| ^~~
ソースコード
namespace atcoder {}
#ifdef LOCAL
#define dbg(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;
#else
#define NDEBUG
#define dbg(x) true;
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#endif
#ifdef GTEST
#include <gtest/gtest.h>
#endif
#include <math.h>
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#ifdef PERF
#include <gperftools/profiler.h>
#endif
using namespace std;
using namespace atcoder;
#define fast_io \
ios_base::sync_with_stdio(false); \
cin.tie(0); \
cout.tie(0);
#define ll long long int
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define reps(i, n) for (int i = 1; i <= (int)(n); i++)
#define REP(i, n) for (int i = n - 1; i >= 0; i--)
#define REPS(i, n) for (int i = n; i > 0; i--)
#define MOD (long long int)(1e9 + 7)
#define INF (int)(1e9)
#define LINF (long long int)(1e18)
#define chmax(a, b) a = (((a) < (b)) ? (b) : (a))
#define chmin(a, b) a = (((a) > (b)) ? (b) : (a))
#define ALL(v) v.begin(), v.end()
typedef pair<int, int> Pii;
typedef pair<ll, ll> Pll;
constexpr double PI = acos(-1);
#ifdef NDEBUG
#define CHECK(v1, op, v2)
#else
#define CHECK(v1, op, v2) \
if (!((v1)op(v2))) { \
cerr << "ERROR:" << (v1) << " " << (v2) << endl; \
assert((v1)op(v2)); \
}
#endif
long double nCr(const int n, const int r) {
long double ret = 1;
rep(t, r) {
ret *= (n - t);
ret /= (r - t);
}
return ret;
}
template <typename T>
string to_string(const vector<T>& vec) {
string ret = "";
rep(i, vec.size()) {
ret += vec[i].to_string();
if (i + 1 != vec.size()) {
ret += ",";
}
}
return ret;
}
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& vec) {
os << to_string(vec);
return os;
}
uint32_t xorshift() {
static uint32_t x = 12345789;
static uint32_t y = 362436069;
static uint32_t z = 521288629;
static uint32_t w = 88675123;
uint32_t t;
t = x ^ (x << 11);
x = y;
y = z;
z = w;
w ^= t ^ (t >> 8) ^ (w >> 19);
return w;
}
int rand(const uint32_t l, const uint32_t r) {
return xorshift() % (r - l) + l;
}
uint32_t rand_other_than(const uint32_t l, const uint32_t r,
const uint32_t other) {
const uint32_t num = rand(l, r - 1);
return num + (num >= other);
}
template <typename T>
const T& rand_vec(const vector<T>& vec) {
assert(vec.size() > 0);
return vec[rand(0, vec.size())];
}
template <typename T>
void shuffle(vector<T>& vec) {
rep(l, (int)vec.size() - 1) {
const int idx = rand(l, vec.size());
swap(vec[idx], vec[l]);
}
}
class Timer {
chrono::system_clock::time_point _start, _end;
ll _sum = 0, _count = 0;
public:
void start() { _start = chrono::system_clock::now(); }
void stop() { _end = chrono::system_clock::now(); }
void add() {
const chrono::system_clock::time_point now = chrono::system_clock::now();
_sum += static_cast<double>(
chrono::duration_cast<chrono::nanoseconds>(now - _start).count());
_count++;
}
ll sum() const { return _sum / 1000; }
int count() const { return _count; }
string average() const {
if (_count == 0) {
return "NaN";
}
return to_string(_sum / 1000 / _count);
}
void reset() {
_start = chrono::system_clock::now();
_sum = 0;
_count = 0;
}
inline int ms() const {
const chrono::system_clock::time_point now = chrono::system_clock::now();
return static_cast<double>(
chrono::duration_cast<chrono::microseconds>(now - _start).count() /
1000);
}
inline int ns() const {
const chrono::system_clock::time_point now = chrono::system_clock::now();
return static_cast<double>(
chrono::duration_cast<chrono::microseconds>(now - _start).count());
}
};
#ifdef LOCAL
struct Timers : unordered_map<string, Timer> {
friend ostream& operator<<(ostream& os, const Timers& timers) {
for (const auto& pa : timers) {
os << pa.first << " time: " << pa.second.sum() / 1000
<< " count: " << pa.second.count() << endl;
}
return os;
}
};
#else
struct Timers {
struct Dummy {
void start() const {}
void add() const {}
};
Dummy dummy;
const Dummy& operator[](const std::string& str) { return dummy; }
friend ostream& operator<<(ostream& os, const Timers& timers) { return os; }
};
#endif
Timers global_timers;
enum Dir {
// y-1, y+1, x-1, x+1
kU,
kD,
kL,
kR
};
Dir RightDir(const Dir dir) {
constexpr Dir kRightDirs[4] = {kR, kL, kU, kD};
return kRightDirs[dir];
}
Dir InvDir(const Dir dir) {
constexpr Dir kInvDirs[4] = {kD, kU, kR, kL};
return kInvDirs[dir];
}
struct Pos {
int idx_;
Pos() {}
explicit Pos(const int _idx) : idx_(_idx) {}
Pos(int _x, int _y) : idx_(_y * N + _x) { assert(N > 0); }
int X() const { return pos_2_x[*this]; }
int Y() const { return pos_2_y[*this]; }
int Idx() const { return idx_; }
operator int() const { return Idx(); }
operator size_t() const { return Idx(); }
const vector<Pos>& Adj() const { return adj_poses[*this]; }
const vector<Dir>& AdjDirs() const { return adj_dirs[*this]; }
int Manhattan(const Pos& other) const {
return abs(X() - other.X()) + abs(Y() - other.Y());
}
int Euclid2(const Pos& other) const {
const int dx = X() - other.X();
const int dy = Y() - other.Y();
return dx * dx + dy * dy;
}
bool Move(const Dir dir) {
if (move_to[dir][*this].IsDummy()) {
return false;
} else {
*this = move_to[dir][*this];
return true;
}
}
template <typename ID>
bool IsConnectedAfterRemoving(const vector<ID>& ids) const {
// 自身を削除してもids[p]の連結性が維持されるか3x3を見て判定
bitset<8> bs = 0;
int adj_count = 0;
int i = -1;
const auto& p = *this;
const int base_id = ids[p];
for (const auto adj : p.Adj()) {
i++;
if (ids[adj] == base_id) {
adj_count++;
bs[i] = true;
}
}
if (adj_count <= 1) return true;
i = 3;
for (const auto adjadj : adjadjs_check_remove[p]) {
i++;
bs[i] = ids[adjadj] == base_id;
}
return can_remove_bses[p][bs.to_ulong()];
}
bool operator<(const Pos& other) const { return this->Idx() < other.Idx(); }
bool operator==(const Pos& other) const { return this->Idx() == other.Idx(); }
bool operator!=(const Pos& other) const { return this->Idx() != other.Idx(); }
friend ostream& operator<<(ostream& os, const Pos& pos) {
os << pos.X() << " " << pos.Y();
return os;
}
bool IsDummy() const { return this->idx_ < 0; }
static Pos Dummy() {
Pos p;
p.idx_ = -1;
return p;
}
static Pos TryCreate(const int x, const int y) {
if (y < 0 || y >= N || x < 0 || x >= N) {
return Pos::Dummy();
} else {
return Pos(x, y);
}
}
static void StaticInit(const int n) {
N = n;
N2 = N * N;
N4 = N2 * N2;
adj_poses = vector<vector<Pos>>(N2);
adj_dirs = vector<vector<Dir>>(N2);
move_to = vector<vector<Pos>>(4, vector<Pos>(N2, Pos::Dummy()));
pos_2_y.resize(N2);
pos_2_x.resize(N2);
rep(y, N) {
rep(x, N) {
const Pos p{x, y};
all_poses.push_back(p);
pos_2_y[p] = y;
pos_2_x[p] = x;
for (int dy = -1; dy <= 1; ++dy) {
for (int dx = -1; dx <= 1; ++dx) {
if (abs(dy) + abs(dx) != 1) continue;
const int adj_y = y + dy;
const int adj_x = x + dx;
if (adj_y < 0 || adj_y >= N) continue;
if (adj_x < 0 || adj_x >= N) continue;
adj_poses[p].emplace_back(adj_x, adj_y);
Dir dir;
if (dy == -1) {
dir = kU;
} else if (dy == 1) {
dir = kD;
} else if (dx == -1) {
dir = kL;
} else if (dx == 1) {
dir = kR;
} else {
assert(false);
}
move_to[dir][p] = {adj_x, adj_y};
adj_dirs[p].emplace_back(dir);
}
}
}
}
all_poses.shrink_to_fit();
if (N * N * 256 <= 1e7) {
can_remove_bses.resize(N2);
adjadjs_check_remove.resize(N2);
rep(idx, N * N) {
const Pos p(idx);
set<Pos> S;
for (const auto adj : p.Adj()) {
for (const auto adjadj : adj.Adj()) {
if (adjadj == p) continue;
if (S.count(adjadj) > 0) {
adjadjs_check_remove[p].push_back(adjadj);
} else {
S.insert(adjadj);
}
}
}
assert(adjadjs_check_remove[p].size() <= 4);
rep(bit, 256) {
// adj0, adj1, ..., adjadj0, adjdadj1, ... を詰めずに並べる
bitset<8> bs(bit);
set<Pos> adjs, adjadjs;
rep(j, p.Adj().size()) {
if (bs[j]) {
adjs.insert(p.Adj()[j]);
}
}
rep(j, adjadjs_check_remove[p].size()) {
const auto adjadj = adjadjs_check_remove[p][j];
if (bs[j + 4]) {
int count = 0;
for (const auto adjadjadj : adjadj.Adj()) {
count += adjs.count(adjadjadj);
}
if (count >= 2) {
adjadjs.insert(adjadj);
}
}
}
can_remove_bses[p][bs.to_ulong()] =
((int)adjadjs.size() >= (int)adjs.size() - 1);
}
}
}
}
static int N, N2, N4;
static vector<Pos> all_poses;
static vector<vector<Pos>> adj_poses;
static vector<vector<Dir>> adj_dirs;
static vector<vector<Pos>> move_to;
static vector<int> pos_2_x, pos_2_y;
// 2^8のbit列を受け取って削除可能かを返す
// adj_poses[0], ..., adj_poses[3], adjadjs_check_remove[0], ...,
// adjadjs_check_remove[3]
// の順に詰めずに並べること 左が上位桁。
static vector<bitset<256>> can_remove_bses;
static vector<vector<Pos>> adjadjs_check_remove;
};
vector<Pos> Pos::all_poses;
vector<vector<Pos>> Pos::adj_poses;
vector<vector<Dir>> Pos::adj_dirs;
vector<vector<Pos>> Pos::move_to;
vector<int> Pos::pos_2_x, Pos::pos_2_y;
int Pos::N, Pos::N2, Pos::N4;
vector<bitset<256>> Pos::can_remove_bses;
vector<vector<Pos>> Pos::adjadjs_check_remove;
/* start */
using BS = bitset<50 * 50>;
using ShopBS = bitset<128>;
Timer global_timer;
const int N = 50, M = 20, PDelta = -20;
const char kEmpty = '.';
const char kBlock = '#';
const char kShop = '@';
vector<char> A;
struct Bomb {
int C;
int L;
vector<Pos> ps;
};
vector<Bomb> bombs;
struct Explosion {
int id;
Pos p;
bool operator<(const Explosion& other) const {
if (id != other.id) {
return id < other.id;
}
return p.Idx() < other.p.Idx();
}
};
vector<Pos> shops;
ShopBS all_shop_bs;
BS input_blocks;
vector<Explosion> all_explosions;
vector<vector<Explosion>> pos2explosions;
vector<vector<BS>> _bomb_id2pos2bs;
const BS& BombId2Pos2BS(const int bomb_id, const Pos p) {
return _bomb_id2pos2bs[bomb_id][p];
}
void InitBombId2Pos2BS() {
// 破壊するなら0
_bomb_id2pos2bs.resize(M, vector<BS>(N * N, 0));
rep(bomb_id, M) {
rep(idx, N * N) {
const Pos base_p(idx);
_bomb_id2pos2bs[bomb_id][base_p] = ~(BS{0});
for (const auto delta : bombs[bomb_id].ps) {
const Pos p = Pos::TryCreate(base_p.X() + delta.X() + PDelta,
base_p.Y() + delta.Y() + PDelta);
if (p.IsDummy()) continue;
_bomb_id2pos2bs[bomb_id][base_p][p] = false;
}
}
}
}
vector<vector<ShopBS>> _bomb_id2pos2shop_bs;
const ShopBS& BombId2Pos2ShopBS(const int bomb_id, const Pos p) {
return _bomb_id2pos2shop_bs[bomb_id][p];
}
void InitBombId2Pos2ShopBS() {
// 破壊するなら0
_bomb_id2pos2shop_bs.assign(M, vector<ShopBS>(N * N, ~(ShopBS{0})));
rep(bomb_id, M) {
rep(idx, N * N) {
const Pos base_p(idx);
const auto bs = BombId2Pos2BS(bomb_id, base_p);
rep(shop_id, shops.size()) {
if (!bs[shops[shop_id]]) {
// 破壊対象
_bomb_id2pos2shop_bs[bomb_id][base_p][shop_id] = false;
}
}
}
}
}
double EvalExplosion(const Explosion& exp) {
// 大きいほうが嬉しい
return BombId2Pos2BS(exp.id, exp.p).count() / bombs[exp.id].C;
}
struct Action {
Pos p = Pos::Dummy();
int buy_bomb = -1;
int use_bomb = -1;
static Action CreateMove(const Pos p) {
Action action;
action.p = p;
return action;
}
static Action CreateBuy(const int id) {
Action action;
action.buy_bomb = id;
return action;
}
static Action CreateUse(const int id) {
Action action;
action.use_bomb = id;
return action;
}
friend ostream& operator<<(ostream& os, const vector<Action>& actions) {
stringstream ss;
int command_count = 0;
Pos current_pos = Pos(0, 0);
int move_cost = 0;
int buy_cost = 0;
int bomb_count = 0;
BS remain_blocks = input_blocks;
for (const auto action : actions) {
const Pos p = action.p;
if (!p.IsDummy()) {
while (current_pos != p) {
ss << "\n";
command_count++;
ss << "1 ";
if (current_pos.Y() != p.Y()) {
if (current_pos.Y() < p.Y()) {
ss << "D";
current_pos.Move(kD);
} else {
ss << "U";
current_pos.Move(kU);
}
} else {
if (current_pos.X() < p.X()) {
ss << "R";
current_pos.Move(kR);
} else {
ss << "L";
current_pos.Move(kL);
}
}
const int coef = remain_blocks[current_pos] ? 2 : 1;
move_cost += (bomb_count + 1) * (bomb_count + 1) * coef;
}
} else if (action.buy_bomb != -1) {
command_count++;
bomb_count++;
ss << "\n";
ss << "2 " << action.buy_bomb + 1;
buy_cost += bombs[action.buy_bomb].C;
} else {
command_count++;
bomb_count--;
ss << "\n";
ss << "3 " << action.use_bomb + 1;
remain_blocks &= BombId2Pos2BS(action.use_bomb, current_pos);
}
}
os << command_count;
os << ss.str();
cerr << "move: " << move_cost << " "
<< "buy: " << buy_cost << endl;
cerr << "score: " << (int)(1e12 / (1e4 + move_cost + buy_cost)) << endl;
return os;
}
};
struct Output {
static void StaticInit(istream& is) {
global_timer.start();
Pos::StaticInit(N);
int _;
is >> _ >> _;
input_blocks = 0;
A.resize(N * N);
all_shop_bs = 0;
rep(i, N) {
string s;
is >> s;
rep(j, N) {
const Pos p(j, i);
A[p] = s[j];
if (s[j] == kShop) {
all_shop_bs[(int)shops.size()] = true;
shops.push_back(p);
}
if (s[j] != kEmpty) {
input_blocks[p] = true;
}
}
}
shops.shrink_to_fit();
rep(t, M) {
int C, L;
is >> C >> L;
vector<Pos> ps;
rep(i, L) {
int y, x;
is >> y >> x;
Pos p{x - PDelta, y - PDelta};
ps.push_back(p);
}
bombs.push_back(Bomb{C, L, ps});
}
bombs.shrink_to_fit();
InitBombId2Pos2BS();
InitBombId2Pos2ShopBS();
all_explosions.clear();
rep(bomb_id, M) {
rep(idx, N * N) {
const Pos p(idx);
all_explosions.push_back(Explosion{bomb_id, p});
}
}
sort(ALL(all_explosions), [&](const auto& l, const auto& r) {
return EvalExplosion(l) > EvalExplosion(r);
});
// const int kCount = N * N * 50;
// if ((int)all_explosions.size() > kCount) {
// all_explosions.resize(kCount);
// }
all_explosions.shrink_to_fit();
pos2explosions.clear();
pos2explosions.resize(N * N);
for (const auto& exp : all_explosions) {
const auto bs = BombId2Pos2BS(exp.id, exp.p);
rep(idx, N * N) {
const Pos p(idx);
if (bs[p]) continue;
// constexpr int kCount = 100;
// if ((int)pos2explosions[idx].size() >= kCount) continue;
pos2explosions[idx].push_back(exp);
}
}
}
friend ostream& operator<<(ostream& os, const Output& output) { return os; }
};
/* start */
vector<double> PARAMS = {100.0, 1.0};
/* start */
struct ExplosionSolution {
set<Explosion> S;
BS blocks;
ShopBS remain_shops;
Explosion last_explosion;
int buy_cost_sum = 0;
ExplosionSolution() : blocks(input_blocks), remain_shops(0) {
rep(i, shops.size()) { remain_shops[i] = true; }
}
int CountBlock() const { return blocks.count(); }
int CountRemainShop() const { return remain_shops.count(); }
int CountDestroy(const Explosion& exp) const {
return (blocks & ~BombId2Pos2BS(exp.id, exp.p)).count();
}
void Add(Explosion exp) {
if (S.count(exp)) return;
S.insert(exp);
blocks &= BombId2Pos2BS(exp.id, exp.p);
remain_shops &= BombId2Pos2ShopBS(exp.id, exp.p);
last_explosion = exp;
buy_cost_sum += bombs[exp.id].C;
}
};
class BombSolver {
public:
BombSolver() {}
ExplosionSolution Zatsu() {
ExplosionSolution sol;
while (true) {
auto next_best_sol = sol;
double min_eval = INF;
int start_idx = rand(0, N * N);
int target_idx = sol.blocks._Find_next(start_idx);
while (target_idx < N * N && A[target_idx] == '@') {
target_idx = sol.blocks._Find_next(target_idx);
}
if (target_idx == N * N) {
target_idx = sol.blocks._Find_first();
while (target_idx < N * N && A[target_idx] == '@') {
target_idx = sol.blocks._Find_next(target_idx);
}
}
if (target_idx == N * N) {
target_idx = sol.blocks._Find_first();
}
for (const auto& exp : pos2explosions[target_idx]) {
auto next_sol = sol;
next_sol.Add(exp);
const int diff_count_block = sol.CountBlock() - next_sol.CountBlock();
if (diff_count_block == 0) continue;
if (next_sol.CountBlock() > 0 && next_sol.CountRemainShop() == 0)
continue;
// 1ブロックあたりのコスト
double eval = bombs[exp.id].C / diff_count_block;
if (eval < min_eval) {
min_eval = eval;
next_best_sol = next_sol;
}
}
if (min_eval == INF) continue;
if (next_best_sol.CountBlock() == 0) return next_best_sol;
sol = next_best_sol;
}
assert(false);
}
vector<Explosion> Solve() {
auto best_sol = Zatsu();
int g = 0;
while (global_timer.ms() < 2000) {
g++;
auto sol = Zatsu();
if (sol.buy_cost_sum < best_sol.buy_cost_sum) {
best_sol = sol;
}
}
cerr << "[first] g:" << g << endl;
best_sol.S.erase(best_sol.last_explosion);
auto ret_vec = vector<Explosion>(ALL(best_sol.S));
ret_vec.push_back(best_sol.last_explosion);
return ret_vec;
}
private:
};
/* start */
// NBD = neighborhood
template <class Solution, class NBDGenerator>
struct SimulatedAnnealing {
public:
SimulatedAnnealing(double end_time, double start_temp, double end_temp)
: end_time_(end_time * 1000), // ns
inv_time_(1.0 / end_time_),
cur_time_(0.0),
start_temp_(start_temp),
end_temp_(end_temp),
diff_temp_(end_temp_ / start_temp_),
cur_temp_(start_temp) {
assert(start_temp >= end_temp);
timer_.start();
}
Solution run(const Solution& initial_sol, NBDGenerator& nbd_generator) {
Solution sol(initial_sol);
int acc = 0;
int g = 0;
for (;; ++g) {
if ((g & 0xff) == 0) {
#ifdef SA_MAX_G
if (g >= SA_MAX_G) {
break;
}
#endif
UpdateTime();
UpdateTemp();
if (cur_time_ > end_time_) {
break;
}
}
const auto nbd = nbd_generator.Generate(&sol, g, cur_time_ * inv_time_);
constexpr int mod = 1'000'000'000;
const int r = rand(0, mod);
if (static_cast<double>(r) / mod < exp(-nbd->Diff() / cur_temp_)) {
acc++;
nbd->Update(&sol);
} else {
nbd->Restore(&sol);
}
}
cerr << "g,acc: " << g << " " << acc << endl;
return sol;
}
private:
double end_time_, inv_time_, cur_time_;
double start_temp_, end_temp_, diff_temp_, cur_temp_;
Timer timer_;
void UpdateTime() { cur_time_ = timer_.ns(); }
void UpdateTemp() {
cur_temp_ = start_temp_ * pow(diff_temp_, cur_time_ * inv_time_);
// cur_temp_ = max(0.0, start_temp_ - cur_time_ * diff_temp_ * inv_time_);
}
};
/*
実装手順
0. Output::StaticInit(istream&)を実装
1. Solutionの初期解生成を書く
2. Solutionに対する操作とEvalの更新を書く
3. Evalの初期値計算を書く
4. Eval::Sum()とSolution::Score()を書く
5. 近傍操作と復元操作を書く
6. 近傍の各確率を調整
*/
struct Eval {
// 最小化問題とすること
int dist_sum = 0;
int no_shop_count = 0;
double Sum() const { return (double)dist_sum + (double)no_shop_count * INF; }
};
struct Solution {
// 爆弾を置く順番
// 購入は最寄りの店から一つずつ貪欲に
vector<int> order;
vector<Action> actions;
Eval eval;
static vector<Explosion> all_explosions;
static void InitAllExplosions(const vector<Explosion>& explosions) {
all_explosions = explosions;
}
Solution() : order(all_explosions.size()) {
assert((int)all_explosions.size() > 0);
std::iota(ALL(order), 0);
InitEval(false);
}
void InitEval(const bool update_action) {
eval = Eval();
actions.clear();
ShopBS remain_shops = all_shop_bs;
Pos current_pos = Pos(0, 0);
for (const int exp_idx : order) {
const auto& exp = all_explosions[exp_idx];
const auto& explode_shop = BombId2Pos2ShopBS(exp.id, exp.p);
// 残っている店のうち最も近いところ
// TODO: 高速化
int best_shop_id = -1;
int min_manhattan = INF;
rep(shop_id, shops.size()) {
if (!remain_shops[shop_id]) continue;
const auto shop_pos = shops[shop_id];
const int manhattan =
current_pos.Manhattan(shop_pos) + shop_pos.Manhattan(exp.p);
if (manhattan < min_manhattan) {
min_manhattan = manhattan;
best_shop_id = shop_id;
}
}
if (best_shop_id == -1) {
eval.no_shop_count += 1;
continue;
}
if (update_action) {
// 店に移動、購入、犯行現場に移動、爆破
actions.push_back(Action::CreateMove(shops[best_shop_id]));
actions.push_back(Action::CreateBuy(exp.id));
actions.push_back(Action::CreateMove(exp.p));
actions.push_back(Action::CreateUse(exp.id));
}
remain_shops &= explode_shop;
eval.dist_sum += min_manhattan;
current_pos = exp.p;
}
}
static Solution CreateInitialSol() {
Solution sol;
sol.InitEval(false);
return sol;
}
double Evaluate() const { return eval.Sum(); }
double Score() const {
// 最大化問題とすること
return -Evaluate();
}
friend ostream& operator<<(ostream& os, const Solution& sol) { return os; }
};
vector<Explosion> Solution::all_explosions;
struct NBD {
double Diff() const { return diff; }
void Update(Solution*) const {};
virtual void Restore(Solution*) const = 0;
double diff;
};
struct NBD1 : public NBD {
NBD1() {}
NBD1(Solution* const sol) {
diff = -sol->Evaluate();
//順番swap
while (true) {
idx = rand(0, (int)sol->order.size() - 2);
swap(sol->order[idx], sol->order[idx + 1]);
sol->InitEval(false);
diff += sol->Evaluate();
return;
}
}
void Restore(Solution* sol) const override {
swap(sol->order[idx], sol->order[idx + 1]);
sol->InitEval(false);
}
int idx = 0;
};
struct NBD2 : public NBD {
NBD2() {}
NBD2(Solution* const sol) { diff = -sol->Evaluate(); }
void Restore(Solution* sol) const override {}
};
struct NBDGenerator {
NBD* Generate(Solution* const sol, const int g, const double progress) {
if (sol->Score() > best_sol.Score()) {
best_sol = *sol;
}
const int random = rand(0, 100);
if (random < 100) {
nbd1_ = NBD1(sol);
return &nbd1_;
} else if (random < 100) {
// nbd2_ = NBD2(sol);
// return &nbd2_;
} else {
assert(false);
}
}
const Solution& GetBestSol() const { return best_sol; }
private:
NBD1 nbd1_;
// NBD2 nbd2_;
Solution best_sol;
};
vector<Action> SARun() {
Solution first_sol = Solution::CreateInitialSol();
NBDGenerator gen;
SimulatedAnnealing<Solution, NBDGenerator> SA(2950 - global_timer.ms(),
PARAMS[0], PARAMS[1]);
const auto final_sol = SA.run(first_sol, gen);
auto best_sol = gen.GetBestSol();
cerr << "score: " << best_sol.Score() << endl;
// return best_sol;
best_sol.InitEval(true);
// cerr << first_sol.actions.size() << " " << Solution::all_explosions.size()
// << endl;
// const auto bs = BombId2Pos2BS(0, Pos(21, 16));
// rep(y, N) {
// rep(x, N) { cerr << bs[Pos(x, y)]; }
// cerr << endl;
// }
return best_sol.actions;
}
/* start */
class PlanSolver {
public:
PlanSolver() {}
void Solve(const vector<Explosion>& explosions) {
Solution::InitAllExplosions(explosions);
const auto actions = SARun();
cout << actions << endl;
}
private:
};
/* start */
class Solver {
public:
Solver() {}
void Solve() {
BombSolver solver;
const auto sol = solver.Solve();
PlanSolver solver2;
solver2.Solve(sol);
return;
}
private:
};
int main(int argc, char* argv[]) {
fast_io;
if (argc >= 2) {
int idx = 0;
for (int i = 1; i < argc; ++i) {
PARAMS[idx++] = std::stod(argv[i]);
}
}
Timer timer;
timer.start();
Output::StaticInit(cin);
Solver solver;
solver.Solve();
return 0;
}