C++の練習を兼ねて, AtCoder Beginner Contest 030 の 問題D (D – へんてこ辞書) を解いてみた.
■感想.
1. 解説見る前に, AC版となったので, 良かったと思う.
2. 但し, 細かい条件をいくつも考慮する必要があり, 実装で, 大変苦労した(汗).
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトABC 030解説をご覧下さい.
■C++版プログラム(問題D/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 124 125 126 127 |
#include <bits/stdc++.h> using namespace std; #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--) const int MAX = 101010; char k[MAX]; int b[MAX], loop[MAX], rLoop[MAX], mod[MAX]; int main(){ // 1. 入力情報. int N, a; scanf("%d %d %s", &N, &a, k); rep(i, N){ int tb; scanf("%d", &tb); b[i + 1] = tb; } int kl = strlen(k); // 2. 周期を確認. int cur = a, bef = 0, index = 1, t = 0; while(loop[cur] == 0 && index < MAX){ // 2-1. 訪問済みを設定. loop[cur] = index; // 2-2. loop参照用に設定. rLoop[index] = cur; // 2-3. 前回分を保存. bef = cur; // 2-4. 次の単語を設定. cur = b[cur]; // 2-5. 出現の順位を更新. index++; } t = loop[bef] - loop[cur] + 1; // 周期を設定. // rep(i, N + 1) printf("%d ", loop[i]); // puts(""); // rep(i, N + 1) printf("%d ", rLoop[i]); // puts(""); // printf("bef=%d cur=%d t=%d\n", bef, cur, t); // puts(""); // 3. 周期に入るまでのStep数(loop[bef] - t). // ex. // 9 5 // 12 // 2 3 1 2 6 7 8 9 4 // (step1) 5 -> 6 // (step2) 6 -> 7 // (step3) 7 -> 8 // (step4) 8 -> 9 // (step5) 9 -> 4 // (step6) 4 -> 2 ※ 周期に入る直前(s = 6) // (step7) 2 -> 3 // (step8) 3 -> 1 // (step9) 1 -> 2 ※ 周期1回目終了(t = 3) // ... ~(略)~ ... // -> この場合, s = 6, t = 3 と見ることが出来る. int s = loop[bef] - t; int sl = to_string(s).size(); // printf("s=%d t=%d\n", s, t); // 4. 10 の べき乗に対して, 周期で割った余りを事前計算. mod[0] = (1 % t); rep(i, MAX - 1) mod[i + 1] = (10 * mod[i]) % t; // 5. k Step を 確認. // 5-1. kl が sl 以下 の 場合. int ans = -1; if(kl <= sl){ int nk = 0; rep(i, kl) nk *= 10, nk += k[i] - '0'; if(nk <= s){ ans = b[rLoop[nk]]; }else{ // 周期部分を抽出. nk -= s; // 剰余に変換. nk = (nk % t == 0) ? t : (nk % t); // 周期に入る直前 + 周期部分 で 取得. ans = b[rLoop[s + nk]]; } } // 5-2. kl が sl より大きい場合. if(kl > sl){ // (sl + 1) ~ kl桁 まで. int nsk = 0; rep(i, kl - sl) nsk += (k[i] - '0') * mod[kl - 1 - i], nsk %= t; // 1 ~ sl桁 まで. int nk = 0; repx(i, kl - sl, kl) nk *= 10, nk += k[i] - '0'; // nk と s を 比較. if(nk >= s){ // 周期部分を抽出. int n = nk - s; n += nsk; // 剰余に変換. n = (n % t == 0) ? t : (n % t); // 周期に入る直前 + 周期部分 で 取得. ans = b[rLoop[s + n]]; }else{ // 周期に入る直前における戻り分. int bs = nk - s; // 負の整数. // 周期部分で換算(bs回戻り). bs %= t; // 周期に入る直前 + 周期部分 で 取得. int n = nsk + bs; if(n < 0) n += t; n = (n % t == 0) ? t : (n % t); ans = b[rLoop[s + n]]; } } // 6. 出力. printf("%d\n", ans); 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 97 98 |
[入力例] 6 4 5 2 3 1 2 6 5 [出力例] 3 ※AtCoderテストケースより [入力例] 4 1 100000000000000000000 2 3 4 1 [出力例] 1 ※AtCoderテストケースより [入力例] 8 1 1 2 3 4 5 3 2 4 5 [出力例] 2 ※AtCoderテストケースより [入力例] 9 5 12 2 3 1 2 6 7 8 9 4 [出力例] 2 [入力例] 9 5 3 2 3 1 2 6 7 8 9 4 [出力例] 8 [入力例] 50 25 123 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 1 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 16 [出力例] 21 [入力例] 50 25 135 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 1 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 16 [出力例] 10 [入力例] 50 25 18 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 1 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 16 [出力例] 43 [入力例] 50 25 93 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 1 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 16 [出力例] 14 [入力例] 50 25 1234567890987654321 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 1 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 16 [出力例] 10 [入力例] 50 25 100 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 1 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 16 [出力例] 21 [入力例] 50 25 31415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823066470938446095505822317253594081284811174502841027019385211055596446229489549303819644288109756659334461284756482337867831652712019091456485669234603486104543266482133936072602491412737245870066063155881748815209209628292540917153643678925903600113305305488204665213841469519415116094330572703657595919530921861173819326117931051185480744623799627495673518857527248912279381830119491 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 1 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 16 [出力例] 21 |
■参照サイト
AtCoder Beginner Contest 030