ペネトレーションしのべくん

さようなら、すべてのセキュリティエンジニア

【プログラミング】AtCoder ABC164-D の解法に関するメモ

プログラミング

はじめに

1 年以上ぶりの ABC は C 完でした。 D の理解にすごく苦労したので、メモを残します。

アプローチ

たくさんの解説記事を拝読しましたが、皆さん editorial と同じアプローチのようで、それを踏襲しました。大まかには以下のような感じです。

  • 1つ目の for 文で、 s の各区間の mod 2019 の結果の数を mods に保存する。
  • 2つ目の for 文で、 mods に格納された mod 2019 の結果が同一になる組み合わせの数を足し上げる。

atcoder.jp

s = input()[::-1]
v = 0
mods = [ 0 for i in range(2019) ]
mods[0] = 1
d = 1
 
for c in s:
    v += int(c) * d
    v %= 2019
    d *= 10
    d %= 2019
    mods[v] += 1
 
ans = 0
for n in mods:
    ans += (n * (n - 1)) // 2
 
print(ans)

なんで 10 と 2019 が互いに素だと、/ 10n を無視してよくなるの？

ここからは、私が個人的に理解できなかった部分の補足です。

この部分については、どの解説記事にも特に解説がなかったと思います。解説するまでもないことなのかもしれませんが、数学弱者が直感的にこの結果に辿り着くのは厳しかった……。

Twitterで明け方までうんうん唸っていたら、解説記事を投稿してくださっていたタムログさんが解説してくださいました。

※タムログさんの解説記事はこちら

タムログさんの例にのっかると、 2019 / 3 の mod 2019 を計算するときに、分母を無視すると 2019 ≡ 0 (mod 2019) ですが、分母を考慮に入れると 2019 / 3 = 693 ですから、 693 !≡ 0 (mod 2019)となって、結果が変わってしまう(分子だけだと合同だけど、分母込みだと合同でなくなる)わけです。これがなぜ起こるかというと、分母が 2019 と互いに素でない値だと、2019 の因数を除してしまうからですね。

以下は、分子を 20190 、分母を 10 もしくは 3 としたときの、それぞれの分母なし・ありでの合同式の真偽を確認したメモです。最後のほう、 6930 に見えますが 6730 です。

f:id:befs_anne:20200502200149j:plain

なんで mods[0] = 1 するの？

前述したような処理で解が求められるのは、「(区間A - 区間B) % 2019 ≡ 0 (mod 2019)」であるかどうかを、「区間A ≡ 区間B (mod 2019)」であることを検証することで求められるからです。各区間の mod 2019 の結果の中にはもちろん 0 も含まれるわけですが、区間 A が s[len(s-1)]、つまり s の右端の値を含む場合、区間 B は 0 ということになります。この場合の区間 B ついても区間のひとつとして扱い、0 ≡ 0 (mod 2019) としてカウントしなければ、仮に s の右端の値を含む区間 A の mod 2019 が 0 だった場合に、組み合わせの数が正しく計算されません。

なんで v %= 2019 するの？ mod の結果は別で保存したほうがよくない？

n 回目のループで mod しようがしまいが、 n+1 回目のループでの v %= 2019 の結果には影響を及ぼしません(mod 2019 の結果に再度 mod 2019 しても値は変わらない)。計算効率の観点から見ると、v に mod した値を使うことで、後述の d %= 2019 の処理と同様効率を高めていることになると言えそうです。

なんで d %= 2019 するの？していいの？

これをしないと、ループ毎に d が 10 ずつ増えていくので、そのまま乗じてしまうと桁数がかなり大きくなってしまって v %= 2019 の処理に時間がかかってしまうんですね(実際、これがないと TLE になりました)。これをして結果に影響が及ばないかどうかについては、「(3 * 10000) % 2019」 の結果と 「(3 * 1924) % 2019」(※) の結果が、どちらも 1734 であることを以て証明できている気がします。

※…10000 % 2019 = 1924

さいごに

緑コーダー目指して、解けない問題に真剣に向き合ってみました。ふつうに延べ 1 日くらい費やしました。しんどかったです。数学やアルゴリズムの基礎理解が乏しいので厳しい戦いが続きそうですが、強くなるためにやっていこうと思います。