[ABC350] F - Transpose
[Q] F - Transpose
本番出れていないんですが、裏イベントの 第一回マスターズ選手権 -決勝- で遊んでいました。とても良い日で、ごはんも美味しかった。
ABCに出ていた場合、パフォ1600弱で負けです。
考察
1. 直感では()の深いところから処理していくと思ったが、間違い。
どうしても()の文字列をどこかに保存することになり、S^2のデータを扱ってしまうことになる。これは無理。
2. 貪欲的にO(S)で処理が求まるしかなさそう。実際そう。
3. 文字がどのようにつけられていくかシミュレートする
適当なケースを考える
ab(c(de)fg(i)jk)l
処理順番は次のようになる
12 A 89 76 5 43 B
ab(c(de)fg(i)jk)l
答えは次のとおり
123456789AB
abKJiGFdeCl
観察すると
1, 深さが偶数のときは左から右に処理
2. ()がきたときに深さを1つ潜る
3. 深さが奇数のとき、右から左に処理し、文字の大小反転
文字を通過する際に、1文字ずつ確定させていけばいい。実装
int main() {
cincout();
string S;
cin >> S;
// かっこのペア 英語:parentheses
vector<ll>parentheses(S.size());
stack<ll>st;
rep(i, S.size()){
if (S[i] == '(') st.push(i);
else if (S[i] == ')') {
ll j = st.top(); st.pop();
parentheses[i] = j;
parentheses[j] = i;
}
}
string ans;
auto add_ans = [](string &ans, char c, ll d){
if (d % 2 == 1){
// cが小文字なら大文字に
if (islower(c)) ans += toupper(c);
else ans += tolower(c);
}
else{
ans += c;
}
};
// dfs(深さ、[開始地点, 終了地点], ans)
function<void(ll, ll, ll, string&)> dfs=[&](ll d, ll l, ll r, string &ans){
if (d % 2 == 0){ // 左から右に読んでいく
for(ll i = l; i <= r; ++i){
if (S[i] == '('){
dfs(d + 1, i + 1, parentheses[i] - 1, ans);
i = parentheses[i]; // かっこの終端に移動
}
else{
add_ans(ans, S[i], d);
}
}
}
else{ // 右から左に読んでいく
for (ll i = r; i >= l; --i){
if (S[i] == ')'){
dfs(d + 1, parentheses[i] + 1, i - 1, ans);
i = parentheses[i]; // かっこの先端に移動
}
else{
add_ans(ans, S[i], d); // 大文字小文字を反転
}
}
}
};
dfs(0, 0, S.size() - 1, ans);
cout << ans << endl;
}