提出 #65960870

---

ソースコード 拡げる

use proconio::input;
use rand::Rng;
use nalgebra::{DMatrix, DVector};
use itertools::Itertools;

fn calculate_path_probability(path: &Vec<usize>, a: &Vec<Vec<i64>>) -> f64 {
    if path.len() < 2 {
        return 0.0;
    }
    
    // パスの各遷移の確率を計算
    let mut prob = 1.0f64;
    for i in 0..path.len()-1 {
        prob *= (a[path[i]][path[i+1]] as f64) / 100.0f64;
    }
    
    prob
}

fn calculate_path_probability2(path: &Vec<usize>, a: &Vec<Vec<i64>>, first: &Vec<f64>) -> f64 {
    if path.len() < 2 {
        return 0.0;
    }
    
    // パスの各遷移の確率を計算
    let mut prob1 = first[path[0]/2 * 2];
    let mut prob2 = first[path[0]/2 * 2 + 1];
    for i in 0..path.len()-1 {
        let p1 = path[i] / 2 * 2;
        let p2 = p1 + 1;
        let n1 = path[i+1] / 2 * 2;
        let n2 = n1 + 1;

        let next_prob1 = prob1 * (a[p1][n1] as f64) + prob2 * (a[p2][n1] as f64);
        let next_prob2 = prob1 * (a[p1][n2] as f64) + prob2 * (a[p2][n2] as f64);
        prob1 = next_prob1 * 0.01;
        prob2 = next_prob2 * 0.01;
    }
    
    prob1 + prob2
}


fn run_optimization(words_and_scores: &[(String, i64)], n: usize, m: usize, l: usize) -> (f64, Vec<Vec<i64>>, Vec<char>) {
    let mut rng = rand::thread_rng();
    let mut best_score = 0.0f64;
    let mut best_a = vec![];
    let mut best_c = vec![];
    let mut best_paths = vec![];


    for _ in 0..1500 {
        // 頂点に文字を割り当て（各文字2つずつ）
        let mut c = vec!['a'; m];
        for (i, ch) in "aabbccddeeff".chars().enumerate() {
            c[i] = ch;
        }

        // 遷移確率の初期化
        let mut a = vec![vec![0i64; m]; m];
        
        // 各単語のパスを保存
        let mut word_paths = vec![];
        
        // 各単語に対して処理
        for (word, score) in words_and_scores {
            let chars: Vec<char> = word.chars().collect();
            
            // 単語の各文字に対して、使える頂点のインデックスを列挙
            let vertex_candidates: Vec<Vec<usize>> = chars.iter()
                .map(|&ch| {
                    let base_idx = ((ch as u8 - b'a') as usize) * 2;
                    vec![base_idx, base_idx + 1]
                })
                .collect();
            
            // 1つのパスを生成
            let mut path = vec![];
            for candidates in &vertex_candidates {
                let idx = rng.gen_range(0..2);
                path.push(candidates[idx]);
            }
            
            // パスを保存
            word_paths.push(path.clone());
            
            // パスに対して遷移確率を加算
            for i in 0..path.len()-1 {
                let sadd = *score;
                a[path[i]][path[i+1]] += sadd;
            }
            for i in 0..m {
                let sadd = score / (m - 1) as i64;
                if i == path[0]{
                    continue;
                }
                a[i][path[0]] += sadd / 10;
            }
        }
        
        // 確率を正規化（合計が100になるように）
        for i in 0..m {
            let row_sum: i64 = a[i].iter().sum();
            if row_sum > 0 {
                let mut remainders = vec![];
                let mut total = 0i64;
                for j in 0..m {
                    let val = (a[i][j] * 100) / row_sum;
                    a[i][j] = val;
                    total += val;
                    let remainder = (a[i][j] * row_sum * 100) % row_sum;
                    remainders.push((remainder, j));
                }
                
                remainders.sort_by(|a, b| b.0.cmp(&a.0));
                
                for (_, j) in remainders.iter().take((100 - total) as usize) {
                    a[i][*j] += 1;
                }
            } else {
                let base = 100i64 / m as i64;
                let remainder = 100i64 % m as i64;
                
                for j in 0..m {
                    a[i][j] = base;
                }
                
                for j in 0..remainder as usize {
                    a[i][j] += 1;
                }
            }
        }

        // 初期の確率を計算
        let mut first = vec![1.0 / (m as f64); m];
        for _t in 0..5 {
            let mut next_first = vec![0.0; m];
            for i in 0..m {
                for j in 0..m {
                    next_first[j] += first[i] * (a[i][j] as f64) / 100.0;
                }
            }
            first = next_first;
        }

        // この遷移確率での期待スコアを計算
        let mut total_score = 0.0f64;
        for ((_, score), path) in words_and_scores.iter().zip(word_paths.iter()) {
            let path_prob = calculate_path_probability(&path, &a);
            let trials = (l as f64) * first[path[0]] * 2.0;
            let success_prob = 1.0f64 - (1.0f64 - path_prob).powf(trials);
            total_score += success_prob * (*score as f64);
        }

        if total_score > best_score {
            best_score = total_score;
            best_a = a.clone();
            best_c = c.clone();
            best_paths = word_paths.clone();
        }
    }


    let mut current_score = best_score;
    let mut current_paths = best_paths.clone();
    let mut current_a = best_a.clone();
    
    // 焼きなましのパラメータ
    let initial_temp = 2000.0;
    let final_temp = 0.1;
    let iterations = 20000;
    
    eprintln!("Starting simulated annealing with initial score: {}", current_score);
    
    for iter in 0..iterations {
        // 温度を徐々に下げる（指数冷却）
        let progress = iter as f64 / iterations as f64;
        let temp = initial_temp * f64::powf(final_temp / initial_temp, progress);
        
        // ランダムに1つの単語を選ぶ
        let word_idx = rng.gen_range(0..n);
        let path = &current_paths[word_idx];
        
        // ランダムに1つの位置を選ぶ
        let pos = rng.gen_range(0..path.len());
        
        // その文字に対応する2つの頂点のうち、現在使っていない方を選ぶ
        let ch = words_and_scores[word_idx].0.chars().nth(pos).unwrap();
        let base_idx = ((ch as u8 - b'a') as usize) * 2;
        let new_vertex = if path[pos] == base_idx { base_idx + 1 } else { base_idx };
        
        // パスを変更して評価
        let mut new_paths = current_paths.clone();
        new_paths[word_idx][pos] = new_vertex;
        
        // 新しい遷移確率行列を生成
        let mut new_a = vec![vec![0i64; m]; m];
        for ((_, score), path) in words_and_scores.iter().zip(new_paths.iter()) {
            for i in 0..path.len()-1 {
                let sadd = score;
                new_a[path[i]][path[i+1]] += sadd;
            }
            for i in 0..m {
                let sadd = score / (m - 1) as i64;
                if i == path[0]{
                    continue;
                }
                new_a[i][path[0]] += sadd / 10;
            }
        }
        
        // 確率を正規化
        for i in 0..m {
            let row_sum: i64 = new_a[i].iter().sum();
            if row_sum > 0 {
                let mut remainders = vec![];
                let mut total = 0i64;
                for j in 0..m {
                    let val = (new_a[i][j] * 100) / row_sum;
                    new_a[i][j] = val;
                    total += val;
                    let remainder = (new_a[i][j] * row_sum * 100) % row_sum;
                    remainders.push((remainder, j));
                }
                
                remainders.sort_by(|a, b| b.0.cmp(&a.0));
                
                for (_, j) in remainders.iter().take((100 - total) as usize) {
                    new_a[i][*j] += 1;
                }
            } else {
                let base = 100i64 / m as i64;
                let remainder = 100i64 % m as i64;
                
                for j in 0..m {
                    new_a[i][j] = base;
                }
                
                for j in 0..remainder as usize {
                    new_a[i][j] += 1;
                }
            }
        }

        // 初期の確率を計算
        let mut first = vec![1.0 / (m as f64); m];
        for _t in 0..5 {
            let mut next_first = vec![0.0; m];
            for i in 0..m {
                for j in 0..m {
                    next_first[j] += first[i] * (new_a[i][j] as f64) / 100.0;
                }
            }
            first = next_first;
        }

        // 新しい遷移確率での期待スコアを計算
        let mut new_score = 0.0f64;
        for ((_, score), path) in words_and_scores.iter().zip(new_paths.iter()) {
            let path_prob = calculate_path_probability(&path, &new_a);
            let trials = (l as f64) * first[path[0]] * 2.0;
            let success_prob = 1.0f64 - (1.0f64 - path_prob).powf(trials);
            new_score += success_prob * (*score as f64);
        }

        // スコアの差分
        let score_diff = new_score - current_score;
        
        // 焼きなましの採用判定
        let accept = if score_diff > 0.0 {
            // 改善する場合は常に採用
            true
        } else {
            // 悪化する場合は確率的に採用
            let probability = f64::exp(score_diff / temp);
            rng.gen::<f64>() < probability
        };
        
        if accept {
            current_score = new_score;
            current_paths = new_paths;
            current_a = new_a.clone();  // ここでcloneを追加
            
            // 過去最高スコアの更新
            if current_score > best_score {
                best_score = current_score;
                best_paths = current_paths.clone();
                best_a = current_a.clone();
                
                if iter % 500 == 0 {
                    eprintln!("Iteration {}: New best score = {}, temp = {}", iter, best_score, temp);
                }
            }
        }
        
        // 定期的に温度を表示
        if iter % 1000 == 0 {
            eprintln!("Iteration {}: temp = {}, current_score = {}, best_score = {}", 
                     iter, temp, current_score, best_score);
        }
    }
    
    eprintln!("Simulated annealing completed. Best score: {}", best_score);

    best_score = 0.0f64;

    // 確率行列の微調整
    for _ in 0..10000 {
        // ランダムに行を選ぶ
        let i = rng.gen_range(0..m);
        
        // その行の非ゼロ要素のインデックスを集める
        let nonzero_indices: Vec<usize> = (0..m)
            .filter(|&j| best_a[i][j] > 0)
            .collect();
            
        if nonzero_indices.len() < 2 {
            continue;  // 非ゼロ要素が2未満なら次の試行へ
        }
        
        // 異なる2つの非ゼロ要素をランダムに選ぶ
        let idx1 = rng.gen_range(0..nonzero_indices.len());
        let mut idx2 = rng.gen_range(0..nonzero_indices.len());
        while idx2 == idx1 {
            idx2 = rng.gen_range(0..nonzero_indices.len());
        }
        let j1 = nonzero_indices[idx1];
        let j2 = nonzero_indices[idx2];
        
        // 確率を1移動
        let mut new_a = best_a.clone();
        new_a[i][j1] += 1;
        new_a[i][j2] -= 1;
        
        // 初期の確率を計算
        let mut first = vec![1.0 / (m as f64); m];
        for _t in 0..5 {
            let mut next_first = vec![0.0; m];
            for i in 0..m {
                for j in 0..m {
                    next_first[j] += first[i] * (new_a[i][j] as f64) / 100.0;
                }
            }
            first = next_first;
        }

        // スコアを計算
        let mut new_score = 0.0f64;
        for ((_, score), path) in words_and_scores.iter().zip(&best_paths) {
            let path_prob = calculate_path_probability2(&path, &new_a, &first);
            let trials = (l as f64);
            let success_prob = 1.0f64 - (1.0f64 - path_prob).powf(trials);
            new_score += success_prob * (*score as f64);
        }

        if new_score > best_score {
            best_score = new_score;
            best_a = new_a;  // 直接best_aを更新
        }
    }

    (best_score, best_a, best_c)
}


fn main() {
    input! {
        n: usize,
        m: usize,
        l: usize,
        words_and_scores: [(String, i64); n]
    }

    let mut best_score = 0.0f64;
    let mut best_a = vec![];
    let mut best_c = vec![];

    for i in 0..10{
        eprintln!("Starting run {}", i + 1);
        let (score, a, c) = run_optimization(&words_and_scores, n, m, l);
        eprintln!("Run {} completed with score: {}", i + 1, score);
        
        if score > best_score {
            best_score = score;
            best_a = a;
            best_c = c;
            eprintln!("New best score: {}", best_score);
        }
    }

    eprintln!("Best score after initial optimization: {}", best_score);

    // 最良の結果を出力
    for i in 0..m {
        print!("{}", best_c[i]);
        for j in 0..m {
            print!(" {}", best_a[i][j]);
        }
        println!();
    }
}

提出情報

コンパイルエラー

warning: unused imports: `DMatrix`, `DVector`
 --> src/main.rs:3:16
  |
3 | use nalgebra::{DMatrix, DVector};
  |                ^^^^^^^  ^^^^^^^
  |
  = note: `#[warn(unused_imports)]` on by default

warning: unused import: `itertools::Itertools`
 --> src/main.rs:4:5
  |
4 | use itertools::Itertools;
  |     ^^^^^^^^^^^^^^^^^^^^

warning: unnecessary parentheses around assigned value
   --> src/main.rs:351:26
    |
351 |             let trials = (l as f64);
    |                          ^        ^
    |
    = note: `#[warn(unused_parens)]` on by default
help: remove these parentheses
    |
351 -             let trials = (l as f64);
351 +             let trials = l as f64;
    |

warning: value assigned to `current_a` is never read
   --> src/main.rs:166:13
    |
166 |     let mut current_a = best_a.clone();
    |             ^^^^^^^^^
    |
    = help: maybe it is overwritten before being read?
    = note: `#[warn(unused_assignments)]` on by default

ジャッジ結果