三井住友信託銀行プログラミングコンテスト2019 D Lucky PIN
種類数を求める問題だが, よく考えると設定されうる暗証番号の種類数は高々1000種類のみである. よって少し見方を変え, ある暗証番号が設定されるかという問題を解くことを考える. これは文字列を前から走査することによって
$ O(N)
で解くことができる.
この操作を
$ 1000
回行うわけだが,
$ N = 30000
(最大)としても計算回数は
$ 3 × 10^7
回となり十分高速である.
実装例:
https://atcoder.jp/contests/sumitrust2019/submissions/20431344