Official

G - Take ABC Editorial by leaf1415


問題文中の操作をシミュレーションすれば答えを得ることは出来ますが、愚直な実装では最悪時間計算量が \(\Theta(N^2)\) となり実行制限時間超過(TLE)を招きうるため、実装方針には注意と工夫が必要です。

例えば、文字列 \(S\) を保持するデータ構造によっては、 \(S\) からある文字を削除した際、削除で生じた隙間を詰めるために削除箇所より後ろの部分を先頭にずらす処理が生じます。 (例えば \(S = S_1S_2S_3S_4S_5\) の先頭から \(2\) 文字目 \(S_2\) を削除すると、先程まで \(S_3\) だった文字を \(S_2\) に、\(S_4\) だった文字を \(S_3\) に、\(S_5\) だった文字を \(S_4\) にずらす処理がそれぞれ生じます。)
この処理は最悪の場合( \(S\) の先頭の文字を削除する場合) に \(\Theta(N)\) 時間かかるため、これを繰り返すと、入力で与えられる文字列によってはシミュレーション全体で \(\Theta(N^2)\) 時間かかってしまいます。

そこで、実行制限時間に間に合う方針として、スタックを使った以下の手順でシミュレーションを行うことによって、 全体で \(O(N)\) 時間で本問題を解くことができます。

空のスタックを準備し、\(S\) の文字を先頭から順に \(1\) 文字ずつスタックの先頭にpushしていく。
ただしその過程で、スタックの先頭に文字列 ABC が作られる(つまり、スタックの先頭の文字(最後に push した文字)が C 、先頭から \(2\) 番目の文字が B 、先頭から \(3\) 番目の文字が A の状態になる)たびに、スタックの先頭からその \(3\) 文字 ABC を随時 pop する。

以下に、C++ 言語による本問題の正解例を記載します。

#include <iostream>
using namespace std;

int main(void)
{
  string s, ans;
  cin >> s;
  
  for(auto c : s){
    ans += c;
    if(ans.size() >= 3 && ans.substr(ans.size()-3) == "ABC") ans.erase(ans.end()-3, ans.end());
  }
  cout << ans << endl;
  
  return 0;
}

posted:
last update: