ABC 164 D - Multiple of 2019

高校のときから整数問題苦手だったんだけど10年以上経って改めて苦しめられている... ちなみに4月中に茶色くらいはいけるだろうって言ってたのはなんとか滑り込みで今回達成しました.

初手の方針

そもそも整数問題っていうことに気づかなかった. 2020じゃなくてあえて2019になっていたので意図は感じつつも素数でもないしな？とか思ってスルーした. Nが $2*10^{5}$ なので $O(N^{2})$ だと間に合わないから本番中はしゃくとり法とかを検討していた.

正答

Submission #12439013 - AtCoder Beginner Contest 164

冒頭で述べた通りに整数問題に帰着できる.

解答をもう少し噛み砕いてみていく.

あるn桁の数字(問題では文字列)が以下のように与えられたとき

$a_{1},a_{2},...,a_{i-1},a_{i},a_{i+1},...a_{j-1},a_{j},a_{j+1},...a_{n}$

$T_{k}$ を以下のように定義するというのが解説に書いてあるとおり,ここまでは問題ない.

$a_{n}+10a_{n-1}+100a_{n-2}+...+10^{n-k-1}a_{k+1}$

同様にi-1,jについて(区間[i,j]を考えたいので便宜上i-1にしている)

$T_{i-1} = a_{n}+10a_{n-1}+100a_{n-2}+...+10^{n-i-2}a_{i}$

$T_{j} = a_{n}+10a_{n-1}+100a_{n-2}+...+10^{n-j-1}a_{j+1}$

$T_{i-1}$ と $T_{j}$ の差を取ると

$T_{i-1}-T{j} = 10^{n-j}a_{j}+10^{n-j+1}a_{j-1}+...+10^{n-i-2}a_{i}\\ T_{i-1}-T{j} = 10^{n-j}(a_{j}+10a_{j-1}+...+10^{j-i-2}a_{i})$

両辺を $10^{n-j}$ で割ると区間[i,j]の整数は

$T_{ij} = 10^{j-n}(T_{i-1} - T_{j})$

合同式の差の性質と冒頭の $gcd(2019,10)=1$ という考察から $T_{ij}$ が2019で割り切れるとき

$T_{i-1} ≡ T_{j} (mod2019)$

以上のことを文章化すると区間[i,j]の整数が2019で割り切れるためには $T_{i-1}$ と $T_{j}$ を2019で割った余りが等しければ良いということになる.直感的にしっくりこないのが辛いところ.

（注）
解答にある[tex: 10^{n-j}(T\_{i-1} - T\_{j})]が出てこなかったので間違いがあるかもしれない.
計算ミス見つけた方はご指摘ください.

また今回桁数が $2*10^{5}$ なので愚直に $T_{k}$ のmodを計算することができない点に注意が必要. $T_{k+1}$ は $T_{k}$ を用いて以下のように表すことができる.

$T_{k+1} = 10^{n-k}a_{k+2} + T_{k}$

合同式の和の性質を利用すると $T_{k+1} mod2019$ は $T_{k+1} mod2019 = 10^{n-k}a_{k+2} mod2019 + T_{k} mod2019$ となる.

実例

入力例1を例にとると

1817181712114
T13=0
T12=4
T11=14
T10=114
T9=2114
T8=12114
T7=712114
T6=1712114
T5=81712114
T4=181712114
T3=7181712114
T2=17181712114
T1=817181712114
T0=1817181712114

以下mod2019
T13≡0
T12≡4
T11≡14
T10≡114
T9=95
T8=0
T7=1426
T6=2
T5=1165
T4=95
T3=1917
T2=1924
T1=465
T0=1165

法2019において余りが 0になる整数はT13,T8 95になる整数はT9,T4 1165になる整数はT5,T0 となる.

よって条件を満たす(i,j)の数はそれぞれ

$0-> {}_{2}C_{2}\\ 95-> {}_{2}C_{2}\\ 1165-> {}_{2}C_{2}$

となり3と求まる.

振り返り

整数問題は気づくか気づかないかで,これは学生の時の演習量やもともとのセンスで決まってしまうところなので,典型パターンがあれば押さえつつ暫くは問題を解くしかなさそう.すぐに結果につながらない気配なので難しいところである.

問題を見たときに整数問題であると気づくことと,とりあえず次の問題に目を通すということも必要だと感じる(しゃくとり法検討してる時点で望み薄すぎた)

sky’s 雑記

主にAndroidとサーバーサイドの技術について記事を書きます

ABC 164 D - Multiple of 2019

初手の方針

正答

実例

振り返り