1 of 13

N:Count Same Number

FA(全体): kotatsugame_arigatou (31:05)

FA(オンサイト): kotatsugame_arigatou (31:05)

AC/Try: 12/17

原案:Taiki0715

2 of 13

問題概要

Nが与えられるのでN以下の正の整数で桁に現れる5未満の種類数と5以上の種類数が等しいものはいくつあるか？

3 of 13

制約

1≤N<10^(5×10^5)
問題には書いてないが数字の種類数をd=10とする。

4 of 13

TLE解法

DP[i][j][S]=Nのi桁目まで見て未満フラグとleading zeroの状態がjでこれまでに出現した数の集合がS

これはO(Nd×2^d)で間に合わない。

5 of 13

想定解

以下の3つに場合分けする。

ちょうどN
leading zeroがなく、N未満
leading zeroが1個以上ある

6 of 13

場合分け①ちょうどN

普通に数えて判定するだけ

7 of 13

場合分け②leading zeroがなく、N未満

上から見ていってi桁目でN未満が初めて確定したとする。

９９８２４４３５３

９９８２？？？？？

０〜３

8 of 13

場合分け②leading zeroがなく、N未満

この時、i桁目より下の桁は０から９まで自由に決められる。

９９８２４４３５３

９９８２？？？？？

０〜３

０〜９

9 of 13

場合分け②leading zeroがなく、N未満

i桁目の数字と何種類出現するかを固定するとi+1桁目以降の数字の決め方は包除原理でO(d)で求まる。

９９８２４４３５３

９９８２２？？？？

10 of 13

場合分け②leading zeroがなく、N未満

例(9982まで確定し、その次を2にした)

現在5未満は1種類、5以上は2種類なので種類数として2から5まで全探索する。（種類数として3を選択したとする）

5未満の残り0134から2個、5以上の残り567から1個を必ず選ぶ数として決める。この「必ず選ぶ」に違反するかどうかで包除をすると何通りあるか計算できる。

９９８２２？？？？

11 of 13

場合分け②leading zeroがなく、N未満

「i桁目を固定し」の部分はこれまでに出現した数字、出現していない５未満の数字、出現していない５以上の数字の３通りしか包除原理の係数を考えなくて良いので全体でO(N×d^2)でできる。

９９８２４４３５３

９９８２２？？？？

12 of 13

場合分け③leading zeroが1個以上ある

桁数が|N|未満で各桁が0から9まで自由に使えるので場合分け②と同じようにできる。

13 of 13

計算量

場合分け①がO(N)

場合分け②がO(N×d^2)

場合分け③がO(N×d^2)

全体でO(N×d^2)