#1195083 (C++17) No.5025 Forest Fire

• 問題: No.5025 Forest Fire
• ユーザー: Koi
• 提出日時: 2026-10-24 16:45:44
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 1,865 ms / 2,000 ms
• コード長: 6,214 bytes
• コンパイル時間: 1,842 ms
• コンパイル使用メモリ: 182,832 KB
• 実行使用メモリ: 9,928 KB
• スコア: 167,726,477
• 最終ジャッジ日時: 2026-10-24 16:48:29
• 合計ジャッジ時間: 154,992 ms
• ジャッジサーバーID （参考情報）: judge2_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;

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;
    // 追加: Subsに入らなかった要素を記録する配列
    vector<pair<int, int>> small_elements;
    
    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);
            }
        }
    }
    
    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);
            }
        }
    }
    
    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); 
    
    while (true) {
        auto now = chrono::steady_clock::now();
        double elapsed = chrono::duration<double>(now - t0).count();
        if (elapsed >= 1.9) break;
        
        vector<int> next_Chooses = current_Chooses;
        int next_total_n = current_total_n;
        
        while (next_total_n > 70) {
            if (next_Chooses.empty()) break;
            uniform_int_distribution<int> dist(0, (int)next_Chooses.size() - 1);
            int ind = dist(rng);
            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);
    }
    
    // 追加: K個になるまで、5未満だった要素からランダムに追加する
    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;
}