🌳
【Python】ABC392Fを解く
解説ACですが、Pythonで意外と簡単に解けたので共有です！
問題
Diff: 1395
解説を読む
A′ = [1, 2, …, N] に対し、逆順に削除していく
A′は「最終的な位置」を表しています。
この操作をしていくことで、それぞれの数字が最終的に何番目かを調べることができるので、
その後は数字を当てはめていくことで答えを求めることができます。
便利なライブラリ
要素の挿入・削除がO(logN)でできるSortedSetです！！
pip install sortedcontainers
でインストールしましょう。
解答
提出したコードがこちらです。
from sortedcontainers import SortedSet
N = int(input())
P = [int(x) - 1 for x in input().split()]
ans = [-1] * N
last_pos = SortedSet(range(N))
for i in range(N - 1, -1, -1):
pos = last_pos.pop(P[i])
ans[pos] = i + 1
print(*ans)
実行時間: 977ms / 2000ms （なかなか怖い…！）
定数倍の違いがありそうですね。
ちなみに、
from sortedcontainers import SortedSet
だけで130ms近く取られてました…()
おわりに
最後まで読んでくださりありがとうございます。
もっと高速に解ける方法（セグ木とか？）もありそうですが、
ライブラリは使いこなせるようにしておきたい！という話でした。
今回の他の問題（A～E）の解答はこちらから！
Discussion