問題リンク atcoder.jp 問題概要 長さNの数列\(A_1,,,A_N\)が与えられる。 \(1 \leqq L \leqq R \leqq N\)に対し、\(f(L,R)\)を\(A_L\)から\(A_R\)までの数を使って和をSにする組み合わせの総数とする。 \(f(L,R)\)の総和を求めよ。 解法 各組み合わせに対し…

問題リンク atcoder.jp 問題概要 縦H、横Wマスのチョコレートがあり、一部のマスはホワイトチョコレートである。 このチョコを縦または横に一直線に切ることを何回か繰り返して、各部分に含まれるチョコレートがK個以下になるようにしたい。 切る回数の最小…

問題リンク atcoder.jp 問題概要 数直線上にN体のロボットがいる。i番目のロボットは座標\(X_i\)にいて、起動させると正の方向に\(D_i\)動いた後、取り除かれる。 動いている途中に他のロボットに接触すると、そのロボットも起動する。 いくつかのロボットを…

問題リンク atcoder.jp 問題概要 0～9からなる文字列Sと素数Pが与えられる。 Sの連続部分列で、10進数の数とみなした時にPの倍数となるものはいくつあるか。 解法 P=2とP=5は一番下の1桁を見て数えられるので除いておく。 Pが10と互いに素な場合を考える。考…