結果
| 問題 | No.5019 Hakai Project |
| ユーザー |
 iiljj
|
| 提出日時 | 2023-11-19 19:18:07 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 2,879 ms / 3,000 ms |
| コード長 | 41,640 bytes |
| コンパイル時間 | 3,727 ms |
| コンパイル使用メモリ | 195,384 KB |
| 実行使用メモリ | 6,676 KB |
| スコア | 2,668,270,505 |
| 最終ジャッジ日時 | 2023-11-19 19:20:35 |
| 合計ジャッジ時間 | 146,585 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge13 |
| 純コード判定しない問題か言語 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2,658 ms
6,676 KB |
| testcase_01 | AC | 2,814 ms
6,676 KB |
| testcase_02 | AC | 2,874 ms
6,676 KB |
| testcase_03 | AC | 2,617 ms
6,676 KB |
| testcase_04 | AC | 2,571 ms
6,676 KB |
| testcase_05 | AC | 2,717 ms
6,676 KB |
| testcase_06 | AC | 2,678 ms
6,676 KB |
| testcase_07 | AC | 2,777 ms
6,676 KB |
| testcase_08 | AC | 2,629 ms
6,676 KB |
| testcase_09 | AC | 2,879 ms
6,676 KB |
| testcase_10 | AC | 2,533 ms
6,676 KB |
| testcase_11 | AC | 2,769 ms
6,676 KB |
| testcase_12 | AC | 2,752 ms
6,676 KB |
| testcase_13 | AC | 2,727 ms
6,676 KB |
| testcase_14 | AC | 2,593 ms
6,676 KB |
| testcase_15 | AC | 2,680 ms
6,676 KB |
| testcase_16 | AC | 2,643 ms
6,676 KB |
| testcase_17 | AC | 2,497 ms
6,676 KB |
| testcase_18 | AC | 2,766 ms
6,676 KB |
| testcase_19 | AC | 2,660 ms
6,676 KB |
| testcase_20 | AC | 2,765 ms
6,676 KB |
| testcase_21 | AC | 2,705 ms
6,676 KB |
| testcase_22 | AC | 2,558 ms
6,676 KB |
| testcase_23 | AC | 2,813 ms
6,676 KB |
| testcase_24 | AC | 2,805 ms
6,676 KB |
| testcase_25 | AC | 2,706 ms
6,676 KB |
| testcase_26 | AC | 2,780 ms
6,676 KB |
| testcase_27 | AC | 2,532 ms
6,676 KB |
| testcase_28 | AC | 2,643 ms
6,676 KB |
| testcase_29 | AC | 2,542 ms
6,676 KB |
| testcase_30 | AC | 2,668 ms
6,676 KB |
| testcase_31 | AC | 2,725 ms
6,676 KB |
| testcase_32 | AC | 2,743 ms
6,676 KB |
| testcase_33 | AC | 2,581 ms
6,676 KB |
| testcase_34 | AC | 2,767 ms
6,676 KB |
| testcase_35 | AC | 2,741 ms
6,676 KB |
| testcase_36 | AC | 2,643 ms
6,676 KB |
| testcase_37 | AC | 2,718 ms
6,676 KB |
| testcase_38 | AC | 2,692 ms
6,676 KB |
| testcase_39 | AC | 2,634 ms
6,676 KB |
| testcase_40 | AC | 2,874 ms
6,676 KB |
| testcase_41 | AC | 2,767 ms
6,676 KB |
| testcase_42 | AC | 2,667 ms
6,676 KB |
| testcase_43 | AC | 2,567 ms
6,676 KB |
| testcase_44 | AC | 2,828 ms
6,676 KB |
| testcase_45 | AC | 2,567 ms
6,676 KB |
| testcase_46 | AC | 2,617 ms
6,676 KB |
| testcase_47 | AC | 2,683 ms
6,676 KB |
| testcase_48 | AC | 2,788 ms
6,676 KB |
| testcase_49 | AC | 2,830 ms
6,676 KB |
ソースコード
/* #region Head */
// #include <bits/stdc++.h>
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert> // assert.h
#include <cmath> // math.h
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pll = pair<ll, ll>;
template <class T> using vc = vector<T>;
template <class T> using vvc = vc<vc<T>>;
using vll = vc<ll>;
using vvll = vvc<ll>;
using vld = vc<ld>;
using vvld = vvc<ld>;
using vs = vc<string>;
using vvs = vvc<string>;
template <class T, class U> using um = unordered_map<T, U>;
template <class T> using pq = priority_queue<T>;
template <class T> using pqa = priority_queue<T, vc<T>, greater<T>>;
template <class T> using us = unordered_set<T>;
#define TREP(T, i, m, n) for (T i = (m), i##_len = (T)(n); i < i##_len; ++(i))
#define TREPM(T, i, m, n) for (T i = (m), i##_max = (T)(n); i <= i##_max; ++(i))
#define TREPR(T, i, m, n) for (T i = (m), i##_min = (T)(n); i >= i##_min; --(i))
#define TREPD(T, i, m, n, d) for (T i = (m), i##_len = (T)(n); i < i##_len; i += (d))
#define TREPMD(T, i, m, n, d) for (T i = (m), i##_max = (T)(n); i <= i##_max; i += (d))
#define REP(i, m, n) for (ll i = (m), i##_len = (ll)(n); i < i##_len; ++(i))
#define REPM(i, m, n) for (ll i = (m), i##_max = (ll)(n); i <= i##_max; ++(i))
#define REPR(i, m, n) for (ll i = (m), i##_min = (ll)(n); i >= i##_min; --(i))
#define REPD(i, m, n, d) for (ll i = (m), i##_len = (ll)(n); i < i##_len; i += (d))
#define REPMD(i, m, n, d) for (ll i = (m), i##_max = (ll)(n); i <= i##_max; i += (d))
#define REPI(itr, ds) for (auto itr = ds.begin(); itr != ds.end(); itr++)
#define REPIR(itr, ds) for (auto itr = ds.rbegin(); itr != ds.rend(); itr++)
#define ALL(x) begin(x), end(x)
#define SIZE(x) ((ll)(x).size())
#define ISIZE(x) ((int)(x).size())
#define PERM(c) \
sort(ALL(c)); \
for (bool c##p = 1; c##p; c##p = next_permutation(ALL(c)))
#define UNIQ(v) v.erase(unique(ALL(v)), v.end());
#define CEIL(a, b) (((a) + (b)-1) / (b))
#define endl '\n'
constexpr ll INF = 1'010'000'000'000'000'017LL;
constexpr int IINF = 1'000'000'007LL;
constexpr ll MOD = 1'000'000'007LL; // 1e9 + 7
// constexpr ll MOD = 998244353;
constexpr ld EPS = 1e-12;
constexpr ld PI = 3.14159265358979323846;
template <typename T> istream &operator>>(istream &is, vc<T> &vec) { // vector 入力
for (T &x : vec) is >> x;
return is;
}
template <typename T> ostream &operator<<(ostream &os, const vc<T> &vec) { // vector 出力 (for dump)
os << "{";
REP(i, 0, SIZE(vec)) os << vec[i] << (i == i_len - 1 ? "" : ", ");
os << "}";
return os;
}
template <typename T> ostream &operator>>(ostream &os, const vc<T> &vec) { // vector 出力 (inline)
REP(i, 0, SIZE(vec)) os << vec[i] << (i == i_len - 1 ? "\n" : " ");
return os;
}
template <typename T, size_t _Nm> istream &operator>>(istream &is, array<T, _Nm> &arr) { // array 入力
REP(i, 0, SIZE(arr)) is >> arr[i];
return is;
}
template <typename T, size_t _Nm> ostream &operator<<(ostream &os, const array<T, _Nm> &arr) { // array 出力 (for dump)
os << "{";
REP(i, 0, SIZE(arr)) os << arr[i] << (i == i_len - 1 ? "" : ", ");
os << "}";
return os;
}
template <typename T, typename U> istream &operator>>(istream &is, pair<T, U> &pair_var) { // pair 入力
is >> pair_var.first >> pair_var.second;
return is;
}
template <typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &pair_var) { // pair 出力
os << "(" << pair_var.first << ", " << pair_var.second << ")";
return os;
}
// map, um, set, us 出力
template <class T> ostream &out_iter(ostream &os, const T &map_var) {
os << "{";
REPI(itr, map_var) {
os << *itr;
auto itrcp = itr;
if (++itrcp != map_var.end()) os << ", ";
}
return os << "}";
}
template <typename T, typename U> ostream &operator<<(ostream &os, const map<T, U> &map_var) {
return out_iter(os, map_var);
}
template <typename T, typename U> ostream &operator<<(ostream &os, const um<T, U> &map_var) {
os << "{";
REPI(itr, map_var) {
auto [key, value] = *itr;
os << "(" << key << ", " << value << ")";
auto itrcp = itr;
if (++itrcp != map_var.end()) os << ", ";
}
os << "}";
return os;
}
template <typename T> ostream &operator<<(ostream &os, const set<T> &set_var) { return out_iter(os, set_var); }
template <typename T> ostream &operator<<(ostream &os, const us<T> &set_var) { return out_iter(os, set_var); }
template <typename T> ostream &operator<<(ostream &os, const pq<T> &pq_var) {
pq<T> pq_cp(pq_var);
os << "{";
if (!pq_cp.empty()) {
os << pq_cp.top(), pq_cp.pop();
while (!pq_cp.empty()) os << ", " << pq_cp.top(), pq_cp.pop();
}
return os << "}";
}
// tuple 出力
template <size_t N = 0, bool end_line = false, typename... Args> ostream &operator<<(ostream &os, tuple<Args...> &a) {
if constexpr (N < std::tuple_size_v<tuple<Args...>>) {
os << get<N>(a);
if constexpr (N + 1 < std::tuple_size_v<tuple<Args...>>) {
os << ' ';
} else if constexpr (end_line) {
os << '\n';
}
return operator<< <N + 1, end_line>(os, a);
}
return os;
}
template <typename... Args> void print_tuple(tuple<Args...> &a) { operator<< <0, true>(std::cout, a); }
void pprint() { std::cout << endl; }
template <class Head, class... Tail> void pprint(Head &&head, Tail &&...tail) {
std::cout << head;
if (sizeof...(Tail) > 0) std::cout << ' ';
pprint(move(tail)...);
}
// dump
#define DUMPOUT cerr
void dump_func() { DUMPOUT << endl; }
template <class Head, class... Tail> void dump_func(Head &&head, Tail &&...tail) {
DUMPOUT << head;
if (sizeof...(Tail) > 0) DUMPOUT << ", ";
dump_func(move(tail)...);
}
// chmax (更新「される」かもしれない値が前)
template <typename T, typename U, typename Comp = less<>> bool chmax(T &xmax, const U &x, Comp comp = {}) {
if (comp(xmax, x)) {
xmax = x;
return true;
}
return false;
}
// chmin (更新「される」かもしれない値が前)
template <typename T, typename U, typename Comp = less<>> bool chmin(T &xmin, const U &x, Comp comp = {}) {
if (comp(x, xmin)) {
xmin = x;
return true;
}
return false;
}
// ローカル用
#ifndef ONLINE_JUDGE
#define DEBUG_
#endif
#ifndef MYLOCAL
#undef DEBUG_
#endif
#ifdef DEBUG_
#define DEB
#define dump(...) \
DUMPOUT << " " << string(#__VA_ARGS__) << ": " \
<< "[" << to_string(__LINE__) << ":" << __FUNCTION__ << "]" << endl \
<< " ", \
dump_func(__VA_ARGS__)
#else
#define DEB if (false)
#define dump(...)
#endif
#define VAR(type, ...) \
type __VA_ARGS__; \
assert((std::cin >> __VA_ARGS__));
template <typename T> istream &operator,(istream &is, T &rhs) { return is >> rhs; }
template <typename T> ostream &operator,(ostream &os, const T &rhs) { return os << ' ' << rhs; }
struct AtCoderInitialize {
static constexpr int IOS_PREC = 15;
static constexpr bool AUTOFLUSH = false;
AtCoderInitialize() {
ios_base::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr);
std::cout << fixed << setprecision(IOS_PREC);
if (AUTOFLUSH) std::cout << unitbuf;
}
} ATCODER_INITIALIZE;
void Yn(bool p) { std::cout << (p ? "Yes" : "No") << endl; }
void YN(bool p) { std::cout << (p ? "YES" : "NO") << endl; }
template <typename T> constexpr void operator--(vc<T> &v, int) noexcept {
for (int i = 0; i < ISIZE(v); ++i) v[i]--;
}
template <typename T> constexpr void operator++(vc<T> &v, int) noexcept {
for (int i = 0; i < ISIZE(v); ++i) v[i]++;
}
/* #endregion */
// #include <atcoder/all>
// using namespace atcoder;
/* #region rand */
// [lb, ub] の値を等確率で発生させる
template <typename T = ll> class Rand {
using dist_type = std::uniform_int_distribution<T>;
T _lb;
T _ub;
// std::random_device rd; // Will be used to obtain a seed for the random number engine
std::mt19937_64 gen; // Standard mersenne_twister_engine seeded with rd()
dist_type dis;
public:
Rand(T lb, T ub, int seed) : _lb(lb), _ub(ub), gen(seed), dis(lb, ub) {}
inline T operator()() noexcept { return dis(gen); }
inline void set_param(T lb, T ub) noexcept {
if (lb == _lb && ub == _ub) return;
_lb = lb, _ub = ub;
typename dist_type::param_type param(lb, ub);
dis.param(param);
}
};
// [lb, ub) の値を等確率で発生させる
template <typename T = double> class RandDouble {
// std::random_device seed_gen;
std::default_random_engine engine;
std::uniform_real_distribution<T> dist;
public:
RandDouble(T lb, T ub, int seed) : engine(seed), dist(lb, ub) {}
inline T operator()() noexcept { return dist(engine); }
};
/* #endregion */
/* #region Anneal */
#include <chrono>
// 誰でもできる焼きなまし法 - gasin’s blog http://gasin.hatenadiary.jp/entry/2019/09/03/162613
struct Anneal {
using clk = chrono::system_clock;
int64_t timespan_microsecs; // 焼きなます時間
float start_temp; // 開始温度 (一回の遷移で動きうるスコア幅の最大値程度)
float end_temp; // 終了温度 (一回の遷移で動きうるスコア幅の最小値程度)
RandDouble<float> rd;
clk::time_point start_time;
int64_t microsecs_elapsed;
ll max_trial_count;
ll trial_count;
// コンストラクタ
Anneal(int64_t timespan_microsecs, float start_temp, float end_temp, int seed, ll max_trial_count = -1)
: timespan_microsecs(timespan_microsecs), start_temp(start_temp), end_temp(end_temp), rd(0, 1, seed),
start_time(clk::now()), microsecs_elapsed(0), max_trial_count(max_trial_count), trial_count(0) {}
inline void restart() noexcept {
start_time = clk::now();
microsecs_elapsed = 0;
}
// スコアの差分から，遷移するかどうかを確率的に決定して返す
inline bool transit(float dif) noexcept {
if (max_trial_count == -1) {
clk::time_point cur_time = clk::now();
microsecs_elapsed = chrono::duration_cast<chrono::microseconds>(cur_time - start_time).count();
// 温度関数
const float temperature =
start_temp + (end_temp - start_temp) * ((float)microsecs_elapsed / timespan_microsecs);
// 遷移確率関数(最大化の場合)
float prob = exp((float)dif / temperature);
// cout << dif, prob, '\n';
return prob > rd();
} else {
trial_count++;
// 温度関数
const float temperature = start_temp + (end_temp - start_temp) * ((float)trial_count / max_trial_count);
// 遷移確率関数(最大化の場合)
float prob = exp((float)dif / temperature);
// cout << dif, prob, '\n';
return prob > rd();
}
}
// transit の山登り版
inline bool climb(float dif) noexcept {
clk::time_point cur_time = clk::now();
microsecs_elapsed = chrono::duration_cast<chrono::microseconds>(cur_time - start_time).count();
return dif > 0;
}
// 時間切れかどうかを返す
inline bool runnable() noexcept { return microsecs_elapsed < timespan_microsecs; }
};
/* #endregion */
/* #region dijkstra_f_restore */
/**
* @param N ノード数
* @param delta 隣接行列を生成する関数．delta(Node v, fn(Node t)).
* fn は現在の頂点 current と隣接する頂点を探索する関数．
* @param index 頂点→頂点インデックス，のマップ関数．（index(Node v) -> int）
* @return 距離テーブル
*/
template <class Node, class Delta, class Index, class Weight = ll, Weight inf = INF>
pair<Weight, vc<int>> dijkstra_f_restore(int N, const Node &start, const Node &terminal, Delta delta, Index index,
vc<Weight> &dist, Weight init = 0) {
struct state {
Weight cost;
Node dst;
state(Weight cost, Node dst) : cost(cost), dst(dst) {}
bool operator<(const state &o) const { return cost > o.cost; }
// bool operator>(const state &o) const { return cost > o.cost; }
};
vc<int> bs(N, -1); // 経路復元用
// vc<Weight> dist(N, inf); // 距離テーブル
fill(ALL(dist), inf);
priority_queue<state> que; // 「訪問予定」頂点リスト
{
int idx = index(start);
assert(0 <= idx && idx < N);
dist[idx] = init; // 初期条件 (頂点 start を初期頂点とする)
que.emplace(init, start);
}
while (!que.empty()) {
state cur = que.top(); // tie(d, v) = que.top();
que.pop();
Node current = cur.dst;
Weight cur_dist = cur.cost;
int ci = index(current);
if (dist[ci] < cur_dist) continue;
// 隣接ノードに関するループは外に出す
delta(current, [&](Node dst, Weight weight) -> void {
Weight nxt_dist = cur_dist + weight;
int idx = index(dst);
assert(0 <= idx && idx < N);
if (chmin(dist[idx], nxt_dist)) {
que.emplace(nxt_dist, dst);
bs[idx] = ci;
}
});
}
// 経路復元
vc<int> res;
int dst = index(terminal);
int dst_bak = dst;
// if (bs[dst] < 0) return res;
while (~dst) res.emplace_back(dst), dst = bs[dst];
reverse(ALL(res));
// return res;
return {dist[dst_bak], res};
}
/* #endregion */
template <size_t N = 64ull> string to_bin(ll x, bool show_base = false) {
std::stringstream ss;
if (show_base) ss << "0b";
ss << std::bitset<N>(x);
std::string s = ss.str();
return s;
}
constexpr int N = 50;
constexpr int M = 20;
// Problem
void solve() {
VAR(ll, n, m);
assert(n == N);
assert(m == M);
vc<string> A(n);
cin >> A;
vll c(m), l(m);
vvll a(m), b(m);
REP(i, 0, m) {
cin >> c[i], l[i];
a[i].resize(l[i]);
b[i].resize(l[i]);
REP(j, 0, l[i]) cin >> a[i][j], b[i][j];
}
// ボード準備
array<ull, N> board;
fill(ALL(board), 0ull);
REP(i, 0, n) REP(j, 0, n) {
// dump(i, j);
if (A[i][j] != '.') {
board[i] |= (1ull << j);
}
// dump(to_bin<50>(board[i]));
}
// const ull mask = (1ull << N) - 1ull;
// 爆弾準備
constexpr ll offset = 20;
array<array<ull, 41>, M> bombs;
REP(i, 0, m) {
fill(ALL(bombs[i]), 0ull);
// offset を足した位置にする
REP(j, 0, l[i]) {
const ll row = offset + a[i][j];
const ll col = offset + b[i][j];
bombs[i][row] |= (1ull << col);
}
}
// 50x50 の盤面，20 種類の爆弾
// なるべく地元の爆弾屋から仕入れたい．
// なるべく少ない爆弾でやりくりしたい．
// 3000ms あるので解の改善もできるか．
// まずは，どこで何を爆破させるのが得か，調べる．
// sum(#,@)/c[i] が大きい位置・爆弾種類を調べる．
vc<array<ll, 3>> rcbs;
while (true) {
// 効果的な爆弾を探す
ld max_score = 0;
ll argmax_row_center = -1;
ll argmax_col_center = -1;
ll argmax_bomb = -1;
REP(row_center, 0, N) REP(col_center, 0, N) {
REP(i, 0, m) {
ld score = 0;
// 行 [row_center-20] が bombs[i][0] と対応する
// 列 [col_center-20] が bombs[i][0]&1 と対応する
REP(row, max(0LL, row_center - 20), min(n, row_center + 21)) {
const ll row_idx = row - (row_center - 20);
if (col_center > 20) {
const ull bit = board[row] & (bombs[i][row_idx] << (col_center - 20));
score += __builtin_popcountll(bit);
} else {
const ull bit = board[row] & (bombs[i][row_idx] >> (20 - col_center));
score += __builtin_popcountll(bit);
}
}
score /= c[i];
if (chmax(max_score, score)) {
argmax_row_center = row_center;
argmax_col_center = col_center;
argmax_bomb = i;
}
}
}
// dump(max_score, argmax_row_center, argmax_col_center, argmax_bomb, max_score * c[argmax_bomb]);
assert(argmax_bomb != -1);
rcbs.push_back({argmax_row_center, argmax_col_center, argmax_bomb});
// 爆弾を適用する
{
REP(row, max(0LL, argmax_row_center - 20), min(n, argmax_row_center + 21)) {
const ll row_idx = row - (argmax_row_center - 20);
if (argmax_col_center > 20) {
const ull bit = board[row] & (bombs[argmax_bomb][row_idx] << (argmax_col_center - 20));
board[row] ^= bit;
} else {
const ull bit = board[row] & (bombs[argmax_bomb][row_idx] >> (20 - argmax_col_center));
board[row] ^= bit;
}
}
}
// 残り破壊対象を数える
{
ll obj_count = 0;
REP(row, 0, n) {
obj_count += __builtin_popcountll(board[row]); //
}
// dump(obj_count);
if (obj_count == 0) break;
}
// break;
}
rcbs.insert(rcbs.begin(), array<ll, 3>{0, 0, -1});
// dump(rcbs);
// dump(SIZE(rcbs));
vc<int> indices(SIZE(rcbs));
iota(ALL(indices), 0);
// ここは問題ごとに作る
auto rcdist = [&](const array<ll, 3> &p0, const array<ll, 3> &p1) -> ll {
return abs(p1[0] - p0[0]) + abs(p1[1] - p0[1]); //
};
auto cdist = [&](const int i0, const int i1) -> ll {
return rcdist(rcbs[i0], rcbs[i1]); //
};
// TSP として解く
const ll max_trial_count = -1;
// const ll max_trial_count = 20'000'000;
int64_t timespan_microsecs = 2100 * 1000; // 焼きなます時間
double start_temp = (double)(7.0); // 開始温度 (一回の遷移で動きうるスコア幅の最大値程度);
double end_temp = 1.0; // 終了温度 (一回の遷移で動きうるスコア幅の最小値程度);
Anneal anneal(timespan_microsecs, start_temp, end_temp, __LINE__, max_trial_count);
Rand<int> rand(0, SIZE(rcbs) - 2, __LINE__);
Rand<int> choice(0, 99, __LINE__);
ll tsp_diff = 0;
ll min_tsp_diff = 0;
vc<int> argmin_indices = indices;
// REP(_trial, 0, max_trial_count) {
// anneal.runnable();
while (anneal.runnable()) {
const int cur_choice = choice();
if (cur_choice < 75) {
// 2-opt 近傍
rand.set_param(0, SIZE(rcbs) - 2);
int r0 = rand();
if (r0 == 0 || r0 == SIZE(rcbs) - 2) {
rand.set_param(0, SIZE(rcbs) - 2 - 2); // r0 と，r0 の直後/直後いずれか一方を除外する
} else {
rand.set_param(0, SIZE(rcbs) - 2 - 3); // r0 と，r0 の直前・直後を除外する
}
int r1 = rand();
if (r1 == r0 - 1) r1++;
if (r1 == r0) r1++;
if (r1 == r0 + 1) r1++;
if (r0 > r1) swap(r0, r1);
assert(r0 < r1);
assert(r0 + 1 != r1);
assert(r1 <= SIZE(rcbs) - 2);
// assert: 隣接していない辺同士を swap したい
const int from0 = indices[r0];
const int to0 = indices[r0 + 1];
const int from1 = indices[r1];
const int to1 = indices[r1 + 1];
const int dist_old = cdist(from0, to0) + cdist(from1, to1);
const int dist_new = cdist(from0, from1) + cdist(to0, to1);
const int dif = dist_new - dist_old;
if (anneal.transit(-dif)) {
reverse(indices.begin() + r0 + 1, indices.begin() + r1 + 1);
tsp_diff += dif;
if (chmin(min_tsp_diff, tsp_diff)) {
argmin_indices = indices;
}
}
} else if (cur_choice < 1000) {
// 3-opt 近傍
// https://www.researchgate.net/figure/All-possible-3-opt-recombination-cases-3-opt-Three-edges-of-a-tour-are-removed-in-a_fig2_287692116
rand.set_param(0, SIZE(rcbs) - 2);
int r0 = rand();
if (r0 == 0 || r0 == SIZE(rcbs) - 2) {
rand.set_param(0, SIZE(rcbs) - 2 - 2); // r0 と，r0 の直後/直後いずれか一方を除外する
} else {
rand.set_param(0, SIZE(rcbs) - 2 - 3); // r0 と，r0 の直前・直後を除外する
}
int r1 = rand();
if (r1 == r0 - 1) r1++;
if (r1 == r0) r1++;
if (r1 == r0 + 1) r1++;
if (r0 > r1) swap(r0, r1);
assert(r0 < r1);
assert(r0 + 1 != r1);
if (r0 + 2 == r1) {
// r0 の直後 = r1 の直前 のとき
if (r0 == 0) {
if (r1 == SIZE(rcbs) - 2) {
// r0 と，r0 の直後と，r1 を除外する
rand.set_param(0, SIZE(rcbs) - 2 - 3);
} else {
// r0 と，r0 の直後と，r1 と，r1 の直後を除外する
rand.set_param(0, SIZE(rcbs) - 2 - 4);
}
} else {
if (r1 == SIZE(rcbs) - 2) {
// r0 と，r0 の直前・直後と，r1 を除外する
rand.set_param(0, SIZE(rcbs) - 2 - 4);
} else {
// r0 と，r0 の直前・直後と，r1 と，r1 の直後を除外する
rand.set_param(0, SIZE(rcbs) - 2 - 5);
}
}
} else {
// r0 の直後 < r1 の直前 のとき
// r0 と，r0 の直前・直後と，r1 と，r1 の直後を除外する
if (r0 == 0) {
if (r1 == SIZE(rcbs) - 2) {
// r0 と，r0 の直後と，r1 と，r1 の直前を除外する
rand.set_param(0, SIZE(rcbs) - 2 - 4);
} else {
// r0 と，r0 の直後と，r1 と，r1 の直前・直後を除外する
rand.set_param(0, SIZE(rcbs) - 2 - 5);
}
} else {
if (r1 == SIZE(rcbs) - 2) {
// r0 と，r0 の直前・直後と，r1 と，r1 の直前を除外する
rand.set_param(0, SIZE(rcbs) - 2 - 5);
} else {
// r0 と，r0 の直前・直後と，r1 と，r1 の直前・直後を除外する
rand.set_param(0, SIZE(rcbs) - 2 - 6);
}
}
}
int r2 = rand();
if (r2 == r0 - 1) r2++;
if (r2 == r0) r2++;
if (r2 == r0 + 1) r2++;
if (r2 == r1 - 1) r2++;
if (r2 == r1) r2++;
if (r2 == r1 + 1) r2++;
if (r0 > r2) swap(r0, r2);
if (r1 > r2) swap(r1, r2);
assert(r0 < r1);
assert(r1 < r2);
assert(r0 + 1 != r1);
assert(r1 + 1 != r2);
assert(r2 <= SIZE(rcbs) - 2);
const int from0 = indices[r0];
const int to0 = indices[r0 + 1];
const int from1 = indices[r1];
const int to1 = indices[r1 + 1];
const int from2 = indices[r2];
const int to2 = indices[r2 + 1];
const int dist_old = cdist(from0, to0) + cdist(from1, to1) + cdist(from2, to2);
int argmin_type = 0;
int min_dist = dist_old;
{
// type 1
const int dist_new = cdist(from0, to0) + cdist(from1, from2) + cdist(to1, to2);
if (chmin(min_dist, dist_new)) {
argmin_type = 1;
}
}
{
// type 2
const int dist_new = cdist(from0, from1) + cdist(to0, to1) + cdist(from2, to2);
if (chmin(min_dist, dist_new)) {
argmin_type = 2;
}
}
{
// type 3
const int dist_new = cdist(from0, from2) + cdist(to1, from1) + cdist(to0, to2);
if (chmin(min_dist, dist_new)) {
argmin_type = 3;
}
}
{
// type 4
const int dist_new = cdist(from0, from2) + cdist(to1, to0) + cdist(from1, to2);
if (chmin(min_dist, dist_new)) {
argmin_type = 4;
}
}
{
// type 5
const int dist_new = cdist(from0, to1) + cdist(from2, from1) + cdist(to0, to2);
if (chmin(min_dist, dist_new)) {
argmin_type = 5;
}
}
{
// type 6
const int dist_new = cdist(from0, from1) + cdist(to0, from2) + cdist(to1, to2);
if (chmin(min_dist, dist_new)) {
argmin_type = 6;
}
}
{
// type 7
const int dist_new = cdist(from0, to1) + cdist(from2, to0) + cdist(from1, to2);
if (chmin(min_dist, dist_new)) {
argmin_type = 7;
}
}
if (argmin_type == 0) continue;
const int dif = min_dist - dist_old;
if (anneal.transit(-dif)) {
if (argmin_type == 1) {
reverse(indices.begin() + r1 + 1, indices.begin() + r2 + 1);
} else if (argmin_type == 2) {
reverse(indices.begin() + r0 + 1, indices.begin() + r1 + 1);
} else if (argmin_type == 3) {
reverse(indices.begin() + r0 + 1, indices.begin() + r2 + 1);
} else if (argmin_type == 4) {
reverse(indices.begin() + r0 + 1, indices.begin() + r1 + 1);
reverse(indices.begin() + r0 + 1, indices.begin() + r2 + 1);
} else if (argmin_type == 5) {
reverse(indices.begin() + r1 + 1, indices.begin() + r2 + 1);
reverse(indices.begin() + r0 + 1, indices.begin() + r2 + 1);
} else if (argmin_type == 6) {
reverse(indices.begin() + r0 + 1, indices.begin() + r1 + 1);
reverse(indices.begin() + r1 + 1, indices.begin() + r2 + 1);
} else {
assert(argmin_type == 7);
reverse(indices.begin() + r0 + 1, indices.begin() + r1 + 1);
reverse(indices.begin() + r1 + 1, indices.begin() + r2 + 1);
reverse(indices.begin() + r0 + 1, indices.begin() + r2 + 1);
}
tsp_diff += dif;
if (chmin(min_tsp_diff, tsp_diff)) {
argmin_indices = indices;
}
}
}
}
// dump(tsp_diff, min_tsp_diff);
indices = argmin_indices;
// indices にソート結果がある
// dump(rcbs);
// dump(SIZE(rcbs));
using Node = pair<int, int>; // row, col
const static vc<int> dx{1, 0, -1, 0};
// 隣接行列生成関数
auto delta = [&](const Node ¤t, function<void(Node, int)> transit) -> void {
auto [r, c] = current;
// 隣接ノードに関するループ
for (int q = 0; q < 4; q++) {
const int nr = r + dx[q];
const int nc = c + dx[q ^ 1];
// if (nr < 0 || nr >= h || nc < 0 || nc >= w) continue;
if (0 <= nr && nr < N && 0 <= nc && nc < N) {
if ((board[nr] >> nc) & 1) {
transit(Node(nr, nc), 2); // コスト 2 で遷移
} else {
transit(Node(nr, nc), 1); // コスト 1 で遷移
}
}
}
};
// インデックス生成関数
auto index = [&](const Node &v) -> int { return v.first * N + v.second; };
vll dists0(N * N);
vll dists1(N * N);
// できるだけ直前まで残っている店で爆弾を仕入れるようにする
array<ull, N> board_shop;
fill(ALL(board_shop), 0ull);
fill(ALL(board), 0ull);
REP(i, 0, n) REP(j, 0, n) {
// dump(i, j);
if (A[i][j] != '.') {
board[i] |= (1ull << j);
}
if (A[i][j] == '@') {
board_shop[i] |= (1ull << j);
}
}
vc<array<ll, 3>> operations;
REP(i, 1, SIZE(rcbs)) {
// rcbs[indices[i-1]] 〜 rcbs[indices[i]] の間で店に寄るとして，どこに寄るのが最善か？
// 更地を通ったほうがお得！
// const Node start = {rcbs[indices[i - 1]][0], rcbs[indices[i - 1]][1]};
// const Node goal = {rcbs[indices[i]][0], rcbs[indices[i]][1]};
// auto [dist0, res0] = dijkstra_f_restore(N * N, start, goal, delta, index, dists0, 0LL);
// auto [dist1, res1] = dijkstra_f_restore(N * N, goal, start, delta, index, dists1, 0LL);
ll min_dist = IINF;
ll argmin_row = -1;
ll argmin_col = -1;
REP(row, 0, n) REP(col, 0, n) {
if ((board_shop[row] >> col) & 1) {
array<ll, 3> t{row, col, -1};
// const ll dist = cdist(rcbs[i - 1], t) + cdist(rcbs[i], t);
const ll dist = rcdist(rcbs[indices[i]], t);
// const ll dist0 = dists0[N * row + col];
// const ll dist1 = dists1[N * row + col];
// const ll dist = dist0 + 4 * dist1;
if (chmin(min_dist, dist)) {
argmin_row = row;
argmin_col = col;
}
}
}
// 店が見つかったら必ず立ち寄る
if (argmin_row != -1) {
assert(argmin_col != -1);
operations.push_back({argmin_row, argmin_col, -10000 - min_dist});
}
operations.push_back(rcbs[indices[i]]);
// 爆弾適用
const auto [argmax_row_center, argmax_col_center, argmax_bomb] = rcbs[indices[i]];
REP(row, max(0LL, argmax_row_center - 20), min(n, argmax_row_center + 21)) {
const ll row_idx = row - (argmax_row_center - 20);
if (argmax_col_center > 20) {
const ull bit = board[row] & (bombs[argmax_bomb][row_idx] << (argmax_col_center - 20));
board[row] ^= bit;
const ull bit_shop = board_shop[row] & (bombs[argmax_bomb][row_idx] << (argmax_col_center - 20));
board_shop[row] ^= bit_shop;
} else {
const ull bit = board[row] & (bombs[argmax_bomb][row_idx] >> (20 - argmax_col_center));
board[row] ^= bit;
const ull bit_shop = board_shop[row] & (bombs[argmax_bomb][row_idx] >> (20 - argmax_col_center));
board_shop[row] ^= bit_shop;
}
}
}
// dump(operations);
// dump(SIZE(operations));
// 店の訪問時に，どの操作で使う爆弾を仕入れるか調べる
vvll op2idx(SIZE(operations));
vll stock;
REPR(i, SIZE(operations) - 1, 0) {
if (operations[i][2] >= 0) { // 爆弾を使用する操作
stock.push_back(i);
} else { // 爆弾を購入する操作
op2idx[i] = stock;
stock.clear();
}
}
// dump(op2idx);
// ある店への訪問を，直前の訪問にマージしたほうがよいか？
REPR(i, SIZE(operations) - 1, 0) {
if (operations[i][2] < 0) {
// 直後の店への訪問を探す
ll nxt_shop_j = -1;
REP(j, i + 1, SIZE(operations)) {
if (operations[j][2] < 0) {
nxt_shop_j = j;
break;
}
}
if (nxt_shop_j == -1) continue;
// 元の移動コスト計算
ll cur_cost = 0;
{
ll prev = i;
REPR(j, SIZE(op2idx[i]) - 1, 0) {
// j+1 個の爆弾を持っている
const ll d = rcdist(operations[prev], operations[op2idx[i][j]]);
cur_cost += (j + 2) * (j + 2) * d;
}
prev = nxt_shop_j;
REPR(j, SIZE(op2idx[nxt_shop_j]) - 1, 0) {
// j+1 個の爆弾を持っている
const ll d = rcdist(operations[prev], operations[op2idx[nxt_shop_j][j]]);
cur_cost += (j + 2) * (j + 2) * d;
}
}
// 新しい移動コストを計算
ll nxt_cost = 0;
{
ll prev = i;
REPR(j, SIZE(op2idx[i]) - 1, 0) {
// j+1+SIZE(op2idx[nxt_shop_j]) 個の爆弾を持っている
const ll d = rcdist(operations[prev], operations[op2idx[i][j]]);
nxt_cost += (j + 2 + SIZE(op2idx[nxt_shop_j])) * (j + 2 + SIZE(op2idx[nxt_shop_j])) * d;
}
REPR(j, SIZE(op2idx[nxt_shop_j]) - 1, 0) {
// j+1 個の爆弾を持っている
const ll d = rcdist(operations[prev], operations[op2idx[nxt_shop_j][j]]);
nxt_cost += (j + 2) * (j + 2) * d;
}
}
// マージしたほうが得ならマージする（後の店訪問は削除する）
if (nxt_cost < cur_cost) {
// dump(nxt_cost, cur_cost, op2idx[i], op2idx[nxt_shop_j]);
// op2idx[i].insert(op2idx[i].end(), ALL(op2idx[nxt_shop_j])); // インデックスが 1 ずれるので駄目
// op2idx[nxt_shop_j] 以降はインデックスを1つずつデクリメントする
REP(j, nxt_shop_j, SIZE(op2idx)) {
if (SIZE(op2idx[j])) {
op2idx[j]--;
}
}
// for (const auto ii : op2idx[nxt_shop_j]) {
// op2idx[i].push_back(ii - 1);
// }
op2idx[i].insert(op2idx[i].end(), ALL(op2idx[nxt_shop_j]));
// dump(nxt_cost, cur_cost, op2idx[i], op2idx[nxt_shop_j]);
operations.erase(operations.begin() + nxt_shop_j);
op2idx.erase(op2idx.begin() + nxt_shop_j);
}
}
}
fill(ALL(board_shop), 0ull);
fill(ALL(board), 0ull);
REP(i, 0, n) REP(j, 0, n) {
// dump(i, j);
if (A[i][j] != '.') {
board[i] |= (1ull << j);
}
if (A[i][j] == '@') {
board_shop[i] |= (1ull << j);
}
}
int row = 0;
int col = 0;
vc<string> ans;
int bomb_count = 0;
ll cost_sum = 0;
REP(i, 0, SIZE(operations)) {
if (operations[i][2] >= 0) { // 爆弾を使用する操作
// 移動する
// なるべく更地を通ったほうが低コスト！
const Node start = {row, col};
const Node goal = {operations[i][0], operations[i][1]};
auto [dist, res] = dijkstra_f_restore(N * N, start, goal, delta, index, dists0, 0LL);
const ll basecost = (bomb_count + 1) * (bomb_count + 1);
REP(j, 1, SIZE(res)) {
const int nxt_row = res[j] / N;
const int nxt_col = res[j] % N;
while (row < nxt_row) {
row++;
ans.push_back("1 D");
cost_sum += ((board[row] >> col) & 1) ? (2 * basecost) : basecost;
}
while (row > nxt_row) {
row--;
ans.push_back("1 U");
cost_sum += ((board[row] >> col) & 1) ? (2 * basecost) : basecost;
}
while (col < nxt_col) {
col++;
ans.push_back("1 R");
cost_sum += ((board[row] >> col) & 1) ? (2 * basecost) : basecost;
}
while (col > nxt_col) {
col--;
ans.push_back("1 L");
cost_sum += ((board[row] >> col) & 1) ? (2 * basecost) : basecost;
}
}
// ans.push_back("# " + to_string(row) + ", " + to_string(col));
// 爆弾を使用する
assert(operations[i][2] >= 0);
assert(operations[i][2] < M);
ans.push_back("3 " + to_string(operations[i][2] + 1));
bomb_count--;
// 盤面更新
const auto [argmax_row_center, argmax_col_center, argmax_bomb] = operations[i];
REP(row, max(0LL, argmax_row_center - 20), min(n, argmax_row_center + 21)) {
const ll row_idx = row - (argmax_row_center - 20);
if (argmax_col_center > 20) {
const ull bit = board[row] & (bombs[argmax_bomb][row_idx] << (argmax_col_center - 20));
board[row] ^= bit;
const ull bit_shop = board_shop[row] & (bombs[argmax_bomb][row_idx] << (argmax_col_center - 20));
board_shop[row] ^= bit_shop;
} else {
const ull bit = board[row] & (bombs[argmax_bomb][row_idx] >> (20 - argmax_col_center));
board[row] ^= bit;
const ull bit_shop = board_shop[row] & (bombs[argmax_bomb][row_idx] >> (20 - argmax_col_center));
board_shop[row] ^= bit_shop;
}
}
} else { // 爆弾を購入する操作
if (SIZE(op2idx[i]) == 0) continue;
// 移動する
// なるべく更地を通ったほうが低コスト！
const Node start = {row, col};
const Node goal = {operations[i][0], operations[i][1]};
auto [dist, res] = dijkstra_f_restore(N * N, start, goal, delta, index, dists0, 0LL);
const ll basecost = (bomb_count + 1) * (bomb_count + 1);
REP(j, 1, SIZE(res)) {
const int nxt_row = res[j] / N;
const int nxt_col = res[j] % N;
while (row < nxt_row) {
row++;
ans.push_back("1 D");
cost_sum += ((board[row] >> col) & 1) ? (2 * basecost) : basecost;
}
while (row > nxt_row) {
row--;
ans.push_back("1 U");
cost_sum += ((board[row] >> col) & 1) ? (2 * basecost) : basecost;
}
while (col < nxt_col) {
col++;
ans.push_back("1 R");
cost_sum += ((board[row] >> col) & 1) ? (2 * basecost) : basecost;
}
while (col > nxt_col) {
col--;
ans.push_back("1 L");
cost_sum += ((board[row] >> col) & 1) ? (2 * basecost) : basecost;
}
}
// ans.push_back("# " + to_string(row) + ", " + to_string(col));
// 爆弾を購入する
for (const ll idx : op2idx[i]) {
if (operations[idx][2] < 0) {
dump(idx, operations[idx][2]);
}
assert(operations[idx][2] >= 0);
assert(operations[idx][2] < M);
ans.push_back("2 " + to_string(operations[idx][2] + 1));
bomb_count++;
cost_sum += c[operations[idx][2]];
}
}
}
// dump(cost_sum);
pprint(SIZE(ans));
for (const string &line : ans) {
pprint(line); //
}
}
// entry point
int main() {
solve();
return 0;
}