Submission #71726703

---

Source Code Expand

#include <iostream>
#include <vector>
#include <cmath>
#include <random>
#include <algorithm>
#include <chrono>
#include <utility>

using namespace std;
using namespace chrono;

// 設定
const double TIME_LIMIT = 1.95;
const double START_TEMP = 500.0;
const double END_TEMP = 1.0;

// グローバル乱数生成器
mt19937 rng;

double simulate(const vector<pair<int,int>>& action_queue, int N, int L, int T, int K, 
                const vector<int>& A, const vector<vector<long long>>& C) {
    // 状態初期化
    vector<vector<long long>> B(L, vector<long long>(N, 1));
    vector<vector<int>> P(L, vector<int>(N, 0));
    long long apples = K;
    
    int queue_idx = 0;
    int queue_len = action_queue.size();
    
    // シミュレーションループ
    for (int t = 0; t < T; t++) {
        // 1. 購入行動
        if (queue_idx < queue_len) {
            int target_lvl = action_queue[queue_idx].first;
            int target_id = action_queue[queue_idx].second;
            int current_p = P[target_lvl][target_id];
            long long cost = C[target_lvl][target_id] * (current_p + 1);
            
            if (apples >= cost) {
                apples -= cost;
                P[target_lvl][target_id]++;
                queue_idx++;
            }
        }
        
        // 2. 生産処理
        // Level 0 -> Apples
        long long daily_apples = 0;
        for (int j = 0; j < N; j++) {
            daily_apples += (long long)A[j] * B[0][j] * P[0][j];
        }
        apples += daily_apples;
        
        // Level 1..3 -> Lower Level Machines
        for (int i = 1; i < L; i++) {
            for (int j = 0; j < N; j++) {
                long long prod = B[i][j] * P[i][j];
                if (prod > 0) {
                    B[i-1][j] += prod;
                }
            }
        }
    }
    
    // 最終スコア計算 (対数スコール)
    if (apples <= 0) return -1e18;
    
    return 100000.0 * log2((double)apples);
}

// 特定のIDに集中する戦略
vector<pair<int,int>> greedy_focus_id(int N, int L, int T, int K,
                                      const vector<int>& A, 
                                      const vector<vector<long long>>& C,
                                      int target_id) {
    vector<vector<long long>> B(L, vector<long long>(N, 1));
    vector<vector<int>> P(L, vector<int>(N, 0));
    long long current_apples = K;
    vector<pair<int,int>> action_queue;
    
    for (int t = 0; t < T; t++) {
        int remaining = T - t;
        pair<int,int> best_action = {-1, -1};
        double best_value = -1.0;
        
        // target_idを最優先で探索
        for (int i = 0; i < L; i++) {
            int j = target_id;
            
            long long cost = C[i][j] * (P[i][j] + 1);
            if (cost > current_apples) continue;
            
            // target_idの評価
            double gain = 0;
            if (i == 0) {
                gain = (double)A[j] * B[0][j] * remaining;
            } else if (i == 1) {
                double total_gain = 0;
                long long temp_b = B[0][j];
                long long production = B[1][j];
                for (int ft = 0; ft < remaining; ft++) {
                    temp_b += production;
                    total_gain += (double)A[j] * production * P[0][j] * (remaining - ft - 1);
                }
                gain = total_gain;
            } else if (i == 2) {
                double factor = (double)remaining * remaining * remaining / 6.0;
                gain = (double)A[j] * B[2][j] * factor * 0.1;
            } else if (i == 3) {
                double factor = (double)remaining * remaining * remaining * remaining / 24.0;
                gain = (double)A[j] * B[3][j] * factor * 0.01;
            }
            
            double value = gain / cost;
            
            if (value > best_value) {
                best_value = value;
                best_action = {i, j};
            }
        }
        
        // target_idで買えるものがなければ、他のIDも検討
        if (best_action.first == -1) {
            for (int i = 0; i < L; i++) {
                for (int j = 0; j < N; j++) {
                    if (j == target_id) continue;  // target_idは既にチェック済み
                    
                    long long cost = C[i][j] * (P[i][j] + 1);
                    if (cost > current_apples) continue;
                    
                    double gain = 0;
                    if (i == 0) {
                        gain = (double)A[j] * B[0][j] * remaining;
                    } else if (i == 1) {
                        double total_gain = 0;
                        long long temp_b = B[0][j];
                        long long production = B[1][j];
                        for (int ft = 0; ft < remaining; ft++) {
                            temp_b += production;
                            total_gain += (double)A[j] * production * P[0][j] * (remaining - ft - 1);
                        }
                        gain = total_gain;
                    } else if (i == 2) {
                        double factor = (double)remaining * remaining * remaining / 6.0;
                        gain = (double)A[j] * B[2][j] * factor * 0.1;
                    } else if (i == 3) {
                        double factor = (double)remaining * remaining * remaining * remaining / 24.0;
                        gain = (double)A[j] * B[3][j] * factor * 0.01;
                    }
                    
                    double value = gain / cost;
                    // 他のIDは評価を下げる
                    value *= 0.1;
                    
                    if (value > best_value) {
                        best_value = value;
                        best_action = {i, j};
                    }
                }
            }
        }
        
        if (best_action.first != -1) {
            int i = best_action.first;
            int j = best_action.second;
            long long cost = C[i][j] * (P[i][j] + 1);
            current_apples -= cost;
            P[i][j]++;
            action_queue.push_back(best_action);
        }
        
        // ターン処理
        for (int j = 0; j < N; j++) {
            current_apples += (long long)A[j] * B[0][j] * P[0][j];
        }
        for (int i = 1; i < L; i++) {
            for (int j = 0; j < N; j++) {
                B[i-1][j] += B[i][j] * P[i][j];
            }
        }
    }
    
    return action_queue;
}

double exponential_cooling(double start_time, double current_time, double time_limit) {
    double progress = (current_time - start_time) / time_limit;
    return START_TEMP * pow(END_TEMP / START_TEMP, progress);
}

void solve() {
    // 入力
    int N, L, T, K;
    cin >> N >> L >> T >> K;
    
    vector<int> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    
    vector<vector<long long>> C(L, vector<long long>(N));
    for (int i = 0; i < L; i++) {
        for (int j = 0; j < N; j++) {
            cin >> C[i][j];
        }
    }
    
    auto start_time = high_resolution_clock::now();
    
    vector<pair<int,int>> best_queue;
    double best_score = -1e18;
    
    for (int target_id = 0; target_id < N; target_id++) {
        auto queue = greedy_focus_id(N, L, T, K, A, C, target_id);
        double score = simulate(queue, N, L, T, K, A, C);
        
        if (score > best_score) {
            best_score = score;
            best_queue = queue;
        }
        
        // デバッグ出力（提出時はコメントアウト）
        // cerr << "ID" << target_id << " focused score: " << score << endl;
    }
    
    // cerr << "Best initial score: " << best_score << endl;
    
    auto current_queue = best_queue;
    double current_score = best_score;
    
    
    int iterations = 0;
    double temp = START_TEMP;
    vector<int> mutation_success(6, 0);
    vector<int> mutation_attempt(6, 0);
    
    uniform_real_distribution<double> uniform(0.0, 1.0);
    
    // 焼きなまし法ループ
    while (true) {
        iterations++;
        if ((iterations & 127) == 0) {
            auto now = high_resolution_clock::now();
            double elapsed = duration<double>(now - start_time).count();
            if (elapsed > TIME_LIMIT) break;
            temp = exponential_cooling(0, elapsed, TIME_LIMIT);
        }
        
        // 適応的な近傍選択
        vector<double> weights(6);
        for (int i = 0; i < 6; i++) {
            if (mutation_attempt[i] > 10) {
                double success_rate = (double)mutation_success[i] / mutation_attempt[i];
                weights[i] = success_rate + 0.1;
            } else {
                weights[i] = 1.0;
            }
        }
        double total_weight = 0;
        for (double w : weights) total_weight += w;
        for (double& w : weights) w /= total_weight;
        
        double rand_val = uniform(rng);
        int mutation_type = 0;
        double cumsum = 0;
        for (int i = 0; i < 6; i++) {
            cumsum += weights[i];
            if (rand_val < cumsum) {
                mutation_type = i;
                break;
            }
        }
        
        mutation_attempt[mutation_type]++;
        
        // 変異の作成
        auto new_queue = current_queue;
        
        if (mutation_type == 0 && !new_queue.empty()) {
            // 削除
            uniform_int_distribution<int> dist(0, new_queue.size() - 1);
            int idx = dist(rng);
            new_queue.erase(new_queue.begin() + idx);
            
        } else if (mutation_type == 1) {
            // 挿入
            uniform_int_distribution<int> dist_idx(0, new_queue.size());
            uniform_int_distribution<int> dist_lvl(0, L - 1);
            uniform_int_distribution<int> dist_id(0, N - 1);
            int idx = dist_idx(rng);
            int lvl = dist_lvl(rng);
            int mid = dist_id(rng);
            new_queue.insert(new_queue.begin() + idx, {lvl, mid});
            
        } else if (mutation_type == 2 && new_queue.size() > 1) {
            // 交換
            uniform_int_distribution<int> dist(0, new_queue.size() - 1);
            int idx1 = dist(rng);
            int idx2;
            if (uniform(rng) < 0.7 && new_queue.size() > 1) {
                idx2 = idx1 + (uniform(rng) < 0.5 && idx1 < (int)new_queue.size() - 1 ? 1 : -1);
                idx2 = max(0, min((int)new_queue.size() - 1, idx2));
            } else {
                idx2 = dist(rng);
            }
            swap(new_queue[idx1], new_queue[idx2]);
            
        } else if (mutation_type == 3 && !new_queue.empty()) {
            // 要素の変更
            uniform_int_distribution<int> dist_idx(0, new_queue.size() - 1);
            int idx = dist_idx(rng);
            if (uniform(rng) < 0.5) {
                uniform_int_distribution<int> dist_lvl(0, L - 1);
                new_queue[idx].first = dist_lvl(rng);
            } else {
                uniform_int_distribution<int> dist_id(0, N - 1);
                new_queue[idx].second = dist_id(rng);
            }
            
        } else if (mutation_type == 4 && new_queue.size() > 2) {
            // 区間反転
            uniform_int_distribution<int> dist1(0, new_queue.size() - 2);
            int idx1 = dist1(rng);
            uniform_int_distribution<int> dist2(idx1 + 1, new_queue.size());
            int idx2 = dist2(rng);
            reverse(new_queue.begin() + idx1, new_queue.begin() + idx2);
            
        } else if (mutation_type == 5 && !new_queue.empty()) {
            // 複数要素の削除
            uniform_int_distribution<int> dist_num(1, min(5, (int)new_queue.size()));
            int num_delete = dist_num(rng);
            for (int i = 0; i < num_delete && !new_queue.empty(); i++) {
                uniform_int_distribution<int> dist_idx(0, new_queue.size() - 1);
                int idx = dist_idx(rng);
                new_queue.erase(new_queue.begin() + idx);
            }
        }
        
        // 評価
        double new_score = simulate(new_queue, N, L, T, K, A, C);
        
        // 遷移判定
        double delta = new_score - current_score;
        bool accept = false;
        
        if (delta >= 0) {
            accept = true;
        } else {
            double prob = exp(delta / temp);
            accept = (uniform(rng) < prob);
        }
        
        if (accept) {
            current_queue = new_queue;
            current_score = new_score;
            
            if (new_score > best_score) {
                best_score = new_score;
                best_queue = new_queue;
                mutation_success[mutation_type]++;
            }
        }
    }
    
    // 結果出力
    vector<vector<long long>> B(L, vector<long long>(N, 1));
    vector<vector<int>> P(L, vector<int>(N, 0));
    long long apples = K;
    int queue_idx = 0;
    
    for (int t = 0; t < T; t++) {
        string action_str = "-1";
        
        if (queue_idx < (int)best_queue.size()) {
            int target_lvl = best_queue[queue_idx].first;
            int target_id = best_queue[queue_idx].second;
            long long cost = C[target_lvl][target_id] * (P[target_lvl][target_id] + 1);
            
            if (apples >= cost) {
                apples -= cost;
                P[target_lvl][target_id]++;
                queue_idx++;
                action_str = to_string(target_lvl) + " " + to_string(target_id);
            }
        }
        
        cout << action_str << "\n";
        
        // 生産
        long long daily_apples = 0;
        for (int j = 0; j < N; j++) {
            daily_apples += (long long)A[j] * B[0][j] * P[0][j];
        }
        apples += daily_apples;
        
        for (int i = 1; i < L; i++) {
            for (int j = 0; j < N; j++) {
                long long prod = B[i][j] * P[i][j];
                if (prod > 0) {
                    B[i-1][j] += prod;
                }
            }
        }
    }
    
    cout.flush();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    // 乱数生成器の初期化
    rng.seed(chrono::steady_clock::now().time_since_epoch().count());
    
    solve();
    
    return 0;
}

Submission Info

Judge Result