結果

問題 No.5024 魔法少女うなと宝集め
コンテスト
ユーザー Shun_PI
提出日時 2026-05-02 17:58:46
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 1,986 ms / 2,000 ms
コード長 4,481 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 6,279 ms
コンパイル使用メモリ 383,644 KB
実行使用メモリ 6,400 KB
スコア 2,175,723
最終ジャッジ日時 2026-05-02 18:04:57
合計ジャッジ時間 109,376 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge3_0
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:131:25: warning: 'score' may be used uninitialized [-Wmaybe-uninitialized]
  131 |     double diff = score - best_score;
      |                   ~~~~~~^~~~~~~~~~~~
main.cpp:99:9: note: 'score' was declared here
   99 |     int score, old_dir, x, y;
      |         ^~~~~
main.cpp:147:19: warning: 'old_dir' may be used uninitialized [-Wmaybe-uninitialized]
  147 |         dir[x][y] = old_dir;
main.cpp:99:16: note: 'old_dir' was declared here
   99 |     int score, old_dir, x, y;
      |                ^~~~~~~

ソースコード

diff #
raw source code 

#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 = 1950;
  int loop = 0;
  float start_temp = 3.5, end_temp = 2.5;
  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;
  int patience = 0;
  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() % 100;
    int score, old_dir, x, y;
    if(mode == 0) {
      //初期位置の変更
      x = sx;
      y = sy;
      while(true) {
        sx = mt() % N;
        sy = mt() % N;
        if(sx == x && sy == y) continue;
        double prob = A[sx][sy] / 300.0;
        if(prob*(float)INF > (mt()%INF)) break;
      }
    } else {
      //現在のベスト解上のルート変更
      while(true) {
        x = mt() % N;
        y = mt() % N;
        if(vst[x][y] == vst_id) break;
      }
      old_dir = dir[x][y];
      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 = A[nx][ny] / (double)300.0;
          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;
      }
      patience = 0;
    } else {
      if(mode == 0) {
        sx = x;
        sy = y;
      } else {
        dir[x][y] = old_dir;
      }
      patience++;
      if(patience >= 3) {
        sx = best_sx;
        sy = best_sy;
        dir = best_dir;
        best_score = best_score_2;
      }
    }
  }
  calc_score(best_sx, best_sy, best_dir, vst, true);
  cerr << best_score_2 << "\n";
}
0