結果
| 問題 | No.5024 魔法少女うなと宝集め |
| コンテスト | |
| ユーザー |
 Rho
|
| 提出日時 | 2026-05-02 17:48:23 |
| 言語 | C++14 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 1,903 ms / 2,000 ms |
| コード長 | 16,993 bytes |
| 記録 | |
| コンパイル時間 | 4,094 ms |
| コンパイル使用メモリ | 244,184 KB |
| 実行使用メモリ | 6,400 KB |
| スコア | 2,049,383 |
| 最終ジャッジ日時 | 2026-05-02 17:51:18 |
| 合計ジャッジ時間 | 102,933 ms |
|
ジャッジサーバーID （参考情報） |
judge1_0 / judge2_1 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
コンパイルメッセージ
main.cpp: In function 'void pop_cell()':
main.cpp:46:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
46 | auto [x, y] = path.back();
| ^
main.cpp: In function 'void clear_path()':
main.cpp:52:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
52 | for (auto [x, y] : path) used[x][y] = false;
| ^
main.cpp: In function 'void extend_random(int)':
main.cpp:60:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
60 | auto [x, y] = path.back();
| ^
main.cpp: In function 'std::vector<std::pair<long long int, long long int> > bfs_shortest(int, int, int, int)':
main.cpp:180:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
180 | auto [x, y] = q.front(); q.pop();
| ^
main.cpp: In function 'void greedy_initial_solution()':
main.cpp:259:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
259 | for (auto [x, y] : chosen.second) push_cell(x, y);
| ^
main.cpp: In function 'bool ins_apply(InsertMove&)':
main.cpp:317:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
317 | auto [x1, y1] = path[i];
| ^
main.cpp:318:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
318 | auto [x2, y2] = path[i + 1];
| ^
main.cpp: In function 'int corner_swap_pass()':
main.cpp:354:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
354 | auto [r0, c0] = path[i - 1];
| ^
main.cpp:355:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu+
ソースコード
//# pragma GCC target("avx2")
# pragma GCC optimize("O3")
# pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
ll N,T;
ll A [20][20];
void input(){
cin>>N>>T;
rep(i,N)rep(j,N)cin>>A[i][j];
}
// =========================================================
// 焼きなまし法による単純パス最大化
// =========================================================
mt19937 rng(20260502);
const int dx4[4] = {-1, 1, 0, 0};
const int dy4[4] = {0, 0, -1, 1};
inline bool in_bounds(int x, int y) {
return 0 <= x && x < N && 0 <= y && y < N;
}
inline bool adj(const P& a, const P& b) {
return abs((int)(a.first - b.first)) + abs((int)(a.second - b.second)) == 1;
}
vector<P> path;
bool used[20][20];
ll score_cur = 0;
vector<P> best_path;
ll best_score = LLONG_MIN;
inline void push_cell(int x, int y) {
path.emplace_back(x, y);
used[x][y] = true;
score_cur += A[x][y];
}
inline void pop_cell() {
auto [x, y] = path.back();
used[x][y] = false;
score_cur -= A[x][y];
path.pop_back();
}
void clear_path() {
for (auto [x, y] : path) used[x][y] = false;
path.clear();
score_cur = 0;
}
// 末尾からランダムウォークで延伸（長さ max_len まで or 行き詰まりまで）
void extend_random(int max_len) {
while ((int)path.size() < max_len) {
auto [x, y] = path.back();
int nxs[4], nys[4], cnt = 0;
for (int k = 0; k < 4; k++) {
int nx = x + dx4[k], ny = y + dy4[k];
if (in_bounds(nx, ny) && !used[nx][ny]) {
nxs[cnt] = nx; nys[cnt] = ny; cnt++;
}
}
if (cnt == 0) break;
int c = rng() % cnt;
push_cell(nxs[c], nys[c]);
}
}
// =========================================================
// Greedy 初期解:
// 1) 5x5 ブロック 16 個を蛇行順に巡る Hamiltonian (400 セル) を構築
// (各ブロックは entry/exit 固定で 5x5 上の DFS により Hamiltonian を生成)
// 2) snake 上の position 順に上位 T/2 個のアンカーを並べる
// 3) 先頭から順に未訪問セル経由で BFS 連結し、長さ T を超えたら打切り
// 4) 余り分は末尾ランダムウォークで延伸
// =========================================================
// ブロック 16 個分の (entry_r, entry_c, exit_r, exit_c) (グローバル座標)
// 並びは serpentine: (0,0)(0,1)(0,2)(0,3) → (1,3)(1,2)(1,1)(1,0) → (2,*) → (3,*)
const int BLOCK_DATA[16][4] = {
{ 0, 0, 4, 4}, // (0,0)
{ 4, 5, 0, 9}, // (0,1)
{ 0,10, 4,14}, // (0,2)
{ 4,15, 4,19}, // (0,3) 折り返し下へ
{ 5,19, 9,15}, // (1,3)
{ 9,14, 5,10}, // (1,2)
{ 5, 9, 9, 5}, // (1,1)
{ 9, 4, 9, 0}, // (1,0) 折り返し下へ
{10, 0, 14, 4}, // (2,0)
{14, 5, 10, 9}, // (2,1)
{10,10, 14,14}, // (2,2)
{14,15, 14,19}, // (2,3) 折り返し下へ
{15,19, 19,15}, // (3,3)
{19,14, 15,10}, // (3,2)
{15, 9, 19, 5}, // (3,1)
{19, 4, 15, 0}, // (3,0) 終端
};
const int BLOCK_TL[16][2] = {
{ 0, 0},{ 0, 5},{ 0,10},{ 0,15},
{ 5,15},{ 5,10},{ 5, 5},{ 5, 0},
{10, 0},{10, 5},{10,10},{10,15},
{15,15},{15,10},{15, 5},{15, 0},
};
bool dfs_vis[5][5];
vector<P> dfs_buf;
bool dfs_block(int r, int c, int r0, int c0, int tr, int tc, int visited) {
dfs_vis[r - r0][c - c0] = true;
dfs_buf.push_back(P(r, c));
if (visited == 25) {
if (r == tr && c == tc) return true;
dfs_vis[r - r0][c - c0] = false;
dfs_buf.pop_back();
return false;
}
// 枝刈り: 残り歩数で目的地に到達できるか (Manhattan + パリティ)
int steps_left = 25 - visited;
int dist = abs(r - tr) + abs(c - tc);
if (dist > steps_left || ((steps_left - dist) & 1)) {
dfs_vis[r - r0][c - c0] = false;
dfs_buf.pop_back();
return false;
}
for (int k = 0; k < 4; k++) {
int nr = r + dx4[k], nc = c + dy4[k];
int br = nr - r0, bc = nc - c0;
if (br < 0 || br >= 5 || bc < 0 || bc >= 5) continue;
if (dfs_vis[br][bc]) continue;
if (dfs_block(nr, nc, r0, c0, tr, tc, visited + 1)) return true;
}
dfs_vis[r - r0][c - c0] = false;
dfs_buf.pop_back();
return false;
}
// 16 ブロックを連結した 400 セルの蛇行 Hamiltonian
vector<P> build_snake_of_snakes() {
vector<P> snake;
snake.reserve(400);
for (int idx = 0; idx < 16; idx++) {
int sr = BLOCK_DATA[idx][0], sc = BLOCK_DATA[idx][1];
int er = BLOCK_DATA[idx][2], ec = BLOCK_DATA[idx][3];
int r0 = BLOCK_TL[idx][0], c0 = BLOCK_TL[idx][1];
memset(dfs_vis, 0, sizeof(dfs_vis));
dfs_buf.clear();
if (!dfs_block(sr, sc, r0, c0, er, ec, 1)) {
cerr << "[snake] block " << idx << " ham not found" << endl;
return {};
}
for (auto p : dfs_buf) snake.push_back(p);
}
// 隣接性チェック (デバッグ)
for (int i = 1; i < (int)snake.size(); i++) {
if (!adj(snake[i - 1], snake[i])) {
cerr << "[snake] non-adjacent at " << i << ": "
<< snake[i-1].first << "," << snake[i-1].second << " -> "
<< snake[i].first << "," << snake[i].second << endl;
return {};
}
}
return snake;
}
// BFS 最短路: (sx,sy) から (tx,ty) へ、used を回避 (始点は除外)。
// 経路 (両端含む) を返す。到達不能なら空。
vector<P> bfs_shortest(int sx, int sy, int tx, int ty) {
static int dist[20][20];
static int prev_dir[20][20];
rep(i, 20) rep(j, 20) { dist[i][j] = -1; prev_dir[i][j] = -1; }
queue<P> q;
dist[sx][sy] = 0;
q.push(P(sx, sy));
while (!q.empty()) {
auto [x, y] = q.front(); q.pop();
if (x == tx && y == ty) break;
for (int k = 0; k < 4; k++) {
int nx = x + dx4[k], ny = y + dy4[k];
if (!in_bounds(nx, ny)) continue;
if (dist[nx][ny] != -1) continue;
if (used[nx][ny]) continue;
dist[nx][ny] = dist[x][y] + 1;
prev_dir[nx][ny] = k;
q.push(P(nx, ny));
}
}
if (dist[tx][ty] == -1) return {};
vector<P> p;
int cx = tx, cy = ty;
while (!(cx == sx && cy == sy)) {
p.emplace_back(cx, cy);
int k = prev_dir[cx][cy];
cx -= dx4[k]; cy -= dy4[k];
}
p.emplace_back(sx, sy);
reverse(p.begin(), p.end());
return p;
}
void greedy_initial_solution() {
// N=20 固定前提
vector<P> snake = build_snake_of_snakes();
assert((int)snake.size() == 400);
// 蛇行順での位置 (ブロック蛇行 + ブロック内蛇行 の合成順)
int snake_pos[20][20];
rep(i, 20) rep(j, 20) snake_pos[i][j] = -1;
for (int i = 0; i < (int)snake.size(); i++) {
snake_pos[snake[i].first][snake[i].second] = i;
}
// 上位 T/2 個の高価値マスをアンカーとして列挙
vector<pair<ll, P>> all_cells;
rep(i, N) rep(j, N) all_cells.push_back({A[i][j], P(i, j)});
sort(all_cells.begin(), all_cells.end(),
[](const auto& a, const auto& b) { return a.first > b.first; });
int top_k = max(1, (int)(T / 2));
if (top_k > (int)all_cells.size()) top_k = all_cells.size();
vector<P> anchors;
for (int i = 0; i < top_k; i++) anchors.push_back(all_cells[i].second);
// 蛇行順に並べる
sort(anchors.begin(), anchors.end(),
[&](const P& a, const P& b) {
return snake_pos[a.first][a.second] < snake_pos[b.first][b.second];
});
// 順方向と逆方向で試して良い方を採用
auto build = [&](const vector<P>& seq) -> pair<ll, vector<P>> {
clear_path();
if (seq.empty()) return {LLONG_MIN, {}};
push_cell(seq[0].first, seq[0].second);
for (int i = 1; i < (int)seq.size(); i++) {
int ax = seq[i].first, ay = seq[i].second;
if (used[ax][ay]) continue;
auto& tail = path.back();
vector<P> seg = bfs_shortest(tail.first, tail.second, ax, ay);
if (seg.empty()) continue;
if ((ll)path.size() + (ll)seg.size() - 1 > T) break;
for (int k = 1; k < (int)seg.size(); k++) {
push_cell(seg[k].first, seg[k].second);
}
}
extend_random((int)T);
return {score_cur, path};
};
vector<P> rev_anchors(anchors.rbegin(), anchors.rend());
auto fwd = build(anchors);
auto bwd = build(rev_anchors);
auto& chosen = (fwd.first >= bwd.first) ? fwd : bwd;
clear_path();
for (auto [x, y] : chosen.second) push_cell(x, y);
best_path = path;
best_score = score_cur;
// 統計用: アンカーヒット数
set<P> anchor_set(anchors.begin(), anchors.end());
int hit = 0;
for (auto& p : path) if (anchor_set.count(p)) hit++;
cerr << "[greedy] anchors=" << top_k
<< " hit=" << hit << "/" << top_k
<< " len=" << path.size() << "/" << T
<< " score=" << best_score
<< " (fwd=" << fwd.first << " bwd=" << bwd.first << ")" << endl;
}
// === 近傍 1: 末尾 k 削除 → 再延伸 ===
struct TailMove {
bool reversed;
int prefix_len;
vector<P> popped;
};
bool tr_apply(TailMove& m) {
int len = path.size();
if (len < 2) return false;
m.reversed = (rng() & 1);
if (m.reversed) reverse(path.begin(), path.end());
int kmax = min(len - 1, 6);
int k = 1 + (int)(rng() % kmax);
m.prefix_len = len - k;
m.popped.clear();
m.popped.reserve(k);
for (int i = 0; i < k; i++) {
m.popped.push_back(path.back());
pop_cell();
}
extend_random(T);
return true;
}
void tr_rollback(TailMove& m) {
while ((int)path.size() > m.prefix_len) pop_cell();
for (int i = (int)m.popped.size() - 1; i >= 0; i--) {
push_cell(m.popped[i].first, m.popped[i].second);
}
if (m.reversed) reverse(path.begin(), path.end());
}
// === 近傍 2: 挿入（path[i] と path[i+1] の共通隣接セルを差し込む）===
struct InsertMove {
int pos;
P cell;
};
bool ins_apply(InsertMove& m) {
int len = path.size();
if (len < 2 || len >= T) return false;
for (int trial = 0; trial < 10; trial++) {
int i = rng() % (len - 1);
auto [x1, y1] = path[i];
auto [x2, y2] = path[i + 1];
P cands[4]; int cnt = 0;
for (int k = 0; k < 4; k++) {
int cx = x1 + dx4[k], cy = y1 + dy4[k];
if (!in_bounds(cx, cy)) continue;
if (used[cx][cy]) continue;
if (abs(cx - x2) + abs(cy - y2) != 1) continue;
cands[cnt++] = P(cx, cy);
}
if (cnt == 0) continue;
P c = cands[rng() % cnt];
m.pos = i + 1;
m.cell = c;
path.insert(path.begin() + m.pos, c);
used[c.first][c.second] = true;
score_cur += A[c.first][c.second];
return true;
}
return false;
}
void ins_rollback(InsertMove& m) {
used[m.cell.first][m.cell.second] = false;
score_cur -= A[m.cell.first][m.cell.second];
path.erase(path.begin() + m.pos);
}
// =========================================================
// 自明な局所改善:
// 連続2手が90度ターンの場合 (path[i-1]→path[i]→path[i+1] が L字)、
// 2x2 ブロックの対角未使用マスの方が高得点なら path[i] と入れ替える。
// 隣接性は両側で維持されるので常に valid。
// =========================================================
int corner_swap_pass() {
int swaps = 0;
int len = path.size();
for (int i = 1; i + 1 < len; i++) {
auto [r0, c0] = path[i - 1];
auto [r1, c1] = path[i];
auto [r2, c2] = path[i + 1];
int dr1 = r1 - r0, dc1 = c1 - c0;
int dr2 = r2 - r1, dc2 = c2 - c1;
// 90度ターンのみ (内積==0 は直角、直進は内積>0、U字は不可)
if (dr1 * dr2 + dc1 * dc2 != 0) continue;
int nr = r0 + dr2, nc = c0 + dc2; // 2x2 の対角マス
if (!in_bounds(nr, nc)) continue;
if (used[nr][nc]) continue;
if (A[nr][nc] <= A[r1][c1]) continue;
used[r1][c1] = false;
used[nr][nc] = true;
score_cur += A[nr][nc] - A[r1][c1];
path[i] = P(nr, nc);
swaps++;
}
return swaps;
}
int corner_sweep() {
int total = 0;
while (true) {
int s = corner_swap_pass();
if (s == 0) break;
total += s;
}
return total;
}
// === 近傍 3: 削除（path[i-1] と path[i+1] が隣接していれば path[i] を削除）===
struct DeleteMove {
int pos;
P cell;
};
bool del_apply(DeleteMove& m) {
int len = path.size();
if (len < 3) return false;
for (int trial = 0; trial < 10; trial++) {
int i = 1 + (int)(rng() % (len - 2));
if (!adj(path[i - 1], path[i + 1])) continue;
m.pos = i;
m.cell = path[i];
used[m.cell.first][m.cell.second] = false;
score_cur -= A[m.cell.first][m.cell.second];
path.erase(path.begin() + i);
return true;
}
return false;
}
void del_rollback(DeleteMove& m) {
path.insert(path.begin() + m.pos, m.cell);
used[m.cell.first][m.cell.second] = true;
score_cur += A[m.cell.first][m.cell.second];
}
const double TIME_LIMIT_MS = 1900.0;
inline double elapsed_ms(chrono::steady_clock::time_point st) {
return chrono::duration<double, milli>(chrono::steady_clock::now() - st).count();
}
int main(){
input();
auto start = chrono::steady_clock::now();
// 温度スケールは A の値域から決める
ll amax = LLONG_MIN, amin = LLONG_MAX;
rep(i, N) rep(j, N) { amax = max(amax, A[i][j]); amin = min(amin, A[i][j]); }
double T_start = max(1.0, (double)(amax - amin));
double T_end = max(0.1, T_start * 0.001);
greedy_initial_solution();
int sw_init = corner_sweep();
if (score_cur > best_score) { best_score = score_cur; best_path = path; }
double t_init_ms = elapsed_ms(start);
ll initial_score = best_score;
ll corner_swaps = sw_init;
ll iter = 0, accepted = 0, improved = 0;
double now_ms = 0;
while (true) {
if ((iter & 1023) == 0) {
now_ms = elapsed_ms(start);
if (now_ms > TIME_LIMIT_MS) break;
}
iter++;
double progress = now_ms / TIME_LIMIT_MS;
double temp = T_start * pow(T_end / T_start, progress);
ll old_score = score_cur;
int op = rng() % 100;
bool applied = false;
TailMove tm; InsertMove im; DeleteMove dm;
int kind = -1;
if (op < 60) { applied = tr_apply(tm); kind = 0; }
else if (op < 80) { applied = ins_apply(im); kind = 1; }
else { applied = del_apply(dm); kind = 2; }
if (!applied) continue;
ll delta = score_cur - old_score;
bool accept;
if (delta >= 0) accept = true;
else {
double prob = exp((double)delta / temp);
double r = (double)(rng() & 0xFFFFFF) / (double)0x1000000;
accept = r < prob;
}
if (accept) {
accepted++;
if (score_cur > best_score) {
improved++;
int sw = corner_sweep();
corner_swaps += sw;
best_score = score_cur;
best_path = path;
}
} else {
if (kind == 0) tr_rollback(tm);
else if (kind == 1) ins_rollback(im);
else del_rollback(dm);
}
}
// 最終 sweep: best 状態を current に復元してから sweep
clear_path();
for (auto [x, y] : best_path) push_cell(x, y);
int sw_final = corner_sweep();
corner_swaps += sw_final;
if (score_cur > best_score) { best_score = score_cur; best_path = path; }
double t_total_ms = elapsed_ms(start);
double t_sa_ms = t_total_ms - t_init_ms;
cerr << fixed << setprecision(2);
cerr << "[time] init=" << t_init_ms << "ms"
<< " sa=" << t_sa_ms << "ms"
<< " total=" << t_total_ms << "ms"
<< " (limit=" << TIME_LIMIT_MS << "ms)" << endl;
cerr << "[stat] iter=" << iter
<< " iter/s=" << (iter * 1000.0 / max(1.0, t_sa_ms))
<< " accepted=" << accepted
<< " (" << (accepted * 100.0 / max((ll)1, iter)) << "%)"
<< " improved=" << improved << endl;
cerr << "[score] init=" << initial_score
<< " best=" << best_score
<< " gain=" << (best_score - initial_score)
<< " len=" << best_path.size() << "/" << T
<< " corner_swaps=" << corner_swaps << endl;
// 出力（フォーマットは問題に合わせて要調整）
cout << best_path.size() << "\n";
for (auto [x, y] : best_path) cout << x << " " << y << "\n";
return 0;
}