結果

問題 No.5024 魔法少女うなと宝集め
コンテスト
ユーザー hiikunZ
提出日時 2026-05-02 17:21:07
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 1,902 ms / 2,000 ms
コード長 3,511 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,625 ms
コンパイル使用メモリ 258,900 KB
実行使用メモリ 6,400 KB
スコア 1,858,346
最終ジャッジ日時 2026-05-02 17:22:44
合計ジャッジ時間 95,944 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge3_0
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
// #include <atcoder/all>

using namespace std;
using namespace chrono;

unsigned int rnd() {
    const unsigned long long C = 0xcafef00dd15ea5e5ULL;
    static unsigned long long X = C;
    X *= C;
    return (X >> 32);
}
static double rand01() { return (rnd() + 0.5) * (1.0 / UINT_MAX); }
static int randint(int N) {
    // [0, N)
    return ((unsigned long long)rnd() * N) >> 32;
}
std::chrono::_V2::system_clock::time_point startClock;
double gettime() {
    return (double)duration_cast<microseconds>(system_clock::now() - startClock)
               .count() *
           1e-6;
}

#define N 20
int A[N][N];
int T;

bool used[N][N];
int di[4] = {1, -1, 0, 0};
int dj[4] = {0, 0, 1, -1};

int best_ans_x[N * N], best_ans_y[N * N];
int now_ans_x[N * N], now_ans_y[N * N];

int now_score = 0;
int best_score = 0;
int best_L = 0;

void solve_mini(int i, int j, int depth) {
    if (gettime() > 0.1) { return; }

    {
        if (now_score > best_score) {
            best_L = depth + 1;
            best_score = now_score;
            for (int k = 0; k < best_L; k++) {
                best_ans_x[k] = now_ans_x[k];
                best_ans_y[k] = now_ans_y[k];
            }
        }
    }

    if (depth == T - 1) return;

    for (int dir = 0; dir < 4; dir++) {
        int ni = i + di[dir];
        int nj = j + dj[dir];

        if (ni < 0 || nj < 0 || ni >= N || nj >= N) continue;
        if (used[ni][nj]) continue;

        now_ans_x[depth + 1] = ni;
        now_ans_y[depth + 1] = nj;
        used[ni][nj] = true;
        now_score += A[ni][nj];
        solve_mini(ni, nj, depth + 1);
        used[ni][nj] = false;
        now_score -= A[ni][nj];
    }
}

void solve(int i, int j, int depth) {
    if (gettime() > 1.9) { return; }

    {
        if (now_score > best_score) {
            best_L = depth + 1;
            best_score = now_score;
            for (int k = 0; k < best_L; k++) {
                best_ans_x[k] = now_ans_x[k];
                best_ans_y[k] = now_ans_y[k];
            }
        }
    }

    if (depth == T - 1) return;

    vector<tuple<int, int, int>> candidates;
    for (int dir = 0; dir < 4; dir++) {
        int ni = i + di[dir];
        int nj = j + dj[dir];

        if (ni < 0 || nj < 0 || ni >= N || nj >= N) continue;
        if (used[ni][nj]) continue;

        candidates.emplace_back(-A[ni][nj], ni, nj);
    }
    sort(candidates.begin(), candidates.end());
    for (int i = 0; i < (int)candidates.size(); i++) {
        int ni = get<1>(candidates[i]);
        int nj = get<2>(candidates[i]);
        now_ans_x[depth + 1] = ni;
        now_ans_y[depth + 1] = nj;
        used[ni][nj] = true;
        now_score += A[ni][nj];
        solve(ni, nj, depth + 1);
        used[ni][nj] = false;
        now_score -= A[ni][nj];
    }
}

int main() {
    startClock = system_clock::now();
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int N_;
    cin >> N_ >> T;
    for (int i = 0; i < N_; i++) {
        for (int j = 0; j < N_; j++) { cin >> A[i][j]; }
    }
    for (int i = 0; i < N_; i++) {
        for (int j = 0; j < N_; j++) { used[i][j] = 0; }
    }

    now_ans_x[0] = 0;
    now_ans_y[0] = 0;
    used[0][0] = true;
    now_score = A[0][0];
    solve_mini(0, 0, 0);
    solve(0, 0, 0);

    cout << best_L << endl;
    for (int i = 0; i < best_L; i++) {
        cout << best_ans_x[i] << " " << best_ans_y[i] << "\n";
    }
}
0