Rustコトハジメ

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

【AGC032-A Limited Insertion】最終図を想像する + 厳しい方から攻める + 逆算する

AGCはAでもすでに難しいことがある。早くB,Cで打率5割マンになりたい。

A - Limited Insertion

競プロあるあるな考え方なので紹介します。

問題

長さNの数列を以下のようにして作る。

  • i(1<=i<=N)番目の操作ではj(1<=j<=i)をj番目に挿入する

こうやって出来た数列Aが、別の数列Bに等しくなるかどうか答えよ。等しくなる場合は、操作方法を列挙せよ。

方針

まず、数字aはインデックスaより後ろにしかいないことがわかる。前に挿入されたらその分だけ偏位が上がっていく。

最終図を想像すると、必ず、偏位0のやつを最後に入れたはずである。

数列の中には、偏位0のやつが2ついる場合がある。仮に、前方のやつを最後に入れた場合、後方のやつは後ろにずれているはずである。従って後方のやつが最後に入れられたことになる。

あとは、最終図から逆算していけばよい。

実装

Nが100と小さいので、多少強引にやっていっても通る。Nが10000とかなった場合にも解けるんだろうか?

この問題の場合、1オリジンで実装してしまった方が素直だと思う。

fn solve() {
    input!{
        N:usize,
        B:[usize;N]
    }

    let mut xs = vec![0];
    for b in B {
        xs.push(b)
    }

    let mut moves = vec![];
    let mut diff = vec![0;N+1];

    loop {
        for i in 1..xs.len() {
            if i<xs[i] {
                println!("-1");
                return
            }
            diff[i]=i-xs[i]
        }
        let mut ok=true;
        for i in 1..xs.len() {
            if diff[i]!=0 { ok=false }
        }
        if ok {
            for i in (1..xs.len()).rev() {
                moves.push(xs[i]);
            }
            moves.reverse();
            for m in moves {
                println!("{}",m);
            }
            return;
        } else {
            let mut next = None;
            for i in (1..xs.len()).rev() {
                if diff[i]==0 {
                    next=Some(i);
                    break;
                }
            }
            if next.is_none() {
                break;
            } else {
                let mut j = next.unwrap();
                moves.push(j);
                xs.remove(j);
            }
        }
    }

    println!("-1")
}

考察

こういう感じで逆からやっていくのはあるあるだが、最近では

D - Summer Vacation

逆から行く系は貪欲になることが多いように思う。