C++の練習を兼ねて, AtCoder Beginner Contest 090 の 問題D (D – Remainder Reminder) を解いてみた.
■感想.
1. 解説の方針と異なっているように見えるが, 計算量を落とすようには書けたと思うので, 及第点取れたと思う.
本家のサイトABC 090/ARC 091 解説をご覧下さい.
■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 |
#include <bits/stdc++.h> using namespace std; typedef long long LL; #define FOR(i, a, b) for(LL i=(a); i<=(b); ++i) int main() { // 1. 入力情報取得. LL N, K; cin >> N >> K; // 2. (a, b) の 候補 を カウント. // ex. // b = K + 1: (N + 1) / (K + 1)個 // b = K + 2: (N + 2) / (K + 2)個, (N + 1) / (K + 2)個 // b = K + 3: (N + 3) / (K + 3)個, (N + 2) / (K + 3)個, (N + 1) / (K + 3)個 // ... // b = K + i: (N + i) / (K + i)個, (N + i - 1) / (K + i)個, ..., (N + 1) / (K + i)個 // ... // b = K + (N - K): (2 * N - K) / N個, (2 * N - K - 1) / N個, ..., (N + 1) / N個 => 計(N - K)通り LL ans = 0; FOR(b, K + 1, N){ // 2-1. 上限, 下限 を 計算. // ex. // b = K + i なら, // 上限: (N + i) / (K + i)個 // 下限: (N + 1) / (K + i)個 LL u = (N - K + b) / b, l = (N + 1) / b; // cout << "b=" << b << " u=" << u << " l=" << l << endl; // 2-2. 各区間について集計. // (N - K + b) ～ u * b: u * ((N - K + b) - u * b + 1) => ...個(★①) // u * b - 1 ～ (u - 1) * b: (u - 1) * ((u * b - 1) - (u - 1) * b + 1) => (u - 1) * b個 // ... // (l + 2) * b - 1 ～ (l + 1) * b: (l + 1) * (((l + 2) * b - 1) - (l + 1) * b + 1) => (l * b)個 // (l + 1) * b - 1 ～ (N + 1): l * (((l + 1) * b - 1) - (N + 1) + 1) 個 => ...個(★②) // 下限 ～ 上限 の 場合. FOR(v, l, u){ LL diff = min(N - K + b, (v + 1) * b - 1); // 上限に近い場合に注意(★①). diff -= max(N + 1, v * b); // 下限に近い場合に注意(★②). ans += v * (diff + 1); // cout << "b=" << b << " l=" << l << " u=" << u << " v=" << v << " diff=" << diff << " ans=" << ans << endl; } } // 3. 出力 ～ 後処理. // K = 0 の 場合は, a = 0 の ケース を 除外する必要がある. if(K == 0) ans -= N; cout << ans << endl; 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 |
[入力例] 5 2 [出力例] 7 ※AtCoderテストケースより [入力例] 10 0 [出力例] 100 ※AtCoderテストケースより [入力例] 31415 9265 [出力例] 287927211 ※AtCoderテストケースより [入力例] 100000 12345 [出力例] 5746887726 [入力例] 123456 54321 [出力例] 2444729736 [入力例] 654321 123456 [出力例] 190231592490 |
■参照サイト
AtCoder Beginner Contest 090