9 N進法 Dif:131 ABC186 C：「AtCoder 凡人が『緑』になるための精選50問詳細解説」サンプル

この記事は拙著「AtCoder　凡人が『緑』になるための精選50問詳細解説」のサンプルです
価格：100円
kindle：https://www.amazon.co.jp/dp/B09C3TPQYV
booth(pdf)：https://sano192.booth.pm/items/3179185

前：https://qiita.com/sano192/items/95ed7094ff71400a2dce
次：https://qiita.com/sano192/items/1eb1ee760594502280fd

　
【目標】
・10進数からN進数への変換を実装できるようになる

【概要】
10進数から8進数への変換ができるかを問う問題。
10進数をN進数に変換して処理させる問題はC~D問題あたりでたまに出題される。変換の手順を覚え、実装できるようになろう。なぜ解説する手順でうまくいくのか、数学的にきちんと理解するのは難しいが、理解できていなくても問題は解けるので無理に理解する必要はない。

【方針】
制約は1<=N<=10^5であるため、1~Nまで全ての数について10進数表示、8進数表示それぞれに7を含むか確認しても余裕で間に合う。

問題はどのようにして1~Nまでの8進数表示を確認するか。
つまりどうすれば10進数を8進数に変換できるか、というところにある。

実はpythonには10進数xを8進数の文字列に変換してくれる関数
oct(x)
が存在する。これを使えばこの問題は一発で解けるのだが、その方法は8進数以外に応用がきかないため今回は使わない。

10進数を8進数に変換する場合、以下の操作を0になるまで繰り返す。
(1)8で割った余りを一番上の桁につける
(2)8で割った商に置き換える

と、言われてもよくわからないと思う。
具体的な数字で説明しよう。

「例：10進数の83を8進数に変換する場合」
(1)83を8で割った余り(83%8=3)を一番上の桁につける(3)
(2)83を8で割った商に置き換える(83//8=10)

(1)10を8で割った余り(10%8=2)を一番上の桁につける(23)
(2)10を8で割った商に置き換える(10//8=1)

(1)1を8で割った余り(1%8=1)を一番上の桁につける(123)
(2)1を8で割った商に置き換える(1//8=0)

0になったので終了。(123)
ゆえに10進数の83を8進数に変換すると123。

上記の方法は8の部分をNに変えれば、同じ手順で10進数をN進数に変換することができる。

なぜこの手順で変換できるか説明する。以下の内容は理解できていなくても問題を解くには困らないので、興味がない場合は飛ばして構わない。

そもそも8進数で表すということは10進数を0<=x1,x2,...xn<=7たるx1,x2,...,xnを使い、以下のように表すこと。

そして8進数表示とはxn、xn-1、...x1、x0を順に並べて書くということ。

例えば10進数の83ならば
83=18^2+28^1+3
と表せる。
つまり
x2=1
x1=2
x0=3
だから、10進数の83は8進数表示で123であることがわかる。

(1)83を8で割った余り(83%8=3)を一番上の桁につける(3)
83を8で割った余りというのはx0に対応する。
なぜならば
83=x28^2+x18^1+x0
と表すと、
右辺を8で割った余り=(x28^2+x18^1+x0)%8=x0
となるからだ。

(2)83を8で割った商に置き換える(83//8=10)
83=x28^2+x18^1+x0
両辺を8で割った商に置き換えると
10=x2*8^1+x1
となる。

(1)10を8で割った余り(10%8=2)を一番上の桁につける(23)
同じように考えれば10を8で割った余りというのはx1に対応する。
なぜならば
10=x28^1+x1
と表すと、
右辺を8で割った余り=(x28^1+x1)%8=x1
となるからだ。

(2)10を8で割った商に置き換える(10//8=1)
10=x2*8^1+x1
両辺を8で割った商に置き換えると
1=x2
となる。

(1)1を8で割った余り(1%8=1)を一番上の桁につける(123)
これも同様に考えると1を8で割った余りというのはx2に対応する。
なぜならば
1=x2
と表すと、
右辺を8で割った余り=(x2)%8=x2
となるからだ。

(2)1を8で割った商に置き換える(1//8=0)
1=x2
両辺を8で割った商に置き換えると
0=0
となる。
こうなったら終了。

【実装】
まず
「10進数表示で7を含むか？」
「8進数表示で7を含むか？」
を判定する関数をそれぞれ作ろう。

「10進数表示で7を含むか？」を判定する関数。
引数xを10進数で表した場合に、7を含むならTrue、そうでないならFalseを返す。
名前はjudge_tenとしよう。

def judge_ten(x):
    x=str(x)
    if "7" in x:
        return True
    else:
        return False

xを数値として受け取る。
xを文字列に変換。(“7”を含むか？の判定は文字列のほうが簡単に行えるため)
"7"を含むか判定。
・含むならTrueを返す。
・含まないならFalseを返す。
文字列に○○が含まれるか？は in を使って判定できる。

次に「8進数表示で7を含むか？」を判定する関数を作ろう。
引数xを8進数で表した場合に、7を含むならTrue、そうでないならFalseを返す。
名前はjudge_eightとしよう。

def judge_eight(x):

xの8進数表示をsとしよう。最初は空文字列にしておく。

    s=""

(1)8で割った余りを一番上の桁につける。
(2)8で割った商に置き換える。
これを0になるまで繰り返す。

    while x>0:
        s=str(x%8)+s
        x//=8

sが"7"を含むか判定。
・含むならTrueを返す。
・含まないならFalseを返す。

    if "7" in s:
        return True
    else:
        return False

これで
「10進数表示で7を含むか？」
「8進数表示で7を含むか？」
を判定する関数ができた。

入力を受け取る。

N=int(input())

「10進法で表しても8進法で表しても7を含まない数」をカウントする変数ansを作る。

ans=0

「10進法で表しても8進法で表しても7を含まない数」
というのはつまり
「10進数表示で7を含むか？」→False
かつ
「8進数表示で7を含むか？」→False
となる数。
1~Nについて条件を満たすか判定し、条件を満たす場合はansに+1カウントする。

for i in range(1,N+1):
    if judge_ten(i)==False and judge_eight(i)==False:
        ans+=1

答えを出力して終わり。

print(ans)

【コード全文】

def judge_ten(x):
    x=str(x)
    if "7" in x:
        return True
    else:
        return False

def judge_eight(x):
    s=""
    while x>0:
        s=str(x%8)+s
        x//=8
    if "7" in s:
        return True
    else:
        return False

N=int(input())

ans=0

for i in range(1,N+1):
    if judge_ten(i)==False and judge_eight(i)==False:
        ans+=1

print(ans)

この記事は拙著「AtCoder　凡人が『緑』になるための精選50問詳細解説」のサンプルです
価格：100円
kindle：https://www.amazon.co.jp/dp/B09C3TPQYV
booth(pdf)：https://sano192.booth.pm/items/3179185

前：https://qiita.com/sano192/items/95ed7094ff71400a2dce
次：https://qiita.com/sano192/items/1eb1ee760594502280fd