問題概要
$1$以上$N$以下の整数のうち, 7, 5, 3が1回以上現れ, なおかつそれら以外の数字が現れないものの個数を求めよ.
制約
- $1 \leq N < 10^9$
考察
bit全探索的なノリで数えれば良さそう.
とりあえず3進法で書いてみたけど, 頭の0に対応するのめんどくさそうだったから4進法に書き直した.
おおまかな工程
ループ変数は$i$.
- $i$を4進数に変換する(
tobase4). - それが
1,2,3を含んでおり, かつ0を含んでいなければ残りの処理を続行(check). 1を3,2を5,3を7に変えたとき(変換の順序に注意), それが$N$より大きいなら終了. そうでないならres++.
提出コード(Python3🐍)
n = int(input())
def tobase4(num):
ans = ''
while num>0:
ans += str(num%4)
num //= 4
return ans[::-1]
def check(s):
if '1' in s and '2' in s and '3' in s and '0' not in s:
return True
return False
def conv(s):
s = s.replace('2','5')
s = s.replace('3','7')
s = s.replace('1','3')
return s
res = 0
for i in range(10**9):
s = tobase4(i)
if not check(s):
continue
s = int(conv(s))
if n < s:
break
res += 1
print(res)
別解
- DFS(解説はこれ)
itertools.product- 桁DP
- †埋め込み†