geam1113’s diary

主にAtcoderのコンテストの備忘録を書きます。AtCoder緑と水色を行ったり来たりしています。

ARC129C Multiple of 7

解説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を求められます。

 

公式解説通りの実装

提出コード1

 

多角数定理による実装

提出コード2