C++の練習を兼ねて, AtCoder Beginner Contest 129 の 問題F (F – Takahashi’s Basics in Education and Learning) を解いてみた.
■感想.
1. 解答の方針が, 全く見えなかったので, 解説を読んだうえで, 実装した.
2. 但し, 実装上, 部分的に, いくつも推測(ex. Cd乗 の 解釈など)しているため, 題意と, ズレている可能性があると思われる.
3. あと, 実装後, テストケース(sub1_killer_04.txt)で, 必ず弾かれてしまうので, ネット上で調べたところ, atcoder_testcases ABC129で, テストケースが公開されていることが分かったので, 内容を確認したところ, 計算範囲が, 小さいことによるバグと判明した.
4. 再提出したところ, ようやく AC版 となった, 計算範囲の把握が大事であることが分かったので, 今後も役立つと思った.
本家のサイトABC 129解説をご覧下さい.
■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 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 |
// 解き直し. // ABC 129解説. // https://img.atcoder.jp/abc129/editorial.pdf #include <bits/stdc++.h> using namespace std; using LL = long long; LL m[9]; // 行列積のロジックを一部抽出した版. // @param p1 ~ q3: 行列の要素. // @param MOD: M. // @return ret: 行列積の計算結果. LL matrixProduct(LL p1, LL p2, LL p3, LL q1, LL q2, LL q3, LL MOD){ LL ret = 0; ret += (p1 % MOD) * (q1 % MOD), ret %= MOD; ret += (p2 % MOD) * (q2 % MOD), ret %= MOD; ret += (p3 % MOD) * (q3 % MOD), ret %= MOD; return ret; } // 本問で設定している (3×3)行列 の Cd 乗 を 計算. // @param p: Cd乗. // @param a: 10 の d乗. // @param b: B. // @param MOD: M. // @return: 特に無し. void matrix33(LL p, LL a, LL b, LL MOD){ // 1. p を 2 で 割っていく(q: 商, r: 余り). map<LL, LL> t; while(p){ LL q = p >> 1, r = p & 1; t[q] = r; p >>= 1; } // for(auto &p : t) cout << p.first << " " << p.second << endl; // 2. 1. の 結果から, 逆算. // (初期状態) // 第 0成分(1行1列): a, 第 1成分(1行2列): 0, 第 2成分(1行3列): 0 // 第 3成分(2行1列): 1, 第 4成分(2行2列): 1, 第 5成分(2行3列): 0 // 第 6成分(3行1列): 0, 第 7成分(3行2列): b, 第 8成分(3行3列): 1 m[0] = 1, m[1] = 0, m[2] = 0; m[3] = 0, m[4] = 1, m[5] = 0; m[6] = 0, m[7] = 0, m[8] = 1; for(auto &p : t){ if(p.first != 0){ LL t11 = m[0], t12 = m[1], t13 = m[2], t21 = m[3], t22 = m[4], t23 = m[5], t31 = m[6], t32 = m[7], t33 = m[8]; m[0] = matrixProduct(t11, t12, t13, t11, t21, t31, MOD); m[1] = matrixProduct(t11, t12, t13, t12, t22, t32, MOD); m[2] = matrixProduct(t11, t12, t13, t13, t23, t33, MOD); m[3] = matrixProduct(t21, t22, t23, t11, t21, t31, MOD); m[4] = matrixProduct(t21, t22, t23, t12, t22, t32, MOD); m[5] = matrixProduct(t21, t22, t23, t13, t23, t33, MOD); m[6] = matrixProduct(t31, t32, t33, t11, t21, t31, MOD); m[7] = matrixProduct(t31, t32, t33, t12, t22, t32, MOD); m[8] = matrixProduct(t31, t32, t33, t13, t23, t33, MOD); } if(p.second == 1){ LL t11 = m[0], t12 = m[1], t13 = m[2], t21 = m[3], t22 = m[4], t23 = m[5], t31 = m[6], t32 = m[7], t33 = m[8]; m[0] = matrixProduct(t11, t12, t13, a, 1, 0, MOD); m[1] = matrixProduct(t11, t12, t13, 0, 1, b, MOD); m[2] = matrixProduct(t11, t12, t13, 0, 0, 1, MOD); m[3] = matrixProduct(t21, t22, t23, a, 1, 0, MOD); m[4] = matrixProduct(t21, t22, t23, 0, 1, b, MOD); m[5] = matrixProduct(t21, t22, t23, 0, 0, 1, MOD); m[6] = matrixProduct(t31, t32, t33, a, 1, 0, MOD); m[7] = matrixProduct(t31, t32, t33, 0, 1, b, MOD); m[8] = matrixProduct(t31, t32, t33, 0, 0, 1, MOD); } } return; } int main() { // 1. 入力情報取得. LL L, A, B, M; scanf("%lld %lld %lld %lld", &L, &A, &B, &M); // 2. 解説通り. // d = 1, 2, ... , 18 で, 解説にある, 以下の計算式をベースに合算. // [計算式] // (X, s, 1) × matrix33(Cd, 10 の d乗, B, M) = (X × 10 の d乗 + s, s + B, 1) LL ans[3] = {0, A, 1}; LL cur10 = 1, bef10 = 1; // 以下のテストケースが, 正しく通らなかった. // sub1_killer_04.txt // https://www.dropbox.com/sh/arnpe0ef5wds8cv/AAAGk5qU1izrmUvpKMvgSN7ga/ABC129/F/in?dl=0&preview=sub1_killer_04.txt&subfolder_nav_tracking=1 // [入力例] // 1 999999999999999999 999999999999999999 998244353 // // [出力例] // 716070897 が 正解らしいが, 0 と 出力されてしまう. // -> 計算範囲が足りてないことが分かったので, for文 の 範囲 を 修正. // for(int i = 1; i <= 18; i++){ for(int i = 1; i < 20; i++){ // 2-1. 10 の べき乗 を 更新. cur10 *= 10; // 2-2. Cd を 計算. // i を 数列の桁数 と 見て, 計算. // ex. // i = 1, A = 3, B = 4 の 場合. // 0桁 … max(0, 0 - A) ÷ B = 0 // 1桁 … max(0, 9 - A) ÷ B = 1 // -> C1 = 1 - 0 = 1個. // ※ C1 は 2個 の はず. // // i = 2, A = 3, B = 4 の 場合. // 1桁 … max(0, 9 - A) ÷ B = 1 // 2桁 … max(0, 99 - A) ÷ B = 24 // -> C2 = 24 - 1 = 23個. // // i = 3, A = 3, B = 4 の 場合. // 2桁 … max(0, 99 - A) ÷ B = 24 // 3桁 … max(0, 999 - A) ÷ B = 249 // -> C3 = 249 - 24 = 225個. LL d1 = max(0LL, bef10 - 1 - A) / B; LL d2 = max(0LL, cur10 - 1 - A) / B; LL Cd = d2 - d1; // d1 が 0 の場合 かつ d2 が 0 より大きい場合は, // d2 の方で, 初項 A を 含んでいる筈なので, Cd を 1増やす必要があるはず. if(d1 == 0 && d2 > 0) Cd++; // printf("Cd=%lld, L=%lld\n", Cd, L); // printf("cur10=%lld, bef10=%lld\n", cur10, bef10); // 2-3. 行列計算. matrix33(min(Cd, L), cur10, B, M); // 2-4. 行列 ans を 更新. LL t[3] = {0, 0, 0}; t[0] = matrixProduct(ans[0], ans[1], ans[2], m[0], m[3], m[6], M); t[1] = matrixProduct(ans[0], ans[1], ans[2], m[1], m[4], m[7], M); t[2] = matrixProduct(ans[0], ans[1], ans[2], m[2], m[5], m[8], M); swap(t, ans); // 2-5. 計算を継続するかチェック. // 等差数列の長さは, L と指定されているので, 1回計算するごとに, Cd個分 を 減らす 必要あり. L -= Cd; // L が 0以下となったら, 計算終了と見ることが出来る. if(L <= 0) break; // 2-6. 前回 の 10 の べき乗 を 保存. bef10 = cur10; } // for(int i = 0; i < 3; i++) printf("ans[%d]=%lld ", i, ans[i]); // printf("\n"); // 3. 出力 ~ 後処理. printf("%lld\n", ans[0]); 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 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 |
[入力例] 5 3 4 10007 [出力例(debug版)] Cd=2, L=5 Cd=23, L=3 ans[0]=5563 ans[1]=23 ans[2]=1 5563 ※AtCoderテストケースより [入力例] 4 8 1 1000000 [出力例(debug版)] Cd=2, L=4 Cd=90, L=2 ans[0]=891011 ans[1]=12 ans[2]=1 891011 ※AtCoderテストケースより [入力例] 107 10000000000007 1000000000000007 998244353 [出力例(debug版)] Cd=0, L=107 Cd=0, L=107 Cd=0, L=107 Cd=0, L=107 Cd=0, L=107 Cd=0, L=107 Cd=0, L=107 Cd=0, L=107 Cd=0, L=107 Cd=0, L=107 Cd=0, L=107 Cd=0, L=107 Cd=0, L=107 Cd=0, L=107 Cd=0, L=107 Cd=10, L=107 Cd=90, L=97 Cd=900, L=7 ans[0]=39122908 ans[1]=201747450 ans[2]=1 39122908 ※AtCoderテストケースより [入力例(sub1_killer_04.txt)] 1 999999999999999999 999999999999999999 998244353 [出力例(debug版)] Cd=0, L=1 Cd=0, L=1 Cd=0, L=1 Cd=0, L=1 Cd=0, L=1 Cd=0, L=1 Cd=0, L=1 Cd=0, L=1 Cd=0, L=1 Cd=0, L=1 Cd=0, L=1 Cd=0, L=1 Cd=0, L=1 Cd=0, L=1 Cd=0, L=1 Cd=0, L=1 Cd=0, L=1 Cd=0, L=1 Cd=10, L=1 ans[0]=716070897 ans[1]=433897441 ans[2]=1 716070897 ※AtCoderテストケースより [入力例] 123 1234567654321 123456787654321 123454321 [出力例(debug版)] Cd=0, L=123 Cd=0, L=123 Cd=0, L=123 Cd=0, L=123 Cd=0, L=123 Cd=0, L=123 Cd=0, L=123 Cd=0, L=123 Cd=0, L=123 Cd=0, L=123 Cd=0, L=123 Cd=0, L=123 Cd=0, L=123 Cd=0, L=123 Cd=9, L=123 Cd=72, L=114 Cd=729, L=42 ans[0]=24290706 ans[1]=95659107 ans[2]=1 24290706 [入力例] 98765 12345654321 1234567654321 987654321 [出力例(debug版)] Cd=0, L=98765 Cd=0, L=98765 Cd=0, L=98765 Cd=0, L=98765 Cd=0, L=98765 Cd=0, L=98765 Cd=0, L=98765 Cd=0, L=98765 Cd=0, L=98765 Cd=0, L=98765 Cd=0, L=98765 Cd=0, L=98765 Cd=9, L=98765 Cd=72, L=98756 Cd=729, L=98684 Cd=7290, L=97955 Cd=72901, L=90665 Cd=729000, L=17764 ans[0]=768437437 ans[1]=797217809 ans[2]=1 768437437 |
■参照サイト
AtCoder Beginner Contest 129
atcoder_testcases ABC129