結果
| 問題 | No.5024 魔法少女うなと宝集め |
| コンテスト | |
| ユーザー |
 syndrome
|
| 提出日時 | 2026-05-02 17:57:48 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 193 ms / 2,000 ms |
| コード長 | 9,759 bytes |
| 記録 | |
| コンパイル時間 | 4,426 ms |
| コンパイル使用メモリ | 370,980 KB |
| 実行使用メモリ | 6,400 KB |
| スコア | 1,487,430 |
| 最終ジャッジ日時 | 2026-05-02 18:01:03 |
| 合計ジャッジ時間 | 21,598 ms |
|
ジャッジサーバーID （参考情報） |
judge2_1 / judge3_0 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
コンパイルメッセージ
main.cpp: In member function 'simulated_annealing::Cost simulated_annealing::State::CalcScore(simulated_annealing::Cost)':
main.cpp:131:5: warning: no return statement in function returning non-void [-Wreturn-type]
131 | }
| ^
ソースコード
// (◕ᴗ◕✿)
// #pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define srep(i, s, n) for (ll i = s; i < (n); ++i)
#define len(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
using namespace std;
template<typename T> using vc = vector<T>;
template<typename T> using vv = vc<vc<T>>;
using vi = vc<int>;using vvi = vv<int>; using vvvi = vv<vi>;
using ll = long long;using vl = vc<ll>;using vvl = vv<ll>; using vvvl = vv<vl>;
using ld = long double; using vld = vc<ld>; using vvld = vc<vld>; using vvvld = vc<vvld>;
using uint = unsigned int;
using ull = unsigned long long;
const ld pi = 3.141592653589793;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
// const ll mod = 1000000007;
const ll mod = 998244353;
#define debug(var) do { cerr << #var << " :\n"; view(var); } while(0)
template<typename T>void view(const T& e) {cerr << e;}
template<typename T1, typename T2>void view(const pair<T1, T2>& p) {cerr << "{" << p.first << ", " << p.second << "}";}
template<typename T>void view(const vc<T>& v) {for (const auto& e : v) {view(e);cerr << " ";} cerr << endl;}
template<typename T>void view(const vv<T>& vv) {for (const auto& v : vv) {view(v);} cerr << endl;}
template<typename T>void view(const set<T>& s) {for (const auto& e : s) {view(e);cerr << " ";} cerr << endl;}
template<typename T>void view(const multiset<T>& s) {for (const auto& e : s) {view(e);cerr << " ";} cerr << endl;}
template<typename T>void view(const unordered_set<T>& s) {for (const auto& e : s) {view(e);cerr << " ";} cerr << endl;}
template<typename T1, typename T2>void view(const map<T1, T2>& mp){for (const auto& e : mp) {view(e);cerr << " ";} cerr << endl;}
ifstream in;
ofstream wrt;
string outputfile = "output.txt", inputfile = "input.txt";
unsigned int randxor(){
static unsigned int x = 123456789, y = 362436069, z = 521288629, w = 88675123;
unsigned int t;
t = (x ^ (x << 11)); x = y; y = z; z = w; return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}
int randint(int a, int b) {return(a + randxor() % (b - a));}
struct Timer {
public:
Timer(int limit){
start = chrono::high_resolution_clock::now();
goal = start + chrono::milliseconds(limit);
}
inline double rate(){
return (chrono::high_resolution_clock::now() - start).count() / (double)(goal - start).count();
}
inline int get_time(){return (chrono::high_resolution_clock::now() - start).count() / 1e6;}
private:
chrono::high_resolution_clock::time_point start;
chrono::high_resolution_clock::time_point goal;
};
double log_table[70000];
//variable
constexpr int TIME_LIMIT = 190;
constexpr int N = 20;
constexpr int NN = (N + 1) * (N + 2);
constexpr int dir[4] = {-1, 1, N+1, -N-1};
int T;
int A[NN];
namespace simulated_annealing {
constexpr int transition_num = 2;
int transition_count[transition_num];
int success_count[transition_num];
using Cost = int;
struct Config {
int time_limit;
int temperature_type;
double start_temp, goal_temp;
int probability[transition_num];
};
struct State {
int d[4] = {0, 1, 2, 3};
Cost score;
vi path;
bitset<NN> used;
State(){
score = inf;
}
// void operator=(const State &other) {
// score = other.score;
// }
void init(){
used.reset();
rep(i, N + 1){
used.set(i);
used.set(N * (N + 1) + i);
used.set(i * (N + 1) + N);
}
path.clear();
path.push_back(randint(1, N + 1) * (N + 1) + randint(0, N));
used.set(path[0]);
score = A[path[0]];
while (len(path) < T){
bool add = false;
rep(i, 2) swap(d[i], d[randint(i + 1, 4)]);
for (auto a : d){
int k = dir[a];
if (!used[path.back() + k]){
score += A[path.back() + k];
used.set(path.back() + k);
path.push_back(path.back() + k);
add = true;
break;
}
}
if (!add) break;
}
}
Cost CalcScore(Cost threshold = inf){
}
void transition01(Cost &threshold){
if (len(path) > T - 2) return;
transition_count[0]++;
int p = randint(0, len(path) - 1);
if (abs(path[p] - path[p + 1]) == 1){
if (path[p] + 1 == path[p + 1]){
int f = randint(0, 2);
if (f == 0) f = -1;
if (!used[path[p] + f * (N+1)] && !used[path[p]+1 + f * (N+1)]){
path.insert(path.begin() + p + 1, path[p] + 1 + f * (N+1));
path.insert(path.begin() + p + 1, path[p] + f * (N+1));
score += A[path[p + 1]];
score += A[path[p + 2]];
used[path[p + 1]] = true;
used[path[p + 2]] = true;
}
}else{
int f = randint(0, 2);
if (f == 0) f = -1;
if (!used[path[p] + f * (N+1)] && !used[path[p]-1 + f * (N+1)]){
path.insert(path.begin() + p + 1, path[p] - 1 + f * (N+1));
path.insert(path.begin() + p + 1, path[p] + f * (N+1));
score += A[path[p + 1]];
score += A[path[p + 2]];
used[path[p + 1]] = true;
used[path[p + 2]] = true;
}
}
}else{
if (path[p] + N + 1 == path[p + 1]){
int f = randint(0, 2);
if (f == 0) f = -1;
if (!used[path[p] + f] && !used[path[p] + (N + 1) + f]){
path.insert(path.begin() + p + 1, path[p] + (N + 1) + f);
path.insert(path.begin() + p + 1, path[p] + f);
score += A[path[p + 1]];
score += A[path[p + 2]];
used[path[p + 1]] = true;
used[path[p + 2]] = true;
}
}else{
int f = randint(0, 2);
if (f == 0) f = -1;
if (!used[path[p] + f] && !used[path[p] - (N + 1) + f]){
path.insert(path.begin() + p + 1, path[p] - (N + 1) + f);
path.insert(path.begin() + p + 1, path[p] + f);
score += A[path[p + 1]];
score += A[path[p + 2]];
used[path[p + 1]] = true;
used[path[p + 2]] = true;
}
}
}
}
void transition02(Cost &threshold){
if (len(path) < 5) return;
transition_count[1]++;
int p = randint(1, len(path) - 2);
if (abs(path[p] - path[p + 1]) == 1){
if (abs(path[p - 1] - path[p + 2]) == 1){
}
}else{
if (abs(path[p - 1] - path[p + 2]) == N + 1){
}
}
if (score <= threshold){
success_count[1]++;
}else{
}
}
};
State simulated_annealing(const Config& config, State state) {
State best;
Timer timer(config.time_limit);
int roop = 0;
double tmp = config.start_temp;
double rate = 0;
while (true){
roop++;
int randomint = randint(0, 100);
Cost threshold = state.score - tmp * log_table[randint(0, 70000)];
// if (randomint < config.probability[0]){ // transition 01
// state.transition01(threshold);
// }else{
// }
state.transition01(threshold);
if (rate > 0.9 && best.score > state.score){ // update best
best = state;
}
if (roop % 1000 == 0){
// if (roop % 10000 == 0) cerr << state.score << " " << best.score << endl;
rate = timer.rate();
if (config.temperature_type == 0){
tmp = config.start_temp + rate * (config.goal_temp - config.start_temp);
}else{
tmp = config.start_temp * pow(config.goal_temp / config.start_temp, rate);
}
if (rate > 1.0){
break;
}
}
}
cerr << "roop : " << roop << endl;
cerr << "score : " << best.score << endl;
rep(i, transition_num) cerr << "transition" << i << " conversion rate : " << fixed << setprecision(4) << success_count[i] / (double)transition_count[i] * 100 << " % " << success_count[i] << " / " << transition_count[i] << endl;
return best;
};
}// namespace simulated_annealing
struct Solver{
simulated_annealing::State ans;
void input(){
int a; cin >> a >> T;
fill(A, A + NN, -1);
rep(i, N) rep(j, N) cin >> A[(N + 1) * (i + 1) + j];
}
void init(){
double n = 1 / (double)(2 * 70000);
for (int i = 0; i < 70000; i++) {
log_table[i] = log(((double)i / 70000) + n);
}
}
void output(){
cout << len(ans.path) << endl;
for (auto p : ans.path) cout << p / (N + 1) - 1 << ' ' << p % (N+1) << endl;
cerr << ans.score << endl;
}
void run(){
Timer timer(TIME_LIMIT);
input();
init();
simulated_annealing::State state;
state.init();
simulated_annealing::Config config = {
TIME_LIMIT - timer.get_time(),
0,
1.0,
0.1,
{70, 100}
};
ans = simulated_annealing::simulated_annealing(config, state);
output();
}
};
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
Solver solver;
solver.run();
return 0;
}