AtCoder Beginner Contest 234の感想

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

A – Weird Function

関数を定義し、カッコの場所に注意しながら実装。

t = int(input())


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


ans = func(func(func(t) + t) + func(func(t)))
print(ans)

B – Longest Segment

2点間距離を全探索する。

N<=100なので、O(N^2)でも十分間に合う。

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

ans = 0
for i in range(n):
    for j in range(n):
        x1, y1 = xy[i]
        x2, y2 = xy[j]
        dist = (x1 - x2) ** 2 + (y1 - y2) ** 2
        dist **= 0.5
        ans = max(ans, dist)

print(ans)

C – Happy New Year!

0か2の2通りで表現するので、ビット演算が使える。

入力値を1ビットずつシフトしていき、0は0、1は2に置き換えるように処理をする。

1の位から順に右シフトで処理していくので、最後に左右反転させると答えになる。

k = int(input())

ans = ""
while k > 0:
    if k & 1:
        ans += "2"
    else:
        ans += "0"

    k >>= 1

ans = ans[::-1]
print(ans)

D – Prefix K-th Max

最初にK個の配列を取り分けておき、K+1,K+2,…個目の要素を追加していくことを考える。

新たに追加する要素が取り分けた配列の最小値より小さい場合、K番目に大きい値は更新されない。

そうでない場合はK番目に大きい値が更新されるので、新たな要素の追加と最小値の除去を行う必要がある。

通常のリストを使った場合、要素の追加appendはO(1)で可能だが、最小値の取り出しが遅い。

最小値の判定minで全配列を捜査するためO(N)、その後deleteにO(N)かかってしまうため、別のデータ構造を使いたくなる。

プライオリティキュー(ヒープ)ならば、要素の追加はO(logN)、最小値の取り出しはO(1)で処理出来るため、実行時間内に間に合うように解くことが出来た。

計算量は、最初のK個の要素の取り出しでO(K)、K+1,K+2,…の要素を順に処理していくので、O(N-K)=O(N)、ループ内のヒープ処理がO(logN)となり、全体の計算量はO(NlogN)となる。

from heapq import heapify, heappop, heappush

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

topk = p[:k]
heapify(topk)

ans = topk[0]
print(ans)
for i in range(k, n):
    val = p[i]
    if val <= ans:
        print(ans)
    else:
        heappush(topk, val)
        heappop(topk)
        ans = topk[0]
        print(ans)

E – Arithmetic Number

X<=10^17のため、一見全探索が間に合わないように見える。

しかし、等差数という性質から1桁目の値が分かれば2桁目以降も自動的に決まるので、最大17桁の数字を列挙する問題に切り替わる。

1桁目の数は1〜9の9通り、等差の候補が-9〜9の19通り、桁数が最大17桁のため、9x19x17≒3000=O(10^3)程度の計算量で全列挙出来る。

全列挙した後は、重複を省いてソートし、条件を満たす値を二分探索する。

x = int(input())

result = set()

for first in range(1, 10):
    for diff in range(-9, 10):
        val = str(first)
        for _ in range(0, 18):
            result.add(int(val))
            addval = int(val[-1]) + diff
            if 0 <= addval <= 9:
                val += str(int(val[-1]) + diff)
            else:
                break

result = sorted(list(result))

l = -1
r = len(result)
while r - l > 1:
    mid = (l + r) // 2
    if result[mid] < x:
        l = mid
    else:
        r = mid

ans = result[r]
print(ans)

といっても候補は数百個しかないため、二分探索せずともソートして前から見ていくO(N)でも十分間に合う。

result = sorted(list(result))
 
for i in result:
  if i>=x:
    ans=i
    break
 
print(ans)




 

コメント

タイトルとURLをコピーしました