🌊

Google Code Jam 'Reversort Engineering'[Rust]

2021/03/28に公開

Rust

競プロ

gcj

tech

問題概要

配列の長さ N と Reversort の計算コスト C が与えられる。N と C を満たす配列を答えなさい。なお、計算が不可能な場合は IMPOSSIBLE と回答する。

Reversort とは、以下の処理を配列の最初から、最後から 2 番めの要素まで繰り返すアルゴリズムです。
i 番目から配列の最後の要素までの最小値を探す。
i から最小値までのサブ配列をリバースする。

この、ひっくり返す要素の数が計算コストになります。なお、i 番目の要素が最小値だった場合、計算コストは 1 になります。

詳細は問題を参照。

制約

Time limit: 10 seconds.
Memory limit: 1 GB.
1≤T≤100.
1≤C≤1000.
Test Set 1 (Visible Verdict)
2≤N≤7.
Test Set 2 (Visible Verdict)
2≤N≤100.

考えたこと

最小コストと最大コストを考えます。

最小コストは、1 から N までの要素すべてがソート済みで、ひっくり返す必要がない場合です。その場合、コストは N-1 になります。

最大コストは 2 から N の、差が 1 である等差数列の和である $(N-1) * (2 * 2 + (N-2)) / 2$ です。

こうしたコストになる長さ 4 の具体的な配列は $2 4 3 1$ です。

これは、リバースコストが最も高いのは、対象となる要素数が最も多い場合。つまり、i 番目の要素を検討する際に、その要素が配列の右端にあれば、最もコストがかさみます。

こうした配列は、1 から N まで順番に外側から内部を埋めるように、右左交互に要素 i を置いていくと実現できます。

$2 4 3 1$ を例にとります。1 を最初に検討するので、1 はソート前のオリジナルの配列の右端にある必要があります。
$○ ○ ○ 1$
続いて 2 を検討する際、2 は右端にある必要があります。しかし、1 が右端にある場合、配列全体をひっくり返します。そのため、1 度目のリバース後に右端に配置されるよう、2 は左端に置きます。
$2 ○ ○ 1$
3 に進むと、3 を検討するのは、2 回リバースした後なので、最大コストになるのは右端にある場合です。元々右端にあった 1 は左端にソート済みのため、3 は右から 2 番目、1 の左隣に配置します。
$2 ○ 3 1$
$2 4 3 1$

この場合、コストは各回、i から N までの要素をリバースした合計になります。つまり、 $4 + 3 + 2 = 9$

これは 2 から N までの差が 1 の等差数列となります。そのため合計は、 $(N-1) * (2 * 2 + (N-2)) / 2$ です。

逆に、i 番目の要素を検討する際に最もコストが低いのは、i-1 番目の要素の次にある場合です。

解法

最大コストと最小コストの範囲になければ IMPOSSIBLE を出力して、範囲内なら貪欲法。

最小コストから指定のコストを超えないように、大きいコストから足していきます。リバースコストが 2 の場合、追加コストは計算済みの最小コスト 1 との差分である 1 で、コストが中途半端で埋められないということは起きないため、貪欲法で大丈夫です。

具体的には、長さ N の空配列を右から埋める場合(v[n-rpad])と左(v[lpad])から埋める場合を考えます。

コストを足す場合は、前の要素とは反対の方向から埋めます(1 の場合は右端)。

コストを足すと指定コストを超過したり、すでに指定コストピッタリになっている場合は、前の要素の次に起きます。つまり、前の要素が右端から ○ 番目に置かれていれば、右端から ○+1 番目に、同様に左端から ○ 番目なら、左端から ○+1 番目に置きます。

コストを足す場合と足さない場合の要素の置き場所は、左右逆転しています。つまり、1 つの真偽値(from_right)を用意すれば十分です。from_right = trueでコストを足すなら右から、コストを足さないなら左から埋めます。

use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let t:usize = read();

    for i in 1..=t {
        let n:usize = read();
        let c:usize = read();
        let max_cost = (n-1) * (2 * 2 + (n-2)) / 2;
        if c > max_cost || c < n - 1 {
            println!("Case #{}: IMPOSSIBLE", i);
            continue;
        }
        let mut v = vec![0; n];

        let mut rpad = 1;
        let mut lpad = 0;
        let mut from_right = true;
        let mut now_cost = n-1;
        for j in 1..=n {
            if now_cost == c || now_cost + n - j > c {
                if !from_right {
                    v[n-rpad] = j;
                    rpad += 1;
                } else {
                    v[lpad] = j;
                    lpad += 1;
                }
            } else if now_cost + n - j <= c {
                now_cost += n - j;
                if from_right {
                    v[n-rpad] = j;
                    rpad += 1;
                    from_right = false;
                } else {
                    v[lpad] = j;
                    lpad += 1;
                    from_right = true;
                }
            }
        }

        print!("Case #{}:", i);
        for j in v {
            print!(" {}", j);
        }
        println!("");
    }
}

余談

ちなみに、特定の N と C から複数の配列がありえます。
サンプルケースでは N=4, C=6 で、Case #1: 4 2 1 3とあります。

しかし、上のコードだとCase #1: 4 3 2 1になります。

問題概要

制約

考えたこと

解法

余談

Discussion