はまやんはまやんはまやん

hamayanhamayan's blog

Minimum SubArray [CodeChef December Cook-Off 2017 C]

https://www.codechef.com/COOK89/problems/MINSUBAR

N個の配列Aがある。
この中の連続部分列で、総和がD以上となるもので最小の長さを答えよ。

前提知識

  • 累積和
  • 座標圧縮
  • セグメントツリー(区間min)

解法

連続部分列の右側を全探索しよう。
Rを固定して[L,R]を考えるが、満たすべき条件は「L<RかつD≦sm[L..R]」を満たすLのうち最も大きいLが得られると嬉しい。
D≦sm[L..R]を累積和を使って言い換えよう。
D≦sm[R] - sm[L - 1]
sm[L - 1]≦sm[R] - D
より、「L<Rかつsm[L - 1]≦sm[R] - D」を満たすLのうち最も大きいLを求める。

これは区間maxのセグメントツリーを使おう。
予めsm[i]とsm[i] - Dで座圧を準備しておこう。
これでsm[R]-D以下の区間を取れる。
L<Rは順次更新していこうようにして対応できる。
これでLを求めつつ、答えを更新していく。

#define INF INT_MAX
int N; int D, A[101010], sm[101010];
//---------------------------------------------------------------------------------------------------
int solve() {
    cin >> N >> D;
    rep(i, 0, N) cin >> A[i];
    sm[0] = A[0];
    rep(i, 1, N) sm[i] = sm[i - 1] + A[i];
 
    SegTree<int> st; st.init(N * 2 + 10);
 
    Zaatsu z;
    rep(i, 0, N) z.add(sm[i]), z.add(sm[i] - D);
    z.add(0);
    z.build();
 
    st.update(z[0], -1);
 
    int ans = INF;
    rep(i, 0, N) {
        int id = st.get(0, z[sm[i] - D] + 1);
        if (-1 <= id) ans = min(ans, i - id);
        st.update(z[sm[i]], i);
    }
 
    if (ans == INF) ans = -1;
    return ans;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    int T; cin >> T;
    rep(t, 0, T) printf("%d\n", solve());
}