Rustコトハジメ

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

【Educational DP-T Permutation】激ムズ。小さい方からk個がDPの添字

全くわからなかったです。運良くkmjpさんが解説してるのを見て、理解しました。

T - Permutation

問題

<と>で構成された長さN-1のSが与えられる。

順列Pを作りたい。ただし、P[i] S[i] P[j+1]のような関係でありたい。

場合の数を求めよ。

制約: N=3000

方針

こういう問題を見た時に、

  1. ">>>>"と"<<<"の連続に着目する
  2. "<"と">"の境界に着目する

ということを考えたいです。

私はとりあえず、何らかの数字の集合が与えられて、"<<<<>>>>>"のような上がって下がっての列にマッチさせるとした場合、中心は最大値になって、あとは片方だけを適当に選べばよい(n-1Ck)ということに気づいてしまったため、きっとそういう話だろうと思ってずっと考えましたが、ついにふて寝しました。

正解の考え方は、

dp[i][k] := 前からi番目を決めたとして、そいつを選ぶ時に残ってたやつのうち小さい方からk番目(0-index)を選んだ場合の数

です。こんなの初見ではわかりません。GGです。

こう考えると、例えば今、P[i]を決めるとしてs[i-1]が">"だった時に残ってたN-i個のうち小さい方からk個目を選んだ時の場合の数は、P[i-1]を入れた時はどういう状況だったかを考えると、その時に残っていたN-i+1個のうち下からk個目以上を選んでいたことになります。逆の"<"についてもまとめるとこういう関係なります。

f:id:akiradeveloper529:20190926161735j:plain

これは、毎ラウンド最初に累積和を計算することで計算量をO(N2)まで減らすことが出来ます。

実装

fn solve() {
    input!{
        N:usize,
        s:chars,
    }

    let mut dp=vec![0;N];

    // 1個目で小さい方からk個のやつをとる場合の数は全部1
    for k in 0..N {
        dp[k]=1;
    }

    for i in 1..N { // i番目を埋める
        let m = N-i; // 残りの個数
        let mut cum = CumSum1::build(&dp);
        if s[i-1] == '<' {
            for k in 0..m {
                dp[k] = cum.query(0,k+1);
            }
        } else {
            for k in 0..m {
                dp[k] = cum.query(k+1,m+1);
            }
        }
    }
    println!("{}", dp[0]);
}

考察

順列が題材で、なんらかの近傍において大きい(小さい方)k個にしか注目しなくて良いという意味では、

E - Second Sum

ではあります。脳内ではセットをイメージしてしまう時に、なんらかの数値でそれを置き換えて情報を圧縮出来ないかと考えることくらいは出来た気がします。