#1162559 (C++23) No.5024 魔法少女うなと宝集め

• 問題: No.5024 魔法少女うなと宝集め
• ユーザー: Shun_PI
• 提出日時: 2026-05-02 17:43:23
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 1,814 ms / 2,000 ms
• コード長: 4,535 bytes
• コンパイル時間: 6,260 ms
• コンパイル使用メモリ: 383,652 KB
• 実行使用メモリ: 6,400 KB
• スコア: 1,936,241
• 最終ジャッジ日時: 2026-05-02 17:45:11
• 合計ジャッジ時間: 98,418 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

ファイルパターン	結果
other	AC * 50

コンパイルメッセージ

main.cpp: In function 'int main()':
main.cpp:138:25: warning: 'score' may be used uninitialized [-Wmaybe-uninitialized]
  138 |     double diff = score - best_score;
      |                   ~~~~~~^~~~~~~~~~~~
main.cpp:98:9: note: 'score' was declared here
   98 |     int score, old_dir, x, y;
      |         ^~~~~
main.cpp:153:19: warning: 'old_dir' may be used uninitialized [-Wmaybe-uninitialized]
  153 |         dir[x][y] = old_dir;
main.cpp:98:16: note: 'old_dir' was declared here
   98 |     int score, old_dir, x, y;
      |                ^~~~~~~

ソースコード

#include <string>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
using P = pair<int, int>;
using PL = pair<lint, lint>;
#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)
#define ALL(a)  (a).begin(),(a).end()
constexpr int MOD = 1000000007;
vector<lint> RH_B = {1532834020, 1388622299};
vector<lint> RH_M = {2147482409, 2147478017};
constexpr int INF = 2147483647;
void yes(bool expr) {cout << (expr ? "Yes" : "No") << "\n";}
template<class T>void chmax(T &a, const T &b) { if (a<b) a=b; }
template<class T>void chmin(T &a, const T &b) { if (b<a) a=b; }
vector<int> dx = {1, 0, -1, 0};
vector<int> dy = {0, 1, 0, -1};
int N, T;
vector<vector<int>> A;
mt19937 mt(0);
int vst_id = -1;

int calc_score(int sx, int sy, vector<vector<int>> &dir, vector<vector<int>> &vst, bool output=false) {
  int score = 0;
  vst_id++;
  vector<int> path_x, path_y;
  REP(t, T) {
    score += A[sx][sy];
    vst[sx][sy] = vst_id;
    if(output) {
      path_x.push_back(sx);
      path_y.push_back(sy);
    }
    int d = dir[sx][sy];
    bool moved = false;
    int nx, ny;
    REP(d_try, 4) {
      int nd = (d + d_try) % 4;
      nx = sx + dx[nd];
      ny = sy + dy[nd];
      if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
      if(vst[nx][ny] == vst_id) continue;
      //dir[sx][sy] = nd;
      moved = true;
      break;
    }
    if(!moved) break;
    sx = nx;
    sy = ny;
  }
  if(output) {
    cout << path_x.size() << "\n";
    REP(i, path_x.size()) {
      cout << path_x[i] << " " << path_y[i] << "\n";
    }
  }
  return score;
}

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> N >> T;
  A.resize(N, vector<int>(N));
  REP(i, N) REP(j, N) cin >> A[i][j];
  vector<vector<int>> dir(N, vector<int>(N));
  REP(i, N) REP(j, N) dir[i][j] = mt() % 4;
  vector<vector<int>> vst(N, vector<int>(N, -1));
  int sx = 0, sy = 0;
  int best_score = calc_score(sx, sy, dir, vst);
  auto sa_start_time = chrono::system_clock::now();
  double sa_time_limit = 1800;
  int loop = 0;
  float start_temp = 4.0, end_temp = 3.0;
  float temp = start_temp;
  float time;
  int best_score_2 = best_score;
  vector<vector<int>> best_dir = dir;
  int best_sx = sx, best_sy = sy;
  while(true) {
    if(loop%10000 == 0) {
      time = chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now() - sa_start_time).count();
      if(time > sa_time_limit) break;
      cerr << loop << " " << best_score << " " << best_score_2 << "\n";
      temp = start_temp + (end_temp - start_temp) * time / (float)sa_time_limit;
    }
    loop++;

    int mode = mt() % 50;
    int score, old_dir, x, y;
    if(mode == 0) {
      //初期位置の変更
      x = sx;
      y = sy;
      int nx = x + dx[dir[x][y]];
      int ny = y + dy[dir[x][y]];
      if(nx >= 0 && nx < N && ny >= 0 && ny < N) {
        sx = nx;
        sy = ny;
      }
    } else {
      //現在のベスト解上のルート変更
      while(true) {
        x = mt() % N;
        y = mt() % N;
        if(vst[x][y] == vst_id) break;
      }
      old_dir = dir[x][y];
      int nbr_score_sum = 0;
      vector<int> nbr_score(4);
      REP(i, 4) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
        nbr_score_sum += A[nx][ny];
        nbr_score[i] = A[nx][ny];
      }
      while(true) {
        dir[x][y] = mt() % 4;
        if(dir[x][y] != old_dir) {
          int nx = x + dx[dir[x][y]];
          int ny = y + dy[dir[x][y]];
          if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
          double prob = nbr_score[dir[x][y]] / (double)nbr_score_sum;
          if(prob*(float)INF > (mt()%INF)) break;
        }
      }
      score = calc_score(sx, sy, dir, vst);
    }
    double diff = score - best_score;
    float prob = exp(diff*pow(0.1, temp));
    if(diff > 0 || prob*(float)INF > (mt()%INF)) {
      best_score = score;
      if(score > best_score_2) {
        best_score_2 = score;
        best_sx = sx;
        best_sy = sy;
        best_dir = dir;
      }
    } else {
      if(mode == 0) {
        sx = x;
        sy = y;
      } else {
        dir[x][y] = old_dir;
      }
    }
  }
  calc_score(best_sx, best_sy, best_dir, vst, true);
  cerr << best_score_2 << "\n";
}