🐶

ABC234解説：本番でACできた問題＋1問（Python）

2022/02/02に公開

Python

A - Weird Function

実直に関数を定義します。
計算式は問題文からコピペすると間違えないです。

a.py

def f(x):
    return x**2 + 2*x + 3

t = int(input())
print(f(f(f(t)+t)+f(f(t))))

B - Longest Segment

これも関数を定義する問題です。
2点 $(x_{1}, y_{1}), (x_{2}, y_{2})$ の距離（ユークリッド距離）は $\sqrt{(x_{1}-x_{2})^2+(y_{1}-y_{2})^2}$ です。

b.py


N = int(input())
xy = [tuple(map(int, input().split())) for _ in range(N)]


def dist(x1, y1, x2, y2):
    return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5


ans = 0
for i in range(N):
    for j in range(i + 1, N):
        x1, y1 = xy[i]
        x2, y2 = xy[j]
        ans = max(ans, dist(x1, y1, x2, y2))

print(ans)

Python3.8からmathモジュールにdist関数が入ったので、これを用いても大丈夫です。

math_dist.py

from math import dist

N = int(input())
xy = [tuple(map(int, input().split())) for _ in range(N)]

ans = 0
for i in range(N):
    for j in range(i + 1, N):
        ans = max(ans, dist(xy[i], xy[j]))

print(ans)

C - Happy New Year!

0,2のみからなる正整数を小さい順に並べると以下のようになります。

2, 20, 22, 200, 202, 220, 222, 2000, 2002, 2020, 2022, 2200, 2202, 2220, 2222...

これは2進数表記の2倍に対応していることがわかります。

# 2進数
1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111...

そのため、2進数表記に変換したものを2倍したものが答えになります。

2進数への変換はf文字列を使うと簡潔に記載できます。

print(f"{5:b}")
# 101

c.py

N = int(input())
print(int(f"{N:b}") * 2)

D - Prefix K-th Max

優先度付きキューを使えるか、という問題です。
優先度付きキューを使うことで、区間の最小値（最大値）の取り出しと要素の挿入をO(logN)で行うことができます。
また、最小値は常に0番目に格納されます。

本問では新しい要素の追加と以前の最小値の取り出しをしたのちに、更新された最小値を参照する操作を繰り返します。

d.py

from heapq import heapify, heappush, heappop

N, K = list(map(int, input().split()))
P = list(map(int, input().split()))

hq = P[:K]
heapify(hq)
print(hq[0]) # 現在の最小値を表示

for x in P[K:]:
    heappush(hq, x) # 新しい要素の追加
    _ = heappop(hq) # 以前の最小値の削除
    print(hq[0])    # 現在の最小値を表示

E - Arithmetic Number

競プロの典型的な考察として、制約の両端を考えます。

制約の最大値である $10^{17}$ 、つまり18桁の正の整数で等差数はいくつあるかを見てみると、以下のものしかないことがわかります。

111111111111111111
222222222222222222
333333333333333333
444444444444444444
555555555555555555
666666666666666666
777777777777777777
888888888888888888
999999999999999999

11桁以上の正の整数の等差数は、上記のように111...111, 222...222..999...999の1桁あたり9通りしかありません。

このことから、等差数の数は実はかなり少ないのではと思いつくことができれば、本問題の攻略の糸口が見えてきます。

次に、等差数を生成する実装を考えます。
1,2桁目まではすべての数が等差数なので、それ以外を考えます。

初項(左端の桁の値:a1)は{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}、公差(d)は{-9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}、桁数(digits)は{3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18}となります。

ここで321という公差-1の等差数は123という公差+1の等差数を反転させたものなので、公差は{0-9}までの値を考えて、公差が負の場合は反転を行えばよいことになります。

また、初項1、公差6、桁数3の数列は1, 7, 13となり、末項が10以上のものは等差数ではなくなるため、考慮しないことにします。
なお末項は初項＋公差*(桁数-1)で求められます。

最後に、range関数の第3引数(step)に0を渡すことができないため、公差が0の場合は条件分岐をします。
初項を桁数分掛け算して表示するという形で対応します。

e.py

X = int(input())

if len(str(X)) <= 2:
    print(X)
    exit()

ans = []
for a1 in range(10):
    for d in range(10):
        for digits in range(3, 19):
            an = a1 + d * (digits - 1)
            if an >= 10:  # 末項が10以上のものは考慮しません
                continue
            if d == 0: # 公差が0の場合にはrange関数が使えないので分岐します
                ans.append(int("".join(map(str, [a1] * digits))))
                continue
            A = []
            for a in range(a1, an + 1, d): # 初項a1、末項an、公差dとなる等差数列を作ります
                A.append(a)
            A = "".join(map(str, A))
            ans.append(int(A))
            ans.append(int(A[::-1])) # 反転することで公差が負の等差数を得ます

ans.sort()

for x in ans:
    if x >= X:
        print(x)
        exit()

A - Weird Function

B - Longest Segment

C - Happy New Year!

D - Prefix K-th Max

E - Arithmetic Number

Discussion