結果
| 問題 | No.5024 魔法少女うなと宝集め |
| コンテスト | |
| ユーザー |
 hakatashi
|
| 提出日時 | 2026-04-24 14:38:37 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 1,858 ms / 2,000 ms |
| コード長 | 6,484 bytes |
| 記録 | |
| コンパイル時間 | 3,406 ms |
| コンパイル使用メモリ | 269,548 KB |
| 実行使用メモリ | 152,348 KB |
| スコア | 2,036,215 |
| 最終ジャッジ日時 | 2026-05-02 16:37:04 |
| 合計ジャッジ時間 | 105,342 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge1_1 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
// Implementation by Gemini CLI - v7_chokudai_sa.cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <bitset>
#include <chrono>
#include <random>
#include <queue>
#include <unordered_map>
using namespace std;
int N, T;
int A[20][20];
uint64_t zobrist[400];
int dr[] = {0, 0, 1, -1};
int dc[] = {1, -1, 0, 0};
struct State {
int r, c;
long long score;
int parent_idx;
int step;
bitset<400> visited;
uint64_t hash;
double eval_score;
bool operator<(const State& other) const { return eval_score < other.eval_score; }
};
struct SavedState { int r, c; int parent_idx; };
vector<pair<int, int>> run_chokudai(auto start_time, double time_limit) {
priority_queue<State> queues[405];
vector<SavedState> history[405];
unordered_map<uint64_t, long long> seen[405];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
State s; s.r = i; s.c = j; s.score = A[i][j]; s.parent_idx = -1; s.step = 1;
s.visited.set(i * N + j); s.hash = zobrist[i * N + j];
int deg = 0;
for(int d=0; d<4; d++){
int nr=i+dr[d], nc=j+dc[d];
if(nr>=0 && nr<N && nc>=0 && nc<N) deg++;
}
s.eval_score = s.score + deg * 10.0;
queues[1].push(s);
}
}
long long best_total_score = -1;
int best_total_step = -1, best_total_idx = -1;
int loop = 0;
while (true) {
if (++loop % 100 == 0) {
if (chrono::duration<double>(chrono::steady_clock::now() - start_time).count() > time_limit) break;
}
bool pushed = false;
for (int t = 1; t <= T; t++) {
if (queues[t].empty()) continue;
State s = queues[t].top(); queues[t].pop();
uint64_t state_key = s.hash ^ (uint64_t(s.r * N + s.c) << 32);
if (seen[t].count(state_key) && seen[t][state_key] >= s.score) continue;
seen[t][state_key] = s.score;
int current_idx = history[t].size();
history[t].push_back({s.r, s.c, s.parent_idx});
if (s.score > best_total_score) {
best_total_score = s.score; best_total_step = t; best_total_idx = current_idx;
}
if (t >= T) continue;
for (int d = 0; d < 4; d++) {
int nr = s.r + dr[d], nc = s.c + dc[d];
if (nr >= 0 && nr < N && nc >= 0 && nc < N && !s.visited.test(nr * N + nc)) {
State next_s; next_s.r = nr; next_s.c = nc; next_s.score = s.score + A[nr][nc];
next_s.parent_idx = current_idx; next_s.step = t + 1; next_s.visited = s.visited;
next_s.visited.set(nr * N + nc); next_s.hash = s.hash ^ zobrist[nr * N + nc];
int deg = 0;
for(int d2=0; d2<4; d2++){
int nnr=nr+dr[d2], nnc=nc+dc[d2];
if(nnr>=0 && nnr<N && nnc>=0 && nnc<N && !next_s.visited.test(nnr*N+nnc)) deg++;
}
next_s.eval_score = next_s.score + deg * 50.0;
uint64_t next_state_key = next_s.hash ^ (uint64_t(nr * N + nc) << 32);
if (!seen[t+1].count(next_state_key) || seen[t+1][next_state_key] < next_s.score) {
queues[t+1].push(next_s); pushed = true;
}
}
}
}
if (!pushed) {
bool any = false;
for(int t=1; t<=T; t++) if(!queues[t].empty()) any=true;
if(!any) break;
}
}
vector<pair<int, int>> path;
int curr_t = best_total_step, curr_idx = best_total_idx;
while (curr_t >= 1) {
path.push_back({history[curr_t][curr_idx].r, history[curr_t][curr_idx].c});
curr_idx = history[curr_t][curr_idx].parent_idx; curr_t--;
}
reverse(path.begin(), path.end());
return path;
}
int main() {
auto start_time = chrono::steady_clock::now();
mt19937 rng(42);
mt19937_64 rng64(42);
for (int i = 0; i < 400; i++) zobrist[i] = rng64();
if (!(cin >> N >> T)) return 0;
for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) cin >> A[i][j];
vector<pair<int, int>> best_path = run_chokudai(start_time, 1.2);
long long best_score = 0;
for (auto p : best_path) best_score += A[p.first][p.second];
// Local Search: Backtrack and regrow
while (chrono::duration<double>(chrono::steady_clock::now() - start_time).count() < 1.85) {
int k = uniform_int_distribution<int>(0, (int)best_path.size() - 2)(rng);
vector<pair<int, int>> current_path;
bitset<400> visited;
long long current_score = 0;
for (int i = 0; i <= k; i++) {
current_path.push_back(best_path[i]);
visited.set(best_path[i].first * N + best_path[i].second);
current_score += A[best_path[i].first][best_path[i].second];
}
// Regrow greedily with some randomness
while (current_path.size() < T) {
int r = current_path.back().first, c = current_path.back().second;
vector<pair<int, int>> candidates;
for (int d = 0; d < 4; d++) {
int nr = r + dr[d], nc = c + dc[d];
if (nr >= 0 && nr < N && nc >= 0 && nc < N && !visited.test(nr * N + nc)) {
candidates.push_back({nr, nc});
}
}
if (candidates.empty()) break;
// Pick candidate: higher value is better, but add some randomness
sort(candidates.begin(), candidates.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
return A[a.first][a.second] > A[b.first][b.second];
});
int idx = 0;
if (candidates.size() > 1 && uniform_real_distribution<double>(0, 1)(rng) < 0.2) {
idx = uniform_int_distribution<int>(0, candidates.size() - 1)(rng);
}
int nr = candidates[idx].first, nc = candidates[idx].second;
current_path.push_back({nr, nc});
visited.set(nr * N + nc);
current_score += A[nr][nc];
}
if (current_score > best_score) {
best_score = current_score;
best_path = current_path;
}
}
cout << (int)best_path.size() << endl;
for (auto p : best_path) cout << p.first << " " << p.second << endl;
return 0;
}