POJ 1026 - Cipher

http://poj.org/problem?id=1026

概要

1 .. N の順列 a[1], ..., a[N] が与えられ，これを用いて文字列を暗号化する．

整数 k と長さが N 以下の文字列 s に対して，「s'[a[i]] <- s[i]」という処理を k 回繰り返すことで暗号化する． s の長さが N に満たないとき，s の末尾に長さが N になるまで空白を追加する．

暗号化された文字列を答える．

制約

解法

k についての制約が無く，おそらく結構大きい値がくるので，本当に k 回繰り返すと TLE すると思われる．

i に対して何回置換 a を作用させると再び i になるか(= 周期)を予め計算しておき，周期で割った値の分だけ処理を行う． 周期は高々 N である．

 1 #include <iostream>
 2 #include <vector>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   ios::sync_with_stdio(false);
 8   int N;
 9   while (cin >> N && N != 0) {
10     vector<int> a(N);
11     for (int i = 0; i < N; i++) {
12       cin >> a[i];
13       --a[i];
14     }
15     vector<int> periods(N, 1);
16     for (int i = 0; i < N; i++) {
17       for (int j = a[i]; j != i; j = a[j]) {
18         ++periods[i];
19       }
20     }
21 
22     int k;
23     while (cin >> k && k != 0) {
24       cin.ignore();
25       string msg;
26       getline(cin, msg);
27       string buf(N, ' '), ans(N, ' ');
28       copy(msg.begin(), msg.end(), buf.begin());
29       for (int i = 0; i < N; i++) {
30         const int M = k % periods[i];
31         int j = i;
32         for (int c = 0; c < M; c++) {
33           j = a[j];
34         }
35         ans[j] = buf[i];
36       }
37       cout << ans << endl;
38     }
39     cout << endl;
40   }
41   return 0;
42 }
poj/1026.cc