C++ の動作確認をしてみた（５７１）

C++の練習を兼ねて, 京都大学プログラミングコンテスト 2021 の問題C (Gacha) を解いてみた.

■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に提出して, AC版に到達出来た.
2. 個人的には, 戻りが発生する箇所の考え方など, 大変勉強になったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト京都大学プログラミングコンテスト 2021 解説の各リンクをご覧下さい.

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

// 解き直し.
// https://atcoder.jp/contests/kupc2021/editorial/2862
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#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--)
#define a first
#define b second
LL a[202020], b[202020];
int aCum[202020], bCum[202020], diff[202020];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    map<LL, int> im;
    im[0] = 0;
    rep(i, N){
        scanf("%lld", &a[i]);
        im[a[i]] = 0;
    }
    rep(i, N){
        scanf("%lld", &b[i]);
        im[b[i]] = 0;
    }
    
    // 2. 番号付け.
    map<int, LL> om;
    int idx = -1;
    for(auto &p : im) p.b = ++idx, om[idx] = p.a;
    
    // 3. 累積和.
    rep(i, N){
        aCum[im[a[i]]]++;
        bCum[im[b[i]]]++;
    }
    rep(i, 202020 - 1){
        // ガチャ.
        aCum[i + 1] += aCum[i];
        
        // コイン.
        bCum[i + 1] += bCum[i];
        
        // コイン - ガチャ.
        diff[i + 1] = bCum[i + 1] - aCum[i + 1];
    }
    
    // 4. 全探索.
    LL ans = 202020202020202020, l = 0, r = 0, o = 0;
    bool isPlus = true;
    rep(f, idx + 1){
        // 最終地点が, f の 場合.
        l = om[f] - om[0];
        r = (om[idx] - om[f]) * 2;
        
        // 符号がマイナスの場合は, 戻りが発生する.
        if(!isPlus) o += (om[f] - om[f - 1]) * 2;
        
        // 符号チェック.
        isPlus = (diff[f] < 0) ? false : true;
        
        // 最小値更新.
        ans = min(ans, l + r + o);
    }
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/kupc2021/editorial/2862

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

#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--)

#define a first

#define b second

LL a[202020], b[202020];

int aCum[202020], bCum[202020], diff[202020];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

map<LL, int> im;

im[0] = 0;

rep(i, N){

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

im[a[i]] = 0;

}

rep(i, N){

scanf("%lld", &b[i]);

im[b[i]] = 0;

}

// 2. 番号付け.

map<int, LL> om;

int idx = -1;

for(auto &p : im) p.b = ++idx, om[idx] = p.a;

// 3. 累積和.

rep(i, N){

aCum[im[a[i]]]++;

bCum[im[b[i]]]++;

}

rep(i, 202020 - 1){

// ガチャ.

aCum[i + 1] += aCum[i];

// コイン.

bCum[i + 1] += bCum[i];

// コイン - ガチャ.

diff[i + 1] = bCum[i + 1] - aCum[i + 1];

}

// 4. 全探索.

LL ans = 202020202020202020, l = 0, r = 0, o = 0;

bool isPlus = true;

rep(f, idx + 1){

// 最終地点が, f の場合.

l = om[f] - om[0];

r = (om[idx] - om[f]) * 2;

// 符号がマイナスの場合は, 戻りが発生する.

if(!isPlus) o += (om[f] - om[f - 1]) * 2;

// 符号チェック.

isPlus = (diff[f] < 0) ? false : true;

// 最小値更新.

ans = min(ans, l + r + o);

}

// 5. 出力.

printf("%lld\n", ans);

return 0;

}

[入力例]
4
1 6 7 12
3 5 10 11

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

[入力例]
2
1 2
1 1000000000

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

[入力例]
5
2 8 9 10 13
3 5 6 12 15

[出力例]
22

※実際, 以下の行動で, 移動距離 22 となる.
座標  3 (コイン)
座標  2 (ガチャ)
座標  5 (コイン)
座標  6 (コイン)
座標  8 (ガチャ)
座標  9 (ガチャ)
座標 12 (コイン)
座標 13 (ガチャ)
座標 15 (コイン)
座標 10 (ガチャ)
-> 3 + (3 - 2) * 2 + (10 - 3) + (15 - 10) * 2 = 22

[入力例]
8
1 6 23 50 55 63 83 100
11 15 31 35 72 88 93 97

[出力例]
189

※実際, 以下の行動で, 移動距離 189 となる.
座標  11 (コイン)
座標  15 (コイン)
座標   6 (ガチャ)
座標   1 (ガチャ)
座標  31 (コイン)
座標  23 (ガチャ)
座標  35 (コイン)
座標  50 (ガチャ)
座標  72 (コイン)
座標  88 (コイン)
座標  93 (コイン)
座標  97 (コイン)
座標 100 (ガチャ)
座標  83 (ガチャ)
座標  63 (ガチャ)
座標  55 (ガチャ)
-> 1 + (15 - 1) * 2 + (31 - 1) + (31 - 23) * 2 + (55 - 31) + (100 - 55) * 2 = 189

[入力例]
15
3 8 14 32 34 35 51 57 73 80 83 88 95 98 100
10 18 23 25 27 28 40 44 59 64 68 82 107 111 118

[出力例]
181

※実際, 以下の行動で, 移動距離 181 となる.
座標  10 (コイン)
座標  18 (コイン)
座標  23 (コイン)
座標  14 (ガチャ)
座標   8 (ガチャ)
座標   3 (ガチャ)
座標  25 (コイン)
座標  27 (コイン)
座標  28 (コイン)
座標  32 (ガチャ)
座標  34 (ガチャ)
座標  35 (ガチャ)
座標  40 (コイン)
座標  44 (コイン)
座標  51 (ガチャ)
座標  57 (ガチャ)
座標  59 (コイン)
座標  64 (コイン)
座標  68 (コイン)
座標  73 (ガチャ)
座標  80 (ガチャ)
座標  82 (コイン)
座標  83 (ガチャ)
座標  88 (ガチャ)
座標 107 (コイン)
座標 111 (コイン)
座標 118 (コイン)
座標 100 (ガチャ)
座標  98 (ガチャ)
座標  95 (ガチャ)
-> 23 + (23 - 3) * 2 + (95 - 23) + (118 - 95) * 2 = 181

[入力例]
10
688454010 695372079 700190565 739169216 787159174 793136394 796656444 814339966 822191962 869694568
663823866 681857178 702347983 719953098 721150465 757252320 774871450 831521457 849407523 880851457

[出力例]
951677784

※実際, 以下の行動で, 移動距離 951677784 となる.
座標 663823866 (コイン)
座標 681857178 (コイン)
座標 688454010 (ガチャ)
座標 695372079 (ガチャ)
座標 702347983 (コイン)
座標 700190565 (ガチャ)
座標 719953098 (コイン)
座標 721150465 (コイン)
座標 739169216 (ガチャ)
座標 757252320 (コイン)
座標 774871450 (コイン)
座標 787159174 (ガチャ)
座標 793136394 (ガチャ)
座標 796656444 (ガチャ)
座標 831521457 (コイン)
座標 849407523 (コイン)
座標 880851457 (コイン)
座標 869694568 (ガチャ)
座標 822191962 (ガチャ)
座標 814339966 (ガチャ)
-> 702347983 + (702347983 - 700190565) * 2 + (814339966 - 702347983) + (880851457 - 814339966) * 2 = 951677784

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

[入力例]

1 6 7 12

3 5 10 11

[出力例]

※AtCoderテストケースより

[入力例]

1 2

1 1000000000

[出力例]

1999999998

※AtCoderテストケースより

[入力例]

2 8 9 10 13

3 5 6 12 15

[出力例]

※実際, 以下の行動で, 移動距離 22 となる.

座標 3 (コイン)

座標 2 (ガチャ)

座標 5 (コイン)

座標 6 (コイン)

座標 8 (ガチャ)

座標 9 (ガチャ)

座標 12 (コイン)

座標 13 (ガチャ)

座標 15 (コイン)

座標 10 (ガチャ)

-> 3 + (3 - 2) * 2 + (10 - 3) + (15 - 10) * 2 = 22

[入力例]

1 6 23 50 55 63 83 100

11 15 31 35 72 88 93 97

[出力例]

189

※実際, 以下の行動で, 移動距離 189 となる.

座標 11 (コイン)

座標 15 (コイン)

座標 6 (ガチャ)

座標 1 (ガチャ)

座標 31 (コイン)

座標 23 (ガチャ)

座標 35 (コイン)

座標 50 (ガチャ)

座標 72 (コイン)

座標 88 (コイン)

座標 93 (コイン)

座標 97 (コイン)

座標 100 (ガチャ)

座標 83 (ガチャ)

座標 63 (ガチャ)

座標 55 (ガチャ)

-> 1 + (15 - 1) * 2 + (31 - 1) + (31 - 23) * 2 + (55 - 31) + (100 - 55) * 2 = 189

[入力例]

3 8 14 32 34 35 51 57 73 80 83 88 95 98 100

10 18 23 25 27 28 40 44 59 64 68 82 107 111 118

[出力例]

181

※実際, 以下の行動で, 移動距離 181 となる.

座標 10 (コイン)

座標 18 (コイン)

座標 23 (コイン)

座標 14 (ガチャ)

座標 8 (ガチャ)

座標 3 (ガチャ)

座標 25 (コイン)

座標 27 (コイン)

座標 28 (コイン)

座標 32 (ガチャ)

座標 34 (ガチャ)

座標 35 (ガチャ)

座標 40 (コイン)

座標 44 (コイン)

座標 51 (ガチャ)

座標 57 (ガチャ)

座標 59 (コイン)

座標 64 (コイン)

座標 68 (コイン)

座標 73 (ガチャ)

座標 80 (ガチャ)

座標 82 (コイン)

座標 83 (ガチャ)

座標 88 (ガチャ)

座標 107 (コイン)

座標 111 (コイン)

座標 118 (コイン)

座標 100 (ガチャ)

座標 98 (ガチャ)

座標 95 (ガチャ)

-> 23 + (23 - 3) * 2 + (95 - 23) + (118 - 95) * 2 = 181

[入力例]

688454010 695372079 700190565 739169216 787159174 793136394 796656444 814339966 822191962 869694568

663823866 681857178 702347983 719953098 721150465 757252320 774871450 831521457 849407523 880851457

[出力例]

951677784

※実際, 以下の行動で, 移動距離 951677784 となる.

座標 663823866 (コイン)

座標 681857178 (コイン)

座標 688454010 (ガチャ)

座標 695372079 (ガチャ)

座標 702347983 (コイン)

座標 700190565 (ガチャ)

座標 719953098 (コイン)

座標 721150465 (コイン)

座標 739169216 (ガチャ)

座標 757252320 (コイン)

座標 774871450 (コイン)

座標 787159174 (ガチャ)

座標 793136394 (ガチャ)

座標 796656444 (ガチャ)

座標 831521457 (コイン)

座標 849407523 (コイン)

座標 880851457 (コイン)

座標 869694568 (ガチャ)

座標 822191962 (ガチャ)

座標 814339966 (ガチャ)

-> 702347983 + (702347983 - 700190565) * 2 + (814339966 - 702347983) + (880851457 - 814339966) * 2 = 951677784

■参照サイト
京都大学プログラミングコンテスト 2021

C++の練習を兼ねて, 京都大学プログラミングコンテスト 2021 の 問題C (Gacha) を解いてみた.

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

C++の練習を兼ねて, 京都大学プログラミングコンテスト 2021 の問題C (Gacha) を解いてみた.

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