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

C++の練習を兼ねて, AtCoder Regular Contest 092 の問題E (Both Sides Merger) を解いてみた.

■感想.
1. 問題E は, 解答方針が見えなかったので, 解説を参考に実装したところ, 何とかAC版に到達できた.
2. 解説を見て, なるほどと感心したものの, これを実装で表現する点に, 非常に苦労したように思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

本家のサイト AtCoder Regular Contest 092 解説をご覧下さい.

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

// 解き直し.
// https://img.atcoder.jp/arc092/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using P = pair<LL, int>;
#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 pof pop_front
#define pob pop_back
#define pub push_back
#define puf push_front
#define a first
#define b second
LL a[1010];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    deque<P> dq;
    LL minus = -202020202020202020, mIdx = -1, oSum = 0, eSum = 0;
    rep(i, N){
        scanf("%lld", &a[i]);
        int x = i & 1;
        P p = {a[i], x};
        dq.pub(p);
        if(minus < a[i]) minus = a[i], mIdx = i;
        if(a[i] >= 0){
            if(x) eSum += a[i];
            else  oSum += a[i];
        }
    }
    
    // 2. 全部の要素が, マイナスの場合.
    if(minus < 0){
        printf("%lld\n", minus);
        printf("%d\n", N - 1);
        rep(i, mIdx)         printf("%d\n", 1);
        rep(i, N - mIdx - 1) printf("%d\n", N - mIdx - i);
        return 0;
    }
    
    // 3. それ以外の場合.
    // -> 偶奇で, より大きい方を選択.
    int f = (eSum > oSum); // 偶奇判定のフラグ.
    vector<int> ans;
    // 左端.
    while(!dq.empty()){
        P p = dq.front();
        if(p.a < 0 || p.b == !f) ans.pub(1), dq.pof();
        else                     break;
    }
    // 右端.
    while(!dq.empty()){
        P p = dq.back();
        if(p.a < 0 || p.b == !f) ans.pub(dq.size()), dq.pob();
        else                     break;
    }
    // それ以外.
    while(!dq.empty()){
        // パターン A(両端残す).
        if(dq.size() >= 3){
            P p1 = dq.front();
            dq.pof();
            P p2 = dq.front();
            dq.pof();
            P p3 = dq.front();
            dq.pof();
            if(p1.b == f && p1.a >= 0 && p3.a >= 0){
                ans.pub(2);
                dq.puf({p1.a + p3.a, f});
            }else if(p1.b == !f){
                ans.pub(1);
                dq.puf(p3);
                dq.puf(p2);
            }else if(p1.b == f && p1.a < 0){
                ans.pub(1);
                dq.puf(p3);
                dq.puf(p2);
            }else{
                dq.puf(p3);
                dq.puf(p2);
                dq.puf(p1);
            }
        }
        
        // パターン B(両端, 中央ともに残さない).
        if(dq.size() >= 4){
            P p1 = dq.front();
            dq.pof();
            P p2 = dq.front();
            dq.pof();
            P p3 = dq.front();
            dq.pof();
            P p4 = dq.front();
            dq.pof();
            if(p1.b == f && p3.a < 0){
                ans.pub(3);
                dq.puf({p2.a + p4.a, !f});
                dq.puf(p1);
            }else if(p1.b == !f){
                ans.pub(1);
                dq.puf(p4);
                dq.puf(p3);
                dq.puf(p2);
            }else{
                dq.puf(p4);
                dq.puf(p3);
                dq.puf(p2);
                dq.puf(p1);
            }
        }
        
        // サイズが, 2.
        if(dq.size() == 2 && dq.front().b == f) ans.pub(1), dq.pof();
        if(dq.size() == 2 && dq.back().b == f)  ans.pub(dq.size()), dq.pob();
        
        // サイズが, 1.
        if(dq.size() == 1) break;
    }
    printf("%lld\n", f ? eSum : oSum);
    printf("%d\n", (int)ans.size());
    for(auto &p : ans) printf("%d\n", p);
    return 0;
    
}

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

// 解き直し.

// https://img.atcoder.jp/arc092/editorial.pdf

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using P = pair<LL, int>;

#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 pof pop_front

#define pob pop_back

#define pub push_back

#define puf push_front

#define a first

#define b second

LL a[1010];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

deque<P> dq;

LL minus = -202020202020202020, mIdx = -1, oSum = 0, eSum = 0;

rep(i, N){

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

int x = i & 1;

P p = {a[i], x};

dq.pub(p);

if(minus < a[i]) minus = a[i], mIdx = i;

if(a[i] >= 0){

if(x) eSum += a[i];

else oSum += a[i];

}

// 2. 全部の要素が, マイナスの場合.

if(minus < 0){

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

printf("%d\n", N - 1);

rep(i, mIdx) printf("%d\n", 1);

rep(i, N - mIdx - 1) printf("%d\n", N - mIdx - i);

return 0;

}

// 3. それ以外の場合.

// -> 偶奇で, より大きい方を選択.

int f = (eSum > oSum); // 偶奇判定のフラグ.

vector<int> ans;

// 左端.

while(!dq.empty()){

P p = dq.front();

if(p.a < 0 || p.b == !f) ans.pub(1), dq.pof();

else break;

}

// 右端.

while(!dq.empty()){

P p = dq.back();

if(p.a < 0 || p.b == !f) ans.pub(dq.size()), dq.pob();

else break;

}

// それ以外.

while(!dq.empty()){

// パターン A(両端残す).

if(dq.size() >= 3){

P p1 = dq.front();

dq.pof();

P p2 = dq.front();

dq.pof();

P p3 = dq.front();

dq.pof();

if(p1.b == f && p1.a >= 0 && p3.a >= 0){

ans.pub(2);

dq.puf({p1.a + p3.a, f});

}else if(p1.b == !f){

ans.pub(1);

dq.puf(p3);

dq.puf(p2);

}else if(p1.b == f && p1.a < 0){

ans.pub(1);

dq.puf(p3);

dq.puf(p2);

}else{

dq.puf(p3);

dq.puf(p2);

dq.puf(p1);

}

// パターン B(両端, 中央ともに残さない).

if(dq.size() >= 4){

P p1 = dq.front();

dq.pof();

P p2 = dq.front();

dq.pof();

P p3 = dq.front();

dq.pof();

P p4 = dq.front();

dq.pof();

if(p1.b == f && p3.a < 0){

ans.pub(3);

dq.puf({p2.a + p4.a, !f});

dq.puf(p1);

}else if(p1.b == !f){

ans.pub(1);

dq.puf(p4);

dq.puf(p3);

dq.puf(p2);

}else{

dq.puf(p4);

dq.puf(p3);

dq.puf(p2);

dq.puf(p1);

}

// サイズが, 2.

if(dq.size() == 2 && dq.front().b == f) ans.pub(1), dq.pof();

if(dq.size() == 2 && dq.back().b == f) ans.pub(dq.size()), dq.pob();

// サイズが, 1.

if(dq.size() == 1) break;

}

printf("%lld\n", f ? eSum : oSum);

printf("%d\n", (int)ans.size());

for(auto &p : ans) printf("%d\n", p);

return 0;

}

[入力例]
5
1 4 3 7 5

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

[入力例]
4
100 100 -1 100

[出力例]
200
2
3
1
※AtCoderテストケースより

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

[入力例]
6
-1 -2 -3 1 2 3

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

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

[入力例]
9
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

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

[入力例]
7
8 1 4 3 7 5 3

[出力例]
22
3
2
2
2

[入力例]
5
-3 -2 -1 -9 -13

[出力例]
-1
4
1
1
3
2

[入力例]
13
-83 840 994 1084 -283 -375 -58 664 562 -170 853 1214 -198

[出力例]
3802
7
1
12
2
3
2
3
2

[入力例]
100
62536621 -12636020 72621087 -6522930 119543690 66294048 -35235198 93877858 -26094807 72086179 112722016 -40301996 -10236702 -12370328 -29856576 -39044819 119659839 67297065 -38546198 -34392459 -44390278 -31447203 93480485 55342861 74789209 103326342 103221147 77828820 97437660 88260408 -2804496 -38531193 -27114944 86388268 81357158 -40247576 96272334 -5690001 -42884202 90401792 113052606 89991396 114931064 -20488013 98379466 61561437 -48724825 -21157473 -43266751 54097040 92922757 70307777 103449247 87477827 58073136 72898620 58809340 -8975631 -2271680 62264875 -5982175 -41765656 65483889 -39490864 69664462 -31273472 91949198 63777269 78515322 96534376 90211813 75033411 56620359 -26654650 -23504039 117369196 -48027981 -46108720 -39974972 95202929 -16774182 81626926 101832312 -26636420 -14852444 -9062756 -22929040 95172526 93071595 -13471908 64941248 -37725370 54127490 104369622 -5049626 -29994342 90907586 121743721 -640853 50557949

[出力例]
2530584136
51
100
99
98
2
2
3
3
2
3
3
2
3
3
2
2
2
2
3
3
2
2
3
2
2
2
3
3
2
2
2
2
3
3
2
2
2
2
2
2
3
3
3
3
2
3
3
2
2
2
3
2

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

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

[入力例]

1 4 3 7 5

[出力例]

※AtCoderテストケースより

[入力例]

100 100 -1 100

[出力例]

200

※AtCoderテストケースより

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

200

[入力例]

-1 -2 -3 1 2 3

[出力例]

※AtCoderテストケースより

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

[入力例]

1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

[出力例]

5000000000

※AtCoderテストケースより

[入力例]

8 1 4 3 7 5 3

[出力例]

[入力例]

-3 -2 -1 -9 -13

[出力例]

-1

[入力例]

-83 840 994 1084 -283 -375 -58 664 562 -170 853 1214 -198

[出力例]

3802

[入力例]

100

62536621 -12636020 72621087 -6522930 119543690 66294048 -35235198 93877858 -26094807 72086179 112722016 -40301996 -10236702 -12370328 -29856576 -39044819 119659839 67297065 -38546198 -34392459 -44390278 -31447203 93480485 55342861 74789209 103326342 103221147 77828820 97437660 88260408 -2804496 -38531193 -27114944 86388268 81357158 -40247576 96272334 -5690001 -42884202 90401792 113052606 89991396 114931064 -20488013 98379466 61561437 -48724825 -21157473 -43266751 54097040 92922757 70307777 103449247 87477827 58073136 72898620 58809340 -8975631 -2271680 62264875 -5982175 -41765656 65483889 -39490864 69664462 -31273472 91949198 63777269 78515322 96534376 90211813 75033411 56620359 -26654650 -23504039 117369196 -48027981 -46108720 -39974972 95202929 -16774182 81626926 101832312 -26636420 -14852444 -9062756 -22929040 95172526 93071595 -13471908 64941248 -37725370 54127490 104369622 -5049626 -29994342 90907586 121743721 -640853 50557949

[出力例]

2530584136

100

■参照サイト
AtCoder Regular Contest 092

C++の練習を兼ねて, AtCoder Regular Contest 092 の 問題E (Both Sides Merger) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 092 の問題E (Both Sides Merger) を解いてみた.

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