ARC129C Multiple of 7 - geam1113’s diary

解説AC

ABCのこの問題のように類題は出題されています。しかし、このように逆に構成できることは思いつきませんでした。

右からi桁目までを10進数の整数 $S_i$ としたとき、 $j\lt i$ なる区間(j,i]を10進数としたものが7の倍数となる条件は、

$(S_i - S_j) \times 10^{-j} \equiv 0\ mod\ 7$

を満たすことです。なお、10と7は互いに素なので逆元を持つことが保証されます。

式を整理すると、

$S_i \equiv S_j\ mod\ 7$

となるので、下から順に $S_i \ mod\ 7$ を計算して、余りがkとなるインデックスの個数をカウントします。

それを $c_k$ とすると、ここから2つ選ぶとその区間が表す10進数は7の倍数となるの

で、

$_{c_k}C_{2}=\frac{c_k(c_k-1)}{2}$
となり、これをk=0〜6まで足すと、すべての組みが得られます。

今回はこれを逆に構成する問題でした。

公式解説のように高々7個の $_{c_k}C_{2}=\frac{c_k(c_k-1)}{2}$ で解を構成できることにどうやったら気づけるか考えてみます。

構成部分以外の考え方は過去に出題例があるので、そこから当たりをつけて、実際に7回の操作でNを0にできるか、実装して確認してみるのが一案です。

もし、公式解説にある多角数定理を知っていれば、

$N=\frac{a(a-1)}{2} + \frac{b(b-1)}{2} + \frac{c(c-1)}{2}$
を満たすa,b,cを求める問題になり、

$10^6$ 以下の三角数は多くとも2000個は超えないので、

・予めi=1〜2000までの三角数を求めてハッシュマップなどに記録しておく

・a,bを全探索し、

$c=N-\frac{a(a-1)}{2}-\frac{b(b-1)}{2}$
を満たすcが存在するかハッシュマップで調べる

ことによって求めれるので、解を構成する余り3つを $10^6$ くらいの計算量で得られます。

ちなみにi文字目の求め方ですが、

$S_{i-1}\ mod\ 7$ をrとし、i文字目に整数xを設定し、 $S_i\ mod\ 7$ をdにしたいとします。

その時、

$r+x\times 10^{i-1}\equiv d\ mod\ 7$
が成り立つので、

$x\equiv (r-d)\times (10^{-1})^{i-1}\ mod\ 7$

とすると、整数xを求められます。

公式解説通りの実装

多角数定理による実装