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
２点間距離を全探索する。
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)
コメント