AtCoder Grand Contest 005 - A - STring
割と典型問題?
https://gyazo.com/c8a9400411f91be18df60fee259c813a
考えたこと
操作回数$ 10^{1000}は無限回操作可能と考えていいだろう。
愚直にやると配列を先頭から見ていって、STが連続していたら取り除いて、取り除いた配列をまた先頭から見ていって、、というのを取り出せなくまでやるけど、これは明らかにTLE.iconになりそう
STを取り除いた直後を考える
TSSTTTTTという文字列があったとき, 3,4文字目のSTを取り除くとTS__TTTTとなる
次に考えるのは2,5文字目(取り除いた文字の前後だけ)でいいだろう。
これでかなり計算量は落とせるはず
あとはどう実装するか、vectorを使って, left, rightみたいにポインタ管理してもいいけど、かなり複雑になりそう。
ここはスタックを使えばうまく実装できるのでは?
文字列を先頭から順番にスタックにpushしていく
そして、push前にスタックの先頭をのぞいて、それがSかつ追加するのがTだったらそれを削除みたいな
TSSTTTTTという文字列をスタックにpushする流れを見ていく
T
TS
TSS
ここで次のがTかつ、スタックの先頭がSなので、これらを削除する
厳密には、先頭をpopかつ、このTをpushしない
TS
さらにまた次がTかつスタックの先頭がSなので、これらを削除する
T
TT
TTT
TTTT
提出したコード
code: A.cpp
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i) #define erep(i, n) for (ll i = 0; i <= (ll)(n); ++i) #define FOR(i,a,b) for (ll i = (a); i < (ll)(b); ++i) #define EFOR(i,a,b) for (ll i = (a); i <= (ll)(b); ++i) template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } }
using Graph = vector<vector<int>>;
int main() {
string x; cin >> x;
stack<char> s;
rep(i, x.size()) {
if(s.empty()) s.push(tmp);
else {
if(s.top() == 'S' && tmp == 'T') s.pop();
else s.push(tmp);
}
}
cout << s.size() << endl;
return 0;
}
stackのpush/popは$ O(1)なので、文字列の探査だけになり計算量は$ O(N) = O(10^5)
stackを素で使う問題は珍しいね。