Rustコトハジメ

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

【ABC075-D Axis-Parallel Rectangle】最小値を求める時の初期値は組み込みの最大値を使いなさい

400点をひたすらやっつけてます。

簡単な問題だと思いましたがハマってデバグに2時間かかったので教訓がてら書いておきます。

D - Axis-Parallel Rectangle

問題

2次元平面にN(<=50)個の点がばらまいてあります。Kが与えられます。K個以上の点を含む(辺上の点はカウントする)長方形のうち最小の面積を求めなさい。

方針

エディトリは愚直にO(N5)で間に合うとしていますが、おれは愚直解法はO(N6)で間に合わないと錯覚したため、エディトリで詳細は省略されている2次元累積和を使った実装をしてしまいました。

なぜ、愚直解法で間に合わないと錯覚したかというと、愚直解法で間に合うような問題なわけがないという脳内補正のためというのもあると思いますが、それよりも、問題文自体から漂う座圧してください臭のせいです。まず、座圧することから入ってしまったので、そこからどうするかと考えた時、自然と二次元累積和となりました。

二次元累積和を使うと、最後の4重ループの中身がO(1)になるため、トータルでO(N4)になり速いはずなのですが、O(N5)の愚直解法で実装されたC++の実装も同じくらいの時間で走っているので、無駄な努力でした。

実装

fn solve() {
    input! {
        N:usize,K:usize,
        XY:[(i64,i64);N],
    }

    let mut xs = vec![];
    let mut ys = vec![];
    for &(x,y) in &XY {
        xs.push(x);
        ys.push(y);
    }
    xs.sort();
    ys.sort();

    let mut compress_x = HashMap::new();
    let mut uncompress_x = HashMap::new();
    for i in 0..N {
        let x = xs[i];
        compress_x.insert(x, i+1);
        uncompress_x.insert(i+1, x);
    }

    let mut compress_y = HashMap::new();
    let mut uncompress_y = HashMap::new();
    for i in 0..N {
        let y = ys[i];
        compress_y.insert(y, i+1);
        uncompress_y.insert(i+1, y);
    }

    // dbg!(&compress_x);
    // dbg!(&compress_y);

    let mut cxy = vec![];
    for &(x,y) in &XY {
        cxy.push((*compress_x.get(&x).unwrap(), *compress_y.get(&y).unwrap()));
    }
    // dbg!(&cxy);

    let mut accum = vec![vec![0;N+1];N+1];
    for (i,j) in cxy {
        accum[i][j] = 1;
    }
    // dbg!(&accum);
    for i in 1..N+1 {
        for j in 1..N+1 {
            accum[i][j] = accum[i][j] + accum[i-1][j] + accum[i][j-1] - accum[i-1][j-1];
        }
    }
    // dbg!(&accum);

    let calc = |x0:usize,x1:usize,y0:usize,y1:usize| {
        accum[x1][y1] - (accum[x1][y0-1] + accum[x0-1][y1] - accum[x0-1][y0-1])
    };

    let mut minv = std::i64::MAX;
    for x0 in 1..N+1 {
        for x1 in 1..N+1 {
            if !(x0<x1) { continue; }
            for y0 in 1..N+1 {
                for y1 in 1..N+1 {
                    if !(y0<y1) { continue; }
                    let n = calc(x0,x1,y0,y1);
                    if n >= K {
                        let xx0 = *uncompress_x.get(&x0).unwrap();
                        let xx1 = *uncompress_x.get(&x1).unwrap();
                        let yy0 = *uncompress_y.get(&y0).unwrap();
                        let yy1 = *uncompress_y.get(&y1).unwrap();
                        let v = (xx1-xx0)*(yy1-yy0);
                        // dbg!(xx0,xx1,yy0,yy1,v);
                        minv = min(minv,v);
                    }
                }
            }
        }
    }
    println!("{}",minv);
}

考察

何でハマっていたかというと、minvの初期値を適当に1<<60とかしてました。こうすると、サンプル3で計算される値がすべてこの値を超えているので、一切更新されることがなく、サンプル3は意味不明な値を出して通らなかったです。

教訓としては、最小値の初期値はstd::i64::MAXか、新しいバージョンのコンパイラであれば、i64::max_valueを使うように徹底した方がいいですね。

あと、累積和の実装はライブラリ化してもいいかも知れないですね。時々出るので。