ハイスコアの時はGoogle AI StudioでGemini Pro 2.5にプログラムを書いてもらっていたので、解説も書いてもらいました。 解説を以下に示します。

AtCoder Heuristic Contestで提出したC++コードについて、その戦略と実装を解説します。

AtCoder Heuristic Contest 解法解説

このコードは、制限時間内にできるだけ良い解を見つける「ヒューリスティックコンテスト」の典型的なアプローチを採用しています。核となる戦略は、序盤をじっくり考える「ビームサーチ」と、中盤以降を素早く進める「貪欲法」を組み合わせたハイブリッド探索です。さらに、この探索を何度も繰り返すことで、解の精度を高めていきます。

---

1. 全体戦略：反復改善とハイブリッド探索

この問題は「どの宝箱をどの順番で、どの武器を使って開けるか」を最適化する問題です。最適な手順を見つけるのは非常に困難なため、このコードでは以下の戦略を取ります。

• 反復改善: 制限時間が終了するまで、「最初に開ける宝箱」を様々に変えながら何度もシミュレーションを実行します。その中で見つかった最も手数が良かったものを最終的な答えとして出力します。
• ハイブリッド探索: 1回のシミュレーションは、2つのフェーズに分かれています。
  • フェーズ1: 序盤のビームサーチ: ゲームの序盤は、その後の展開に大きな影響を与えます。そこで、最初の数ターンは有望な手を複数候補保持しながら探索する「ビームサーチ」を行い、悪い手を早い段階で選んでしまうリスクを減らします。
  • フェーズ2: 中盤以降の貪欲法: 序盤の探索で最も有望だった盤面を引き継ぎ、残りの宝箱は「今最も得な一手」を選び続ける「貪欲法」で高速に最後までシミュレーションします。

この戦略により、探索の幅と速度のバランスを取っています。

---

2. 事前計算：武器の価値評価

本格的な探索を始める前に、それぞれの宝箱を開けたときに手に入る「武器」がどれくらい強力かをあらかじめ計算しておきます。これにより、探索中に「どの宝箱を優先して開けるべきか」を判断する際の重要な指標とします。

武器の価値は、以下の式で評価しています。

武器の価値 = (0.6 * 平均ダメージ + 0.4 * 最大ダメージ) * 初期使用回数

• 平均ダメージ: 安定して高いダメージを出せる武器を評価します。
• 最大ダメージ: 特定の宝箱に対して非常に有効な一撃を持つ武器を評価します。
• 初期使用回数: 価値の高い攻撃を何度も繰り出せる武器を高く評価します。

この計算を precompute_weapon_values 関数で行っています。

---

3. 探索エンジンの詳細 (solve_hybrid)

この関数が探索の心臓部です。指定された「最初に開ける宝箱」からシミュレーションを開始します。

フェーズ1：序盤のビームサーチ

• 目的: 序盤の数ターン（このコードではBEAM_SEARCH_TURNS = 6）で、最善の盤面だけでなく、有望な盤面の候補を複数（BEAM_WIDTH = 8）残します。
• 動作:
  1. 現在の各盤面から、まだ開けていない全ての宝箱を開ける手をシミュレートします。
  2. 宝箱を開ける際は、手持ちの武器で最もダメージ効率の良いものを使い続けます。
  3. シミュレート後の盤面を「スコア」で評価します。スコアは 「-(手数) + (開けた宝箱の武器価値)」 で計算され、手数が少なく、かつ価値の高い武器が手に入る盤面が高く評価されます。
  4. 全ての候補の中からスコアの高い順にBEAM_WIDTH個だけを残し、次のターンに進みます。
• 効果: この手法により、目先の利益は小さくても将来的に非常に強力な武器が手に入るような、有望な手を見逃しにくくなります。

フェーズ2：中盤以降の高速貪欲法

• 目的: ビームサーチで得られた最もスコアの高い盤面を引き継ぎ、ゲーム終了までを高速にシミュレーションします。
• 動作:
  1. 毎ターン、「手持ちの武器」と「まだ開いていない宝箱」の全ての組み合わせについて、「今この一手を打ったらどれだけ得か」を評価関数でスコアリングします。
  2. 評価関数は非常に重要で、以下のような要素を考慮しています。
     • 現在の利益: 宝箱の残りHPに対してどれだけダメージを与えられるか。
     • 武器の消耗度: 武器の使用回数が多いほど、少し高く評価し、使い切ることを促します。
     • 将来の利益: この攻撃で宝箱を開けられるなら、その宝箱から得られる武器の価値もスコアに加算します。
  3. 最もスコアが高かった「武器で宝箱を攻撃する」という一手を選択し、実行します。
  4. もし使える武器がない、あるいは武器を使うより素手で攻撃した方が効率的だと判断した場合は、最もコストパフォーマンスの良い宝箱を素手で攻撃します。
• 効果: 複雑な評価関数を用いることで、単に目先のダメージだけでなく、将来的な展開も考慮した賢い選択を高速に行うことができます。

---

4. メインループの挙動

main関数では、時間制限が来るまで以下のループを実行します。

1. 初期ターゲットの選定: 「最初にどの宝箱を開けるか」を決めます。
   • 候補は、事前計算した「武器価値 ÷ 初期HP」のスコアが高い順にソートされています。
   • ループの序盤は、このスコアが高い有望な候補から順番に試します。
   • ループが進むと、あえて下位の候補もランダムに選ぶようになります。これにより、一見すると不利に見える初期行動が最終的に良い結果に繋がる可能性（局所最適解からの脱出）を探ります。
2. 探索の実行: 選んだ初期ターゲットでsolve_hybrid関数を呼び出し、一連の行動手順を得ます。
3. 最良解の更新: 得られた解の手数が、それまでに見つかった最良解の手数より少なければ、最良解を更新します。
4. 時間切れまで繰り返し: 1〜3を時間いっぱいまで繰り返します。

最終的に、この反復の中で見つかった最も手数の少ない行動手順が出力されます。

---

まとめ

このコードは、ヒューリスティックコンテストで高得点を狙うための洗練されたテクニックを複数組み合わせています。

• 戦略的な事前計算による的確な状況判断。
• ビームサーチによる序盤の慎重な探索。
• 賢い評価関数を持つ貪欲法による高速な終盤シミュレーション。
• 反復改善による解の継続的なブラッシュアップ。

これらの要素が組み合わさることで、複雑な問題に対して非常に質の高い解を導き出すことが可能になっています。

対象のコード全体

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <cmath>
#include <limits>
#include <random>
#include <chrono>

using namespace std;
using namespace std::chrono;

// --- グローバル変数 ---
int N_g;
vector<int> H_g, C_g;
vector<vector<int>> A_g;
vector<double> weapon_values_g;
mt19937 rng(random_device{}());

struct GameState {
    vector<int> chest_H;
    vector<int> weapon_durability;
    vector<bool> chest_opened;
    int opened_chests_count;

    GameState(const vector<int>& H, const vector<int>& C) 
        : chest_H(H), weapon_durability(C), chest_opened(H.size(), false), opened_chests_count(0) {}
};

struct Action {
    int w = -1, b = -1;
    double score = -1e18;
};

// 武器価値の事前計算
void precompute_weapon_values() {
    weapon_values_g.resize(N_g);
    for (int i = 0; i < N_g; ++i) {
        long long total_damage = 0;
        int max_damage = 0;
        for (int damage : A_g[i]) {
            total_damage += damage;
            max_damage = max(max_damage, damage);
        }
        double avg_damage = static_cast<double>(total_damage) / N_g;
        weapon_values_g[i] = (0.6 * avg_damage + 0.4 * max_damage) * C_g[i];
    }
}

// 盤面とパラメータに基づき、最善手（のスコア）を計算するヘルパー関数
Action find_best_action(const GameState& state, double dur_w, double fut_w) {
    Action best_action;
    
    vector<int> available_weapons;
    for (int w = 0; w < N_g; ++w) {
        if (state.chest_opened[w] && state.weapon_durability[w] > 0) {
            available_weapons.push_back(w);
        }
    }

    if (available_weapons.empty()) { // 使える武器がない場合は素手
        double best_hand_score = -1.0;
        for (int b = 0; b < N_g; ++b) {
            if (!state.chest_opened[b]) {
                double score = weapon_values_g[b] / state.chest_H[b];
                if (score > best_hand_score) {
                    best_hand_score = score;
                    best_action.b = b;
                }
            }
        }
        best_action.score = best_hand_score;
        return best_action;
    }

    for (int w : available_weapons) {
        for (int b = 0; b < N_g; ++b) {
            if (state.chest_opened[b]) continue;
            
            int damage = A_g[w][b];
            int remaining_H = state.chest_H[b];
            
            double effective_damage = min(damage, remaining_H);
            double durability_bonus = 1.0 + dur_w * state.weapon_durability[w];
            double future_value = (damage >= remaining_H) ? weapon_values_g[b] : 0.0;
            double score = effective_damage * durability_bonus + fut_w * future_value;
            if (damage > remaining_H) score -= (damage - remaining_H) * 0.01;
            
            if (score > best_action.score) {
                best_action.score = score;
                best_action.w = w;
                best_action.b = b;
            }
        }
    }
    return best_action;
}


// ★★★ 1手先読みを実装した新しい貪欲エンジン ★★★
vector<pair<int, int>> run_lookahead_trial(int first_chest, double dur_w, double fut_w) {
    GameState state(H_g, C_g);
    vector<pair<int, int>> actions;
    
    for(int i = 0; i < H_g[first_chest]; ++i) actions.push_back({-1, first_chest});
    state.chest_H[first_chest] = 0;
    state.chest_opened[first_chest] = true;
    state.opened_chests_count = 1;
    
    while (state.opened_chests_count < N_g) {
        const int LOOKAHEAD_K = 3;
        vector<Action> candidates;
        
        // Step 1: 有望な候補手をK個リストアップ
        // (実装をシンプルにするため、ここでは全探索から上位Kを選ぶ)
        vector<int> available_weapons;
        for (int w = 0; w < N_g; ++w) if (state.chest_opened[w] && state.weapon_durability[w] > 0) available_weapons.push_back(w);

        for (int w : available_weapons) {
            for (int b = 0; b < N_g; ++b) {
                if (state.chest_opened[b]) continue;
                 int damage = A_g[w][b]; int remaining_H = state.chest_H[b];
                 double score = min(damage, remaining_H) * (1.0 + dur_w * state.weapon_durability[w]) + ((damage >= remaining_H) ? fut_w * weapon_values_g[b] : 0.0);
                 candidates.push_back({w, b, score});
            }
        }
        sort(candidates.begin(), candidates.end(), [](const Action& a, const Action& b){ return a.score > b.score; });
        if(candidates.size() > LOOKAHEAD_K) candidates.resize(LOOKAHEAD_K);

        // 素手の候補も追加
        Action hand_action = find_best_action(state, dur_w, fut_w);
        if(hand_action.w == -1) candidates.push_back(hand_action);


        // Step 2: 各候補手について1手先を読み、最終的な手を決定
        Action final_action;
        double max_lookahead_score = -1e18;

        for(const auto& candidate_action : candidates) {
            GameState temp_state = state;
            
            // 候補手を適用してみる
            if(candidate_action.w != -1) {
                temp_state.chest_H[candidate_action.b] -= A_g[candidate_action.w][candidate_action.b];
                temp_state.weapon_durability[candidate_action.w]--;
            } else {
                temp_state.chest_H[candidate_action.b]--;
            }

            int temp_opened_count = 0;
            if (temp_state.chest_H[candidate_action.b] <= 0 && !temp_state.chest_opened[candidate_action.b]) {
                 temp_state.chest_opened[candidate_action.b] = true;
                 temp_opened_count = 1;
            }

            // 1手先の盤面で最善手のスコアを計算
            Action next_best_action = find_best_action(temp_state, dur_w, fut_w);
            
            // 総合スコア = 現在の手のスコア + 0.5 * 次の最善手のスコア
            double lookahead_score = candidate_action.score + 0.5 * next_best_action.score;

            if (lookahead_score > max_lookahead_score) {
                max_lookahead_score = lookahead_score;
                final_action = candidate_action;
            }
        }
        
        // Step 3: 最善だった手で、実際の状態を更新
        actions.push_back({final_action.w, final_action.b});
        if(final_action.w != -1) {
            state.chest_H[final_action.b] -= A_g[final_action.w][final_action.b];
            state.weapon_durability[final_action.w]--;
        } else {
            state.chest_H[final_action.b]--;
        }
        if (state.chest_H[final_action.b] <= 0 && !state.chest_opened[final_action.b]) {
            state.chest_opened[final_action.b] = true;
            state.opened_chests_count++;
        }
    }
    return actions;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N_g;
    H_g.resize(N_g); C_g.resize(N_g); A_g.assign(N_g, vector<int>(N_g));
    for (int i = 0; i < N_g; ++i) cin >> H_g[i];
    for (int i = 0; i < N_g; ++i) cin >> C_g[i];
    for (int i = 0; i < N_g; ++i) for (int j = 0; j < N_g; ++j) cin >> A_g[i][j];
    
    precompute_weapon_values();
    
    auto start_time = high_resolution_clock::now();
    const int TIME_LIMIT_MS = 1950;
    
    vector<pair<double, int>> first_chest_candidates_scored;
    for (int i = 0; i < N_g; ++i) {
        first_chest_candidates_scored.push_back({weapon_values_g[i] / H_g[i], i});
    }
    sort(first_chest_candidates_scored.rbegin(), first_chest_candidates_scored.rend());
    
    vector<pair<int, int>> best_solution;
    size_t best_attack_count = numeric_limits<int>::max();
    
    uniform_real_distribution<double> dur_dist(0.01, 0.08);
    uniform_real_distribution<double> fut_dist(0.01, 0.05);
    
    int trial_count = 0;
    while(true) {
        auto current_time = high_resolution_clock::now();
        if (duration_cast<milliseconds>(current_time - start_time).count() >= TIME_LIMIT_MS) break;
        
        int first_chest;
        if(trial_count < 20) { // 序盤は有望な候補を試す
            first_chest = first_chest_candidates_scored[trial_count % first_chest_candidates_scored.size()].second;
        } else { // その後はランダムに
            uniform_int_distribution<int> dist(0, min((int)first_chest_candidates_scored.size() - 1, 25));
            first_chest = first_chest_candidates_scored[dist(rng)].second;
        }
        
        double durability_weight = dur_dist(rng);
        double future_value_weight = fut_dist(rng);
            
        auto solution = run_lookahead_trial(first_chest, durability_weight, future_value_weight);
            
        if (solution.size() < best_attack_count) {
            best_attack_count = solution.size();
            best_solution = solution;
        }
        trial_count++;
    }
    
    for (auto& act : best_solution) {
        cout << act.first << " " << act.second << "\n";
    }

    return 0;
}

私自身はプログラミングがほとんどできず、コードを書いたことがほとんどなかったことに加え、AHCは初参加だったので不安でしたが、楽しむことができました！