C++の練習を兼ねて, AtCoder Beginner Contest 150 の 問題F (Xor Shift) を解いてみた.
■感想.
1. 問題Fは, 方針が見えなかったので, 解説を参考にして, ようやく, AC版に到達出来た.
2. クヌース–モリス–プラット(Knuth–Morris–Pratt algorithm)法 を 学習できたので, 非常に良かったと思う.
3. 本問では, 周期を知る必要が出てきたため, KMP法を, 最大2回まで実施する形で対応した.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 150 解説 を ご覧下さい.
■C++版プログラム(問題F/AC版).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 |
// 解き直し. // https://img.atcoder.jp/abc150/editorial.pdf // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using P = pair<int, int>; using vi = vector<int>; using vp = vector<P>; #define repex(i, a, b, c) for(int i = a; i < b; i += c) #define repx(i, a, b) repex(i, a, b, 1) #define rep(i, n) repx(i, 0, n) #define repr(i, a, b) for(int i = a; i >= b; i--) #define a first #define b second #define all(x) x.begin(), x.end() #define pb push_back // https://ja.wikipedia.org/wiki/クヌース–モリス–プラット法 // -> 照合が一致する複数の箇所を抽出するように拡張した版. template<typename T> struct KMP{ vi M; // 部分マッチテーブル. T S; // テキスト. T W; // 単語. int E; // 実行回数. KMP(T s, T w, int e = 1): S(s), W(w), E(e) {} void makeTable(){ int i = 2, j = 0, n = W.size(); vi t(n + 1); t[0] = -1; t[1] = 0; while(i < n){ // 第一のケース. if(W[i - 1] == W[j]){ t[i] = j + 1; ++i; ++j; continue; } // 第二のケース. if(j){ j = t[j]; continue; } // 第三のケース. t[i] = 0; ++i; } // 生成結果. M = t; } vi search(){ vi ret; // マッチした位置を保存. int m = 0; // S 内 の 現在照合中の開始位置. int i = 0; // W 内 の 現在位置. while(m + i < S.size() && E){ if(W[i] == S[m + i]){ ++i; if(i == W.size()){ ret.pb(m); // マッチした位置を保存. ++m; // 次へ. i = 0; // 初期化. --E; // デクリメント. } continue; } m += (i - M[i]); if(i) i = M[i]; } return ret; } }; int main(){ // 1. 入力情報. int N; scanf("%d", &N); vi a(N), b(N); rep(i, N) scanf("%d", &a[i]); rep(i, N) scanf("%d", &b[i]); // 2. 数列 c, d 作成. vi c, d; rep(i, N * 2 - 1) c.pb(a[i % N] ^ a[(i + 1) % N]); rep(i, N * 1 - 0) d.pb(b[i % N] ^ b[(i + 1) % N]); // ex. // 以下の場合, 11 77 111 123 150 が出力される. // KMP<string> kmp("aopqrssttuuabracadabrapqrabra cadabrapqrpqrsabraceadabraroutxowiystabrcadabraabracadabraabdracadabraxyzabcdefghabracadabraiabracadabra deded xyzdeded abracadabraopqtdhg abracadabrajjtxhg", "abracadabra", 5); // kmp.makeTable(); // vi v = kmp.search(); // for(auto &p : v) printf("%d ", p); // puts(""); // 3. KMP法(k の 抽出). KMP<vi> kmp(c, d, 2); kmp.makeTable(); vi ks = kmp.search(); // for(auto &k : ks) printf("%d ", k); // puts(""); // 4. 周期を考慮. if(ks.size() == 2){ int f = ks[1] - ks[0]; while(f + ks.back() < N) ks.pb(f + ks.back()); } // 5. x の 抽出. vp ans; for(auto &k : ks) ans.pb({k, a[k] ^ b[0]}); // 6. sort. sort(all(ans)); // 7. 出力. for(auto &p : ans) printf("%d %d\n", p.a, p.b); return 0; } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 |
[入力例] 3 0 2 1 1 2 3 [出力例] 1 3 ※AtCoderテストケースより [入力例] 5 0 0 0 0 0 2 2 2 2 2 [出力例] 0 2 1 2 2 2 3 2 4 2 ※AtCoderテストケースより [入力例] 6 0 1 3 7 6 4 1 5 4 6 2 3 [出力例] 2 2 5 5 ※AtCoderテストケースより [入力例] 2 1 2 0 0 [出力例] ※AtCoderテストケースより [入力例] 3 1 1 1 3 3 3 [出力例] 0 2 1 2 2 2 [入力例] 4 1 0 1 0 0 1 0 1 [出力例] 0 1 1 0 2 1 3 0 [入力例] 15 1 0 2 1 0 2 1 0 2 1 0 2 1 0 2 0 2 1 0 2 1 0 2 1 0 2 1 0 2 1 [出力例] 1 0 4 0 7 0 10 0 13 0 [入力例] 18 0 1 2 8 5 7 0 1 2 8 5 7 0 1 2 8 5 7 6 5 15 2 0 7 6 5 15 2 0 7 6 5 15 2 0 7 [出力例] 1 7 7 7 13 7 [入力例] 24 1 2 5 2 1 2 5 2 1 2 5 2 1 2 5 2 1 2 5 2 1 2 5 2 3 4 3 0 3 4 3 0 3 4 3 0 3 4 3 0 3 4 3 0 3 4 3 0 [出力例] 1 1 5 1 9 1 13 1 17 1 21 1 |
■参照サイト
AtCoder Beginner Contest 150