AtCoder Beginner Contest(ABC) 193 C - Unexpressed の解説

初めに

この間のAtCoder Beginner Contest(ABC)のC問題が解けなかったので、復習を兼ねて簡単な解説を書きます。 使用言語はpythonを想定しています。

C - Unexpressedの問題文

整数が与えられます。以上以下の整数のうち、以上の整数を用いてと表せないものはいくつあるでしょうか？ ただし、は整数でである。

解答までの道のり

まずは問題文をよく見る

この問題分を見て私みたいな素人が真っ先に思いつくのがありうるに対してが以下かどうかをカウントするという方法です。 しかし、競プロでは秒で程度しか計算できないため、今回のという制約の中ではこの方法は取れません。 よって、もう少しスマートな解法を見つける必要があります。

実験してみる

スマートな解法を見つけるために実験をします。 とりあえず20までの整数を並べて考えてみましょう。

並べてみてわかることは、

• で表せる数は少ない
• 複数ので表せる数もある

ということです。 これらをもとに解答を考えてみましょう。

解答の道筋を考える

まずで表せる数は少ないということから考えてみましょう。 で表せる数は少ないということからは、 工夫して条件を絞れば全探索ができるかもしれないという事がわかります。

早速条件を絞ってみましょう。

まずについて、なので、が成り立ちます。

よってということがわかります。

なので、であり、計算量的には問題ありません。

次に、について、かつなので、 が成り立ちます。

なので、であり、計算量的には問題ありません。

更に、複数ので表せる数もあるということを考えてみましょう。 今回のケースでは、重複をカウントはしないということは問題文からわかります。 重複をカウントしないといったら・・・setですね。 よって、setに値を入れていくことでで表せる数をカウントできるとわかります。

コーディング

前項で解答の道筋がわかったので、コーディングしてみましょう。

import math
 
N = int(input())
 
# a**2 <= a**b <= N --> a <= N**0.5
max_a = int(N**0.5) + 1
# a**b <= N --> b <= log_a(N) <= log_2(N)
max_b = int(math.log2(N)) + 1
 
s = set() # 2**4 と 4**2 のような重複を消したい
for a in range(2, max_a):
    for b in range(2, max_b):
        val = a**b
        if val > N:
            break
        s.add(val)
 
print(N-len(s))

これが解答となります。

感想

いざ解答を考えてみると、なんでこんな問題がわからなかったのか・・・となりますね。 実験 → 解答の草案 という流れを着実に考えれば容易に解けた問題だと思います。 同じ轍（てつ）は踏まないようにするぞ！