結果
| 問題 | No.5024 魔法少女うなと宝集め |
| コンテスト | |
| ユーザー |
 LNG
|
| 提出日時 | 2026-05-02 18:57:32 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 1,983 ms / 2,000 ms |
| コード長 | 6,225 bytes |
| 記録 | |
| コンパイル時間 | 2,635 ms |
| コンパイル使用メモリ | 219,916 KB |
| 実行使用メモリ | 6,400 KB |
| スコア | 2,186,260 |
| 最終ジャッジ日時 | 2026-05-02 18:59:26 |
| 合計ジャッジ時間 | 105,739 ms |
|
ジャッジサーバーID （参考情報） |
judge2_0 / judge1_0 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <iostream>
#include <chrono>
#include <cmath>
using namespace std;
struct Xorshift {
uint32_t x = 123456789;
uint32_t y = 362436069;
uint32_t z = 521288629;
uint32_t w = 88675123;
inline uint32_t next() {
uint32_t t = x ^ (x << 11);
x = y; y = z; z = w;
return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}
inline double nextDouble() {
return next() * 2.32830643653869628906e-10;
}
inline uint32_t nextInt(uint32_t bound) {
return (uint32_t)(((uint64_t)next() * bound) >> 32);
}
};
int N, T_max;
int A[400];
int adj[400][4];
int adj_deg[400];
struct State {
int path[400];
uint64_t visited[7];
int len;
int score;
inline void init() {
len = 0;
score = 0;
visited[0] = visited[1] = visited[2] = visited[3] =
visited[4] = visited[5] = visited[6] = 0ULL;
}
inline void push(int u) {
path[len++] = u;
visited[u >> 6] |= (1ULL << (u & 63));
score += A[u];
}
inline int pop() {
int u = path[--len];
visited[u >> 6] &= ~(1ULL << (u & 63));
score -= A[u];
return u;
}
inline bool is_visited(int u) const {
return (visited[u >> 6] >> (u & 63)) & 1ULL;
}
inline void copy_to(State& dst) const {
dst.len = len;
dst.score = score;
dst.visited[0] = visited[0];
dst.visited[1] = visited[1];
dst.visited[2] = visited[2];
dst.visited[3] = visited[3];
dst.visited[4] = visited[4];
dst.visited[5] = visited[5];
dst.visited[6] = visited[6];
for(int i = 0; i < len; ++i) {
dst.path[i] = path[i];
}
}
};
void generate_initial(State& best_init, Xorshift& rnd) {
best_init.score = -1;
State s;
for(int i = 0; i < 5000; ++i) {
s.init();
int start = rnd.nextInt(N * N);
s.push(start);
while(s.len < T_max) {
int u = s.path[s.len - 1];
int best_v = -1;
int max_a = -1;
int cands[4];
int cands_sz = 0;
for(int k = 0; k < adj_deg[u]; ++k) {
int v = adj[u][k];
if(!s.is_visited(v)) {
cands[cands_sz++] = v;
if(A[v] > max_a) {
max_a = A[v];
best_v = v;
}
}
}
if(cands_sz == 0) break;
int nxt;
if(best_v != -1 && rnd.next() < 3435973836U) {
nxt = best_v;
} else {
nxt = cands[rnd.nextInt(cands_sz)];
}
s.push(nxt);
}
if(s.score > best_init.score) {
s.copy_to(best_init);
}
}
}
inline void mutate(State& s, Xorshift& rnd) {
if(s.len > 1 && (rnd.next() & 1)) {
int half = s.len >> 1;
for(int i = 0; i < half; ++i) {
int tmp = s.path[i];
s.path[i] = s.path[s.len - 1 - i];
s.path[s.len - 1 - i] = tmp;
}
}
if(s.len > 1) {
double r = rnd.nextDouble();
int pop_len = 1 + (int)(r * r * (s.len - 1));
if(pop_len > s.len - 1) pop_len = s.len - 1;
for(int i = 0; i < pop_len; ++i) s.pop();
}
while(s.len < T_max) {
int u = s.path[s.len - 1];
int best_v = -1;
int max_a = -1;
int cands[4];
int cands_sz = 0;
for(int k = 0; k < adj_deg[u]; ++k) {
int v = adj[u][k];
if(!s.is_visited(v)) {
cands[cands_sz++] = v;
if(A[v] > max_a) {
max_a = A[v];
best_v = v;
}
}
}
if(cands_sz == 0) break;
int nxt;
if(best_v != -1 && rnd.next() < 3006477107U) {
nxt = best_v;
} else {
nxt = cands[rnd.nextInt(cands_sz)];
}
s.push(nxt);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
if (!(cin >> N >> T_max)) return 0;
for(int i = 0; i < N * N; ++i) {
cin >> A[i];
}
for(int i = 0; i < N; ++i) {
for(int j = 0; j < N; ++j) {
int u = i * N + j;
adj_deg[u] = 0;
if(i > 0) adj[u][adj_deg[u]++] = (i - 1) * N + j;
if(i < N - 1) adj[u][adj_deg[u]++] = (i + 1) * N + j;
if(j > 0) adj[u][adj_deg[u]++] = i * N + j - 1;
if(j < N - 1) adj[u][adj_deg[u]++] = i * N + j + 1;
}
}
Xorshift rnd;
auto start_clock = chrono::steady_clock::now();
double start_time = chrono::duration_cast<chrono::nanoseconds>(start_clock.time_since_epoch()).count() * 1e-9;
double time_limit = 1.98;
State stateA, stateB, best;
State* cur = &stateA;
State* nxt = &stateB;
generate_initial(*cur, rnd);
cur->copy_to(best);
double T0 = 5000.0;
double T1 = 10.0;
double temp = T0;
int iter = 0;
while(true) {
if((iter & 1023) == 0) {
auto now_clock = chrono::steady_clock::now();
double current_time = chrono::duration_cast<chrono::nanoseconds>(now_clock.time_since_epoch()).count() * 1e-9 - start_time;
if(current_time > time_limit) break;
double progress = current_time / time_limit;
temp = T0 * pow(T1 / T0, progress);
}
iter++;
cur->copy_to(*nxt);
mutate(*nxt, rnd);
int diff = nxt->score - cur->score;
if(diff >= 0 || rnd.nextDouble() < exp(diff / temp)) {
State* tmp = cur;
cur = nxt;
nxt = tmp;
if(cur->score > best.score) {
cur->copy_to(best);
}
}
}
cout << best.len << "\n";
for(int i = 0; i < best.len; ++i) {
cout << best.path[i] / N << " " << best.path[i] % N << "\n";
}
return 0;
}