C++ の動作確認をしてみた（６３９）

C++の練習を兼ねて, AtCoder Beginner Contest 236 の問題E (Average and Median) を解いてみた.

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に実装して, AC版に到達できたと思う.
2. 個人的には, 二分探索の復習, および, 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト AtCoder Beginner Contest 236 解説の各リンクをご覧下さい.

■C++版プログラム(問題E／AC版).

// 解き直し.
// https://atcoder.jp/contests/abc236/editorial/3279
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vl = vector<LL>;
#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 a[101010];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%lld", &a[i]);
    
    // 2. 評価関数(平均値).
    auto f = [&](LL m) -> bool {
        // 2-1. 平均値を, m以上にできるか？
        vl dp(N + 1), pd(N + 1);
        rep(i, N){
            dp[i + 1] = max(dp[i], pd[i]) + (1000 * a[i] - m);
            pd[i + 1] = dp[i];
        }
        
        // 2-2. 判定結果.
        return (max(dp[N], pd[N]) >= 0);
    };
    
    // 3. 評価関数(中央値).
    auto g = [&](LL m) -> bool {
        // 3-1. 中央値を, m以上にできるか？
        vl dp(N + 1), pd(N + 1);
        rep(i, N){
            dp[i + 1] = max(dp[i], pd[i]) + ((a[i] >= m) ? 1 : -1);
            pd[i + 1] = dp[i];
        }
        
        // 3-2. 判定結果.
        return (max(dp[N], pd[N]) > 0);
    };
    
    // 4. 二分探索で確認してみる(平均値).
    LL l = 0, h = 2e12 + 1;
    while(l + 1 < h){
        LL m = (h + l) >> 1;
        if(f(m)) l = m;
        else     h = m;
        // printf("h=%lld l=%lld m=%lld\n", h, l, m);
    }
    LL maxMean = l;
    
    // 5. 二分探索で確認してみる(中央値).
    l = 0, h = 2e9 + 1;
    while(l + 1 < h){
        LL m = (h + l) >> 1;
        if(g(m)) l = m;
        else     h = m;
        // printf("h=%lld l=%lld m=%lld\n", h, l, m);
    }
    LL maxMedian = l;
    
    // 6. 出力.
    printf("%.3lf\n%lld\n", (double)maxMean / 1000.0, maxMedian);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc236/editorial/3279

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vl = vector<LL>;

#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 a[101010];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N) scanf("%lld", &a[i]);

// 2. 評価関数(平均値).

auto f = [&](LL m) -> bool {

// 2-1. 平均値を, m以上にできるか？

vl dp(N + 1), pd(N + 1);

rep(i, N){

dp[i + 1] = max(dp[i], pd[i]) + (1000 * a[i] - m);

pd[i + 1] = dp[i];

}

// 2-2. 判定結果.

return (max(dp[N], pd[N]) >= 0);

};

// 3. 評価関数(中央値).

auto g = [&](LL m) -> bool {

// 3-1. 中央値を, m以上にできるか？

vl dp(N + 1), pd(N + 1);

rep(i, N){

dp[i + 1] = max(dp[i], pd[i]) + ((a[i] >= m) ? 1 : -1);

pd[i + 1] = dp[i];

}

// 3-2. 判定結果.

return (max(dp[N], pd[N]) > 0);

};

// 4. 二分探索で確認してみる(平均値).

LL l = 0, h = 2e12 + 1;

while(l + 1 < h){

LL m = (h + l) >> 1;

if(f(m)) l = m;

else h = m;

// printf("h=%lld l=%lld m=%lld\n", h, l, m);

}

LL maxMean = l;

// 5. 二分探索で確認してみる(中央値).

l = 0, h = 2e9 + 1;

while(l + 1 < h){

LL m = (h + l) >> 1;

if(g(m)) l = m;

else h = m;

// printf("h=%lld l=%lld m=%lld\n", h, l, m);

}

LL maxMedian = l;

// 6. 出力.

printf("%.3lf\n%lld\n", (double)maxMean / 1000.0, maxMedian);

return 0;

}

[入力例]
6
2 1 2 1 1 10

[出力例]
4
2
※AtCoderテストケースより

※但し, 上記のプログラムでは, 以下の内容が出力される.
4.000
2

[入力例]
7
3 1 4 1 5 9 2

[出力例]
5.250000000
4
※AtCoderテストケースより

※但し, 上記のプログラムでは, 以下の内容が出力される.
5.250
4

[入力例]
10
8 18 28 2 18 20 15 17 12 21

[出力例]
20.333
18

[入力例]
50
1534 1993 842 127 172 1834 409 510 1117 1172 804 157 516 1644 1877 505 1468 1204 1752 1445 960 1807 1335 1189 199 1117 394 98 1193 1221 496 470 1391 986 1665 820 447 1229 1454 86 1272 690 136 1853 488 728 1886 380 1221 1779

[出力例]
1259.096
1391

[入力例]
150
93302 62538 89452 42425 44435 71496 29725 90563 8793 99500 92586 16243 86849 53851 22514 39271 69471 80528 64641 58584 19431 66758 49676 47265 93718 1327 64433 13729 69773 84893 95444 15668 14975 81144 48397 32389 16928 97314 13842 16956 130 72861 65377 88928 28591 86404 72886 99434 29164 61853 91776 10823 23759 41434 71850 51656 19927 64536 16592 451 70065 35886 79105 53865 13176 37295 7871 17574 64756 92886 97573 31391 10596 98653 39374 34673 49248 41525 46520 60125 50024 92813 93518 30639 82782 59796 55623 69102 36042 36794 80653 85233 52208 40492 73530 35112 57254 6463 87848 49361 20681 61948 4737 50429 42490 30610 99179 13068 53455 84426 3921 22226 49329 48002 18928 84734 86630 10502 32007 57934 31180 11383 37728 26371 70605 20101 56202 91981 29667 702 96602 74258 50209 26074 86719 9891 99463 24847 52501 56676 38125 85244 3337 59419 75076 5607 4647 38281 49673 3307

[出力例]
65380.076
70065

[入力例]
300
45 48 70 79 96 86 5 89 21 48 45 25 97 45 75 87 11 89 97 93 34 80 77 54 14 68 83 25 33 70 47 95 52 26 29 46 47 58 67 20 66 89 69 42 67 51 57 14 82 62 30 39 89 35 43 57 14 61 14 33 15 66 10 45 90 21 83 39 2 92 24 94 76 73 39 34 95 60 68 77 57 47 79 34 56 14 15 23 51 80 79 2 93 16 16 93 6 67 19 4 1 37 83 99 27 54 36 1 10 76 12 19 86 87 78 23 89 5 27 16 56 19 81 72 46 82 77 94 8 85 33 24 70 59 71 46 71 87 4 18 51 11 48 14 74 83 37 57 82 60 23 60 23 93 97 33 14 11 24 19 42 93 99 63 79 45 5 46 98 14 60 21 87 29 89 55 51 52 44 31 83 93 74 86 58 49 92 99 7 86 94 80 24 53 3 64 35 29 58 27 48 1 53 83 57 6 74 19 78 21 37 13 92 95 84 8 85 39 4 59 74 87 85 97 86 32 28 34 42 5 6 64 15 81 8 2 35 57 32 99 64 34 89 12 54 81 17 91 57 14 99 52 81 91 69 82 88 99 40 34 45 92 9 30 54 80 70 55 62 85 41 65 38 46 82 69 92 18 52 17 19 81 66 21 2 32 3 93 14 26 70 37 94 18 89 50 1 64 92 8

[出力例]
67.476
77

[入力例]

2 1 2 1 1 10

[出力例]

※AtCoderテストケースより

※但し, 上記のプログラムでは, 以下の内容が出力される.

4.000

[入力例]

3 1 4 1 5 9 2

[出力例]

5.250000000

※AtCoderテストケースより

※但し, 上記のプログラムでは, 以下の内容が出力される.

5.250

[入力例]

8 18 28 2 18 20 15 17 12 21

[出力例]

20.333

[入力例]

1534 1993 842 127 172 1834 409 510 1117 1172 804 157 516 1644 1877 505 1468 1204 1752 1445 960 1807 1335 1189 199 1117 394 98 1193 1221 496 470 1391 986 1665 820 447 1229 1454 86 1272 690 136 1853 488 728 1886 380 1221 1779

[出力例]

1259.096

1391

[入力例]

150

93302 62538 89452 42425 44435 71496 29725 90563 8793 99500 92586 16243 86849 53851 22514 39271 69471 80528 64641 58584 19431 66758 49676 47265 93718 1327 64433 13729 69773 84893 95444 15668 14975 81144 48397 32389 16928 97314 13842 16956 130 72861 65377 88928 28591 86404 72886 99434 29164 61853 91776 10823 23759 41434 71850 51656 19927 64536 16592 451 70065 35886 79105 53865 13176 37295 7871 17574 64756 92886 97573 31391 10596 98653 39374 34673 49248 41525 46520 60125 50024 92813 93518 30639 82782 59796 55623 69102 36042 36794 80653 85233 52208 40492 73530 35112 57254 6463 87848 49361 20681 61948 4737 50429 42490 30610 99179 13068 53455 84426 3921 22226 49329 48002 18928 84734 86630 10502 32007 57934 31180 11383 37728 26371 70605 20101 56202 91981 29667 702 96602 74258 50209 26074 86719 9891 99463 24847 52501 56676 38125 85244 3337 59419 75076 5607 4647 38281 49673 3307

[出力例]

65380.076

70065

[入力例]

300

45 48 70 79 96 86 5 89 21 48 45 25 97 45 75 87 11 89 97 93 34 80 77 54 14 68 83 25 33 70 47 95 52 26 29 46 47 58 67 20 66 89 69 42 67 51 57 14 82 62 30 39 89 35 43 57 14 61 14 33 15 66 10 45 90 21 83 39 2 92 24 94 76 73 39 34 95 60 68 77 57 47 79 34 56 14 15 23 51 80 79 2 93 16 16 93 6 67 19 4 1 37 83 99 27 54 36 1 10 76 12 19 86 87 78 23 89 5 27 16 56 19 81 72 46 82 77 94 8 85 33 24 70 59 71 46 71 87 4 18 51 11 48 14 74 83 37 57 82 60 23 60 23 93 97 33 14 11 24 19 42 93 99 63 79 45 5 46 98 14 60 21 87 29 89 55 51 52 44 31 83 93 74 86 58 49 92 99 7 86 94 80 24 53 3 64 35 29 58 27 48 1 53 83 57 6 74 19 78 21 37 13 92 95 84 8 85 39 4 59 74 87 85 97 86 32 28 34 42 5 6 64 15 81 8 2 35 57 32 99 64 34 89 12 54 81 17 91 57 14 99 52 81 91 69 82 88 99 40 34 45 92 9 30 54 80 70 55 62 85 41 65 38 46 82 69 92 18 52 17 19 81 66 21 2 32 3 93 14 26 70 37 94 18 89 50 1 64 92 8

[出力例]

67.476

■参照サイト
AtCoder Beginner Contest 236

C++の練習を兼ねて, AtCoder Beginner Contest 236 の 問題E (Average and Median) を解いてみた.

コメントを残す コメントをキャンセル

C++の練習を兼ねて, AtCoder Beginner Contest 236 の問題E (Average and Median) を解いてみた.

コメントを残すコメントをキャンセル