AtCoder Beginner Contest 161の感想

AtCoder

2020.04.042020.04.14

ABC161に参加した。

AtCoder Beginner Contest 161 - AtCoder

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

A – ABC Swap

順番に入れ替えるだけ。

x, y, z = map(int, input().split())

x, y = y, x
x, z = z, x

print(x, y, z)

B – Popular Vote

Aをソートし、大きい方から与えられた条件をチェックする。

n, m = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse=True)

flag = True
total = sum(a)

for i in range(m):
    if a[i] < total / (4 * m):
        flag = False
        break

print('Yes') if flag else print('No')

C – Replacing Integer

xとKの差の絶対値に置き換えるということは、大きい方から小さい方を引く、ということと等しい。

これを無限回繰り返していくと引き算が出来なくなってしまう、つまり割り算した時の余りと等しくなる。

まず割り算した時の余りを求め、その後に差と余りのどちらか小さい方が答え。

n, k = map(int, input().split())

n %= k
n = min(n, abs(n - k))
print(n)

D – Lunlun Number

幅優先探索で総当りする。

制約が1<=K<=10^5、入力例4が最大値の100000、出力例4が3234566667となっており、最大10桁まで探索すれば良いことが分かる。

キューは1〜10の10個の値から開始し、条件に合う数値を右側に足していく。

数値として扱うと記述がややこしいので、文字列として扱った。

from collections import deque

k = int(input())
limit = 10

start = [i for i in range(1, 10)]
q = deque(start)
ans = []

while q:
    cur = q.popleft()
    if len(str(cur)) > 11:
        continue
    ans.append(cur)
    r = str(cur)[-1]
    if r == '0':
        add = ['0', '1']
    elif r == '9':
        add = ['8', '9']
    else:
        add = [str(int(r) - 1), str(int(r)), str(int(r) + 1)]

    for i in add:
        q.append(int(str(cur) + i))

ans = sorted(ans)
print(ans[k - 1])

初めて本番中に幅優先探索を実装することができ、緑上位パフォーマンスを出してレートを大きく伸ばすことができた。

アルゴリズムの本を読んで勉強した結果が少しずつだけど出てきている気がする。