問題概要

$1$以上$N$以下の整数のうち, 7, 5, 3が 1 回以上現れ, なおかつそれら以外の数字が現れないものの個数を求めよ.

制約

  • $1 \leq N < 10^9$

考察

bit 全探索的なノリで数えれば良さそう. とりあえず 3 進法で書いてみたけど, 頭の0に対応するのめんどくさそうだったから 4 進法に書き直した.

おおまかな工程

ループ変数は$i$.

  1. $i$を 4 進数に変換する(tobase4).
  2. それが1, 2, 3を含んでおり, かつ0を含んでいなければ残りの処理を続行(check).
  3. 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)

別解

  1. DFS(解説はこれ)
  2. itertools.product
  3. 桁 DP
  4. †埋め込み†