#1195163 (C++23) No.5025 Forest Fire

• 問題: No.5025 Forest Fire
• ユーザー: Koi
• 提出日時: 2026-10-24 17:29:34
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 1,897 ms / 2,000 ms
• コード長: 8,616 bytes
• コンパイル時間: 3,635 ms
• コンパイル使用メモリ: 307,688 KB
• 実行使用メモリ: 9,936 KB
• スコア: 182,306,221
• 最終ジャッジ日時: 2026-10-24 17:44:08
• 合計ジャッジ時間: 156,904 ms
• ジャッジサーバーID （参考情報）: judge4_0 / <nil>

ファイルパターン	結果
other	AC * 50

ソースコード

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include <iostream>
#include <vector>
#include <string>
#include <chrono>
#include <random>
#include <numeric>
#include <algorithm>
#include <set>

using namespace std;

// --- SA.cppからの移植: 高速乱数 ---
static uint64_t s_rng[2] = {123456789, 362436069};
inline uint64_t rng64() {
    uint64_t s1 = s_rng[0], s0 = s_rng[1];
    s_rng[0] = s0;
    s1 ^= s1 << 23; 
    s_rng[1] = s1 ^ s0 ^ (s1 >> 17) ^ (s0 >> 26);
    return s_rng[1] + s0;
}
inline uint32_t rand_xor() { return rng64() >> 32; }

inline int rand_int(int n) {
    return (uint64_t(rand_xor()) * n) >> 32;
}
// ---------------------------------------------

constexpr int N = 50;
constexpr int K = 100;

struct DSU {
    vector<int> parent_or_size;
    DSU(int n) : parent_or_size(n, -1) {}
    
    int leader(int a) {
        if (parent_or_size[a] < 0) return a;
        return parent_or_size[a] = leader(parent_or_size[a]);
    }
    
    void merge(int a, int b) {
        int x = leader(a), y = leader(b);
        if (x == y) return;
        if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);
        parent_or_size[x] += parent_or_size[y];
        parent_or_size[y] = x;
    }
};

int D[N][N];
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

long long calc_score(const vector<pair<int, int>>& L) {
    vector<vector<bool>> in_S(N, vector<bool>(N, false));
    for (const auto& p : L) {
        in_S[p.first][p.second] = true;
    }
    
    DSU ds(N * N);
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (in_S[i][j] || D[i][j] < 5) continue;
            
            int ij = i * N + j;
            for (int k = 0; k < 4; ++k) {
                int x2 = i + dx[k];
                int y2 = j + dy[k];
                if (x2 >= 0 && x2 < N && y2 >= 0 && y2 < N) {
                    if (!in_S[x2][y2] && D[x2][y2] >= 5) {
                        int xy2 = x2 * N + y2;
                        ds.merge(ij, xy2);
                    }
                }
            }
        }
    }
    
    long long s = 0;
    for (int i = 0; i < N * N; ++i) {
        if (ds.parent_or_size[i] < 0) { 
            long long sz = -ds.parent_or_size[i];
            s += sz * sz;
        }
    }
    return s;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int dummy_n, dummy_k;
    if (!(cin >> dummy_n >> dummy_k)) return 0;
    
    for (int i = 0; i < N; ++i) {
        string S;
        cin >> S;
        for (int j = 0; j < N; ++j) {
            D[i][j] = S[j] - '0';
        }
    }
    
    vector<vector<pair<int, int>>> Subs;
    vector<pair<int, int>> small_elements;
    
    // 既存の走査1
    for (int i = 1; i < N - 1; ++i) {
        vector<pair<int, int>> L;
        for (int x = 0; x < N; ++x) {
            if (D[x][i + x % 2] >= 5) {
                L.push_back({x, i + x % 2});
            } else {
                if (L.size() > 5) {
                    Subs.push_back(L);
                } else if (!L.empty()) {
                    for (const auto& p : L) small_elements.push_back(p);
                }
                L.clear();
            }
        }
        if (!L.empty()) {
            if (L.size() > 5) {
                Subs.push_back(L);
            } else {
                for (const auto& p : L) small_elements.push_back(p);
            }
        }
    }
    
    // 既存の走査2
    for (int i = 1; i < N - 1; ++i) {
        vector<pair<int, int>> L;
        for (int x = 0; x < N; ++x) {
            if (D[i + x % 2][x] >= 5) {
                L.push_back({i + x % 2, x});
            } else {
                if (L.size() > 5) {
                    Subs.push_back(L);
                } else if (!L.empty()) {
                    for (const auto& p : L) small_elements.push_back(p);
                }
                L.clear();
            }
        }
        if (!L.empty()) {
            if (L.size() > 5) {
                Subs.push_back(L);
            } else {
                for (const auto& p : L) small_elements.push_back(p);
            }
        }
    }

    // x + y == k の斜め走査 (kは 0 から 2*N-2 まで)
    for (int k = 0; k <= 2 * N - 2; ++k) {
        vector<pair<int, int>> L;
        int start_x = max(0, k - N + 1);
        int end_x = min(N - 1, k);
        for (int x = start_x; x <= end_x; ++x) {
            int y = k - x;
            if (D[x][y] >= 5) {
                L.push_back({x, y});
            } else {
                if (L.size() > 5) {
                    Subs.push_back(L);
                } else if (!L.empty()) {
                    for (const auto& p : L) small_elements.push_back(p);
                }
                L.clear();
            }
        }
        if (!L.empty()) {
            if (L.size() > 5) {
                Subs.push_back(L);
            } else {
                for (const auto& p : L) small_elements.push_back(p);
            }
        }
    }

    // x - y == k の斜め走査 (kは -(N-1) から N-1 まで)
    for (int k = -(N - 1); k <= N - 1; ++k) {
        vector<pair<int, int>> L;
        int start_x = max(0, k);
        int end_x = min(N - 1, k + N - 1);
        for (int x = start_x; x <= end_x; ++x) {
            int y = x - k;
            if (D[x][y] >= 5) {
                L.push_back({x, y});
            } else {
                if (L.size() > 5) {
                    Subs.push_back(L);
                } else if (!L.empty()) {
                    for (const auto& p : L) small_elements.push_back(p);
                }
                L.clear();
            }
        }
        if (!L.empty()) {
            if (L.size() > 5) {
                Subs.push_back(L);
            } else {
                for (const auto& p : L) small_elements.push_back(p);
            }
        }
    }
    
    auto t0 = chrono::steady_clock::now();
    mt19937 rng(51); 
    
    vector<int> current_Chooses;
    int current_total_n = 0;
    long long current_score = calc_score({});
    
    vector<pair<int, int>> best_ans;
    long long best_score = current_score;
    
    vector<int> P(Subs.size());
    iota(P.begin(), P.end(), 0); 
    
    const double tl = 1.9;
    int cnt = 0;
    double threshold = 60.0; // 追加: 初期閾値
    
    while (true) {
        cnt++;
        
        if ((cnt & 127) == 0) {
            auto now = chrono::steady_clock::now();
            double elapsed = chrono::duration<double>(now - t0).count();
            if (elapsed >= tl) break;
            
            // 時間に応じて閾値を60から90へ線形に変化させる
            threshold = 70.0 + 20.0 * (elapsed / tl);
        }
        
        vector<int> next_Chooses = current_Chooses;
        int next_total_n = current_total_n;
        
        // 変更箇所: 閾値変数による判定
        while (next_total_n > threshold) {
            if (next_Chooses.empty()) break;
            int ind = rand_int((int)next_Chooses.size());
            int val = next_Chooses[ind];
            next_total_n -= Subs[val].size();
            
            auto it = find(next_Chooses.begin(), next_Chooses.end(), val);
            if (it != next_Chooses.end()) {
                next_Chooses.erase(it);
            }
        }
        
        shuffle(P.begin(), P.end(), rng);
        
        for (int i : P) {
            if (next_total_n + (int)Subs[i].size() < K) {
                next_Chooses.push_back(i);
                next_total_n += Subs[i].size();
            }
        }
        
        vector<pair<int, int>> L;
        for (int i : next_Chooses) {
            for (const auto& p : Subs[i]) {
                L.push_back(p);
            }
        }
        
        long long new_score = calc_score(L);
        
        if (new_score < current_score) {
            current_score = new_score;
            current_Chooses = next_Chooses;
            current_total_n = next_total_n;
            
            if (new_score < best_score) {
                best_score = new_score;
                best_ans = L;
            }
        }
    }
    
    set<pair<int, int>> final_ans;
    for (const auto& p : best_ans) {
        final_ans.insert(p);
    }
    
    shuffle(small_elements.begin(), small_elements.end(), rng);
    for (const auto& p : small_elements) {
        if (final_ans.size() >= K) break;
        final_ans.insert(p);
    }
    
    cout << final_ans.size() << "\n";
    for (const auto& p : final_ans) {
        cout << p.first << " " << p.second << "\n";
    }
    
    return 0;
}