【ABC114】C - 755

問題概要

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

制約

1 <= N < 10⁹

考察

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

おおまかな工程

ループ変数はi.

1. iを4進数に変換する(tobase4).
2. それが'1', '2', '3'を含んでおり, かつ'0'を含んでいなければ残りの処理を続行(check).
3. '1'を'3', '2'を'5', '3'を'7'に変えたとき(変換の順序に注意), それがNより大きいなら終了. そうでないならres++.

ACコード(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(†埋め込み†)