D - Digits Parade ～右からDP, 左からDP～

Quiz

https://atcoder.jp/contests/abc135/tasks/abc135_d

内容

• 解法というか、左からDP, 右からDPのどちらでも解けますというメモです

解法

• 文字列の左からDP
• AC Code https://atcoder.jp/contests/abc135/submissions/6595777
• 公式解説と同じで、DPの添字がx10で求まる

ABCのDをAC. 文字列の右側からやると(10^100000) mod 13とか出てきちゃうけど、左からやると毎回x10で済むんだなぁ。1000人が通すのか・・・

— peroon_cp (@peroon_cp) July 28, 2019

昨日のD、stringの整数をmod取った値に変換するやつやったことあればやるだけなんだよな(前回のFの埋め込み)

— Cinnamoroll(シナモロール) (@Cinnamon_VR) July 28, 2019

解法2

• 文字列の右からDP
• AC Code https://atcoder.jp/contests/abc135/submissions/6590600
• こちらの方が小さい桁から確定させていくのでイメージしやすい
• しかし、添字を決める箇所で10¹⁰⁰⁰⁰⁰ mod 13を高速に計算する必要がある
• 一般に、a^b mod cは高速に求まる https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/fast-modular-exponentiation

• 上記に書いてあるとおりに実装し、bitsetも使って高速化したところACした

学び

• 大きな数字（文字列で表すレベル）のmodは左から1桁ずつ処理していくと楽