ARC042 A - 掲示板 - ゆらのふなびと

A問題やけど解けんかった！　ということでメモ。

問題

1 から N までの番号がついたスレッドのある掲示板があります。スレッドは書き込みがあると一番上に来ます。書き込み前のスレッドは上から順に 1 から N の順に並んでいました。 M 個の書き込みが書き込まれた順で与えられるので、全ての書き込みが終わった後のスレッドの順番を出力してください。

制約

1≦N≦10**5

1≦M≦10**5

解法（に至るまでの思考過程）

部分点

最初、下の問題と同じで逆順にシミュレーションすればいいのかと思っていた。

No.123 カードシャッフル - yukicoder

しかしこれは一番上に来るカードだけを求めるときの方法。今回のARCの問題では掲示板の最終的な順番をすべて出力しないといけないので、逆順にやったとしても結局O(NM)になりO(10**10))でTLE。

特に賢い方法も思いつかないので、最初から愚直にシミュレーションするコードを出してみる。具体的には、

初期化: cards = [1, 2, ..., n]
各a_i(次に一番上に来る掲示板)に対して以下を繰り返す
1. cardsの中のa_iを削除
2. cardsの一番最初にa_iを追加

N, M = map(int, input().split())
a = []
for i in range(M):
    a.append(int(input()))
 
cards = list(range(1, N+1))
for i in range(M):
    cards.remove(a[i])
    cards.insert(0, a[i])
    
for x in cards:
    print(x)

しかしこれもO(NM)なのでTLE。部分点しか取れない。

満点解法

入力される配列a(更新履歴)と最後の並び順の関係を考えると、

まず一番上から、aを逆順にソートして重複を取り除いたものが並ぶ(重複を取り除くときは同じ要素のうち一番上にあるものを残す)
次に、aに入っていない要素が昇順に並ぶ

要は、

一度でも更新されたスレッド: より後に（より最近）更新されたものほど上にある
他のスレッド: 最初の位置関係を保ってずるずる下に落ちていく

ということである。実際、入力例1を見ると出力が入力の逆順になっていることがわかる（このケースでは1～3のすべての要素がaに入っているので、上記の場合分けで言うところの2はない）

この方法ならO(NlogN + M)で済むので、O(10**5)で間に合う*1

N, M = map(int, input().split())
a = []
for i in range(M):
    a.append(int(input()))

a.reverse()

done = [False] * (N + 1)
for ax in a:
    if not done[ax]:
        print(ax)
        done[ax] = True

for i in range(1, N+1):
    if not done[i]:
        print(i)

ちなみに done = [False] * (N + 1) の部分、最初は done = [] → 1個ずつappend という風にしていたのだが、それだとTLEした。どうやらリストのサイズが大きい場合には1個ずつappendするより、先に配列を初期化してそこに入れていった方が速いらしい。

*1:正直言うとなんでこの計算量になるのかわかってない。ソートでNlogN？しかしそれならaは要素M個なのだからMlogMでは？？