C++の練習を兼ねて, AtCoder Beginner Contest 143 の 問題D (D – Triangles) を解いてみた.
■感想.
1. 解説見る前に, AC版となったので良かったと思う.
2. 二重カウント回避, カウント漏れ回避 に 結構時間かかってしまった.
本家のサイトABC 143解説をご覧下さい.
■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 |
#include <bits/stdc++.h> using namespace std; using LL = long long; int main(){ // 1. 入力情報取得. int N; scanf("%d", &N); int L[N]; for(int i = 0; i < N; i++) scanf("%d", &L[i]); // 2. sort. sort(L, L + N); // 3. 三角形をカウント. // ex. // 10 // 1 2 2 3 3 3 4 4 4 4 // -> 90 が正解のはず. // (234系)24 + (443, 442, 441系)36 + (433系)12 + (332, 331系)9 + (322系)3 + (221系)1 + (444系)4 + (333系)1 = 90 LL ans = 0; int a = 0, b = 0, c = 0, minC = 0, maxC = 0, s = 0, e = 0; for(int i = 0; i < N - 2; i++){ for(int j = i + 1; j < N - 1; j++){ // 3-1. 棒の長さ a, b を 取得. a = L[i], b = L[j]; // 3-2. 棒の長さ c を 取得. // minC = abs(a - b) + 1; // 2重カウントとなってしまうので却下. // maxC = a + b - 1; // lower_bound で取得するインデックスの都合から, 修正. // minC = max(a + 1, b + 1); // カウント漏れが発生するため却下. minC = b; maxC = a + b; // 3-3. c となり得る個数をカウント. s = lower_bound(L, L + N, minC) - L; e = lower_bound(L, L + N, maxC) - L; // printf("i=%d j=%d minC=%d s=%d maxC=%d e=%d\n", i, j, minC, s, maxC, e); s = max(s, j + 1); // 2重カウント回避. ans += (LL)(e - s); } } // 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 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 |
[入力例] 4 3 4 2 1 [出力例] i=0 j=1 minC=2 s=1 maxC=3 e=2 i=0 j=2 minC=3 s=2 maxC=4 e=3 i=1 j=2 minC=3 s=2 maxC=5 e=4 1 ※AtCoderテストケースより [入力例] 3 1 1000 1 [出力例(debug版)] i=0 j=1 minC=1 s=0 maxC=2 e=2 0 ※AtCoderテストケースより [入力例] 7 218 786 704 233 645 728 389 [出力例(debug版)] i=0 j=1 minC=233 s=1 maxC=451 e=3 i=0 j=2 minC=389 s=2 maxC=607 e=3 i=0 j=3 minC=645 s=3 maxC=863 e=7 i=0 j=4 minC=704 s=4 maxC=922 e=7 i=0 j=5 minC=728 s=5 maxC=946 e=7 i=1 j=2 minC=389 s=2 maxC=622 e=3 i=1 j=3 minC=645 s=3 maxC=878 e=7 i=1 j=4 minC=704 s=4 maxC=937 e=7 i=1 j=5 minC=728 s=5 maxC=961 e=7 i=2 j=3 minC=645 s=3 maxC=1034 e=7 i=2 j=4 minC=704 s=4 maxC=1093 e=7 i=2 j=5 minC=728 s=5 maxC=1117 e=7 i=3 j=4 minC=704 s=4 maxC=1349 e=7 i=3 j=5 minC=728 s=5 maxC=1373 e=7 i=4 j=5 minC=728 s=5 maxC=1432 e=7 23 ※AtCoderテストケースより [入力例] 7 1 1 1 1 1 1 1 [出力例(debug版)] i=0 j=1 minC=1 s=0 maxC=2 e=7 i=0 j=2 minC=1 s=0 maxC=2 e=7 i=0 j=3 minC=1 s=0 maxC=2 e=7 i=0 j=4 minC=1 s=0 maxC=2 e=7 i=0 j=5 minC=1 s=0 maxC=2 e=7 i=1 j=2 minC=1 s=0 maxC=2 e=7 i=1 j=3 minC=1 s=0 maxC=2 e=7 i=1 j=4 minC=1 s=0 maxC=2 e=7 i=1 j=5 minC=1 s=0 maxC=2 e=7 i=2 j=3 minC=1 s=0 maxC=2 e=7 i=2 j=4 minC=1 s=0 maxC=2 e=7 i=2 j=5 minC=1 s=0 maxC=2 e=7 i=3 j=4 minC=1 s=0 maxC=2 e=7 i=3 j=5 minC=1 s=0 maxC=2 e=7 i=4 j=5 minC=1 s=0 maxC=2 e=7 35 [入力例] 10 1 2 2 3 3 3 4 4 4 4 [出力例] 90 [入力例] 15 5 5 5 5 5 4 4 4 4 1 2 2 3 3 3 [出力例] 345 [入力例] 35 3 1 62 27 76 60 16 83 79 33 19 98 89 3 5 44 43 27 18 5 3 37 19 55 51 39 32 52 16 82 6 8 57 50 48 [出力例] 2017 |
■参照サイト
AtCoder Beginner Contest 143