結果
| 問題 | No.5024 魔法少女うなと宝集め |
| コンテスト | |
| ユーザー |
 fepic_
|
| 提出日時 | 2026-05-02 17:59:10 |
| 言語 | C++17 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 901 ms / 2,000 ms |
| コード長 | 9,218 bytes |
| 記録 | |
| コンパイル時間 | 2,789 ms |
| コンパイル使用メモリ | 237,940 KB |
| 実行使用メモリ | 619,236 KB |
| スコア | 1,633,239 |
| 最終ジャッジ日時 | 2026-05-02 18:04:11 |
| 合計ジャッジ時間 | 34,436 ms |
|
ジャッジサーバーID （参考情報） |
judge1_0 / judge2_0 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand_int(int l, int r){
return uniform_int_distribution<int>(l, r)(rng);
}
// 1000000007
// 998244353
using pll = pair<long long, long long>;
typedef long long ll;
typedef long double ld;
// #define _GLIBCXX_DEBUG
#define INF (ll)2e18
#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;
}
struct state{
bool a[20][20];
int eval_score;
int8_t x, y;
int8_t sousax, sousay;
int oya = -1;
};
struct CompareState
{
bool operator()(const state &a, const state &b) const
{
return a.eval_score > b.eval_score;
}
};
int n,t;
int a[20][20];
void solve(){
int maxscore = -1e9;
pair<int,int> where = {0, 0};
int width = 5000;
vector<vector<state>> beam(t+1);
vector<pair<int,int>> c;
rep(i,n){
rep(j,n){
c.PB({i,j});
}
} std::random_device rd;
std::mt19937 g(rd());
shuffle(all(c),g);
rep(i,20){
state init_state{};
auto[x,y] = c[i];
init_state.a[x][y] = true;
init_state.x = x, init_state.y = y;
init_state.eval_score = 0;
beam[0].PB(init_state);}
for(int turn = 0; turn < t; turn++){
cerr << turn << " " << beam[turn].size() << endl;
vector<state> next_candidates;
for(int i = 0; i < beam[turn].size(); i++){
state &next_state = beam[turn][i];
int8_t prex = next_state.x;
int8_t prey = next_state.y;
int oyaa = next_state.oya;
for(int j = 0; j < 4; j++){
int x1 = next_state.x + f1[j];
int y1 = next_state.y + f2[j];
if(!bfs_est(x1,y1,n,n))continue;
if(next_state.a[x1][y1])continue;
next_state.a[x1][y1] = 1;
next_state.x = x1;
next_state.y = y1;
next_state.eval_score += a[x1][y1];
next_state.oya = i;
next_candidates.PB(next_state);
next_state.a[x1][y1] = 0;
next_state.x = prex;
next_state.y = prey;
next_state.eval_score -= a[x1][y1];
next_state.oya = oyaa;
}
}
if(next_candidates.size() > width){
std::nth_element(next_candidates.begin(), next_candidates.begin() + width, next_candidates.end(), CompareState());
next_candidates.resize(width);
}
int idx = 0;
for(auto& ns : next_candidates){
// moveする前に評価する
if(ns.eval_score > maxscore){
maxscore = ns.eval_score;
where = {idx, turn + 1};
}
beam[turn+1].push_back(std::move(ns));
idx++;
}
}
cerr << maxscore << endl;
// return;
string the_best_history = "";
vector<pair<int,int>> output;
while (where.second >= 0) {
output.push_back({
beam[where.second][where.first].x,
beam[where.second][where.first].y
});
int parent = beam[where.second][where.first].oya;
where = {parent, where.second - 1};
}
reverse(output.begin(), output.end());
cout <<output.size()-1 << endl;
int aa = 0;
for(auto [x, y ] : output){
if(aa++ == 0)continue;
cout << x << " " << y << endl;
}
}
int main(){
cin>>n>>t;
rep(i,n){
rep(j,n){
cin>>a[i][j];
}
}
solve();
}