Rustコトハジメ

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

【AGC005-B Minimum Sum】RMQと分割統治

良い問題だなーと思いました。想定解法とは違ってRMQを使う解法です。100msかかってるテストケースがあるので言語によってはTLEするかも。

B - Minimum Sum

問題

長さNの数列Aが与えられる。このうち、全i,j(i<=j)についてmin{Ak}を全部足し合わせたらいくつになるか?なお、Aは1からNの順列。

方針

自分は分割統治とRMQを使ってシンプルに考えました。

まず、Ak->kは求まります。(Aの逆関数

そして、想定解法と同様に、例えば1は何回足し合わされるかを考えます。

サンプル1の[2,1,3]で考えると、それは、1から2,1,3に対するエッジと、2と3を結ぶエッジの数と考えられます。次に2が何回足し合わされるかと考えると、1が出現してる時点でだめなので、[2]の中で同様に考えればいいことがわかります。

つまり、

  1. ある配列の中で最小の値とそのインデックスを求める
  2. まず、その最小の値が何回足し合わされるか求める(左の個数x右の個数 + 領域長さ)
  3. その最小値をmidにして、左と右に再帰して、足し合わせる

という計算になります。

    let mut n = 0;
    n += minv * (right-left+1);
    n += minv * (mini-left) * (right-mini);
    if !(mini==left) {
        n += dfs(rmq, pos, left, mini-1);
    }
    if !(mini==right) {
        n += dfs(rmq, pos, mini+1, right);
    }

最小の値を求めるのは、いちいち舐めるとO(N2)になってTLEのするのでRMQを使います。

実装

// [left,right]
fn dfs(rmq: &SEG<MIN>, pos: &[usize], left: usize, right: usize) -> usize {
    let minv = rmq.query(left, right+1);
    let mini = pos[minv];
    // dbg!(left,right,mini,minv);
    let mut n = 0;
    n += minv * (right-left+1);
    n += minv * (mini-left) * (right-mini);
    if !(mini==left) {
        // dbg!("L");
        n += dfs(rmq, pos, left, mini-1);
    }
    if !(mini==right) {
        // dbg!("R");
        n += dfs(rmq, pos, mini+1, right);
    }
    // dbg!(n);
    n
}
fn solve() {
    input!{
        N:usize,
        A:[usize;N],
    }
    let mut a = vec![0];
    for x in A { 
        a.push(x);
    }
    let mut pos = vec![0;N+1];
    for i in 0..N+1 {
        pos[a[i]] = i;
    }
    // dbg!(&a,&pos);
    let mut rmq: SEG<MIN> = SEG::new(N+1);
    for i in 0..N+1 {
        rmq.update(i, a[i]);
    }
    println!("{}",dfs(&rmq,&pos,1,N));
}

考察

他の問題でも、RMQを使う方がシンプルに書けるが、想定はNlogNではなくNということがあった。実際にRMQを使うと1秒かかるようなものもあるので、RustやC++でなければTLEする可能性が高い。ちなみにこの問題だとマックスで80ms程度だが、言語によってはTLEすると思う。高速言語を使うと、logNを妥協出来て、実装がシンプルになるということはありそう。

Rustオススメです。