C++の練習を兼ねて, AtCoder Beginner Contest 108 の 問題C（Triangular Relationship）を解いてみた.
■感想.
1. 時間内で, テストケース C022_scrambled 以外まで通過出来た.
2. 時間後, 変数 N, K の型 を int -> LL で動作確認したところ, 全テストケース通過出来た.
-> 時間内に, 変数の型 が bug の原因だった点に, 気付けなかったのは残念だったが, 今後の注意点として, 覚えておくようにしたい.
3. テストケース 35897 932 -> 114191 = 54872 + 59319 = 38 * 38 * 38 + 39 * 39 * 39 に等しいことから着想を得て, 以下のようなソースコードとなったが, 個人的には, 解説されているロジックで実装するのが, 一番スマートだと思う.
本家のサイトARC 102 解説をご覧下さい.
■C++版プログラム
|
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 |
// 時間切れ. #include <iostream> using namespace std; typedef long long LL; int main() { // 1. 入力情報取得. // int N, K; // int -> LL に書き換えて動作確認したところ, 全テストケース通過したので, C022_scrambled も, 通過したと想定される. LL N, K; cin >> N >> K; // 2. N以下の正の整数(a, b, c)で, a + b, b + c, c + a が, Kの倍数となっているものの個数を計算. LL total = 0; // // a + b = x * K, b + c = y * K, c + a = z * K (x, y, z は, 正の整数)として, // a + b + c = (x + y + z) * K / 2 = t と置くと, // // a = t - y * K = (x - y + z) * K / 2 // b = t - z * K = (x + y - z) * K / 2 // c = t - x * K = (- x + y + z) * K / 2 // -> a, b, c は, いずれも, K / 2 の 倍数になっている筈. // b を K で割った余り mb. -> a, c を, K で 割った余り ma, mc は, // ma = K - mb, mc = K - mb だが, さらに, ma + mc が, Kの倍数になっている筈なので, // 2 * K - 2 * mb を K で割った余りは, ゼロの筈. // 2-1. C017_scrambled - C022_scrambled 通過出来なかったので, K == 1 のパターンを追加. // C017_scrambled だけ, 通過OK となった. if(K == 1) { total = N * N * N; } // 2-2. K = 2 の場合. if(K == 2) { LL even = N / 2; LL odd = N - even; total = (even * even * even) + (odd * odd * odd); } // 2-3. K > 2 の場合. // 10 8 -> 2 のパターンを対応するため, ロジック修正. if(K > 2) { if(K % 2 != 0) { LL multiplesOfK = N / K; total = multiplesOfK * multiplesOfK * multiplesOfK; } else { double e0 = (N + 0.0) / K; // C022_scrambled 以外は, 通過した. LL e1 = N / K; LL e2 = e1; if (e0 - e1 >= 0.5) e2++; total = e1 * e1 * e1 + e2 * e2 * e2; } } // 3. 出力 ～ 後処理. cout << total << endl; return 0; } |
■参照サイト
AtCoder Beginner Contest 108