C++の練習を兼ねて, 競プロ典型 90 問 の 問題066 (Various Arrays) を解いてみた.
■感想.
1. 問題066は, 方針が見えなかったので, (問題066 (Various Arrays) 解説) などを参考に実装したところ, AC版に到達出来た.
2. 期待値の性質について, 確認できたので, 非常に良かったと思う.
3. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.
詳細は, 本家のサイト(GitHub) 競プロ典型 90 問 の 問題066 を ご覧下さい.
■C++版プログラム(問題066／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 |
// 解き直し. // https://github.com/E869120/kyopro_educational_90/blob/main/editorial/066.jpg // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; #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--) int l[111], r[111]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N) scanf("%d %d", &l[i], &r[i]); // 2. 期待値(解説通り). double ans = 0.0; rep(i, N){ repx(j, i + 1, N){ // 全パターン. int a = (r[i] - l[i] + 1) * (r[j] - l[j] + 1); // 転倒数(a[i] > a[j]). int b = 0; if(r[i] > l[j]){ if(l[i] > r[j]) b = a; if(l[i] <= r[j]){ // r[j] ～ r[i] の 部分. b += max(0, r[i] - r[j]) * (r[j] - l[j] + 1); // max(l[i], l[j]) ～ min(r[i], r[j]) の 部分. int x = min(r[i], r[j]); int y = max(l[i], l[j]); b += ((x - l[j]) + (y - l[j])) * (x - y + 1) / 2; } } // 期待値更新. ans += (double)b / (double)a; } } // 3. 出力. printf("%.12lf\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 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 |
[入力例] 2 1 2 1 2 [出力例] 0.250000000000 ※AtCoderテストケースより [入力例] 3 3 3 1 1 4 4 [出力例] 1.000000000000 ※AtCoderテストケースより [入力例] 10 1 10 38 40 8 87 2 9 75 100 45 50 89 92 27 77 23 88 62 81 [出力例] 13.696758921226 ※AtCoderテストケースより [入力例] 7 38 48 16 34 33 78 29 56 38 60 23 47 46 89 [出力例] 7.511059338519 [入力例] 20 11 30 25 65 7 38 25 37 10 17 46 69 19 21 34 34 38 58 30 77 28 36 9 43 39 52 22 66 23 68 18 57 40 79 14 44 15 52 35 66 [出力例] 71.321298694677 [入力例] 30 28 47 14 42 24 26 21 49 16 54 3 24 22 26 29 65 18 26 10 68 28 62 19 78 22 54 20 66 6 56 14 33 28 49 9 65 4 29 24 38 18 37 28 56 16 18 30 64 9 45 17 17 15 44 20 58 25 55 13 29 [出力例] 222.216725416714 |