ABC477 D - Masking Tape
- サイト
- AtCoder
- コンテスト
- ABC477
- 問題
- D - Masking Tape
- 難易度
- 946
個のマスが一列に並んでいて、はじめはすべて色 a でタイルは置かれていません。次の 2 種類のクエリを 個処理したあとの、各マスの色を求める問題です()。
1 X:マス のタイルの有無を切り替える。2 C:タイルが置かれていないすべてのマスの色を に変える。
タイプ 2 のクエリのたびにタイルのないマスを全部塗り直すと、 かかって間に合いません。
そこでクエリを後ろから見ていきます。各マスの最終的な色は、そのマスにタイルがなかった最後のタイプ 2 のクエリで決まります。なので、後ろから見て最初に当たった「そのマスにタイルがない時点のタイプ 2」の色が答えです。一度色が決まったマスは、それより前のクエリの影響を受けません。
具体的には次のようにします。
- まずクエリを前から処理して、タイルの状態だけを追い、最後の時点でタイルのないマスの集合 を求めます。
- はじめの状態を「全マスを a に塗るタイプ 2 のクエリ」とみなして先頭に加えます。
- クエリを後ろから処理します。
- タイプ 2 なら、 のマスをすべてその色に決めて、 を空にします。
- タイプ 1 なら、マス の色がまだ決まっていない場合だけ、タイルの切り替えを取り消します( に があれば除き、なければ加える)。
に入るのは色が決まっていないマスだけで、各マスの色が決まるのは 1 回だけです。また に加えられるのはタイプ 1 のクエリ 1 回につき高々 1 個なので、全体で 回の集合操作で済みます。
cLay
ll@N,@Q,t[Q]={97};string S(N,'!');set<ll>s;rep(i,N)s.insert(i);rep(i,1,Q+1){ll@X;if(X-1){char@C;t[i]=C;}else{ll@Y--;if(!s.insert(Y).second)s.erase(Y);t[i]=-Y;}}rrep(i,Q+1){if(t[i]>0){for(ll p:s)S[p]=t[i];s.clear();}else if(S[-t[i]]<'$')if(!s.insert(-t[i]).second)s.erase(-t[i]);}wt(S);cLay(C++ っぽいコードを C++ に変換するツール)で書いています。ll@N のように変数名の前に @ を付けると、宣言と同時に標準入力から読み込みます。ll@Y-- は読み込んだ直後に 1 減らして 0 始まりにしています。rep(i, 1, Q + 1) は 、rrep(i, Q + 1) は のループで、wt は出力です。
t[i] に 番目のクエリを記録しています。タイプ 2 なら色の文字コード(正の値)、タイプ 1 なら ( は 0 始まりのマス番号)を入れます。t[0] = 97 は、はじめの状態を表す「a に塗るクエリ」です。
S は色がまだ決まっていないマスを '!' にしておき、S[-t[i]] < '$' で未決定かどうかを判定しています。集合 s の切り替えは、insert が失敗したら(すでにあったら)erase する形で書いています。
Python
N, Q = map(int, input().split())queries = [("2", "a")]untiled = set(range(N))for _ in range(Q): t, x = input().split() if t == "1": x = int(x) - 1 if x in untiled: untiled.remove(x) else: untiled.add(x) queries.append((t, x))ans = [""] * Nfor t, x in reversed(queries): if t == "2": for p in untiled: ans[p] = x untiled.clear() elif not ans[x]: if x in untiled: untiled.remove(x) else: untiled.add(x)print("".join(ans))cLay 版と同じ処理です。はじめの状態を ("2", "a") としてクエリの先頭に入れ、ans が空文字列のマスを色が未決定のマスとして扱っています。