結果
| 問題 | No.5024 魔法少女うなと宝集め |
| コンテスト | |
| ユーザー |
 fepic_
|
| 提出日時 | 2026-06-20 18:39:39 |
| 言語 | C++17 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 1,985 ms / 2,000 ms |
| コード長 | 12,323 bytes |
| 記録 | |
| コンパイル時間 | 3,855 ms |
| コンパイル使用メモリ | 292,448 KB |
| 実行使用メモリ | 6,400 KB |
| スコア | 2,097,731 |
| 最終ジャッジ日時 | 2026-06-20 18:41:26 |
| 合計ジャッジ時間 | 105,852 ms |
|
ジャッジサーバーID （参考情報） |
judge3_1 / judge1_0 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:430:21: warning: 'olddir' may be used uninitialized [-Wmaybe-uninitialized]
430 | s.dir[x][y] = olddir;
main.cpp:373:9: note: 'olddir' was declared here
373 | int olddir;
| ^~~~~~
main.cpp:435:18: warning: 'sx' may be used uninitialized [-Wmaybe-uninitialized]
435 | cal_score(s);
| ~~~~~~~~~^~~
main.cpp:374:21: note: 'sx' was declared here
374 | int x,y,sx,sy;
| ^~
main.cpp:435:18: warning: 'sy' may be used uninitialized [-Wmaybe-uninitialized]
435 | cal_score(s);
| ~~~~~~~~~^~~
main.cpp:374:24: note: 'sy' was declared here
374 | int x,y,sx,sy;
| ^~
ソースコード
//-------------------------------------------------------------------------------------
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
// #include <boost/multiprecision/cpp_int.hpp>
// namespace boo = boost::multiprecision;
using mint = modint998244353;
// 1000000007
// 998244353
using pll = pair<long long, long long>;
typedef long long ll;
typedef long double ld;
// #define _GLIBCXX_DEBUG
#define INF (ll)1e9 + 1
#define fi first
#define se second
#define R return 0
#define PB push_back
#define stirng string
#define vll vector<ll>
#define NO cout << "No" << endl
#define YES cout << "Yes" << endl
#define ANS cout << ans << endl
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define dou fixed << setprecision(20)
#define an cout << (ans ? "Yes" : "No")
#define en cout << "------------" << endl
// #define min(x,y) ((x) < (y) ? (x) : (y))
// #define max(x,y) ((x) > (y) ? (x) : (y))
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define vv(name, h, w, type, init) \
std::vector<std::vector<type>> name((h), std::vector<type>((w), (init)))
#define vvv(name, d, h, w, type, init) \
std::vector<std::vector<std::vector<type>>> name((d), \
std::vector<std::vector<type>>((h), std::vector<type>((w), (init))))
#define vvvv(name, x, y, z, w, type, init) \
std::vector<std::vector<std::vector<std::vector<type>>>> name((x), \
std::vector<std::vector<std::vector<type>>>((y), \
std::vector<std::vector<type>>((z), std::vector<type>((w), (init)))))
#define vvvvv(name, a, b, c, d, e, type, init) \
std::vector<std::vector<std::vector<std::vector<std::vector<type>>>>> name( \
(a), std::vector<std::vector<std::vector<std::vector<type>>>>( \
(b), std::vector<std::vector<std::vector<type>>>( \
(c), std::vector<std::vector<type>>( \
(d), std::vector<type>((e), (init))))))
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
long long TEN(int x) { return x == 0 ? 1 : TEN(x - 1) * 10; }
template <class T>
inline bool chmax(T &a, T b)
{
if (a < b)
{
a = b;
return 1;
}
return 0;
}
template <class T>
inline bool chmin(T &a, T b)
{
if (a > b)
{
a = b;
return 1;
}
return 0;
}
// ll mod = (ll)1000000007;
ll mod = (ll)998244353;
// ll inv = 499122177;
vector<ll> f1 = {-1, 0, 0, 1}, f2 = {0, -1, 1, 0}; // 四方向
vector<ll> f3 = {-1, 0, 1, 0, 1, -1, 1, -1}, f4 = {0, 1, 0, -1, 1, 1, -1, -1}; // ハチ方向
template <class T>
using minpq = priority_queue<T, vector<T>, greater<T>>;
template <class T>
long long reduce(const vector<T> &a)
{
long long s = 0;
for (auto &x : a)
s += x;
return s;
}
void yn(bool ok)
{
cout << (ok ? "Yes" : "No") << '\n';
}
#define vvl_kaiten(v) \
{ \
ll n = size(v); \
vvl nx(n, vl(n)); \
rep(i, n) rep(j, n) nx[j][n - i - 1] = v[i][j]; \
swap(nx, v); \
} // 時計回りに90°回転
// #define vvl_kaiten(v) {ll n = size(v);vvl nx(n,vl(n));rep(i,n)rep(j,n)nx[n-j-1][i]=v[i][j];swap(nx,v);}//反時計周りに90°回転
#define vs_kaiten(v) \
{ \
ll n = v.size(); \
vector<string> nx(n, string(n, '.')); \
rep(i, n) rep(j, n) nx[j][n - i - 1] = v[i][j]; \
swap(nx, v); \
} // 文字列版 時計回りに90°回転
// #define vs_kaiten(v) {ll n = size(v);vs nx(n,string(n,'.'));rep(i,n)rep(j,n)nx[n-j-1][i]=v[i][j];swap(nx,v);}//文字列版 反時計周りに90°回転
#define yu_qurid(x, y) ((x) * (x) + (y) * (y)) // ユークリッド距離 sqrtはしてないなので注意
#define mannhattan(x1, x2, y1, y2) (abs(x1 - x2) + abs(y1 - y2)) // マンハッタン距離 = |x1-x2|+|y1-y2|
// reference @frest
#define vc_cout(v) \
do \
{ \
ll nn = v.size(); \
for (int i = 0; i < nn; i++) \
{ \
cout << v[i] << " "; \
} \
cout << endl; \
} while (0)
#define vv_cout(v) \
do \
{ \
ll nn = v.size(); \
for (int i = 0; i < nn; i++) \
{ \
for (int j = 0; j < v[i].size(); j++) \
cout << v[i][j] << " "; \
cout << endl; \
} \
} while (0)
// n(10進数)をa進数に
string to_oct(ll n, ll a)
{
string s;
while (n)
{
s = to_string(n % a) + s;
n /= a;
}
return s;
}
bool bfs_est(ll xx1, ll yy1, ll hhh, ll www)
{
return (0 <= xx1 && xx1 < hhh && 0 <= yy1 && www > yy1);
}
bool IsPrime(int num) // 素数判定
{
if (num < 2)
return false;
else if (num == 2)
return true;
else if (num % 2 == 0)
return false;
double sqrtNum = sqrt(num);
for (int i = 3; i <= sqrtNum; i += 2)
{
if (num % i == 0)
{
return false;
}
}
// 素数である
return true;
}
long long modpow(long long a, long long n, long long mod)
{ //@Nyaan
a %= mod;
long long ret = 1;
while (n > 0)
{
if (n & 1)
ret = ret * a % mod;
a = a * a % mod;
n >>= 1;
}
return ret % mod;
};
vector<ll> enumdiv(ll n)
{ // 約数全列挙
vector<ll> S;
for (ll i = 1; 1LL * i * i <= n; i++)
if (n % i == 0)
{
S.push_back(i);
if (i * i != n)
S.push_back(n / i);
}
// sort(S.begin(), S.end());
return S;
}
// struct NewlineGuard {//プログラム終了時に改行
// ~NewlineGuard() { cout << '\n'; }
// };
// NewlineGuard guard;
struct pair_hash
{ // unodered_mapの時に使う
// unordered_map<pll,ll, pair_hash> mp;
size_t operator()(const pair<ll, ll> &p) const
{
// 64bit のハッシュ合成
return hash<ll>()(p.first) ^ (hash<ll>()(p.second) << 1);
}
};
struct VectorHash
{
size_t operator()(const vector<long long> &v) const
{
size_t h = 0;
for (long long x : v)
{
h = h * 31 + std::hash<long long>()(x);
}
return h;
}
};
vector<pair<long long, long long>> prime_factorize(long long n)
{ // 素数全検挙 @drken
vector<pair<long long, long long>> res;
for (long long p = 2; p * p <= n; ++p)
{
if (n % p != 0)
continue;
int num = 0;
while (n % p == 0)
{
++num;
n /= p;
}
res.push_back(make_pair(p, num));
}
if (n != 1)
res.push_back(make_pair(n, 1));
return res;
}
ll LIS(const vector<long long> &a)
{
int N = (int)a.size();
vector<long long> dp_(N, INF);
for (int i = 0; i < N; ++i)
{
// dp[k] >= a[i] となる最小のイテレータを見つける
auto it = lower_bound(dp_.begin(), dp_.end(), a[i]);
// そこを a[i] で書き換える
*it = a[i];
}
// dp[k] < INF となる最大の k に対して k+1 が答え
// それは dp[k] >= INF となる最小の k に一致する
return lower_bound(dp_.begin(), dp_.end(), INF) - dp_.begin();
}
static const auto fast_io = []()
{
cin.tie(nullptr);
ios::sync_with_stdio(false);
return 0;
}();
bool colinear(ll ax, ll ay, ll bx, ll by, ll cx, ll cy)
{
// 2つのA,Bを通る直線上にcがのってるかどうか
long long val1 = (by - ay) * (cx - ax);
long long val2 = (bx - ax) * (cy - ay);
return (val1 == val2);
}
template <class T>
bool next_combination(T &bit, int N)
{
T x = bit & -bit, y = bit + x;
bit = (((bit & ~y) / x) >> 1) | y;
return (bit < (1LL << N));
}
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
mt19937 mt(0);
int n,t;
int a[20][20];
vector<int> dx = {1, 0, -1, 0};
vector<int> dy = {0, 1, 0, -1};
struct state{
int sx,sy;
vector<vector<int>> dir = vector<vector<int>>(20, vector<int>(20));
};
int cnt = 1;
vector<vector<int>> vst(20,vector<int>(20,0));
vector<pair<int,int>> path;
int cal_score(state &s){
int score = 0;
int sx = s.sx;
int sy = s.sy;
path.clear();
rep(i,t){
path.push_back({sx,sy});
score += a[sx][sy];
vst[sx][sy] = cnt;
int nexdir = s.dir[sx][sy];
bool mov = false;
int nx, ny;
rep(d,4){
int nd = (nexdir + d) % 4;
nx = sx + dx[nd];
ny = sy + dy[nd];
if(!bfs_est(nx,ny,20,20))continue;
if(vst[nx][ny] == cnt)continue;
mov = true;
break;
}
if(!mov)break;
sx = nx;
sy = ny;
}
//s.sx = sx,s.sy = sy;
cnt++;
return score;
}
int main() {
cin>>n>>t;
rep(i,n){
rep(j,n){
cin>>a[i][j];
}
}
state s;
s.sx = 0,s.sy = 0;
rep(i,n){
rep(j,n){
s.dir[i][j] = mt() % 4;
}
}
int best_score = cal_score(s);
int ma = 2147483647;
auto sa_start_time = chrono::system_clock::now();
double sa_time_limit = 1950;
int loop = 0;
float start_temp = 3.5, end_temp = 0.1;
float temp = start_temp;
int best_score_2 = best_score;
float time;
int nsc;
state best_s = s;
while(1){
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 olddir;
int x,y,sx,sy;
if(99 <= mode){
int mg = mt();
x = path[mg%(path.size())].first,y = path[mg%(path.size())].second;
olddir = s.dir[x][y];
while(true) {
s.dir[x][y] = mt() % 4;
if(s.dir[x][y] != olddir) {
int nx = x + dx[s.dir[x][y]];
int ny = y + dy[s.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;
}
}
nsc = cal_score(s);
}
else{
sx = s.sx;
sy = s.sy;
while(true){
x = mt()%n;
y = mt()%n;
if(s.sx == x && s.sy == y) continue;
double prob = a[x][y] / 300.0;
if(prob*(double)ma > (mt()%ma)) break;
}
s.sx = x;
s.sy = y;
nsc = cal_score(s);
}
double diff = nsc - best_score;
float prob = exp(diff*pow(0.1, temp));
if(diff > 0 || prob*(float)INF > (mt()%INF)) {
best_score = nsc;
if(nsc > best_score_2) {
best_score_2 = nsc;
best_s.sx = s.sx;
best_s.sy = s.sy;
best_s.dir = s.dir;
}
}
else{
if(99 <= mode)
s.dir[x][y] = olddir;
else{
s.sx = sx,s.sy = sy;
}
cal_score(s);
}
}
cal_score(best_s);
cout << path.size() << endl;
for(auto[x,y] : path){
cout << x << " " << y << endl;
}
}