緑コーダーの参加記録: ABC186 C - Unlucky 7

問題

https://atcoder.jp/contests/abc186/tasks/abc186_c

解法

開く

$1$ から $N$ までループして、 $10$ 進法で表しても $8$ 進法で表しても $7$ を含まない数の個数を求める。

解説

ループが必要になりそうな問題では、まず制約を見ます。制約を見ると $1 \le N \le 10^5$ と書いてあります。
計算量的に考えると、 $O(N)$ や $O(N \log N)$ だと間に合い、 $O(N^2)$ だと間に合わないという感じです。
$O(N \log N)$ が間に合うので、多くの言語に標準で付いている基数変換機能を使うことにします。この機能は多くの場合 $O(\log N)$ 程度で計算することができ、これを $1$ から $N$ に対して繰り返すと $O(N \log N)$ となります。
遅めの言語だと少々心配になるかもしれませんが、そこはお使いの言語の処理速度を信じて進みましょう。

ポイント

• 制約を見る

コード

abc186_c.rb

N = gets.to_i
puts (1 .. N).count { |i| !i.to_s(10).include?(?7) && !i.to_s(8).include?(?7) }