結果
| 問題 | No.5024 魔法少女うなと宝集め |
| コンテスト | |
| ユーザー |
 Ojun
|
| 提出日時 | 2026-05-02 17:57:55 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 3 ms / 2,000 ms |
| コード長 | 6,392 bytes |
| 記録 | |
| コンパイル時間 | 2,610 ms |
| コンパイル使用メモリ | 232,804 KB |
| 実行使用メモリ | 6,400 KB |
| スコア | 796,251 |
| 最終ジャッジ日時 | 2026-05-02 18:01:14 |
| 合計ジャッジ時間 | 9,987 ms |
|
ジャッジサーバーID （参考情報） |
judge2_1 / judge3_0 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
#include <algorithm>
#include <chrono>
#include <cmath>
#include <iostream>
#include <limits>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, T;
cin >> N >> T;
vector<vector<int>> A(N, vector<int>(N));
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> A[i][j];
}
}
const int B = 3;
const int BR = (N + B - 1) / B;
const int BC = (N + B - 1) / B;
vector<vector<int>> block_sum(BR, vector<int>(BC, 0));
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
block_sum[i / B][j / B] += A[i][j];
}
}
vector<pair<int, int>> cells;
cells.reserve(N * N);
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cells.push_back({i, j});
}
}
sort(cells.begin(), cells.end(), [&](const auto &lhs, const auto &rhs) {
if (A[lhs.first][lhs.second] != A[rhs.first][rhs.second]) {
return A[lhs.first][lhs.second] > A[rhs.first][rhs.second];
}
return lhs < rhs;
});
auto start_score = [&](int si, int sj) -> long long {
bool used[20][20] = {};
const int di[4] = {-1, 1, 0, 0};
const int dj[4] = {0, 0, -1, 1};
long long best = A[si][sj];
auto dfs = [&](auto &&self, int ci, int cj, int depth, long long sum) -> void {
best = max(best, sum);
if (depth == 5) return;
for (int dir = 0; dir < 4; dir++) {
int ni = ci + di[dir];
int nj = cj + dj[dir];
if (ni < 0 || ni >= N || nj < 0 || nj >= N) continue;
if (used[ni][nj]) continue;
used[ni][nj] = true;
self(self, ni, nj, depth + 1, sum + A[ni][nj]);
used[ni][nj] = false;
}
};
used[si][sj] = true;
dfs(dfs, si, sj, 0, A[si][sj]);
return best;
};
int best_start_i = cells[0].first;
int best_start_j = cells[0].second;
long long best_start_val = -1;
int start_limit = min<int>(40, (int)cells.size());
for (int k = 0; k < start_limit; k++) {
int i = cells[k].first;
int j = cells[k].second;
long long val = start_score(i, j);
if (val > best_start_val) {
best_start_val = val;
best_start_i = i;
best_start_j = j;
}
}
auto start_time = chrono::steady_clock::now();
const double TIME_LIMIT = 1.99;
auto elapsed = [&]() {
return chrono::duration<double>(chrono::steady_clock::now() - start_time).count();
};
auto block_dist = [&](int bi, int bj, int ti, int tj) {
return abs(bi - ti) + abs(bj - tj);
};
auto best_neighbor_block = [&](int bi, int bj) {
int best_id = bi * BC + bj;
int best_sum = -1;
for (int di = -1; di <= 1; di++) {
for (int dj = -1; dj <= 1; dj++) {
if (di == 0 && dj == 0) continue;
int ni = bi + di;
int nj = bj + dj;
if (ni < 0 || ni >= BR || nj < 0 || nj >= BC) continue;
int id = ni * BC + nj;
if (block_sum[ni][nj] > best_sum || (block_sum[ni][nj] == best_sum && id < best_id)) {
best_sum = block_sum[ni][nj];
best_id = id;
}
}
}
return best_id;
};
vector<vector<bool>> visited(N, vector<bool>(N, false));
vector<pair<int, int>> path;
int cur_i = best_start_i;
int cur_j = best_start_j;
visited[cur_i][cur_j] = true;
path.push_back({cur_i, cur_j});
const int di[4] = {-1, 1, 0, 0};
const int dj[4] = {0, 0, -1, 1};
while ((int)path.size() < T) {
double remain_time = TIME_LIMIT - elapsed();
if (remain_time <= 0.0) break;
int remain_steps = T - (int)path.size();
double step_budget = remain_time / max(1, remain_steps);
auto step_deadline = chrono::steady_clock::now() + chrono::duration<double>(step_budget);
int curr_bi = cur_i / B;
int curr_bj = cur_j / B;
int target_block = best_neighbor_block(curr_bi, curr_bj);
int ti = target_block / BC;
int tj = target_block % BC;
int best_i = -1;
int best_j = -1;
long long best_val = numeric_limits<long long>::min();
int best_first_a = -1;
auto eval_cell = [&](int i, int j) -> long long {
int bi = i / B;
int bj = j / B;
long long val = 3LL * A[i][j] + 2LL * block_sum[bi][bj];
val += 2LL * (block_dist(curr_bi, curr_bj, ti, tj) - block_dist(bi, bj, ti, tj));
return val;
};
auto dfs = [&](auto &&self, int ci, int cj, int depth, long long sum, int first_i, int first_j) -> void {
if (chrono::steady_clock::now() >= step_deadline) return;
if (depth > 0) {
if (sum > best_val || (sum == best_val && A[first_i][first_j] > best_first_a)) {
best_val = sum;
best_i = first_i;
best_j = first_j;
best_first_a = A[first_i][first_j];
}
}
if (depth == 3) return;
for (int dir = 0; dir < 4; dir++) {
int ni = ci + di[dir];
int nj = cj + dj[dir];
if (ni < 0 || ni >= N || nj < 0 || nj >= N) continue;
if (visited[ni][nj]) continue;
visited[ni][nj] = true;
int next_first_i = (depth == 0 ? ni : first_i);
int next_first_j = (depth == 0 ? nj : first_j);
self(self, ni, nj, depth + 1, sum + eval_cell(ni, nj), next_first_i, next_first_j);
visited[ni][nj] = false;
if (chrono::steady_clock::now() >= step_deadline) return;
}
};
visited[cur_i][cur_j] = true;
dfs(dfs, cur_i, cur_j, 0, 0, -1, -1);
if (best_i == -1) break;
cur_i = best_i;
cur_j = best_j;
visited[cur_i][cur_j] = true;
path.push_back({cur_i, cur_j});
}
cout << path.size() << '\n';
for (const auto &p : path) {
cout << p.first << ' ' << p.second << '\n';
}
return 0;
}