C++の練習を兼ねて, AtCoder Beginner Contest 044 の 問題C (高橋君とカード) ～ 問題D (桁和) を解いてみた.
■感想.
1. 方針が全く見えなかったので, 解説を参考に実装したところ, AC版となった.
2. 苦手なdpの訓練を積めたので良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトABC 044/ARC 060 解説をご覧下さい.
■C++版プログラム(問題C／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 |
// 解き直し. // https://img.atcoder.jp/data/arc/060/editorial.pdf #include <bits/stdc++.h> using namespace std; using LL = long long; #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--) LL dp[55][55][3030]; int x[55]; int main(){ // 1. 入力情報. int N, A; scanf("%d %d", &N, &A); rep(i, N) scanf("%d", &x[i]); // 2. dp更新. rep(j, N + 1){ rep(k, N + 1){ rep(s, N * A + 1){ if(!j && !k && !s) dp[j][k][s] = 1; if(j){ if(s < x[j - 1]) dp[j][k][s] = dp[j - 1][k][s]; if(k && s >= x[j - 1]) dp[j][k][s] = dp[j - 1][k][s] + dp[j - 1][k - 1][s - x[j - 1]]; } } } } // 3. 集計. LL ans = 0; repx(k, 1, N + 1) ans += dp[N][k][k * A]; // 4. 出力. 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 43 44 45 |
[入力例] 4 8 7 9 8 9 [出力例] 5 ※AtCoderテストケースより [入力例] 3 8 6 6 9 [出力例] 0 ※AtCoderテストケースより [入力例] 8 5 3 6 2 8 7 6 5 9 [出力例] 19 ※AtCoderテストケースより [入力例] 33 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 [出力例] 8589934591 ※AtCoderテストケースより [入力例] 12 7 10 22 5 1 12 16 11 25 14 7 9 30 [出力例] 7 [入力例] 25 5 3 4 5 6 7 3 4 5 6 7 3 4 5 6 7 3 4 5 6 7 3 4 5 6 7 [出力例] 3721727 |
■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 |
// 解き直し. // https://img.atcoder.jp/data/arc/060/editorial.pdf #include <bits/stdc++.h> using namespace std; using LL = long long; #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--) // n を b進数表記した場合の各桁の和. // @param b: 2以上の整数. // @param n: 1以上の整数. // @return: 計算結果. LL f(LL b, LL n){ if(n < b) return n; else return f(b, n / b) + (n % b); } int main(){ // 1. 入力情報. LL N, S; scanf("%lld %lld", &N, &S); // 2. S = N の 場合. if(N == S){ printf("%lld\n", N + 1); return 0; } // 3. S != N の 場合. // 3-1. 2 <= b <= √N かつ f(b, N) = S となる 整数b が 存在するか. int rn = (int)sqrt(N); repx(b, 2, rn + 1){ if(f((LL)b, N) == S){ printf("%d\n", b); return 0; } } // 3-2. √N < b <= N かつ f(b, N) = S となる 整数b が 存在するか. // 上位桁 p, 下位桁 q として, N = p * b + q, p + q = S に注意. // -> 上位桁 p を 全探索し, 条件を満たすものを探索. // subtask1_100000000000_2.txt などの WA回避のため, ロジック修正. // repx(p, 1, rn){ repr(p, rn, 1){ LL b = (N - S) / (LL)p + 1LL; if(b < 2LL) continue; if(f(b, N) == S){ printf("%lld\n", b); return 0; } } // 3-3. 存在しなかった場合. puts("-1"); 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 |
[入力例] 87654 30 [出力例] 10 ※AtCoderテストケースより [入力例] 87654 138 [出力例] 100 ※AtCoderテストケースより [入力例] 87654 45678 [出力例] -1 ※AtCoderテストケースより [入力例] 31415926535 1 [出力例] 31415926535 ※AtCoderテストケースより [入力例] 1 31415926535 [出力例] -1 ※AtCoderテストケースより [入力例] 2718281828 52 [出力例] 17 [入力例] 17320508075 77 [出力例] 2886751334 |
■参照サイト
AtCoder Beginner Contest 044