結果
| 問題 | No.5024 魔法少女うなと宝集め |
| コンテスト | |
| ユーザー |
 hitonanode
|
| 提出日時 | 2026-08-28 23:01:45 |
| 言語 | C++23 (gcc 15.3.0 + boost 1.92.0) |
| 結果 |
AC
|
| 実行時間 | 1,341 ms / 2,000 ms |
| + 498µs | |
| コード長 | 17,877 bytes |
| 記録 | |
| コンパイル時間 | 3,178 ms |
| コンパイル使用メモリ | 354,424 KB |
| 実行使用メモリ | 6,272 KB |
| スコア | 2,234,587 |
| 最終ジャッジ日時 | 2026-08-28 23:03:03 |
| 合計ジャッジ時間 | 70,502 ms |
|
ジャッジサーバーID （参考情報） |
judge1_0 / judge3_0 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <deque>
#include <forward_list>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <optional>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using lint = long long;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
struct fast_ios { fast_ios(){ cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(20); }; } fast_ios_;
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
template <typename T> bool chmax(T &m, const T q) { return m < q ? (m = q, true) : false; }
template <typename T> bool chmin(T &m, const T q) { return m > q ? (m = q, true) : false; }
const std::vector<std::pair<int, int>> grid_dxs{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int floor_lg(long long x) { return x <= 0 ? -1 : 63 - __builtin_clzll(x); }
template <class T1, class T2> T1 floor_div(T1 num, T2 den) { return (num > 0 ? num / den : -((-num + den - 1) / den)); }
template <class T1, class T2> std::pair<T1, T2> operator+(const std::pair<T1, T2> &l, const std::pair<T1, T2> &r) { return std::make_pair(l.first + r.first, l.second + r.second); }
template <class T1, class T2> std::pair<T1, T2> operator-(const std::pair<T1, T2> &l, const std::pair<T1, T2> &r) { return std::make_pair(l.first - r.first, l.second - r.second); }
template <class T> std::vector<T> sort_unique(std::vector<T> vec) { sort(vec.begin(), vec.end()), vec.erase(unique(vec.begin(), vec.end()), vec.end()); return vec; }
template <class T> int arglb(const std::vector<T> &v, const T &x) { return std::distance(v.begin(), std::lower_bound(v.begin(), v.end(), x)); }
template <class T> int argub(const std::vector<T> &v, const T &x) { return std::distance(v.begin(), std::upper_bound(v.begin(), v.end(), x)); }
template <class IStream, class T> IStream &operator>>(IStream &is, std::vector<T> &vec) { for (auto &v : vec) is >> v; return is; }
template <class OStream, class T> OStream &operator<<(OStream &os, const std::vector<T> &vec);
template <class OStream, class T, size_t sz> OStream &operator<<(OStream &os, const std::array<T, sz> &arr);
template <class OStream, class T, class TH> OStream &operator<<(OStream &os, const std::unordered_set<T, TH> &vec);
template <class OStream, class T, class U> OStream &operator<<(OStream &os, const pair<T, U> &pa);
template <class OStream, class T> OStream &operator<<(OStream &os, const std::deque<T> &vec);
template <class OStream, class T> OStream &operator<<(OStream &os, const std::set<T> &vec);
template <class OStream, class T> OStream &operator<<(OStream &os, const std::multiset<T> &vec);
template <class OStream, class T> OStream &operator<<(OStream &os, const std::unordered_multiset<T> &vec);
template <class OStream, class T, class U> OStream &operator<<(OStream &os, const std::pair<T, U> &pa);
template <class OStream, class TK, class TV> OStream &operator<<(OStream &os, const std::map<TK, TV> &mp);
template <class OStream, class TK, class TV, class TH> OStream &operator<<(OStream &os, const std::unordered_map<TK, TV, TH> &mp);
template <class OStream, class... T> OStream &operator<<(OStream &os, const std::tuple<T...> &tpl);
template <class OStream, class T> OStream &operator<<(OStream &os, const std::vector<T> &vec) { os << '['; for (auto v : vec) os << v << ','; os << ']'; return os; }
template <class OStream, class T, size_t sz> OStream &operator<<(OStream &os, const std::array<T, sz> &arr) { os << '['; for (auto v : arr) os << v << ','; os << ']'; return os; }
template <class... T> std::istream &operator>>(std::istream &is, std::tuple<T...> &tpl) { std::apply([&is](auto &&... args) { ((is >> args), ...);}, tpl); return is; }
template <class OStream, class... T> OStream &operator<<(OStream &os, const std::tuple<T...> &tpl) { os << '('; std::apply([&os](auto &&... args) { ((os << args << ','), ...);}, tpl); return os << ')'; }
template <class OStream, class T, class TH> OStream &operator<<(OStream &os, const std::unordered_set<T, TH> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; }
template <class OStream, class T> OStream &operator<<(OStream &os, const std::deque<T> &vec) { os << "deq["; for (auto v : vec) os << v << ','; os << ']'; return os; }
template <class OStream, class T> OStream &operator<<(OStream &os, const std::set<T> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; }
template <class OStream, class T> OStream &operator<<(OStream &os, const std::multiset<T> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; }
template <class OStream, class T> OStream &operator<<(OStream &os, const std::unordered_multiset<T> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; }
template <class OStream, class T, class U> OStream &operator<<(OStream &os, const std::pair<T, U> &pa) { return os << '(' << pa.first << ',' << pa.second << ')'; }
template <class OStream, class TK, class TV> OStream &operator<<(OStream &os, const std::map<TK, TV> &mp) { os << '{'; for (auto v : mp) os << v.first << "=>" << v.second << ','; os << '}'; return os; }
template <class OStream, class TK, class TV, class TH> OStream &operator<<(OStream &os, const std::unordered_map<TK, TV, TH> &mp) { os << '{'; for (auto v : mp) os << v.first << "=>" << v.second << ','; os << '}'; return os; }
#ifdef HITONANODE_LOCAL
const string COLOR_RESET = "\033[0m", BRIGHT_CYAN = "\033[1;36m", NORMAL_FAINT = "\033[0;2m";
#define dbg(x) std::cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = " << (x) << NORMAL_FAINT << " (L" << __LINE__ << ") " << __FILE__ << COLOR_RESET << std::endl
#define dbgif(cond, x) ((cond) ? std::cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = " << (x) << NORMAL_FAINT << " (L" << __LINE__ << ") " << __FILE__ << COLOR_RESET << std::endl : std::cerr)
#else
#define dbg(x) ((void)0)
#define dbgif(cond, x) ((void)0)
#endif
using State = pair<int, vector<int>>;
// https://hitonanode.github.io/cplib-cpp/utilities/timer.hpp
#include <chrono>
class timer_ {
std::chrono::system_clock::time_point start_;
public:
timer_() : start_(now()) {}
static std::chrono::system_clock::time_point now() { return std::chrono::system_clock::now(); }
int spent_ms() const {
auto diff = now() - start_;
return std::chrono::duration_cast<std::chrono::milliseconds>(diff).count();
}
} timer;
// https://hitonanode.github.io/cplib-cpp/random/rand_nondeterministic.hpp
#include <cassert>
#include <chrono>
#include <cstdint>
#include <random>
struct RNGMt19937 {
using lint = long long;
std::mt19937 mt;
RNGMt19937(long long seed) : mt(seed) {}
lint operator()(lint x) { // [0, x)
assert(x > 0);
return this->operator()(0, x);
}
lint operator()(lint l, lint r) {
assert(l < r);
std::uniform_int_distribution<lint> d(l, r - 1);
return d(mt);
}
};
// RNGMt19937 rnd(123456789);
// RNGMt19937 rnd(std::chrono::steady_clock::now().time_since_epoch().count());
// Fast random number generator based on xoshiro256++.
struct FastRNG {
using ull = unsigned long long;
ull s[4];
static ull rotl(ull x, int k) { return (x << k) | (x >> (64 - k)); }
static ull splitmix64(ull &x) {
ull z = (x += 0x9e3779b97f4a7c15ULL);
z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9ULL;
z = (z ^ (z >> 27)) * 0x94d049bb133111ebULL;
return z ^ (z >> 31);
}
FastRNG(ull seed) {
for (auto &x : s) x = splitmix64(seed);
}
ull next_u64() {
ull res = rotl(s[0] + s[3], 23) + s[0];
ull t = s[1] << 17;
s[2] ^= s[0];
s[3] ^= s[1];
s[1] ^= s[2];
s[0] ^= s[3];
s[2] ^= t;
s[3] = rotl(s[3], 45);
return res;
}
uint32_t next_u32() { return next_u64() >> 32; }
// [0, n)
uint32_t operator()(uint32_t n) {
assert(n > 0);
return (uint64_t(next_u32()) * n) >> 32;
}
// [l, r)
int operator()(int l, int r) {
assert(l < r);
uint32_t width = uint64_t(int64_t(r) - int64_t(l));
return int(int64_t(l) + (*this)(width));
}
uint16_t next_u16() { return next_u64() >> 48; }
};
inline FastRNG rnd(123456789);
// FastRNG rnd(std::chrono::steady_clock::now().time_since_epoch().count());
// https://hitonanode.github.io/cplib-cpp/heuristic/exponential_dist_sampler.hpp
#include <cmath>
#include <cstdint>
#include <array>
template <int D> struct ExponentialDistSampler {
std::array<double, (1 << D)> minuslogps;
constexpr ExponentialDistSampler() {
for (int i = 0; i < (1 << D); ++i) minuslogps.at(i) = -log((0.5 + i) / (1 << D));
}
double sample(uint32_t random_mask) const {
return minuslogps.at(random_mask & ((1 << D) - 1));
}
// p ~ U(0, 1) => -log(p) ~ Ex(1)
// P[exp(-|dx| / T) >= p] = P[|dx| <= -log(p) * T]
bool check_sa(double abs_dx, double T, uint32_t random_mask) const {
return abs_dx <= minuslogps.at(random_mask & ((1 << D) - 1)) * T;
}
};
const ExponentialDistSampler<16> log_ps;
static constexpr int N = 20;
// int f(int i, int j) { return i * N + j; }
bool in(int i, int j) { return 0 <= i and i < N and 0 <= j and j < N; }
const vector<int> dxs{1, -1, 0, 0}, dys{0, 0, 1, -1};
template <int UPDATE_INTERVAL = 256> struct Annealer {
double temp;
double ratio;
int next_update = UPDATE_INTERVAL;
Annealer(double start_temp, double end_temp, int iterations) : temp(start_temp) {
int updates = (iterations + UPDATE_INTERVAL - 1) / UPDATE_INTERVAL;
ratio = pow(end_temp / start_temp, 1.0 / updates);
}
void update(int iter) {
if (iter >= next_update) {
temp *= ratio;
next_update += UPDATE_INTERVAL;
}
}
template <class Sampler> bool accept(int delta, FastRNG &rng, const Sampler &sampler) const {
if (delta >= 0) return true;
return sampler.check_sa(-delta, temp, rng.next_u16());
}
};
pair<int, vector<pint>> Solve(const vector<vector<int>> &A, int T, int ITER) {
int score = 0;
vector<pint> seq;
int best_score = 0;
vector<pint> best_seq;
vector isin(N, vector<int>(N));
auto CheckBest = [&]() {
if (chmax(best_score, score)) best_seq = seq;
};
auto Insert = [&](int idx, int i, int j) {
assert(!isin[i][j]);
score += A[i][j];
seq.insert(seq.begin() + idx, {i, j});
isin[i][j] = true;
};
auto Remove = [&](int idx) {
const int i = seq[idx].first, j = seq[idx].second;
assert(isin[i][j]);
score -= A[i][j];
seq.erase(seq.begin() + idx);
isin[i][j] = false;
};
auto Change = [&](int idx, int i, int j) {
const int i0 = seq[idx].first, j0 = seq[idx].second;
assert(isin[i0][j0]);
assert(!isin[i][j]);
score += A[i][j] - A[i0][j0];
seq[idx] = {i, j};
isin[i0][j0] = false;
isin[i][j] = true;
};
auto IsAdj = [&](int i, int j) -> bool {
auto [xi, yi] = seq.at(i);
auto [xj, yj] = seq.at(j);
return abs(xi - xj) + abs(yi - yj) == 1;
};
auto PosWeight = [&](int i) -> int { return A[seq[i].first][seq[i].second]; };
{
int a = -1;
int i0 = -1, j0 = -1;
REP(i, N) REP(j, N) if (chmax(a, A[i][j])) i0 = i, j0 = j;
Insert(0, i0, j0);
}
const int BASE = 0;
double init_temp = 1e4, end_temp = 1.0;
Annealer annealer(init_temp, end_temp, ITER);
REP(iter, ITER) {
annealer.update(iter);
// const double temp = annealer.temp;
const int tp = rnd(7);
if (tp < 1) {
// add
const int pos = rnd(seq.size() + 1);
if (pos == 0 or pos == (int)seq.size()) {
if ((int)seq.size() + 1 <= T) {
const int d = rnd(4);
if (pos == 0) {
const int ni = seq[0].first + dxs[d], nj = seq[0].second + dys[d];
if (in(ni, nj) and !isin[ni][nj]) {
const int w = A[ni][nj] - BASE;
if (annealer.accept(w, rnd, log_ps)) {
Insert(0, ni, nj);
}
}
} else {
const int ni = seq.back().first + dxs[d], nj = seq.back().second + dys[d];
if (in(ni, nj) and !isin[ni][nj]) {
const int w = A[ni][nj] - BASE;
if (annealer.accept(w, rnd, log_ps)) {
Insert(seq.size(), ni, nj);
}
}
}
}
} else {
if ((int)seq.size() + 2 <= T) {
const int dx = seq[pos].first - seq[pos - 1].first;
const int dy = seq[pos].second - seq[pos - 1].second;
int d = -1;
REP(dd, 4) if (dxs[dd] == dx and dys[dd] == dy) d = dd;
assert(d != -1);
const int dc = d ^ 2 ^ rnd(2);
const int ni = seq[pos - 1].first + dxs[dc], nj = seq[pos - 1].second + dys[dc];
const int mi = seq[pos].first + dxs[dc], mj = seq[pos].second + dys[dc];
if (in(ni, nj) and in(mi, mj) and !isin[ni][nj] and !isin[mi][mj]) {
const int w = A[ni][nj] + A[mi][mj] - BASE * 2;
if (annealer.accept(w, rnd, log_ps)) {
Insert(pos, ni, nj);
Insert(pos + 1, mi, mj);
}
}
}
}
} else if (tp < 4) {
// change one
const int pos = rnd(seq.size());
const int dir1 = rnd(2), dir2 = rnd(2) + 2;
const int i = seq[pos].first + dxs[dir1] + dxs[dir2],
j = seq[pos].second + dys[dir1] + dys[dir2];
bool fail = false;
if (pos) {
const int di = seq[pos - 1].first - i, dj = seq[pos - 1].second - j;
if (abs(di) + abs(dj) != 1) fail = true;
}
if (pos + 1 < (int)seq.size()) {
const int di = seq[pos + 1].first - i, dj = seq[pos + 1].second - j;
if (abs(di) + abs(dj) != 1) fail = true;
}
if (in(i, j) and !isin[i][j] and !fail) {
const int w = A[i][j] - PosWeight(pos);
if (annealer.accept(w, rnd, log_ps)) { Change(pos, i, j); }
}
} else if (tp < 5) {
// remove
if (seq.size() > 3) {
const int pos = rnd(seq.size() - 3);
if (IsAdj(pos, pos + 3)) {
const int w = -(PosWeight(pos + 1) + PosWeight(pos + 2)) + BASE * 2;
if (annealer.accept(w, rnd, log_ps)) {
Remove(pos + 1);
Remove(pos + 1);
}
}
}
} else if (tp < 6) {
// swap
if (seq.size() > 3) {
int pos1 = rnd(seq.size() - 1), pos2 = rnd(seq.size() - 1);
if (pos1 > pos2) swap(pos1, pos2);
if (pos1 != pos2 and IsAdj(pos1, pos2) and abs(pos1 - pos2) > 1 and
IsAdj(pos1 + 1, pos2 + 1)) {
std::reverse(seq.begin() + pos1 + 1, seq.begin() + pos2 + 1);
}
}
} else if (tp < 7) {
// remove and add
const int direction = rnd(2);
const int d = rnd(4);
if (direction) {
const int ni = seq.back().first + dxs[d], nj = seq.back().second + dys[d];
if (in(ni, nj) and !isin[ni][nj]) {
const int w = A[ni][nj] - PosWeight(0);
if (annealer.accept(w, rnd, log_ps)) {
Remove(0);
Insert(seq.size(), ni, nj);
}
}
} else {
const int ni = seq[0].first + dxs[d], nj = seq[0].second + dys[d];
if (in(ni, nj) and !isin[ni][nj]) {
const int w = A[ni][nj] - PosWeight(seq.size() - 1);
if (annealer.accept(w, rnd, log_ps)) {
Remove(seq.size() - 1);
Insert(0, ni, nj);
}
}
}
}
CheckBest();
}
return {best_score, best_seq};
}
int main() {
int N_, T;
cin >> N_ >> T;
assert(N == N_);
vector A(N, vector<int>(N));
cin >> A;
int best_score = 0;
vector<pint> best_seq;
REP(_, 2) {
auto [score, seq] = Solve(A, T, 25000000);
if (chmax(best_score, score)) { best_seq = seq; }
}
cout << best_seq.size() << '\n';
REP(i, best_seq.size() - 1) {
auto [dx, dy] = best_seq[i + 1] - best_seq[i];
assert(abs(dx) + abs(dy) == 1);
}
for (auto [i, j] : best_seq) cout << i << ' ' << j << '\n';
cerr << "score = " << best_score << endl;
}