階段 (Stairs) (日本情報オリンピック 春合宿 2010 day1-3) を解いた

• 階段 (Stairs) (日本情報オリンピック 春合宿 2010 day1-3) https://atcoder.jp/contests/joisc2010/tasks/joisc2010_stairs
  • https://atcoder.jp/contests/joisc2010/submissions/42747893
  • DP
  • 素朴に「貰う DP 」で書くと O(N²) で間に合わない
  • 貰う部分を累積和で求めれば間に合う
  • 書籍ではしゃくとり法で解いてあった

use proconio::input;
use superslice::Ext;

fn main() {
    input! {
        n: usize,
        p: usize,
        h: [usize; n],
    }
    let c = std::iter::once(0)
        .chain(h.iter().scan(0, |acc, &i| {
            *acc += i;
            Some(*acc)
        }))
        .collect::<Vec<usize>>();
    let modp = 1234567;

    let mut sum = vec![0_usize; n + 1 + 1];
    let mut dp = vec![0_usize; n + 1];
    dp[0] = 1_usize;
    sum[1] = 1_usize;
    for i in 1..=n {
        let v_l = c[i].saturating_sub(p);
        let left = c.lower_bound(&v_l);
        let right = i;
        // for j in left..right {
        //     dp[i] += dp[j];
        //     dp[i] %= modp;
        // }
        dp[i] += (modp + sum[right] - sum[left]) % modp;
        sum[i + 1] += sum[i] + dp[i];
        sum[i + 1] %= modp;
    }
    let ans = dp[n];
    println!("{}", ans);
}

---

今日のコミット。

• tsukota 1 commit
  • Update readme
• rust-atcoder 1 commit
  • pastbook2 joisc2010_stairs