AHC35の復習【Atcoder Heuristic Contest】

はじめに

AHC39を受ける前に慣れておこうと思い、過去コンテストを復習しました。スコアは110位くらいで、黄パフォくらいです。

問題

問題概要

穀物の品種改良を目指し、美味しさ、収穫量、病気耐性などの評価項目に優れた穀物を開発している。$N×N$のグリッド状の畑で種を植えて収穫し、新しい種を生成するプロセスを繰り返し、最も価値の高い種を目指そう！

各種にはM個の評価項目があり、種$k$の評価項目ベクトルは$x_k​=(x_{k,0}​, x_{k,1}​,⋯,x_{k,M−1}​)$で与えられ、種$k$の価値$V_k$は$V_k = \sum_{l=0}^{M-1} x_{k,l}$で定義されます。これら前提知識としてを下記の操作を行います。

1. $2N(N-1)$個の種が配られる
2. N×Nの畑に種を植え、残りは破棄
3. 植えた種のうち、上下左右と隣接するマスにある種同士からランダムに新しい評価項目ベクトルを持った種が生成される。この操作で、$2N(N-1)$ 個の新しい種が作られ、次の世代の手持ちの種となる

この操作を$T$回繰り返し、各種の価値の最大値$max(V_0​,V_1​,⋯,V_{2N(N−1)−1​})$の最大化を目指します。

注意点
本問題ではグリッドは$N=6$、評価項目の種類は$M=15$、操作回数$T=10$、配られる種の数は$2N(N-1)=60$で固定されてます。

問題解法の流れ

概要

種を標準得点で評価し、スコアの高いものを選定。畑の良いところに高いスコアの種を植えていき焼きなます。という感じになっています。

種の選び方

各評価項目の値のみで種を選ぶと、種$k$の$l$番目の評価項目$x_{k,l}$が全$k$の中で一番大きいが値は小さい時、無視されてしまう。これを防ぐため、下式の$Z_k$を用いました。なお、下記では$N_x=2N(N-1)$としています。

\begin{align}
&Z_k = \sum_{l=0}^{M-1} Z_{k,l} \\

&Z_{k,l} = \frac{x_{k,l} - \overline{x}}{s}, \quad 
\overline{x} = \frac{\sum_{k=0}^{N_x-1}x_{k,l}}{N_x},\quad
s^2 = \frac{1}{N_x - 1}\sum_{k=0}^{N_x-1} (x_{k,l} - \overline{x})^2
\end{align}

ここで、標準得点が大きいものに注目したほうがより良い種にできるのではないかという考察のもと正の値を3乗し、下記を種の評価としました

\begin{align}
Z_k = \sum_{l=0}^{M-1} 
\begin{cases} 
      Z_{k,l}^3 & (Z_{k,l} > 0) \\
      Z_{k,l} & (Z_{k,l} \leq 0)
\end{cases}
\end{align}

種の植え方

隣接した要素を入れ替えながら焼きなましました。
畑では角:$2$、辺:$3$、角辺以外:$4$ という風にほかの種と隣接します。よって、スコアの高い種から順に角辺以外、辺、角 という順に植え初期解とします。遷移先としては

• 角辺以外同士を入れ替え
• 辺同士を入れ替え
• 角同士を入れ替え

を考え、一つを等確率で選ばせたあと、新しい種の生成をシミュレーションし、スコアを算出します。

コード

main.rs

use proconio::input_interactive;
use rand::seq::SliceRandom;
use rand::Rng;
use std::collections::{HashSet, VecDeque};
use std::time::Instant;

const N: usize = 6;
const M: usize = 15;
const T: usize = 10;
const NX: usize = 60;
const DIJ: [(i32, i32); 4] = [(0, 1), (0, -1), (1, 0), (-1, 0)];
const START_TEMPERATURE: f64 = 50.0;
const END_TEMPERATURE: f64 = 20.0;
const TIME_LIMIT: f64 = 1.99 / T as f64;
const CORNERS: &[(usize, usize)] = &[(0, 0), (5, 0), (0, 5), (5, 5)];
const EDGES: &[(usize, usize)] = &[
    (0, 1),
    (0, 2),
    (0, 3),
    (0, 4),
    (1, 0),
    (2, 0),
    (3, 0),
    (4, 0),
    (1, 5),
    (2, 5),
    (3, 5),
    (4, 5),
    (5, 1),
    (5, 2),
    (5, 3),
    (5, 4),
];

fn calc_score(tanes: &Vec<Vec<i32>>) -> i32 {
    tanes.iter().map(|tane| tane.iter().sum()).max().unwrap()
}

fn zscore_sorted_idx(tanes: &Vec<Vec<i32>>) -> VecDeque<usize> {
    let mut vec_j = vec![Vec::with_capacity(NX); M];
    for i in 0..NX {
        for j in 0..M {
            vec_j[j].push(tanes[i][j] as f64);
        }
    }

    let mut zscores = Vec::with_capacity(M);
    for j in 0..M {
        let data = &vec_j[j];
        let n = data.len() as f64;
        let mean = data.iter().sum::<f64>() / n;
        let variance = data.iter().map(|&x| (x - mean).powi(2)).sum::<f64>() / (n - 1 as f64);
        let stddev = variance.sqrt();
        let zscore = data
            .iter()
            .map(|&x| {
                if stddev == 0.0 {
                    0.0
                } else {
                    let z = (x - mean) / stddev;
                    if z > 0.0 {
                        z.powi(3)
                    } else {
                        z
                    }
                }
            })
            .collect::<Vec<f64>>();
        zscores.push(zscore);
    }

    let mut tot_zscore = vec![0.0; NX];
    for j in 0..M {
        for i in 0..NX {
            tot_zscore[i] += zscores[j][i];
        }
    }
    let mut indices: Vec<usize> = (0..NX).collect();
    indices.sort_by(|&a, &b| tot_zscore[a].partial_cmp(&tot_zscore[b]).unwrap());
    VecDeque::from(indices)
}

fn create_field(z_sorted_idx: &mut VecDeque<usize>) -> Vec<Vec<usize>> {
    let mut field = vec![vec![0; N]; N];
    for i in 0..N {
        for j in 0..N {
            if EDGES.contains(&(i, j)) || CORNERS.contains(&(i, j)) {
                continue;
            }
            field[i][j] = z_sorted_idx.pop_back().unwrap();
        }
    }
    for &(i, j) in EDGES.iter() {
        field[i][j] = z_sorted_idx.pop_back().unwrap();
    }
    for &(i, j) in CORNERS.iter() {
        field[i][j] = z_sorted_idx.pop_back().unwrap();
    }
    field
}

fn swap_field_elements(max_field: &mut Vec<Vec<usize>>, rng: &mut impl Rng) -> Vec<Vec<usize>> {
    let mut swap = Vec::new();
    let q = rand::thread_rng().gen_range(0..3);
    if q == 1 {
        while swap.len() < 2 {
            let i = rng.gen_range(0..N);
            let j = rng.gen_range(0..N);
            if EDGES.contains(&(i, j)) || CORNERS.contains(&(i, j)) {
                continue;
            }
            swap.push((i, j));
        }
    } else if q == 1 {
        swap = EDGES
            .choose_multiple(&mut rand::thread_rng(), 2)
            .cloned()
            .collect();
    } else if q == 2 {
        swap = CORNERS
            .choose_multiple(&mut rand::thread_rng(), 2)
            .cloned()
            .collect();
    }
    let mut swapped_field = max_field.clone();
    if let [(i1, j1), (i2, j2)] = swap.as_slice() {
        let tmp = swapped_field[*i1][*j1];
        swapped_field[*i1][*j1] = swapped_field[*i2][*j2];
        swapped_field[*i2][*j2] = tmp;
    }
    swapped_field
}

fn generate_new_tanes(
    tanes: &Vec<Vec<i32>>,
    field: &Vec<Vec<usize>>,
    rng: &mut impl Rng,
) -> Vec<Vec<i32>> {
    let mut new_tanes = Vec::new();
    let mut visited = HashSet::new();
    for i in 0..N {
        for j in 0..N {
            for &(di, dj) in &DIJ {
                let ni = i as i32 + di;
                let nj = j as i32 + dj;
                if ni < 0 || nj < 0 || ni >= N as i32 || nj >= N as i32 {
                    continue;
                }
                let ni = ni as usize;
                let nj = nj as usize;
                let idx1 = field[i][j];
                let idx2 = field[ni][nj];
                let pair = if idx1 < idx2 {
                    (idx1, idx2)
                } else {
                    (idx2, idx1)
                };
                if visited.contains(&pair) {
                    continue;
                }
                visited.insert(pair);

                let mut new_tane = Vec::with_capacity(M);
                for k in 0..M {
                    let value = if rng.gen_bool(0.5) {
                        tanes[idx1][k]
                    } else {
                        tanes[idx2][k]
                    };
                    new_tane.push(value);
                }
                new_tanes.push(new_tane);
            }
        }
    }
    new_tanes
}

fn main() {
    input_interactive! {
        _: usize, _: usize, _: usize,
    }

    let mut rng = rand::thread_rng();
    for _ in 0..T {
        input_interactive! {
            mut tanes: [[i32; M]; NX],
        }
        let start_time = Instant::now();
        let mut max_score = calc_score(&tanes);
        let mut z_sorted_idx = zscore_sorted_idx(&tanes);
        let mut max_field = create_field(&mut z_sorted_idx);

        while start_time.elapsed().as_secs_f64() < TIME_LIMIT {
            let swapped_field = swap_field_elements(&mut max_field, &mut rng);
            let new_tanes = generate_new_tanes(&tanes, &swapped_field, &mut rng);
            let new_score = calc_score(&new_tanes);
            let dt = start_time.elapsed().as_secs_f64();
            let temp = START_TEMPERATURE + (END_TEMPERATURE - START_TEMPERATURE) * dt / TIME_LIMIT;
            let delta_score = max_score - new_score;
            if f64::exp(delta_score as f64 / temp) > rng.gen::<f64>() {
                max_score = new_score;
                max_field = swapped_field.clone();
            }
        }

        // Output max_field
        for j in 0..N {
            for k in 0..N {
                print!("{} ", max_field[j][k]);
            }
            println!();
        }
    }
}

感想

Rust初心者なのでいろいろ許して・・・。AHC39に参加するにあたってどんなものなのか復習できて楽しかったです。記事を書いていて思ったのですが、遷移しない時cloneしたものを渡していたのですが、逆にswapしなおした方がスマートなのかもしれない。