C++の練習を兼ねて, AtCoder Beginner Contest 132 の 問題F (F – Small Products) を解いてみた.
■感想.
1. 方針も見えず, 解けそうに無かったので, 解答を参考に実装した.
2. 解説上, N の 平方数 を 考えて, DP高速化 を 図る必要があると指摘があり実装したが, DPの組み立て方で, 非常に苦労した.
3. 実装終わったものの, AC版 とならなかった(※必ず, テストケース 03.txt, 12.txt で, WA版 となる).
4. 考えても分からなかったので, 正解者のソース を, 色々眺めていたところ, “N の 平方数 に 1 を 加算する必要がある” ことが判明したので, 修正後, 再提出して, AC版 と なった.
5. AC版となったものの, “N の 平方数 に 1 を 加算する必要がある” ことの理由が分からないため, とりあえず, 解法パターンの一つとして暗記しておくことにした.
本家のサイトABC 132解説をご覧下さい.
■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 |
// 解き直し. // ABC 132解説. // https://img.atcoder.jp/abc132/editorial.pdf #include <bits/stdc++.h> using namespace std; using LL = long long; const LL MOD = 1e9 + 7; const LL MAX_K = 101; const LL MAX_N = 1e5; LL dp[MAX_K][MAX_N]; int main() { // 1. 入力情報取得. LL N, K; scanf("%lld %lld", &N, &K); // 2. 解説通り. // dp[i][x]: 最後の整数が, x であるような i個 の 整数を並べて条件を満たせる場合の数. // ex. // [入力例] // 10 3 // ※下記, dp[3][XX] については, 計算方法を ()内 に, 記載した. // dp[1][1] = 1, dp[2][1] = 10, dp[3][1] = 27 (= dp[2][1] + ... + dp[2][10]) // dp[1][2] = 1, dp[2][2] = 5, dp[3][2] = 22 (= dp[2][1] + dp[2][2] + dp[2][3] + dp[2][4] + dp[2][5]) // dp[1][3] = 1, dp[2][3] = 3, dp[3][3] = 18 (= dp[2][1] + dp[2][2] + dp[2][3]) // dp[1][4] = 1, dp[2][4] = 2, dp[3][4] = 15 (= dp[2][1] + dp[2][2]) // dp[1][5] = 1, dp[2][5] = 2, dp[3][5] = 15 (= dp[2][1] + dp[2][2]) // dp[1][6] = 1, dp[2][6] = 1, dp[3][6] = 10 (= dp[2][1]) // dp[1][7] = 1, dp[2][7] = 1, dp[3][7] = 10 (= dp[2][1]) // dp[1][8] = 1, dp[2][8] = 1, dp[3][8] = 10 (= dp[2][1]) // dp[1][9] = 1, dp[2][9] = 1, dp[3][9] = 10 (= dp[2][1]) // dp[1][10] = 1, dp[2][10] = 1, dp[3][10] = 10 (= dp[2][1]) // -> dp[3][1] + dp[3][2] + ... + dp[3][9] + dp[3][10] = 147通り と 計算するようである. // 正解者のソースを確認したところ, "N の 平方数 に 1 を 加算する必要がある" ことが判明. // LL nr = sqrt(N + 0.0); // 03.txt, 12.txt で, WA版 となるので, 注意. LL nr = sqrt(N + 0.0) + 1; LL ir = N / nr; for(LL x = 1; x < nr + ir; x++) dp[1][x] = 1; for(LL k = 2; k <= K; k++){ // 2-1. N ～ r + 1 まで集計. // ex. // x = 5 に 6 ～ 10, x = 4 に 4 ～ 5 を 集約. for(LL x = nr + ir - 1; x >= nr; x--){ dp[k][x] = dp[k - 1][nr + ir - x] + dp[k][x + 1]; dp[k][x] %= MOD; } // 2-2. r ～ 1 まで集計. // ex. // x = 3 ～ 1 までを集計. for(LL x = nr - 1; x > 0; x--){ dp[k][x] = dp[k][x + 1] + dp[k - 1][nr + ir - x] * (N / x - N / (x + 1)); dp[k][x] %= MOD; } } // for(LL x = 1; x < nr + ir; x++) cout << dp[K][x] << " "; // cout << endl; // 3. 後処理. LL ans = 0; for(LL x = 1; x < nr; x++) ans += dp[K][x], ans %= MOD; for(LL x = nr; x < nr + ir; x++) ans += dp[K][x] * (N / (nr + ir - x) - N / (nr + ir - x + 1)), ans %= MOD; printf("%lld\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 |
[入力例] 10 3 [出力例(debug版)] 27 22 18 15 10 147 ※AtCoderテストケースより [入力例] 3 2 [出力例(debug版)] 3 1 5 ※AtCoderテストケースより [入力例] 2 5 [出力例(debug版)] 8 5 13 [入力例] 5 7 [出力例(debug版)] 589 352 224 1613 [入力例] 314159265 35 [出力例] 457397712 ※AtCoderテストケースより [入力例] 987654321 100 [出力例] 573601723 |
■参照サイト
AtCoder Beginner Contest 132