ABC 401-500/ABC411D - Conflict 2 - 競技プログラミング用 知識集積所【7/12更新】

---

問題

ABC411D

必要知識

• 特になし

考え方

愚直にやると、TLEする。
これは、string型のデータは実は文字数だけ要素があるvector（未作成）のようなものであるため。
例えば1000文字あるデータをコピーしようとすると、要素数1000のvector（未作成）をコピーするようなもので、当然計算量が1000回分かかる。
そこで、文字列のコピーをしなくてすむよう、以下のような工夫をする。

例えば、入力例1の場合。
まず、0番のテキストとして、空文字列を用意しておく。
そして、サーバーおよび全PCに「表示中のテキストは0番のもの」としておく。

最初のクエリで、PC1の表示に"at"を加えろと来る。
今PC1には0番のテキストが表示されている。
そこで、1番のテキストで「0番+"at"」という情報を用意し、PC1は「表示中のテキストは1番のもの」とする。

次のクエリで、サーバーの表示内容をPC1と同じにしろと来る。
今PC1には1番のテキストが表示されている。
そこで、サーバーも「表示中のテキストは1番のもの」とする。

3つめのクエリで、PC2の表示に"on"を加えろと来る。
今PC2には0番のテキストが表示されている。
そこで、2番のテキストで「0番+"on"」という情報を用意し、PC2は「表示中のテキストは2番のもの」とする。

以下同じように繰り返すと、最終的に以下のようなデータができあがる。

0番のテキスト	1番のテキスト	2番のテキスト	3番のテキスト
空文字列	0番+"at"	0番+"on"	1番+"coder"

サーバー	PC1	PC2
3番のテキスト表示中	1番のテキスト表示中	3番のテキスト表示中

ここからサーバーの表示内容を復元するには、

3番のテキスト
= 1番のテキスト + "coder"
= 0番のテキスト + "at" + "coder"
= 空文字列 + "at" + "coder"

として復元できる。
これはstack（未作成）を使えば簡単。

こうすると、文字列のコピーなどが最後の再構成時しか発生しないため、高速に処理できる。

解答例

解答例

注意点

別解

バックトレースで解く

クエリを逆順に見て、最終的にサーバーが持つ文字列がどこ由来なのかを追いかけていく方法でも解ける。
解答例