🍀

# パナソニックプログラミングコンテスト（AtCoder Beginner Contest 186） C - Unlucky 7

2021/01/22に公開

文字列

パナソニックプログラミングコンテスト（AtCoder Beginner Contest 186） C - Unlucky 7

問題へのリンク

問題概要

$1$ 以上 $N$ 以下の整数のうち、10進数法で表しても8進数法で表しても7を含まないような数はいくつあるか？

制約

$1 \leq N \leq 10^5$

ABC中の解答

以前の問題ででてきた内包の問題だと思った。つまり (7を含むものの和集合) = (10進数法で表して7を含むもの) + (8進数法で表して7を含むもの) - (10, 8進数法どちらで表しても7を含むもの) を求めて、全体 $N$ から引くことで (10進数法で表しても8進数法で表しても7を含まないような数) を求めた。(公式解法を見ればわかるがもっと簡単にできる)
8進数に7が含まれているかは oct 関数を用いて10進数を8進数の文字列に変化して調べた。

N = int(input())

cnt_10 = 0
cnt_8 = 0
cnt_and = 0
for i in range(1, N + 1):
    if '7' in list(str(i)):
        cnt_10 += 1
    if '7' in list(oct(i)[2:]):
        cnt_8 += 1
    if '7' in list(str(i)) and '7' in list(oct(i)[2:]):
        cnt_and += 1
ans = N - cnt_10 - cnt_8 + cnt_and
print(ans)

公式解法1

$N$ の制約が $1 \leq N \leq 10^5$ であるのですべての数に対して (10進数法で表しても8進数法で表しても7を含まないような数) であるかのチェックをするだけでよい。ABC中の解答のように内包を用いるのはチェックが難しいパターンの時にすればよい。

N = int(input())

ans = 0
for i in range(1, N + 1):
    if '7' not in str(i) and '7' not in oct(i):
        ans += 1
print(ans)