Coding Games shadows-of-the-knight-episode-1解説

問題

www.codingame.com

解説

まず探索範囲を考える． 現在位置をx，y，xの探索範囲上限はmax_x，xの探索範囲下限はmin_x，同様にmax_y，min_yとおく． 探索範囲は最初は全範囲とする． max_x = w - 1 min_x = 0 とすればよい．

次に探索範囲を二分探索で狭めていくことを考える．

Uと入力された(現在の位置より上)なら探索範囲を現在位置よりも上の位置に設定，つまりmax_x = x -1 Dと入力された(現在の位置より下)なら探索範囲を現在位置よりも下の位置に設定，min_x = x + 1 yについても同様に行う．

実装(Rust)

use std::io;

macro_rules! parse_input {
    ($x:expr, $t:ident) => ($x.trim().parse::<$t>().unwrap())
}

/**
 * Auto-generated code below aims at helping you parse
 * the standard input according to the problem statement.
 **/
fn main() {
    let mut input_line = String::new();
    io::stdin().read_line(&mut input_line).unwrap();
    let inputs = input_line.split(" ").collect::<Vec<_>>();
    let w = parse_input!(inputs[0], i32); // width of the building.
    let h = parse_input!(inputs[1], i32); // height of the building.
    let mut input_line = String::new();
    io::stdin().read_line(&mut input_line).unwrap();
    let n = parse_input!(input_line, i32); // maximum number of turns before game over.
    let mut input_line = String::new();
    io::stdin().read_line(&mut input_line).unwrap();
    let inputs = input_line.split(" ").collect::<Vec<_>>();
    let mut x = parse_input!(inputs[0], i32);
    let mut y = parse_input!(inputs[1], i32);


    let mut min_x = 0;
    let mut min_y = 0;
    let mut max_x = w - 1;
    let mut max_y = h - 1;

    // game loop
    loop {
        let mut input_line = String::new();
        io::stdin().read_line(&mut input_line).unwrap();
        let bomb_dir = input_line.trim().to_string(); // the direction of the bombs from batman's current location (U, UR, R, DR, D, DL, L or UL)

        // Write an action using println!("message...");
        // To debug: eprintln!("Debug message...");
        if bomb_dir.contains("U"){
            max_y = y - 1;
        }
        else if bomb_dir.contains("D"){
            min_y = y + 1;
        }
        if bomb_dir.contains("L"){
            max_x = x - 1;
        }
        else if bomb_dir.contains("R"){
            min_x = x + 1;
        }

        x = (min_x + max_x) / 2;
        y = (min_y + max_y) / 2;


        // the location of the next window Batman should jump to.
        println!("{} {}",x,y);
    }
}

参考

https://m-ansley.medium.com/a-brief-introduction-to-2d-binary-searches-c-c862d101efbb https://github.com/vadim-job-hg/Codingame/blob/master/MEDIUM/SHADOW%20OF%20THE%20KNIGHT%20-%20EPISODE%201/python/shadows-of-the-knight-episode-1.py https://github.com/luojinzhang/Codingame-medium-solutions/blob/master/Shadows%20of%20the%20Knight%20-%20Episode%201.cpp