提出 #69509878

---

ソースコード 拡げる

// AHC054
// 良い初期解
// 次の進路を妨害する
// 96, 3480, 59906
// ゴールを入口が内側に向くように囲む
// 94, 7374, 100256
// // 進路を3つ先まで妨害する
// // 376, 6810, 56772
// ゴールを入口が外側に向くように囲む
// 44, 1462, 121180
// // 進路妨害を3マス前に変更
// // 56, 1050, 89452
// ふさがなくていい場所をふさがないように変更
// 42, 2902, 127114
// // 進路妨害をゴール側に行かないように変更
// // 100, 3176, 63798
// カタツムリ状に配置
// 1078, 1106,
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
using ll = long long;
using ull = unsigned long long;
#define TIME_LIMIT_MS 1950
#define TEMP_MAX 100000
#define TEMP_MIN 0
#define SUBMIT

random_device seed_gen;
mt19937_64 rng(seed_gen());
uniform_real_distribution<> real_dist(0.0, 1.0);

bool time_check(chrono::high_resolution_clock::time_point start, int limit_ms);

double temp_func(double temp_max, double temp_min, chrono::high_resolution_clock::time_point start, int limit_ms);

// スコアが下がる方向への焼きなまし
double prob_func(ll prev_score, ll crr_score, double temp);

// 入力
int N;
int ti, tj;
vector<vector<char>> b;

// 答え

// それ以外
vector<vector<bool>> rev; // 確認済みか

chrono::high_resolution_clock::time_point start_time;

void input();

int calc_score();

// 座標が有効か
bool valid_coord(int x, int y);

// たどり着けるマスの数
// 大きいほうが良い
// 花にたどり着けないなら0
// 0 ~ N^2
int bfs_score(int pi, int pj);

#ifdef SUBMIT
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    start_time = chrono::high_resolution_clock::now();

    input();

    bool first_flag = true;

    while (1)
    {
        int pi, pj;
        cin >> pi >> pj;
        int n;
        cin >> n;
        rep(i, n)
        {
            int x, y;
            cin >> x >> y;
            rev[x][y] = true;
        }

        if (pi == ti && pj == tj)
        {
            break;
        }

        // トレント配置

        int m = 0;
        vector<int> xt;
        vector<int> yt;

        // 全てのマスをシャッフル
        // O(N^2)
        vector<pair<int, int>> cand;
        cand.reserve(N * N);

        // // ゴールの四方を囲む
        // if(first_flag){
        //     first_flag = false;
        //     priority_queue<
        //         pair<int,pair<int,int>>,
        //         vector<pair<int,pair<int,int>>>,
        //         greater<pair<int,pair<int,int>>>
        //     > pq;
        //     pq.push({abs(ti - N / 2) + abs(tj - N),     {ti,tj-1}}); // 右
        //     pq.push({abs(ti - N / 2) + abs(tj),         {ti,tj+1}}); // 左
        //     pq.push({abs(ti)         + abs(tj - N / 2), {ti+1,tj}}); // 上
        //     pq.push({abs(ti - N)     + abs(tj - N / 2), {ti-1,tj}}); // 下
        //     while(!pq.empty()){
        //         cand.push_back(pq.top().second);
        //         pq.pop();
        //     }
        // }

        // ゴールをカタツムリ状に囲む
        if(first_flag){
            first_flag = false;
            vector<int> di = {-1, 0, 0, 1, 2, 2, 2, 1, 0,-1,-2,-3,-3,-3,-2};
            vector<int> dj = { 0, 1,-1, 1, 0,-1,-2,-3,-3,-3,-2,-1, 0, 1, 2};
            rep(i,di.size()){
                cand.push_back({ti + di[i], tj + dj[i]});
            }
        }

        // 進路妨害
        priority_queue<pair<int,pair<int,int>>> pq;
        vector<int> dirx = {0, 1, 0, -1};
        vector<int> diry = {1, 0, -1, 0};
        rep(i,4){
            int ni = pi + 2*dirx[i];
            int nj = pj + 2*diry[i];
            if(valid_coord(pi+dirx[i],pj+diry[i]) && b[pi+dirx[i]][pj+diry[i]] == 'T')continue;
            cand.push_back({ni,nj});
            // pq.push({N * N - min(abs(ni - ti) + abs(nj - tj), 10), {ni,nj}});
            // pq.push({N * N - min(min(abs(ni - ti), abs(nj - tj)), 5), {ni,nj}});
        }
        rep(i,4){
            int ni = pi + dirx[i];
            int nj = pj + diry[i];
            if(valid_coord(pi+dirx[i],pj+diry[i]) && b[pi+dirx[i]][pj+diry[i]] == 'T')continue;
            for(int j=1;j<4;j++){
                int ni2 = ni + dirx[(i+j) % 4];
                int nj2 = nj + diry[(i+j) % 4];
                cand.push_back({ni2,nj2});
                // pq.push({- min(abs(ni2 - ti) + abs(nj2 - tj), 10), {ni2,nj2}});
                // pq.push({- min(min(abs(ni2 - ti), abs(nj2 - tj)), 5), {ni2,nj2}});
            }
        }
        while(!pq.empty()){
            cand.push_back(pq.top().second);
            pq.pop();
        }

        // 順に配置できるかチェック
        // O(cand.size())
        rep(i, cand.size())
        {
            auto [xc, yc] = cand[i];

            // 有効な座標か
            if (xc < 0 || xc >= N || yc < 0 || yc >= N)
            {
                continue;
            }

            // 空きマスか
            if (b[xc][yc] == 'T' || (ti == xc && tj == yc))
            {
                continue;
            }

            // 未確認か
            if (rev[xc][yc])
                continue;

            int before = bfs_score(pi,pj);

            // 木として配置
            b[xc][yc] = 'T';

            // ゴールがふさがらないか
            // たどり着けるマスが減らないか
            // bfs
            // O(N^2)
            int after = bfs_score(pi,pj);
            if(before - after > 0){
                // ダメなら戻して次へ
                b[xc][yc] = '.';
                continue;
            }

            m++;
            xt.push_back(xc);
            yt.push_back(yc);
        }

        // 出力
        // O(N^2)
        cout << m;
        rep(i, m)
        {
            cout << " " << xt[i] << " " << yt[i];
        }
        cout << '\n';
        cout.flush();
    }
}
#else
int main()
{
}
#endif

/////////////////////////////////

bool time_check(chrono::high_resolution_clock::time_point start, int limit_ms)
{
    auto now = chrono::high_resolution_clock::now();
    auto diff = now - start;
    auto diff_ms = chrono::duration_cast<chrono::milliseconds>(diff).count();
    if (diff_ms < limit_ms)
    {
        return true;
    }
    else
    {
        return false;
    }
}

double temp_func(double temp_max, double temp_min, chrono::high_resolution_clock::time_point start, int limit_ms)
{
    auto now = chrono::high_resolution_clock::now();
    auto diff = now - start;
    auto diff_ms = chrono::duration_cast<chrono::milliseconds>(diff).count();
    double r = (double)diff_ms / (double)limit_ms;
    return temp_max - ((temp_max - temp_min) * r);
}

// スコアが下がる方向への焼きなまし
double prob_func(ll prev_score, ll crr_score, double temp)
{
    return exp((((double)prev_score) - ((double)crr_score)) / temp);
}

////////////

void input()
{
    cin >> N >> ti >> tj;
    b.assign(N, vector<char>(N));
    rep(i, N)
    {
        rep(j, N)
        {
            cin >> b[i][j];
        }
    }
    rev.assign(N, vector<bool>(N, false));
}

/////////////

int calc_score()
{
    return 0;
}

// 座標が有効か
bool valid_coord(int x, int y){
    if (x < 0 || x >= N || y < 0 || y >= N)
    {
        return false;
    }else{
        return true;
    }
}

// たどり着けるマスの数
// 大きいほうが良い
// 花にたどり着けないなら0
// 0 ~ N^2
int bfs_score(int pi, int pj){
    bool ok = false;
    int c = 0;
    queue<pair<int, int>> q;
    vector<int> dirx = {-1, 1, 0, 0};
    vector<int> diry = {0, 0, -1, 1};
    vector<vector<bool>> seen(N, vector<bool>(N, false));
    q.push({pi, pj});
    seen[pi][pj] = true;
    c++;
    while (!q.empty())
    {
        auto [xb, yb] = q.front();
        q.pop();

        rep(j, 4)
        {
            int xn = xb + dirx[j];
            int yn = yb + diry[j];
            if (xn < 0 || N <= xn)
                continue;
            if (yn < 0 || N <= yn)
                continue;
            if (seen[xn][yn])
                continue;
            seen[xn][yn] = true;
            c++;
            if (b[xn][yn] == 'T')
                continue;
            if (xn == ti && yn == tj)
            {
                ok = true;
                continue;
            }
            q.push({xn, yn});
        }
    }
    if(ok){
        return c;
    }else{
        return 0;
    }
}

提出情報

コンパイルエラー

Main.cpp: In function ‘int main()’:
Main.cpp:21:37: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   21 | #define rep(i, n) for (int i = 0; i < n; i++)
      |                                     ^
Main.cpp:129:13: note: in expansion of macro ‘rep’
  129 |             rep(i,di.size()){
      |             ^~~
Main.cpp:21:37: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   21 | #define rep(i, n) for (int i = 0; i < n; i++)
      |                                     ^
Main.cpp:165:9: note: in expansion of macro ‘rep’
  165 |         rep(i, cand.size())
      |         ^~~

ジャッジ結果