ひらめの日常

日常のメモをつらつらと

累積和

AtCoder: ABC164-D Multiple of 2019 (400)

問題はこちら atcoder.jp 1から9までの数字からのみなる、文字列 が与えられる。 次の条件を満たす整数の組 の総数を求めよ。 条件: の 文字目から 文字目までを10進法の整数としてみると、この整数は2019の倍数である。 制約: 考え方 はじめに を二重ループ…

AtCoder: ABC146-E Rem of Sum is Num (500)

問題はこちら atcoder.jp 長さ の整数列 と正の整数 が与えられる。 の空でない連続する部分列であって、要素の和を で割った余りが要素の数と等しくなるものの数を求めよ。 以下は0-indexで話を進める。 考え方 要素の和の余りに関する問題なので、とりあえ…

AtCoder: ABC130-E Common Subsequence (500)

Common Subsequence 問題はこちら atcoder.jp この問題はLCS(Longest common subsequence)と関わりが深いのでまずはそれから書いてみる。 LCS 最長の共通部分列の長さを求めてくださいというのが典型的な問題。次のような例を考えてみる。 s: abcd t: acfed …