hirohirohirohirosのブログ

地方国立大学に通う情報系学部4年

Atcoder ABC233 振り返り

 優先度付きキューというデータ構造を完全に忘れていた.ただ今まで優先度付きキューが必要な問題に当たった記憶も無いので圧倒的精進不足故の結果と言える.

A - Weird Function【AC】

f(x) = x**2 + 2x + 3を関数として作れば後は問題文の通りに書くだけ.

t = int(input())
def f(x):
  return x**2 + 2*x + 3
print(f(f(f(t) + t) + f(f(t))))
B - Longest Segment【AC】

平面上にある二点の距離は \sqrt{(x_{1}-x_{2})^{2} + (y_{1}-y_{2})^{2}}であり,これを全ての二点について全探索する.

N = int(input())
lis = []
for i in range(N):
  lis.append([int(i) for i in input().split()])

ans = 0
for i in range(N):
  for j in range(N):
    if i == j:
      continue
    ans = max(ans, ((lis[i][0] - lis[j][0])**2 + (lis[i][1] - lis[j][1])**2)**(1/2))
print(ans)
C - Happy New Year!【AC】

0と2しか取らないのでKを2進数で表現し,1を2に変換すればいい.pythonはbinで変換すると0b~という形で帰ってくることに注意する.

K = int(input())
k = str(bin(K))[2:]
print(k.replace("1", "2"))
D - Prefix K-th Max【AC】

公式解説にある"結論から言うと、以下のようなアルゴリズムを用いればよい”のアルゴリズムは開始47分後までには思い付いていたがTLEしていた.二分探索することによってP[i]がソート済みリストの何番目に入るかの計算は O(\log n)で出来る.

import bisect
N, K = map(int, input().split())
P = [int(i) for i in input().split()]

ind = 0
sort_K = sorted(P[:K])
print(sort_K[ind])
for i in range(N-K):
  if len(sort_K) == 1:
    if sort_K[ind] < P[i+K]:
      print(P[i+K])
      sort_K.append(P[i+K])
    else:
      print(sort_K[ind])

  elif sort_K[ind] < P[i+K]:
    if P[i+K] < sort_K[ind+1]:
      print(P[i+K])
      sort_K[ind] = P[i+K]
    else:
      print(sort_K[ind+1])
      sort_K[ind] = 0
      bisect.insort(sort_K, P[i+K])
      ind += 1
  else:
    print(sort_K[ind])

このコードのボトルネックはbisect.insortである.bisect.insortは対象のインデックスを返すbisect.bisect_leftとそこに要素を挿入するbisect.insertを合体した関数である.ボトルネックとなっているのはbisect.insertで計算量がO(n)となるためTLEになる.要素の挿入もlog nで行うためには優先度付きキューを用いる.優先度付きキューは最小値の取り出し,最小値の削除,要素の挿入の操作をlog nで行うことが出来る.最大値の取り出し削除は要素に-1を書けることで最小値として扱う事が出来る.

import heapq
N, K = map(int, input().split())
P = [int(i) for i in input().split()]

ind = 0
queP = P[:K]
print(min(queP))
heapq.heapify(queP)
for i in range(K, N):
  mini = heapq.heappop(queP)
  if P[i] < mini:
    print(mini)
    heapq.heappush(queP, mini)
  else:
    heapq.heappush(queP, P[i])
    mini = heapq.heappop(queP)
    print(mini)
    heapq.heappush(queP, mini)