pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Educational Codeforces Round 8 D. Magic Numbers

最初に通した解法、嘘っぽいのにどうして通ったんだろう。

codeforces.com

解法

桁 DP で解ける。

  • dp[ 上から i 桁目まで確定 ][ b 未満が確定 ][ a 超えが確定 ][ 0 以外を使ったか ][ 上からの桁数の偶奇 ][ mod M ] := この状態に至るパターン数

以下のことに注意したい。

  • 0001 と 1 のように、leading zero を認めると上からの桁数の偶奇が異なる場合がある
  • D=0 のとき、 00001020 のように leading zero 部では 0 が自由に使える

less フラグと more フラグを使うという手もあることを他人のコードを見て初めて気がついた。よく考えると当たり前だが、less だけの方に慣れすぎてて気が付かなかった。


雑に書いたら TLE したので、遷移元が 0 のときは弾くようにした。

Educational Codeforces Round 8 D. Magic Numbers

more フラグは良い発見だった。