Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

【AGC034-A Kenken Race】ある瞬間に着目する

A - Kenken Race

問題

N個のマスがあり、石が置いてあったり置いてなかったりする。Nは5乗。

すぬけくんはAから、ふぬけくんはB(A<B)から、それぞれCとDを目指す。一回の操作につき、自分の1つ右か自分の2つ右にしか移動出来ない。石のあるマスや、相方がいるマスには移動出来ないとすると、これは達成可能か?

方針

一人でやるならば簡単。

C<Dの時も簡単。まずはふぬけを動かしてからすぬけを動かせば一人でやるのに等しい。

C>Dは、すぬけくんがふぬけくんを追い越す必要があるため、追い越すとはどういうことなのかに注目する。

すると、

SF○ (○はすぬけくんが移動可能)

という形がどこかで成り立ちうるのであれば、まずはそこにふぬけくんを動かして、からすぬけくんをその左に動かして、追い越させればいい。その後、追い越しは発生しないから、一人プレイに帰着出来る。

実装

fn solve() {
    input!{
        N:usize,A:usize,B:usize,C:usize,D:usize,
        S:chars,
    }
    // 0オリジンに直す
    let A=A-1;
    let B=B-1;
    let C=C-1;
    let D=D-1;
    let mut dps=vec![false;N];
    dps[A]=true;
    for i in A..N {
        if S[i]=='#' { dps[i]=false; }
        else {
            if i>=1 && dps[i-1] { dps[i]=true; }
            if i>=2 && dps[i-2] { dps[i]=true; }
        }
    }
    let mut dpf=vec![false;N];
    dpf[B]=true;
    for i in B..N {
        if S[i]=='#' { dpf[i]=false; }
        else {
            if i>=1 && dpf[i-1] { dpf[i]=true; }
            if i>=2 && dpf[i-2] { dpf[i]=true; }
        }
    }
    // dbg!(&dps);
    // dbg!(&dpf);
 
    if C<D {
        // この場合はまずふぬけを動かしてからスヌケを動かせばよい
        if dps[C] && dpf[D] {
            println!("Yes");
        } else {
            println!("No");
        }
        return
    }
 
    // 以下逆転パターンについて考える
    // 追い越しを考える必要がある
    // 追い越しをふぬけが[B,D]にいる時に行う必要がある
    // そのような追い越しが可能か調べる
 
    let mut found=false;
    for i in B..D+1 {
        if dps[i-1] && dpf[i] && dps[i+1] {
            found=true;
        }
    }
 
    if found && dps[C] && dpf[D] {
        println!("Yes")
    } else {
        println!("No")
    }
}

考察

追い越す瞬間の状態がどういう状態なのか考えないといけない。