水色プログラミング

競プロで解いた問題の記録,ゲーム制作の進捗など...

AtCoder Beginner Contest 105:D - Candy Distribution

問題

D - Candy Distribution

N 個の箱があり,それぞれ A_i (1 <= i <= N) 個キャンディーが入っている.ここで,任意の個数の連続する箱を選び,それらの箱に入っているキャンディーの合計が M で割り切れるようにしたい.連続する箱の選び方は何通りあるか.

解法

まず,和の mod は mod の和なので A_i を全て mod M し,累積和を取る.ここで,累積和をとる段階でも mod M する(最初に累積和をとってから mod M の方がスマート).ここで,A_i = A_j な i, j の組が見つかればその組は問題に当てはまる選び方になる.

この i, j の組を高速に求めたいので,map で A_i の値をカウントしておき,A_i ごとに Comb( A_i の個数, 2) をすればよい.あとは全ての A_i について同様に計算し,それらの和が答えになる.ここで,A_i = 0 の時は i, i も選び方に入るので注意.

解答

Submission #3066597 - AtCoder Beginner Contest 105

1発 AC だったのでよかった.

f:id:babcs2035:20180824220127p:plain

gist.github.com