C - Rotate Colored Subsequence 解説 by leaf1415
まず、各色 \(i = 1, 2, \ldots, M\) に対して、 \(S\) の 色 \(i\) で塗られた文字全ての位置を昇順に格納した可変長配列 \(P^{(i)}\) を作ります。
\(S\) を \(1\) 回走査することで \(P^{(1)}, P^{(2)}, \ldots, P^{(M)}\) 全てを同時に \(O(N)\) 時間で作ることができます。 具体的には、可変長配列 \(P^{(1)}, P^{(2)}, \ldots, P^{(M)}\) がすべて空の状態からはじめ、 \(S\) の各添字 \(i = 1, 2, \ldots, N\) についてこの順番に見ていき、可変長配列 \(P^{(C_i)}\) の末尾に \(i\) を追加するという処理を行えば良いです。
\(P^{(1)}, P^{(2)}, \ldots, P^{(M)}\) を用いて、出力すべき答えである長さ \(N\) の文字列 \(T\) の各文字が下記の通りにわかります。
\(P^{(1)} = (p^{(1)}_1, p^{(1)}_2, \ldots, p^{(1)}_{k_1})\) とおく。\(T\) の \(p^{(1)}_2, \ldots, p^{(1)}_{k_1}, p^{(1)}_1\) 文字目が、それぞれ \(S\) の \(p^{(1)}_1, p^{(1)}_2, \ldots, p^{(1)}_{k_1}\) に等しいとわかる。
\(P^{(2)} = (p^{(2)}_1, p^{(2)}_2, \ldots, p^{(2)}_{k_2})\) とおく。\(T\) の \(p^{(2)}_2, \ldots, p^{(2)}_{k_2}, p^{(2)}_1\) 文字目が、それぞれ \(S\) の \(p^{(2)}_1, p^{(2)}_2, \ldots, p^{(2)}_{k_2}\) に等しいとわかる。
\(\cdots\)
\(P^{(M)} = (p^{(M)}_1, p^{(M)}_2, \ldots, p^{(M)}_{k_M})\) とおく。\(T\) の \(p^{(M)}_2, \ldots, p^{(M)}_{k_M}, p^{(M)}_1\) 文字目が、それぞれ \(S\) の \(p^{(M)}_1, p^{(M)}_2, \ldots, p^{(M)}_{k_M}\) に等しいとわかる。
以下に、C++ 言語による本問題の正解例を記載します。
#include <iostream>
#include <vector>
using namespace std;
int n, m;
string s;
int c[200000];
vector<int> p[200001];
int main(void)
{
cin >> n >> m;
cin >> s;
for(int i = 0; i < n; i++) cin >> c[i];
for(int i = 0; i < n; i++) p[c[i]].push_back(i);
string t(n, '?');
for(int i = 1; i <= m; i++){
int k = p[i].size();
for(int j = 0; j < k; j++) t[p[i][(j+1)%k]] = s[p[i][j]];
}
cout << t << endl;
return 0;
}
投稿日時:
最終更新: