[ABC273 Python]パナソニックグループプログラミングコンテスト2022（AtCoder Beginner Contest 273） A～C問題Python解説

ABC273のA~C問題をPythonで解説します。
ミスやご質問等ありましたら、コメントにてご連絡ください。

A問題

A - A Recursive Function

N = int(input())
f = [0 for i in range(11)]
f[0] = 1
for i in range(1, 11):
    f[i] = i*f[i-1]
print(f[N])

0<=N<=10なので、全部試しても大丈夫です。
問題文通りに解いていくと、
f(0) = 1
f(1) = 1 × f(0) = 1
f(2) = 2 × f(1) = 2
f(3) = 3 × f(2) = 3
…

という風になっているので、
0～10までリストfにf(i)を保存していけば、
最後にf(N)を取り出すことで回答することができます。

B問題

B - Broken Rounding

X, K = map(int, input().split())
from decimal import Decimal, ROUND_HALF_UP
y = 0
for i in range(K):
    y = f"1E{i+1}"
    X = Decimal(str(X)).quantize(Decimal(y), rounding=ROUND_HALF_UP)
print(int(X))

Pyhonには四捨五入にround関数がありますが、
これは正確ではありません。
正確な四捨五入をしたければ、
以下を使います。

Pythonで整数や小数を四捨五入する：roundよりもDecimalを使う（銀行家の丸めに注意しよう） - MathPython

四捨五入する桁については、
i = 0,1,…..,K-1について10^iとなりますので、
1の位、10の位、100の位、…と変換できます。
ただ、記事にも記載してありますが、
引数の所の「Decimal()」は1000などの整数型ではなく、
桁数をEを用いて表した書き方に直す必要があります。
10は1E1、
100は1E2
となります。

これを作成するためにyを作成し、
毎回Xを四捨五入すればいいということになります。
最後に整数型に直します。

C問題

C - (K+1)-th Largest Number

N = int(input())
A = list(map(int, input().split()))
A_sort = list(set(A))
A_sort_len = len(A_sort)
A_sort.sort()
# print(A, A_sort)
import bisect
l = [0 for i in range(N)]
for i in range(N):
    l[A_sort_len - bisect.bisect_right(A_sort, A[i])] += 1

for i in l:
    print(i)

Nが大きいので単純に探すとTLEになります。
テーマは二分探索法です。

二分探索法はある整数がリストの中のどの位置にあるのかを高速に取得することができる手法です。
例えばリスト=[1,2,3,4,5]、x = 3だとすると、
bisect.bisect(リスト, x) = 3となります。
この場合はリストの中のどこにXが入るかを表しています。

まずは、問題文から種類数に着目する必要があるので、
リストAをかぶりをなくすset型に直します。
また、二分探索法を使うためにリストをsortしておきます。

二分探索法ではindex値を取得できるため、Aiよりも大きい種類数を数える場合は全体数からindex値を引くことで取得できます。

ちょうどK種類のものを確認するため、
整数iについてリストlを作成しておき、
l[K]+=1することで、回答できます。