競プロ典型90問　★2問題コード解説[5]

はじめに

競プロ典型90問　★2問題のコード解説は今回で最後になります。
難易度の目安として、★2問題が安定して解けるようになれば茶色くらいの実力はあるとされています。やっとスタートラインに立てたって感じですね。本当のスタートラインはレートで茶色になったときの気もしますが…。
何はともあれ本日も頑張っていきましょう！

はじめに
競プロ典型90問
067 - Base 8 to 9（★2）
078 - Easy Graph Problem（★2）
おわりに

競プロ典型90問

atcoder.jp

067 - Base 8 to 9（★2）

この問題は、8進法の整数Nについて、まずは9進法に直します。そして8を5に変換します。9進法に出てくる数字で一番大きい数字は8なので、それを5に直すということは、出てくる一番大きい数字が7になるということであり、8進法として解釈することが出来ます。それで得た8進法の整数について同様の操作をK回行う、という問題です。8進数を9進数に直接変換するのは大変そうですよね。
解法は以下のように表せます。

8進数を10進数に変換する。
10進数を9進数に変換する。
8 -> 5に変換する。

ここで便利なのがint関数です。int(str(8進数), 8)とすることで、8進数を10進数に変換することが出来ます。10進数を9進数に変換する方法は、数学Aで学習したと思いますが、9で割った余りを下の桁から並べていくことで実現できます。

以下、コードになります。

n,k = map(int, input().split(" "))
 
number8 = n
 
def number10_to_number9(num10):
    num9_list = []
    while True:
        num9_list.append(num10 % 9)
        num10 //= 9
        if num10 == 0:
            num9_list.reverse()
            return "".join(map(str,num9_list))
 
for i in range(k):
    number10 = int(str(number8), 8)
    number9 = number10_to_number9(number10) #str型
    number8 = number9.replace("8", "5")
 
print(number8)

また、例のごとくこちらのコードもPyPy3で実行しています。再帰が入らないコードはPyPyを使うのが丸いんじゃないかと思っています。

078 - Easy Graph Problem（★2）

N頂点M辺の無向グラフが与えられており、ある頂点より頂点番号が小さい隣接頂点が1つ存在するような頂点の数を求める問題です。接続のが与えられる都度、頂点番号をキーとしたディクショナリの要素に、隣接する頂点を追加します。この時、自身の頂点番号より頂点番号が低いときのみ、リストに追加してください。
なお、この問題では頂点の数が与えられているため、あらかじめdict型を用意するということもできましたが、defaultdictを使用しております。dafaultdictは存在しないキーが検索された場合、そのキーの要素がデフォルトのものに設定されるというものです。

from collections import defaultdict
n, m = map(int, input().split(" "))
 
d = defaultdict(lambda:[])
 
for i in range(m):
    a, b = map(int, input().split(" "))
 
    if a < b:
        d[b].append(a)
    elif b < a:
        d[a].append(b)
 
cnt = 0
for key, val in d.items():
    if len(val) == 1:
        cnt += 1
print(cnt)