提出 #73752206

---

ソースコード 拡げる

use std::io::{self, BufRead};
use std::time::Instant;
use rand::Rng;

const DIJ: [(i32, i32); 4] = [(-1, 0), (0, 1), (1, 0), (0, -1)];
const DIR_CHARS: [char; 4] = ['U', 'R', 'D', 'L'];
const MAX_M: usize = 5;

#[derive(Clone, Debug)]
struct Robot {
    m: usize,
    transitions: Vec<(u8, usize, u8, usize)>, // (act_no_wall, next_no_wall, act_wall, next_wall)
    start_i: usize,
    start_j: usize,
    start_d: usize,
}

// act encoding: 0=F, 1=R, 2=L
fn act_char(a: u8) -> char {
    match a {
        0 => 'F',
        1 => 'R',
        _ => 'L',
    }
}

#[derive(Clone)]
struct RobotEntry {
    robot: Robot,
    coverage: Vec<usize>,      // flat cell ids in periodic orbit
    coverage_bits: [u64; 7],   // bitset: bit c is set iff cell c is covered (7×64=448≥400)
    score: f64,                // coverage.len() / m
}

fn make_coverage_bits(coverage: &[usize]) -> [u64; 7] {
    let mut bits = [0u64; 7];
    for &c in coverage {
        bits[c / 64] |= 1u64 << (c % 64);
    }
    bits
}

/// Returns true iff every bit set in `required` is also set in `coverage`.
#[inline(always)]
fn covers_all(coverage: &[u64; 7], required: &[u64; 7]) -> bool {
    (0..7).all(|k| required[k] & coverage[k] == required[k])
}

/// Reusable buffers for simulate_robot — allocated once, reused across calls.
struct SimBufs {
    /// 0 = not visited in current call; else = history_index + 1
    visited_step: Vec<u32>,
    history: Vec<(usize, usize, usize, usize)>,
    /// scratch buffer for unique-cell collection (size = n*n)
    seen: Vec<bool>,
}

impl SimBufs {
    fn new(n: usize) -> Self {
        let max_state_space = n * n * 4 * MAX_M;
        SimBufs {
            visited_step: vec![0u32; max_state_space],
            history: Vec::with_capacity(max_state_space),
            seen: vec![false; n * n],
        }
    }
}

fn main() {
    let stdin = io::stdin();
    let mut lines = stdin.lock().lines();

    let first_line = lines.next().unwrap().unwrap();
    let params: Vec<usize> = first_line
        .split_whitespace()
        .map(|s| s.parse().unwrap())
        .collect();
    let n = params[0];

    let mut wall_v = Vec::new();
    for _ in 0..n {
        let line = lines.next().unwrap().unwrap();
        wall_v.push(line.into_bytes());
    }
    let mut wall_h = Vec::new();
    for _ in 0..(n - 1) {
        let line = lines.next().unwrap().unwrap();
        wall_h.push(line.into_bytes());
    }

    let start_time = Instant::now();
    let time_limit = std::time::Duration::from_millis(1800);
    let random_gen_time = std::time::Duration::from_millis(20);
    let top_n = 100;

    let mut rng = rand::thread_rng();
    let mut bufs = SimBufs::new(n);

    // ===== Phase 1: 構造的パターン（タイマー消費なし、固定パターン） =====
    // act: 0=F, 1=R, 2=L
    // 各テンプレートを全 (cell × direction) に適用する
    let structured_templates: &[&[(u8, usize, u8, usize)]] = &[
        // Uターン右（2状態）: 直進 → 壁でR → もう一度R → 逆方向
        &[(0, 0, 1, 1), (1, 0, 1, 0)],
        // Uターン左（2状態）: 直進 → 壁でL → もう一度L → 逆方向
        &[(0, 0, 2, 1), (2, 0, 2, 0)],
        // 1状態右追従: 前が空→直進、壁→R
        &[(0, 0, 1, 0)],
        // 1状態左追従: 前が空→直進、壁→L
        &[(0, 0, 2, 0)],
        // 2状態右追従強化: 空→L, 壁→R
        &[(2, 0, 1, 1), (0, 0, 1, 0)],
        // 2状態左追従強化: 空→R, 壁→L
        &[(1, 0, 2, 1), (0, 0, 2, 0)],
    ];

    let mut structured_pool: Vec<RobotEntry> = Vec::new();

    for &template in structured_templates {
        let m = template.len();
        let transitions: Vec<(u8, usize, u8, usize)> = template.to_vec();
        for start_i in 0..n {
            for start_j in 0..n {
                for start_d in 0..4 {
                    let robot = Robot { m, transitions: transitions.clone(), start_i, start_j, start_d };
                    let coverage = simulate_robot(n, &wall_v, &wall_h, &robot, &mut bufs);
                    if coverage.is_empty() {
                        continue;
                    }
                    let cnt = coverage.len();
                    let score = cnt as f64 / m as f64;
                    let coverage_bits = make_coverage_bits(&coverage);
                    structured_pool.push(RobotEntry { robot, coverage, coverage_bits, score });
                }
            }
        }
    }
    eprintln!("Structured pool: {}", structured_pool.len());

    // ===== Phase 2 & 3 & 4: Multi-start with random generation =====
    let num_restarts = 10;
    let t_start = 5.0f64;
    let t_end = 0.01f64;
    let time_per_restart = time_limit.as_secs_f64() / num_restarts as f64;

    let mut global_best_robots: Vec<Robot> = Vec::new();
    let mut global_best_m = usize::MAX;

    // Reusable buffers for SA
    let mut newly_uncovered_buf: Vec<usize> = Vec::with_capacity(n * n);

    for restart in 0..num_restarts {
        let restart_start = Instant::now();
        let restart_deadline = restart_start + std::time::Duration::from_secs_f64(time_per_restart);

        eprintln!("--- Restart {}/{} ---", restart + 1, num_restarts);

        // Initialize pool with structured patterns
        let mut pool = structured_pool.clone();

        // Generate random robots for this restart
        let random_deadline = Instant::now() + random_gen_time;
        let mut random_count = 0;
        while Instant::now() < random_deadline {
            let m = rng.gen_range(1..=MAX_M);
            let robot = generate_random_robot(&mut rng, n, m);
            let coverage = simulate_robot(n, &wall_v, &wall_h, &robot, &mut bufs);
            if coverage.is_empty() {
                continue;
            }
            let cnt = coverage.len();
            let score = cnt as f64 / m as f64;
            let coverage_bits = make_coverage_bits(&coverage);
            pool.push(RobotEntry { robot, coverage, coverage_bits, score });
            random_count += 1;
        }

        eprintln!("  Random robots: {}, Total pool: {}", random_count, pool.len());

        // Filter candidates (top-n per cell)
        let mut cell_to_cands: Vec<Vec<usize>> = vec![Vec::new(); n * n];
        for (id, entry) in pool.iter().enumerate() {
            for &cell in &entry.coverage {
                cell_to_cands[cell].push(id);
            }
        }
        for cell_cands in &mut cell_to_cands {
            cell_cands.sort_by(|&a, &b| pool[b].score.partial_cmp(&pool[a].score).unwrap());
            cell_cands.truncate(top_n);
        }
        // Unique candidate ids
        let mut in_candidates = vec![false; pool.len()];
        for cell_cands in &cell_to_cands {
            for &id in cell_cands {
                in_candidates[id] = true;
            }
        }
        let mut candidates: Vec<usize> = (0..pool.len()).filter(|&id| in_candidates[id]).collect();
        candidates.sort_by(|&a, &b| pool[b].score.partial_cmp(&pool[a].score).unwrap());

        // Generate initial solution
        let mut cell_cover_count: Vec<u32> = vec![0; n * n];
        let mut total_covered: usize = 0;
        let mut selected_ids: Vec<usize> = Vec::new();
        let mut selected_pos: Vec<Option<usize>> = vec![None; pool.len()];

        // Randomize candidate order for diversity across restarts
        if restart > 0 {
            use rand::seq::SliceRandom;
            candidates.shuffle(&mut rng);
        }

        for &id in &candidates {
            if total_covered == n * n {
                break;
            }
            if pool[id].coverage.iter().any(|&c| cell_cover_count[c] == 0) {
                add_robot(&pool, id, &mut selected_ids, &mut selected_pos, &mut cell_cover_count, &mut total_covered);
            }
        }

        // Fallback: uncovered cells get a simple 1-state spin robot
        if total_covered < n * n {
            for cell in 0..(n * n) {
                if cell_cover_count[cell] == 0 {
                    let (ci, cj) = (cell / n, cell % n);
                    let robot = create_simple_robot(ci, cj);
                    let coverage = vec![cell];
                    let coverage_bits = make_coverage_bits(&coverage);
                    let id = pool.len();
                    pool.push(RobotEntry { robot, coverage, coverage_bits, score: 1.0 });
                    selected_pos.push(None);
                    cell_to_cands[cell].push(id);
                    add_robot(&pool, id, &mut selected_ids, &mut selected_pos, &mut cell_cover_count, &mut total_covered);
                }
            }
        }

        let initial_m: usize = selected_ids.iter().map(|&id| pool[id].robot.m).sum();
        eprintln!("  Initial M: {} (robots: {})", initial_m, selected_ids.len());

        // SA for this restart
        let mut current_m = initial_m;
        let mut best_selected = selected_ids.clone();
        let mut best_m = current_m;

        // Initialize candidate_visited for this restart (pool size may vary)
        let mut candidate_visited: Vec<bool> = vec![false; pool.len()];

    let mut t = t_start;
    let mut step = 0usize;
    loop {
        // Check time every 1000 steps to reduce syscall overhead
        if step % 1000 == 0 {
            if Instant::now() >= restart_deadline {
                break;
            }
            let elapsed = restart_start.elapsed().as_secs_f64();
            let progress = (elapsed / time_per_restart).clamp(0.0, 1.0);
            t = t_start * (t_end / t_start).powf(progress);
        }
        step += 1;

        // Pick a random robot to remove
        let r_idx = rng.gen_range(0..selected_ids.len());
        let r_id = selected_ids[r_idx];

        // Cells exclusively covered by r_id (count==1) — reuse buffer
        newly_uncovered_buf.clear();
        for &c in &pool[r_id].coverage {
            if cell_cover_count[c] == 1 {
                newly_uncovered_buf.push(c);
            }
        }

        if newly_uncovered_buf.is_empty() {
            // Remove r_id — always an improvement
            let delta = pool[r_id].robot.m;
            remove_robot(&pool, r_id, &mut selected_ids, &mut selected_pos, &mut cell_cover_count, &mut total_covered);
            current_m -= delta;
            if current_m < best_m {
                best_m = current_m;
                best_selected = selected_ids.clone();
            }
        } else {
            // Precompute bitset of uncovered cells once per step (O(|uncovered|) → O(7) per check)
            let mut uncovered_bits = [0u64; 7];
            for &uc in &newly_uncovered_buf {
                uncovered_bits[uc / 64] |= 1u64 << (uc % 64);
            }

            // Find replacement via reservoir sampling, avoiding duplicate checks
            let mut s_id_opt: Option<usize> = None;
            let mut count = 0usize;
            
            for &uc in &newly_uncovered_buf {
                for &cid in &cell_to_cands[uc] {
                    // Skip if already checked this step, or if selected, or if it's the removed robot
                    if candidate_visited[cid] || cid == r_id || selected_pos[cid].is_some() {
                        continue;
                    }
                    candidate_visited[cid] = true;
                    
                    // Check if this candidate covers all newly uncovered cells
                    if covers_all(&pool[cid].coverage_bits, &uncovered_bits) {
                        count += 1;
                        if rng.gen_range(0..count) == 0 {
                            s_id_opt = Some(cid);
                        }
                    }
                }
            }
            
            // Reset visited flags (only those we set)
            for &uc in &newly_uncovered_buf {
                for &cid in &cell_to_cands[uc] {
                    candidate_visited[cid] = false;
                }
            }
            
            let s_id = match s_id_opt {
                Some(id) => id,
                None => continue,
            };

            let delta_m = pool[s_id].robot.m as i64 - pool[r_id].robot.m as i64;
            let rand_val: f64 = rng.gen_range(0.0..1.0);
            if delta_m <= 0 || rand_val < (-(delta_m as f64) / t).exp() {
                remove_robot(&pool, r_id, &mut selected_ids, &mut selected_pos, &mut cell_cover_count, &mut total_covered);
                add_robot(&pool, s_id, &mut selected_ids, &mut selected_pos, &mut cell_cover_count, &mut total_covered);
                current_m = (current_m as i64 + delta_m) as usize;
                if current_m < best_m {
                    best_m = current_m;
                    best_selected = selected_ids.clone();
                }
            }
        }
    }

        eprintln!("  Steps: {}, Best M: {}", step, best_m);

        // Update global best
        if best_m < global_best_m {
            global_best_m = best_m;
            global_best_robots = best_selected.iter().map(|&id| pool[id].robot.clone()).collect();
        }

        // Early termination if time limit exceeded
        if start_time.elapsed() >= time_limit {
            eprintln!("Time limit reached at restart {}", restart + 1);
            break;
        }
    }

    eprintln!("Global best M: {}", global_best_m);

    // Output
    let out_robots: Vec<&Robot> = global_best_robots.iter().collect();
    output_solution(n, &out_robots);
}

fn add_robot(
    pool: &[RobotEntry],
    id: usize,
    selected_ids: &mut Vec<usize>,
    selected_pos: &mut Vec<Option<usize>>,
    cell_cover_count: &mut Vec<u32>,
    total_covered: &mut usize,
) {
    selected_pos[id] = Some(selected_ids.len());
    selected_ids.push(id);
    for &c in &pool[id].coverage {
        if cell_cover_count[c] == 0 {
            *total_covered += 1;
        }
        cell_cover_count[c] += 1;
    }
}

fn remove_robot(
    pool: &[RobotEntry],
    id: usize,
    selected_ids: &mut Vec<usize>,
    selected_pos: &mut Vec<Option<usize>>,
    cell_cover_count: &mut Vec<u32>,
    total_covered: &mut usize,
) {
    let pos = selected_pos[id].unwrap();
    let last = *selected_ids.last().unwrap();
    selected_ids.swap_remove(pos);
    if last != id {
        selected_pos[last] = Some(pos);
    }
    selected_pos[id] = None;
    for &c in &pool[id].coverage {
        cell_cover_count[c] -= 1;
        if cell_cover_count[c] == 0 {
            *total_covered -= 1;
        }
    }
}

fn generate_random_robot<R: Rng>(rng: &mut R, n: usize, m: usize) -> Robot {
    let mut transitions = Vec::with_capacity(m);
    for _ in 0..m {
        let act_no_wall: u8 = rng.gen_range(0..3); // F, R, L
        let next_no_wall = rng.gen_range(0..m);
        let act_wall: u8 = rng.gen_range(1..3); // R or L only
        let next_wall = rng.gen_range(0..m);
        transitions.push((act_no_wall, next_no_wall, act_wall, next_wall));
    }
    Robot {
        m,
        transitions,
        start_i: rng.gen_range(0..n),
        start_j: rng.gen_range(0..n),
        start_d: rng.gen_range(0..4),
    }
}

fn create_simple_robot(i: usize, j: usize) -> Robot {
    Robot {
        m: 1,
        transitions: vec![(1, 0, 1, 0)], // always R
        start_i: i,
        start_j: j,
        start_d: 0,
    }
}

/// Simulate robot and return cells visited in the periodic orbit.
/// Uses pre-allocated SimBufs to avoid per-call allocations.
/// visited_step is reset by clearing only touched entries (no full reinitialization).
fn simulate_robot(
    n: usize,
    wall_v: &[Vec<u8>],
    wall_h: &[Vec<u8>],
    robot: &Robot,
    bufs: &mut SimBufs,
) -> Vec<usize> {
    let m = robot.m;
    let state_space = n * n * 4 * m;

    // Grow buffer if needed (only happens when m > MAX_M, which shouldn't occur)
    if bufs.visited_step.len() < state_space {
        bufs.visited_step.resize(state_space, 0);
    }
    bufs.history.clear();

    let mut i = robot.start_i;
    let mut j = robot.start_j;
    let mut d = robot.start_d;
    let mut s = 0usize;

    // Find cycle
    let cycle_start_idx = loop {
        // Compute encoding: (cell_id * 4 + d) * m + s
        // Prefactor: ((i * n + j) * 4 + d) * m
        let enc = (i * n + j) * 4 + d;
        let enc = enc * m + s;

        if bufs.visited_step[enc] != 0 {
            break (bufs.visited_step[enc] - 1) as usize;
        }

        bufs.visited_step[enc] = (bufs.history.len() + 1) as u32;
        bufs.history.push((i, j, d, s));

        if bufs.history.len() > state_space {
            // Cleanup and bail
            for &(si, sj, sd, ss) in &bufs.history {
                let enc_cleanup = ((si * n + sj) * 4 + sd) * m + ss;
                bufs.visited_step[enc_cleanup] = 0;
            }
            return Vec::new();
        }

        let wall_ahead = check_wall(n, wall_v, wall_h, i, j, d);
        let (act, next_s) = if !wall_ahead {
            let (a, ns, _, _) = robot.transitions[s];
            (a, ns)
        } else {
            let (_, _, a, ns) = robot.transitions[s];
            (a, ns)
        };

        match act {
            0 => {
                let (di, dj) = DIJ[d];
                i = (i as i32 + di) as usize;
                j = (j as i32 + dj) as usize;
            }
            1 => d = (d + 1) % 4,
            _ => d = (d + 3) % 4,
        }
        s = next_s;
    };

    // Collect unique cells in the cycle
    let mut result = Vec::new();
    for k in cycle_start_idx..bufs.history.len() {
        let (ci, cj, _, _) = bufs.history[k];
        let cell = ci * n + cj;
        if !bufs.seen[cell] {
            bufs.seen[cell] = true;
            result.push(cell);
        }
    }

    // Reset seen (only cells we set)
    for &cell in &result {
        bufs.seen[cell] = false;
    }

    // Reset visited_step (only entries we wrote — no full reinitialization)
    for &(si, sj, sd, ss) in &bufs.history {
        bufs.visited_step[((si * n + sj) * 4 + sd) * m + ss] = 0;
    }

    result
}

fn check_wall(n: usize, wall_v: &[Vec<u8>], wall_h: &[Vec<u8>], i: usize, j: usize, d: usize) -> bool {
    let (di, dj) = DIJ[d];
    let ni = i as i32 + di;
    let nj = j as i32 + dj;
    if ni < 0 || ni >= n as i32 || nj < 0 || nj >= n as i32 {
        return true;
    }
    let ni = ni as usize;
    let nj = nj as usize;
    match d {
        0 => wall_h[ni][j] == b'1', // Up
        2 => wall_h[i][j] == b'1',  // Down
        1 => wall_v[i][j] == b'1',  // Right
        3 => wall_v[i][nj] == b'1', // Left
        _ => unreachable!(),
    }
}

fn output_solution(n: usize, robots: &[&Robot]) {
    println!("{}", robots.len());
    for robot in robots {
        println!("{} {} {} {}", robot.m, robot.start_i, robot.start_j, DIR_CHARS[robot.start_d]);
        for &(a0, ns0, a1, ns1) in &robot.transitions {
            println!("{} {} {} {}", act_char(a0), ns0, act_char(a1), ns1);
        }
    }
    for _ in 0..n {
        println!("{}", "0".repeat(n - 1));
    }
    for _ in 0..(n - 1) {
        println!("{}", "0".repeat(n));
    }
}

提出情報

コンパイルエラー

warning: use of deprecated function `rand::thread_rng`: Renamed to `rng`
  --> src/main.rs:96:25
   |
96 |     let mut rng = rand::thread_rng();
   |                         ^^^^^^^^^^
   |
   = note: `#[warn(deprecated)]` on by default

warning: use of deprecated method `rand::Rng::gen_range`: Renamed to `random_range`
   --> src/main.rs:165:25
    |
165 |             let m = rng.gen_range(1..=MAX_M);
    |                         ^^^^^^^^^

warning: use of deprecated method `rand::Rng::gen_range`: Renamed to `random_range`
   --> src/main.rs:265:25
    |
265 |         let r_idx = rng.gen_range(0..selected_ids.len());
    |                         ^^^^^^^^^

warning: use of deprecated method `rand::Rng::gen_range`: Renamed to `random_range`
   --> src/main.rs:307:32
    |
307 |                         if rng.gen_range(0..count) == 0 {
    |                                ^^^^^^^^^

warning: use of deprecated method `rand::Rng::gen_range`: Renamed to `random_range`
   --> src/main.rs:327:37
    |
327 |             let rand_val: f64 = rng.gen_range(0.0..1.0);
    |                                     ^^^^^^^^^

warning: use of deprecated method `rand::Rng::gen_range`: Renamed to `random_range`
   --> src/main.rs:406:35
    |
406 |         let act_no_wall: u8 = rng.gen_range(0..3); // F, R, L
    |                                   ^^^^^^^^^

warning: use of deprecated method `rand::Rng::gen_range`: Renamed to `random_range`
   --> src/main.rs:407:32
    |
407 |         let next_no_wall = rng.gen_range(0..m);
    |                                ^^^^^^^^^

warning: use of deprecated method `rand::Rng::gen_range`: Renamed to `random_range`
   --> src/main.rs:408:32
    |
408 |         let act_wall: u8 = rng.gen_range(1..3); // R or L only
    |                                ^^^^^^^^^

warning: use of deprecated method `rand::Rng::gen_range`: Renamed to `random_range`
   --> src/main.rs:409:29
    |
409 |         let next_wall = rng.gen_range(0..m);
    |                             ^^^^^^^^^

warning: use of deprecated method `rand::Rng::gen_range`: Renamed to `random_range`
   --> src/main.rs:415:22
    |
415 |         start_i: rng.gen_range(0..n),
    |                      ^^^^^^^^^

warning: use of deprecated method `rand::Rng::gen_range`: Renamed to `random_range`
   --> src/main.rs:416:22
    |
416 |         start_j: rng.gen_range(0..n),
    |                      ^^^^^^^^^

warning: use of deprecated method `rand::Rng::gen_range`: Renamed to `random_range`
   --> src/main.rs:417:22
    |
417 |         start_d: rng.gen_range(0..4),
    |                      ^^^^^^^^^

ジャッジ結果