bouzuya.hatenablog.com

ぼうずやのにっき

bouzuya/tsukota 0.3.2 をつくった / 自転車の練習を手伝う / EDPC S を解いた

bouzuya/tsukota v0.3.2 をつくった。

  • copyright の表記の誤りの修正
  • ActivityIndicator の漏れの修正

軽微な修正でお茶をにごしている。

上の子の自転車の練習を手伝う。もう直線なら普通に進める。

問題はこぎはじめ。ペダルだけで動こうとするので厳しそう。

あとはスピードが怖いようで、すぐに足をつけようとする。余計に危ないのに……。

本当にあとは慣れという感じ。

  • Digit Sum (Educational DP Contest:S問題) https://atcoder.jp/contests/dp/tasks/dp_s
    • https://atcoder.jp/contests/dp/submissions/43224011
    • 桁 DP
    • 桁 DP の基本形
    • dp[i][j] := そこまでの剰余が i で K 未満が確定しているなら j = 1 のときの場合の数
    • dp[0][0] = 1 からはじめる
    • 上位桁から順に各桁を走査する
    • 0..=d で各 i について 0..=9 でその桁の各数字を走査する
    • その桁の数字で未満が確定するかしないかで分岐する
    • 1 以上の、なので最後に 1 を引く
use proconio::{input, marker::Chars};

fn main() {
    input! {
        k: Chars,
        d: usize,
    }

    let modp = 1_000_000_007_usize;
    let mut dp = vec![vec![0_usize; 2]; d + 1];
    dp[0][0] = 1;
    for k_i in k.iter().copied() {
        let mut next = vec![vec![0_usize; 2]; d + 1];
        let k_i = (k_i as u8 - b'0') as usize;
        for j in 0..=d {
            for l in 0..=9 {
                let nj = (j + l) % d;
                next[nj][1] += dp[j][1];
                next[nj][1] %= modp;
                match l.cmp(&k_i) {
                    std::cmp::Ordering::Less => {
                        next[nj][1] += dp[j][0];
                        next[nj][1] %= modp;
                    }
                    std::cmp::Ordering::Equal => {
                        next[nj][0] += dp[j][0];
                        next[nj][0] %= modp;
                    }
                    std::cmp::Ordering::Greater => {
                        // do nothing
                    }
                }
            }
        }
        dp = next;
    }

    let ans = (dp[0][0] + dp[0][1] + modp - 1) % modp;
    println!("{}", ans);
}

今日のコミット。