Submission #18695232

---

Source Code Expand

use proconio::input;
use std::collections::VecDeque;
use rand::prelude::*;

struct Input {
    each_cost: i32,
    profits: Vec<Vec<i32>>
}

impl Input {
    fn new(cost: i32, p: Vec<Vec<i32>>) -> Input {
        Input {
            each_cost: cost,
            profits: p
        }
    }
}

struct Mining {
    row: usize,
    col: usize
}

impl Mining {
    fn new(r: usize, c: usize) -> Mining {
        Mining {
            row: r,
            col: c
        }
    }
}

fn main() {
    get_time();

    input! {
        each_cost:i32,
        profits:[[i32;50];50]
    }

    let input = Input::new(each_cost, profits);
    let results = annealing(&input);
    
    println!("{}", results.len());
    for r in results {
        println!("{} {}", r.row, r.col);
    }
}


fn annealing(input: &Input) -> Vec<Mining> {
    let mut mining = vec![vec![true;50];50];
    const TIME_LIMIT: f64 = 1.98;
    const TEMP0: f64 = 20.0;
    const TEMP1: f64 = 0.0;

    let (mut best_score, mut best_out) = calc_score(&mining, &input);
    let mut old_score = best_score;
    let mut rng = rand_pcg::Pcg64Mcg::new(998244353);
    let mut cnt = 0;
    let mut t = get_time() / TIME_LIMIT;
    
    while t < 1.0 {
        cnt += 1;
        let temp = TEMP0.powf(1.0 - t) * TEMP1.powf(t);
        let h = rng.gen_range(1, 6);
        let w = rng.gen_range(1, 6);
        let r = rng.gen_range(0, 50 + 1 - h);
        let c = rng.gen_range(0, 50 + 1 - w);
        
        let mut last = vec![vec![false; w];h];
        let mut mined_count = 0;

        for dr in 0..h {
            for dc in 0..w {
                if mining[r + dr][c + dc] {
                    mined_count += 1;
                    last[dr][dc] = mining[r + dr][c + dc];
                }
            }
        }

        let next = mined_count <= w * h / 2;

        for dr in 0..h {
            for dc in 0..w {
                mining[r + dr][c + dc] = next;
            }
        }

        let (score, out) = calc_score(&mining, &input);

        if score >= old_score || rng.gen_bool(f64::exp((score - old_score) as f64 / temp)) {
            old_score = score;
            //dbg!(score);
        } else {
            for dr in 0..h {
                for dc in 0..w {
                    mining[r + dr][c + dc] = last[dr][dc];
                }
            }
        }

        if score > best_score {
            best_score = score;
            best_out = out;
        }

        t = get_time() / TIME_LIMIT;
    }

    let time = get_time();
    dbg!(cnt);
    dbg!(best_score);
    dbg!(time);

    return best_out;
}

fn calc_score(mining: &Vec<Vec<bool>>, input: &Input) -> (i32, Vec<Mining>) {
    let mut score = 0;
    let mut queue = VecDeque::new();
    let mut seen = vec![vec![false;50];50];
    let mut result = vec![];

    for row in 0..50 {
        if mining[row][0] {
            queue.push_back(Mining::new(row, 0));
        }
        if mining[row][49] {
            queue.push_back(Mining::new(row, 49));
        }
    }

    for col in 1..49 {
        if mining[0][col] {
            queue.push_back(Mining::new(0, col));
        }
        if mining[49][col] {
            queue.push_back(Mining::new(49, col));
        }
    }

    while !queue.is_empty() {
        let current = queue.pop_front().unwrap();
        let row = current.row;
        let col = current.col;
        let mut count = 0;

        if seen[row][col] {
            continue;
        }

        seen[row][col] = true;
        result.push(current);

        if row == 0 || (seen[row - 1][col] && mining[row - 1][col]) {
            count += 1;
        }

        if row == 49 || (seen[row + 1][col] && mining[row + 1][col]) {
            count += 1;
        }

        if col == 0 || (seen[row][col - 1] && mining[row][col - 1]) {
            count += 1;
        }

        if col == 49 || (seen[row][col + 1] && mining[row][col + 1]) {
            count += 1;
        }

        score += input.profits[row][col] - input.each_cost / count;

        if row != 0 && (!seen[row - 1][col] && mining[row - 1][col]) {
            queue.push_back(Mining::new(row - 1, col));
        }

        if row != 49 && (!seen[row + 1][col] && mining[row + 1][col]) {
            queue.push_back(Mining::new(row + 1, col));
        }

        if col != 0 && (!seen[row][col - 1] && mining[row][col - 1]) {
            queue.push_back(Mining::new(row, col - 1));
        }

        if col != 49 && (!seen[row][col + 1] && mining[row][col + 1]) {
            queue.push_back(Mining::new(row, col + 1));
        }
    }

    return (score, result);
}

fn get_time() -> f64 {
	static mut STIME: f64 = -1.0;
	let t = std::time::SystemTime::now().duration_since(std::time::UNIX_EPOCH).unwrap();
	let ms = t.as_secs() as f64 + t.subsec_nanos() as f64 * 1e-9;
	unsafe {
		if STIME < 0.0 {
			STIME = ms;
		}
		ms - STIME
	}
}

Submission Info

Judge Result