Submission #70298523

---

Source Code Expand

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
#include <iomanip>
#include <numeric>
#include <random> // 乱数生成
#include <chrono> // 時間計測
#include <queue> 

using namespace std;
using ll = long long;
const ll INF = 1e18;

// --- 実行時間制限 (秒) ---
const double TIME_LIMIT_SEC = 1.97; 

// --- 焼きなましパラメータ ---
const double START_TEMP = 12.0; 
const double END_TEMP = 1.0;    

// --- ビームサーチ パラメータ ---
const int BEAM_WIDTH = 10; 

// 乱数生成器
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_real_distribution<double> real_dist(0.0, 1.0);

// 時間計測用
auto start_time = chrono::steady_clock::now();


// 宝箱jを開けるコストと攻撃シーケンスを計算
struct CostResult {
    map<int, ll> durability_updates; // <weapon_idx, use_count>
    vector<pair<int, int>> attacks_sequence;
};

/**
 * @brief 宝箱jを開ける最小コストを「機会費用」に基づいて計算 (v8準拠)
 * @param current_durability (const参照)
 */
CostResult calculate_cost(
    int j,
    const vector<ll>& H,
    const vector<vector<ll>>& A,
    const vector<bool>& open_set,
    const vector<ll>& current_durability, // const&
    const vector<double>& weapon_value 
) {
    CostResult res;
    ll h = H[j];
    if (h <= 0) return res;

    vector<pair<double, int>> usable_weapons; // {実質コスト, 武器idx}
    int N = H.size();
    for (int w = 0; w < N; ++w) {
        // 「今使える」武器 (open_set[w] かつ current_durability[w] > 0)
        if (open_set[w] && current_durability[w] > 0 && A[w][j] > 1) {
            double damage = (double)A[w][j];
            double value = weapon_value[w];
            double real_cost = value / damage; 
            usable_weapons.push_back({real_cost, w});
        }
    }

    // 「実質コスト」が低い順にソート O(N log N)
    sort(usable_weapons.begin(), usable_weapons.end());

    for (auto& p : usable_weapons) {
        double real_cost_per_hit = p.first;
        int w_idx = p.second;
        ll damage = A[w_idx][j];

        // 温存ロジック: 実質コストが 1.0 以上なら、素手で殴るのと変わらない（か損）
        // (武器が余る原因だが、v15 の浪費よりはマシという判断)
        if (real_cost_per_hit >= 1.0) {
            break; 
        }

        ll needed_hits = (h + damage - 1) / damage;
        ll use_count = min(current_durability[w_idx], needed_hits); 

        for (int k = 0; k < use_count; ++k) {
            res.attacks_sequence.push_back({w_idx, j});
        }
        h -= use_count * damage;
        res.durability_updates[w_idx] = use_count; // 使った回数を返す
        
        if (h <= 0) break;
    }

    // 残りはすべて素手で攻撃
    if (h > 0) {
        for (int k = 0; k < h; ++k) {
            res.attacks_sequence.push_back({-1, j});
        }
    }
    return res;
}

// ビームサーチで管理する「状態」
struct State {
    vector<bool> open_set;
    vector<ll> current_durability; // 今使える耐久値
    vector<ll> future_durability; // 将来手に入る耐久値 (Cの残り)
    ll total_cost;                  
    int parent_index;
    vector<pair<int, int>> last_attack_log;
    int last_opened_box; 

    bool operator<(const State& other) const {
        return total_cost < other.total_cost;
    }
};

/**
 * @brief 焼きなまし法の「評価関数」 O(N^2 log N) (v17)
 */
pair<ll, vector<pair<int, int>>> evaluate(
    int N,
    const vector<int>& order, 
    const vector<ll>& H,
    const vector<ll>& C,
    const vector<vector<ll>>& A,
    const vector<double>& weapon_value // 機会費用
) {
    vector<bool> open_set(N, false);
    vector<ll> current_durability(N, 0); // 今使える耐久値
    vector<ll> future_durability = C;    // 将来手に入る耐久値
    
    vector<pair<int, int>> total_log;
    ll total_cost = 0;

    for (int j : order) { 
        // 「今使える耐久値」で「機会費用」コストを計算
        CostResult res = calculate_cost(j, H, A, open_set, current_durability, weapon_value);
        
        total_cost += res.attacks_sequence.size();
        total_log.insert(total_log.end(), res.attacks_sequence.begin(), res.attacks_sequence.end());

        // 状態更新 (v15の厳密ロジック)
        for (auto const& [w_idx, use_count] : res.durability_updates) {
            current_durability[w_idx] -= use_count;
        }
        open_set[j] = true;
        current_durability[j] = future_durability[j]; 
        future_durability[j] = 0; 
    }
    return {total_cost, total_log};
}


int main() {
    int N;
    cin >> N; 

    vector<ll> H(N), C(N);
    for (int i = 0; i < N; ++i) cin >> H[i];
    for (int i = 0; i < N; ++i) cin >> C[i];

    vector<vector<ll>> A(N, vector<ll>(N));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            cin >> A[i][j];
        }
    }

    // 1. 前計算: 武器の「価値」を計算 (v8準拠)
    vector<double> weapon_value(N);
    for (int w = 0; w < N; ++w) {
        double total_saving = 0;
        for (int k = 0; k < N; ++k) {
            total_saving += max(0LL, A[w][k] - 1);
        }
        weapon_value[w] = 1.0 + (total_saving / (double)N);
    }

    // --- フェーズ1: ビームサーチ (初期解 P の生成) ---
    vector<int> best_order; 
    ll best_score = INF;
    
    { // ビームサーチのスコープ
        vector<vector<State>> beam_history(N + 1);

        {
            State initial_state;
            initial_state.open_set.resize(N, false);
            initial_state.current_durability.resize(N, 0);
            initial_state.future_durability = C;
            initial_state.total_cost = 0;
            initial_state.parent_index = -1;
            initial_state.last_opened_box = -1;
            beam_history[0].push_back(initial_state);
        }

        for (int step = 0; step < N; ++step) {
            vector<State> next_beam_candidates;
            for (int parent_idx = 0; parent_idx < beam_history[step].size(); ++parent_idx) {
                const auto& parent_state = beam_history[step][parent_idx];
                for (int j = 0; j < N; ++j) {
                    if (parent_state.open_set[j]) continue;

                    // v17 のコスト計算 (機会費用)
                    CostResult res = calculate_cost(j, H, A, 
                                                    parent_state.open_set, 
                                                    parent_state.current_durability, 
                                                    weapon_value); 
                    State new_state;
                    new_state.open_set = parent_state.open_set;
                    new_state.open_set[j] = true;
                    
                    // v15 の厳密なシミュレーションロジック
                    new_state.current_durability = parent_state.current_durability;
                    new_state.future_durability = parent_state.future_durability;
                    for (auto const& [w_idx, use_count] : res.durability_updates) {
                        new_state.current_durability[w_idx] -= use_count;
                    }
                    new_state.current_durability[j] = new_state.future_durability[j];
                    new_state.future_durability[j] = 0;
                    
                    new_state.total_cost = parent_state.total_cost + res.attacks_sequence.size();
                    new_state.parent_index = parent_idx;
                    new_state.last_attack_log = std::move(res.attacks_sequence);
                    new_state.last_opened_box = j; 

                    next_beam_candidates.push_back(std::move(new_state));
                }
            }
            sort(next_beam_candidates.begin(), next_beam_candidates.end());
            beam_history[step + 1].clear();
            for (int i = 0; i < min((int)next_beam_candidates.size(), BEAM_WIDTH); ++i) {
                beam_history[step + 1].push_back(std::move(next_beam_candidates[i]));
            }
        }

        // --- 「順番 P」の復元 ---
        int best_final_index = -1;
        if (!beam_history[N].empty()) {
            for (int i = 0; i < beam_history[N].size(); ++i) {
                if (beam_history[N][i].total_cost < best_score) {
                    best_score = beam_history[N][i].total_cost;
                    best_final_index = i;
                }
            }
        }
        
        if (best_final_index != -1) {
            int current_parent_idx = best_final_index; 
            for (int step = N; step >= 1; --step) {
                const auto& s = beam_history[step][current_parent_idx];
                best_order.push_back(s.last_opened_box); 
                current_parent_idx = s.parent_index;
            }
            reverse(best_order.begin(), best_order.end()); 
        }
    } // ビームサーチ スコープ終了

    if (best_score == INF) {
        return 0; // 解なし
    }
    
    vector<int> current_order = best_order;
    ll current_score = best_score;
    vector<pair<int, int>> best_log;
    {
        auto [score, log] = evaluate(N, best_order, H, C, A, weapon_value);
        best_log = std::move(log);
    }

    
    // --- フェーズ2: 焼きなまし法 (解の改善) ---
    uniform_int_distribution<int> idx_dist(0, N - 1);
    
    int iteration = 0;
    while (true) {
        iteration++;
        
        if (iteration % 10 == 0) {
            auto now = chrono::steady_clock::now();
            double elapsed_sec = chrono::duration<double>(now - start_time).count();
            if (elapsed_sec > TIME_LIMIT_SEC) {
                break;
            }
        }
        
        int i = idx_dist(rng);
        int j = idx_dist(rng);
        if (i == j) continue;
        
        swap(current_order[i], current_order[j]); 

        // 評価 O(N^2 log N)
        auto [new_score, new_log] = evaluate(N, current_order, H, C, A, weapon_value);
        
        double delta = new_score - current_score;
        
        auto now = chrono::steady_clock::now();
        double time_ratio = chrono::duration<double>(now - start_time).count() / TIME_LIMIT_SEC;
        double temp = START_TEMP + (END_TEMP - START_TEMP) * time_ratio;
        
        if (delta < 0 || real_dist(rng) < exp(-delta / temp)) {
            current_score = new_score;
            if (new_score < best_score) {
                best_score = new_score;
                best_order = current_order; // 順番を保存
                best_log = std::move(new_log); // ログを保存
            }
        } else {
            swap(current_order[i], current_order[j]); // 元に戻す
        }
    }
    
    // --- フェーズ3: 最終出力 ---
    // SA で見つけた best_log をそのまま出力
    for (const auto& attack : best_log) {
        cout << attack.first << " " << attack.second << endl;
    }
    cerr << (int)best_log.size() << endl;

    return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘int main()’:
Main.cpp:202:49: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<State>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  202 |             for (int parent_idx = 0; parent_idx < beam_history[step].size(); ++parent_idx) {
      |                                      ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:243:31: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<State>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  243 |             for (int i = 0; i < beam_history[N].size(); ++i) {
      |                             ~~^~~~~~~~~~~~~~~~~~~~~~~~

Judge Result