提出 #32967760

---

ソースコード 拡げる

use std::{fmt::Display, time::Instant};

use itertools::izip;
#[allow(unused_imports)]
use proconio::*;
#[allow(unused_imports)]
use rand::prelude::*;

#[allow(unused_macros)]
macro_rules! chmin {
    ($base:expr, $($cmps:expr),+ $(,)*) => {{
        let cmp_min = min!($($cmps),+);
        if $base > cmp_min {
            $base = cmp_min;
            true
        } else {
            false
        }
    }};
}

#[allow(unused_macros)]
macro_rules! chmax {
    ($base:expr, $($cmps:expr),+ $(,)*) => {{
        let cmp_max = max!($($cmps),+);
        if $base < cmp_max {
            $base = cmp_max;
            true
        } else {
            false
        }
    }};
}

#[allow(unused_macros)]
macro_rules! min {
    ($a:expr $(,)*) => {{
        $a
    }};
    ($a:expr, $b:expr $(,)*) => {{
        std::cmp::min($a, $b)
    }};
    ($a:expr, $($rest:expr),+ $(,)*) => {{
        std::cmp::min($a, min!($($rest),+))
    }};
}

#[allow(unused_macros)]
macro_rules! max {
    ($a:expr $(,)*) => {{
        $a
    }};
    ($a:expr, $b:expr $(,)*) => {{
        std::cmp::max($a, $b)
    }};
    ($a:expr, $($rest:expr),+ $(,)*) => {{
        std::cmp::max($a, max!($($rest),+))
    }};
}

#[allow(unused_macros)]
macro_rules! mat {
    ($e:expr; $d:expr) => { vec![$e; $d] };
    ($e:expr; $d:expr $(; $ds:expr)+) => { vec![mat![$e $(; $ds)*]; $d] };
}

const RADIUS: i64 = 10000;
const COUNT_MIN: usize = 1;
const COUNT_MAX: usize = 11;

#[derive(Debug, Clone)]
struct Input {
    n: usize,
    k: usize,
    counts: Vec<i32>,
    count_sum: i32,
    points: Vec<Point>,
    since: Instant,
}

#[derive(Debug, Clone, Copy)]
struct Point {
    x: i64,
    y: i64,
}

impl Point {
    fn new(x: i64, y: i64) -> Self {
        Self { x, y }
    }
}

#[derive(Debug, Clone)]
struct State {
    /// 縦方向カットのx座標
    v_cut: Vec<i64>,
    /// 横方向カットのy座標
    h_cut: Vec<i64>,
    cut_count_v: usize,
    box_count_v: usize,
    cut_count_h: usize,
    box_count_h: usize,
    boxes: Vec<Vec<Vec<Point>>>,
    counts: Vec<i32>,
}

impl State {
    fn init(input: &Input) -> Self {
        let mut v_cut = vec![];
        let mut h_cut = vec![];

        let mut cut_count_v = 1;
        let cut_count_h = 7;

        while cut_count_v * cut_count_h < input.count_sum as usize {
            cut_count_v += 1;
        }

        // 適当に余裕を持たせる
        cut_count_v += 5;
        chmin!(cut_count_v, input.k - cut_count_h);
        let box_count_v = cut_count_v + 1;
        let box_count_h = cut_count_h + 1;
        eprintln!("{}", box_count_v);

        let min = -RADIUS - 1;
        let max = RADIUS + 1;

        for i in 0..=box_count_v {
            let x = (max - min) * i as i64 / box_count_v as i64 + min;
            v_cut.push(x);
        }

        for i in 0..=box_count_h {
            let x = (max - min) * i as i64 / box_count_h as i64 + min;
            h_cut.push(x);
        }

        let (boxes, counts) =
            State::count_all_inner(&v_cut, &h_cut, box_count_v, box_count_h, input);
        let state = State {
            v_cut,
            h_cut,
            cut_count_v,
            box_count_v,
            cut_count_h,
            box_count_h,
            boxes,
            counts,
        };

        state
    }

    fn count_all_inner(
        v_cut: &[i64],
        h_cut: &[i64],
        box_count_v: usize,
        box_count_h: usize,
        input: &Input,
    ) -> (Vec<Vec<Vec<Point>>>, Vec<i32>) {
        let mut boxes = mat![vec![]; box_count_v * 2 + 1; box_count_h * 2 + 1];

        for point in input.points.iter() {
            let i = match v_cut[1..(v_cut.len() - 1)].binary_search(&point.x) {
                Ok(i) => 2 * i + 1,
                Err(i) => 2 * i,
            };

            let j = match h_cut[1..(h_cut.len() - 1)].binary_search(&point.y) {
                Ok(j) => 2 * j + 1,
                Err(j) => 2 * j,
            };

            boxes[i][j].push(*point);
        }

        let mut counts = vec![0; input.points.len() + 1];

        for i in 0..box_count_v {
            let i = 2 * i;
            for j in 0..box_count_h {
                let j = 2 * j;
                counts[boxes[i][j].len()] += 1;
            }
        }

        (boxes, counts)
    }

    fn calc_score(&self, input: &Input) -> i64 {
        let mut count = 0;

        for (&c0, &c1) in izip!(
            self.counts[COUNT_MIN..COUNT_MAX].iter(),
            input.counts.iter()
        ) {
            count += c0.min(c1);
        }

        (1e6 * count as f64 / input.count_sum as f64).round() as i64
    }

    fn calc_annealing_score(&self, input: &Input, time: f64) -> i64 {
        let mut score = 0;
        let mut c0 = [0; 12];
        let mut c1 = [0; 15];
        for (i, c) in input.counts.iter().enumerate() {
            c0[i + 1] = *c;
        }

        for (i, c) in self.counts[..c1.len()].iter().enumerate() {
            c1[i] = *c;
        }
        c1[14] = std::i32::MAX;

        let mut j = 1;

        for i in 0..c0.len() {
            while c0[i] > 0 {
                while c1[j] == 0 {
                    j += 1;
                }

                let c = c0[i].min(c1[j]);
                c0[i] -= c;
                c1[j] -= c;
                let diff = i as i64 - j as i64;
                score -= diff * diff * c as i64;
            }
        }

        let score = score as f64 * 1000.0 * (1.0 - time);

        score as i64 + self.calc_score(input)
    }

    fn move_lower_v(&mut self, index: usize, diff: i64) {
        self.sub_count_partial_v(index - 1);
        self.sub_count_partial_v(index);
        let line = index * 2 - 1;
        let new_x = self.v_cut[index] + diff;
        let (p, n) = self.boxes.split_at_mut(line);
        let prev = p.last_mut().unwrap();
        let (p, n) = n.split_at_mut(1);
        let line = p.first_mut().unwrap();
        let next = n.first_mut().unwrap();

        // まず線上
        for j in 0..line.len() {
            for p in line[j].iter() {
                next[j].push(*p);
            }

            line[j].clear();
        }

        // 次
        for j in 0..prev.len() {
            for k in (0..prev[j].len()).rev() {
                if prev[j][k].x > new_x {
                    next[j].push(prev[j].swap_remove(k));
                } else if prev[j][k].x == new_x {
                    line[j].push(prev[j].swap_remove(k));
                }
            }
        }

        self.add_count_partial_v(index - 1);
        self.add_count_partial_v(index);
    }

    fn move_upper_v(&mut self, index: usize, diff: i64) {
        self.sub_count_partial_v(index - 1);
        self.sub_count_partial_v(index);
        let line = index * 2 - 1;
        let new_x = self.v_cut[index] + diff;
        let (p, n) = self.boxes.split_at_mut(line);
        let prev = p.last_mut().unwrap();
        let (p, n) = n.split_at_mut(1);
        let line = p.first_mut().unwrap();
        let next = n.first_mut().unwrap();

        // まず線上
        for j in 0..line.len() {
            for p in line[j].iter() {
                prev[j].push(*p);
            }

            line[j].clear();
        }

        // 次
        for j in 0..next.len() {
            for k in (0..next[j].len()).rev() {
                if next[j][k].x < new_x {
                    prev[j].push(next[j].swap_remove(k));
                } else if next[j][k].x == new_x {
                    line[j].push(next[j].swap_remove(k));
                }
            }
        }

        self.add_count_partial_v(index - 1);
        self.add_count_partial_v(index);
    }

    fn move_lower_h(&mut self, index: usize, diff: i64) {
        self.sub_count_partial_h(index - 1);
        self.sub_count_partial_h(index);
        let line = index * 2 - 1;
        let new_y = self.h_cut[index] + diff;

        // まず線上
        for i in 0..self.boxes.len() {
            let b = &mut self.boxes[i];
            let (p, n) = b.split_at_mut(line + 1);
            let line = p.last_mut().unwrap();
            let next = n.first_mut().unwrap();

            for p in line.iter() {
                next.push(*p);
            }

            line.clear();
        }

        // 次
        for i in 0..self.boxes.len() {
            let b = &mut self.boxes[i];
            let (p, n) = b.split_at_mut(line);
            let prev = p.last_mut().unwrap();
            let (p, n) = n.split_at_mut(1);
            let line = p.first_mut().unwrap();
            let next = n.first_mut().unwrap();

            for k in (0..prev.len()).rev() {
                if prev[k].y > new_y {
                    next.push(prev.swap_remove(k));
                } else if prev[k].y == new_y {
                    line.push(prev.swap_remove(k));
                }
            }
        }

        self.add_count_partial_h(index - 1);
        self.add_count_partial_h(index);
    }

    fn move_upper_h(&mut self, index: usize, diff: i64) {
        self.sub_count_partial_h(index - 1);
        self.sub_count_partial_h(index);
        let line = index * 2 - 1;
        let new_y = self.h_cut[index] + diff;

        // まず線上
        for i in 0..self.boxes.len() {
            let b = &mut self.boxes[i];
            let (p, n) = b.split_at_mut(line);
            let prev = p.last_mut().unwrap();
            let line = n.first_mut().unwrap();

            for p in line.iter() {
                prev.push(*p);
            }

            line.clear();
        }

        // 次
        for i in 0..self.boxes.len() {
            let b = &mut self.boxes[i];
            let (p, n) = b.split_at_mut(line);
            let prev = p.last_mut().unwrap();
            let (p, n) = n.split_at_mut(1);
            let line = p.first_mut().unwrap();
            let next = n.first_mut().unwrap();

            for k in (0..next.len()).rev() {
                if next[k].y < new_y {
                    prev.push(next.swap_remove(k));
                } else if next[k].y == new_y {
                    line.push(next.swap_remove(k));
                }
            }
        }

        self.add_count_partial_h(index - 1);
        self.add_count_partial_h(index);
    }

    fn sub_count_partial_v(&mut self, i: usize) {
        let i = 2 * i;

        for j in 0..self.box_count_h {
            let j = 2 * j;
            self.counts[self.boxes[i][j].len()] -= 1;
        }
    }

    fn add_count_partial_v(&mut self, i: usize) {
        let i = 2 * i;

        for j in 0..self.box_count_h {
            let j = 2 * j;
            self.counts[self.boxes[i][j].len()] += 1;
        }
    }

    fn sub_count_partial_h(&mut self, j: usize) {
        let j = 2 * j;

        for i in 0..self.box_count_v {
            let i = 2 * i;
            self.counts[self.boxes[i][j].len()] -= 1;
        }
    }

    fn add_count_partial_h(&mut self, j: usize) {
        let j = 2 * j;

        for i in 0..self.box_count_v {
            let i = 2 * i;
            self.counts[self.boxes[i][j].len()] += 1;
        }
    }
}

impl Display for State {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        writeln!(f, "{}", self.cut_count_v + self.cut_count_h)?;
        for x in self.v_cut[1..(self.v_cut.len() - 1)].iter() {
            writeln!(f, "{} {} {} {}", x, RADIUS + 1, x, -RADIUS - 1)?;
        }

        for y in self.h_cut[1..(self.h_cut.len() - 1)].iter() {
            writeln!(f, "{} {} {} {}", RADIUS + 1, y, -RADIUS - 1, y)?;
        }

        Ok(())
    }
}

fn main() {
    let input = read_input();
    let state = solve(&input);
    println!("{}", &state);
    eprintln!("final score: {}", state.calc_score(&input));

    let elapsed = (Instant::now() - input.since).as_millis();
    eprintln!("elapsed: {}ms", elapsed);
}

fn read_input() -> Input {
    input! {
        n: usize,
        k: usize,
        counts: [i32; 10]
    }

    let mut points = vec![];

    for _ in 0..n {
        input! {
            x: i64,
            y: i64,
        }

        let point = Point::new(x, y);
        points.push(point);
    }

    let since = Instant::now();

    let count_sum = counts.iter().sum();

    let input = Input {
        n,
        k,
        counts,
        count_sum,
        points,
        since,
    };

    return input;
}

fn solve(input: &Input) -> State {
    let state = State::init(&input);
    let state = annealing(input, state, 2.97);
    state
}

fn annealing(input: &Input, initial_solution: State, duration: f64) -> State {
    let mut solution = initial_solution;
    let mut best_solution = solution.clone();
    let mut current_score = solution.calc_annealing_score(input, 0.0);
    let init_score = current_score;
    let mut best_score = current_score;

    let mut all_iter = 0;
    let mut valid_iter = 0;
    let mut accepted_count = 0;
    let mut update_count = 0;
    let mut rng = rand_pcg::Pcg64Mcg::new(42);

    let duration_inv = 1.0 / duration;
    let since = std::time::Instant::now();
    let mut time = 0.0;

    let temp0 = 1e4;
    let temp1 = 1e2;
    let mut inv_temp = 1.0 / temp0;
    let v_prob = solution.cut_count_v as f64 / (solution.cut_count_v + solution.cut_count_h) as f64;

    while time < 1.0 {
        all_iter += 1;
        if (all_iter & ((1 << 4) - 1)) == 0 {
            time = (std::time::Instant::now() - since).as_secs_f64() * duration_inv;
            let temp = f64::powf(temp0, 1.0 - time) * f64::powf(temp1, time);
            inv_temp = 1.0 / temp;
        }

        // 変形
        const MAX_DIFF: i64 = 100;
        let is_v = rng.gen_bool(v_prob);
        let coordinates = if is_v {
            &solution.v_cut
        } else {
            &solution.h_cut
        };

        let cut_count = if is_v {
            solution.cut_count_v
        } else {
            solution.cut_count_h
        };

        let index = rng.gen_range(1, cut_count + 1);

        let prev = coordinates[index - 1];
        let target = coordinates[index];
        let next = coordinates[index + 1];

        let min = (target - MAX_DIFF).max(prev + 1);
        let max = (target + MAX_DIFF).min(next - 1);
        let mut new_p = target;
        let mut trial = 0;

        while new_p == target && trial < 10 {
            new_p = rng.gen_range(min, max + 1);
            trial += 1;
        }

        let diff = new_p - target;

        if diff > 0 {
            if is_v {
                solution.move_upper_v(index, diff);
            } else {
                solution.move_upper_h(index, diff)
            }
        } else if diff < 0 {
            if is_v {
                solution.move_lower_v(index, diff);
            } else {
                solution.move_lower_h(index, diff);
            }
        } else {
            continue;
        }

        if is_v {
            solution.v_cut[index] += diff;
        } else {
            solution.h_cut[index] += diff;
        }

        // スコア計算
        let new_score = solution.calc_annealing_score(input, time);
        let score_diff = new_score - current_score;

        if score_diff >= 0 || rng.gen_bool(f64::exp(score_diff as f64 * inv_temp)) {
            // 解の更新
            current_score = new_score;
            accepted_count += 1;

            if chmax!(best_score, current_score) {
                best_solution = solution.clone();
                update_count += 1;
            }
        } else {
            let diff = -diff;
            if diff > 0 {
                if is_v {
                    solution.move_upper_v(index, diff);
                } else {
                    solution.move_upper_h(index, diff)
                }
            } else if diff < 0 {
                if is_v {
                    solution.move_lower_v(index, diff);
                } else {
                    solution.move_lower_h(index, diff);
                }
            } else {
                continue;
            }

            if is_v {
                solution.v_cut[index] += diff;
            } else {
                solution.h_cut[index] += diff;
            }
        }

        if valid_iter % 50000 == 0 {
            println!("{}", &solution);
        }

        valid_iter += 1;
    }

    eprintln!("===== annealing =====");
    eprintln!("score      : {}", best_score);
    eprintln!("init score : {}", init_score);
    eprintln!("all iter   : {}", all_iter);
    eprintln!("valid iter : {}", valid_iter);
    eprintln!("accepted   : {}", accepted_count);
    eprintln!("updated    : {}", update_count);
    eprintln!("");

    best_solution
}

提出情報

ジャッジ結果