【AtCoder】ABC 465 C - Reverse Permutation

2026-07-07

AtCoder/ABC/C問題 AtCoder/ABC/300点問題 AtCoder/茶Diff AtCoder/NoviSteps/2Q AtCoder/条件の言い換え AtCoder/データ構造/deque 競技プログラミング

C - Reverse Permutation

C - Reverse Permutation

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 443 / NoviSteps: 2Q / 配点: 300 点

問題概要

整数 $N$ とo、xからなる長さ $N$ の文字列 $S$ が与えられる。長さ $N$ の整数列 $A=(1,2,\ldots,N)$ に対して、 $k=1,2,\ldots,N$ の順に以下の操作を行う:

$S_k=$ oである場合、 $A$ の先頭 $k$ 項を反転する。
$S_k=$ x である場合、何もしない。

全ての操作を終えた後の $A$ を求めよ。

制約

$2\le N\le 5\times 10^5$

考察

操作毎に配列 $A$ を反転させていると TLE になってしまうので、まずは操作を言い換えよう。

はじめ、 $A = ()$ とする。
$k = 1, 2, \ldots, N$ $k = 1, 2, \dots, N$ の順に以下の操作を行う。
- $A$ の末尾に $k$ を追加する。
- $S_k=$ oである場合、 $A$ を反転する。

さらに、あらかじめ反転されたかどうかのフラグを持っておくと、以下のように操作を言い換えることができる。

$S_i =$ o の場合、フラグを反転させる。その後、フラグがtrueなら $A$ の先頭に、falseなら末尾に $i$ を追加する。
$S_i =$ x の場合、フラグがtrueなら $A$ の末尾に、falseなら先頭に $i$ を追加する。

最後に、フラグがtrueなら配列を反転させて出力する。

これは、サンプルケースを見ると、何となくエスパーできるかもしれない。

実装についてだが、 $A$ の先頭と末尾に要素を追加する必要があるので、dequeを使うとよいだろう。

実装例

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
5. 
6.// ======================================== //
7. 
8.int main()
9.{
10.    int N;
11.    string S;
12.    cin >> N >> S;
13. 
14.    deque<int> que;
15.    bool reversed = false;
16.    rep(k, 0, N) {
17.        if (S[k] == 'o') {
18.            reversed = !reversed;
19.            if (reversed) {
20.                que.push_back(k);
21.            }
22.            else {
23.                que.push_front(k);
24.            }
25.        }
26.        else {
27.            if (reversed) {
28.                que.push_front(k);
29.            }
30.            else {
31.                que.push_back(k);
32.            }
33.        }
34.    }
35. 
36.    if (reversed) {
37.        while (!que.empty()) {
38.            cout << que.back() + 1 << " ";
39.            que.pop_back();
40.        }
41.    }
42.    else {
43.        while (!que.empty()) {
44.            cout << que.front() + 1 << " ";
45.            que.pop_front();
46.        }
47.    }
48.    cout << endl;
49. 
50.    return 0;
51.}

https://atcoder.jp/contests/abc465/submissions/77182086

実装時間: 10分

コメント

操作の言い換えがちょっと難しい。