AtCoder ABC 158
March 12, 2020
ABC158に参加した。自分用メモ。
A | B | C | D | E | F |
---|---|---|---|---|---|
o | o | o | o | x | x |
A~Dは特に問題なく解けた。
E-Divisible Substring
ある非負整数を表す文字列と素数Pが与えられ、その文字列の連続する部分文字列が表す数でPの倍数となっているものの個数を数える問題。 連続する部分文字列の個数は、文字列の長さをNとしてとなるので、すべての部分文字列について全探索すると制限時間に間に合わない。
文字列が表す数の大きさが()だと勘違いして、素数の倍数を前計算してローリングハッシュ法で答えを求めるなどしてしまった。そもそもこの制約なら全探索で間に合う。A~D問題くらいだと考察ほとんどいらない場合が多いけど、Eあたりからは必要になってくるので、考察をすっぽぬかす癖をなおしたい。
考察
だいたい最初は解説と同じだけど、累積和求めたあとに実際数えるとこがいまいちわからなかったので、書き残しておく。
まず連続する部分文字列の表す数が条件を満たす場合の性質を調べたい。以降、連続する部分文字列を単に部分文字列と書くことにする。 与えられた文字列が表す数は、右端から数えてi番目の数をとすると、
と表すことができるので、l番目からr番目()の文字からなる数は、
で表される。この数が与えられた素数で割り切れるかどうかを知りたい。
が10と互いに素でないとき、これを満たす素数は2か5である。が2か5であれば、部分文字列の右端の数が2か5で割り切れれば、その部分文字列が表す数がで割り切れるかわかるので、で答えを求められる。
が10と互いに素である場合について考える。
ここで解説と同じように、
と定義すると、
となる。つまり、部分文字列の左端を固定したとき、問題の条件を満たすように部分文字列の右端を決めるには、上記の式を満たす累積和を持つインデックスをの右側から見つければいい。問題の答えとして欲しいものは、条件を満たす部分文字列の個数であるから、(今回は配列でも問題ないが)mapで累積和の分布を記憶しつつ、を文字列の右端から左端まで動かせば、それぞれのに対して、で条件を満たすの個数が数えられる。