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

C++の練習を兼ねて, AtCoder Beginner Contest 175 の問題D (Moving Piece) を解いてみた.

■感想.
1. テストケース(26.txt, 28.txt, 36.txt, 37.txt) の WA回避に苦労したものの, ようやくAC版に到達できたので良かったと思う.
2. WA原因は, 1周期を超える場合の条件分岐が, 上手く実装できてなかったためと推測している.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

本家のサイトABC 175 解説をご覧下さい.

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<LL>;
using vvl = vector<vl>;
#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 pb push_back
int P[5050], memo[5050], idx[5050], gIdx[5050];
LL C[5050];

int main(){
    
    // 1. 入力情報.
    int N;
    LL K;
    scanf("%d %lld", &N, &K);
    rep(i, N) scanf("%d", &P[i + 1]);
    rep(i, N) scanf("%lld", &C[i]);
    
    // 2. 巡回する整数ごとにグループ分け.
    vvi g;     // グループ情報.
    int n = 0; // グループ番号.
    vvl gCum;  // グループごとの累積和.
    repx(i, 1, N + 1){
        vi v;
        int cur = i;
        while(!memo[cur]){
            // 2-1. グループに追加.
            v.pb(cur);
            
            // 2-2. 訪問済みフラグ設定.
            memo[cur] = 1;
            
            // 2-3. グループ番号を設定.
            idx[cur] = n;
            
            // 2-4. 次のマス.
            cur = P[cur];
        }
        
        // 2-5. グループサイズが, 0 より大きい場合.
        int l = v.size();
        if(l){
            // グループを追加.
            g.pb(v);
            
            // グループに関する累積和, 追加.
            vl c(l * 2 + 2, 0LL);
            rep(i, l * 2 + 1) c[i + 1] = c[i] + C[v[i % l] - 1];
            gCum.pb(c);
            
            // グループ番号をインクリメント.
            n++;
        }
    }
    // for(auto &v : g){
    //     for(auto &u : v) printf("%d ", u);
    //     puts("");
    // }
    // repx(i, 1, N + 1) printf("%d ", idx[i]);
    // puts("");
    // for(auto &v : gCum){
    //     for(auto &u : v) printf("%lld ", u);
    //     puts("");
    // }
    
    // 3. 各グループごとに, ゲーム終了時のスコアとして, 有り得る最大値を計算.
    LL ans = -202020202020202020;
    repx(i, 1, N + 1){
        // 3-1. 出発点の所属グループ.
        int sg = idx[i];
        
        // 3-2. 出発点の所属グループのサイズ.
        int gSize = g[sg].size();
        
        // 3-3. 周期を計算.
        LL q = K / (LL)gSize, r = K % (LL)gSize;
        
        // 3-4. 項数 1 ～ r 個 までの累積和を全探索.
        // [gIdx[sg], gIdx[sg] + 1], ..., [gIdx[sg], gIdx[sg] + r] の r個 の 区間 を 確認.
        LL t1 = -202020202020202020;
        repx(j, 1, r + 1) t1 = max(t1, gCum[sg][gIdx[sg] + j] - gCum[sg][gIdx[sg]]);
        
        // 3-5. 1周期以上ある場合.
        LL t2 = -202020202020202020, t3 = -202020202020202020;
        if(q){
            // 1周期以下.
            // [gIdx[sg], gIdx[sg] + r + 1], ..., [gIdx[sg], gIdx[sg] + gSize] の (gSize - r)個 の 区間 も 確認.
            repx(j, r + 1, gSize + 1) t2 = max(t2, gCum[sg][gIdx[sg] + j] - gCum[sg][gIdx[sg]]);
            
            // 1周期を超える場合.
            if(gCum[sg][gSize] > 0){
                // t2 の 結果を優先しない場合.
                t3 = max(t3, t1 + q * gCum[sg][gSize]);
                
                // t2 の 結果を優先する場合.
                t3 = max(t3, t2 + (q - 1) * gCum[sg][gSize]);
            }
        }
        
        // 3-6. 出発点の所属グループにおけるインデックスをインクリメント.
        gIdx[sg]++;
        
        // 3-7. ゲーム終了時のスコアの最大値更新.
        ans = max({ans, t1, t2, t3});
    }
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vi = vector<int>;

using vvi = vector<vi>;

using vl = vector<LL>;

using vvl = vector<vl>;

#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 pb push_back

int P[5050], memo[5050], idx[5050], gIdx[5050];

LL C[5050];

int main(){

// 1. 入力情報.

int N;

LL K;

scanf("%d %lld", &N, &K);

rep(i, N) scanf("%d", &P[i + 1]);

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

// 2. 巡回する整数ごとにグループ分け.

vvi g; // グループ情報.

int n = 0; // グループ番号.

vvl gCum; // グループごとの累積和.

repx(i, 1, N + 1){

vi v;

int cur = i;

while(!memo[cur]){

// 2-1. グループに追加.

v.pb(cur);

// 2-2. 訪問済みフラグ設定.

memo[cur] = 1;

// 2-3. グループ番号を設定.

idx[cur] = n;

// 2-4. 次のマス.

cur = P[cur];

}

// 2-5. グループサイズが, 0 より大きい場合.

int l = v.size();

if(l){

// グループを追加.

g.pb(v);

// グループに関する累積和, 追加.

vl c(l * 2 + 2, 0LL);

rep(i, l * 2 + 1) c[i + 1] = c[i] + C[v[i % l] - 1];

gCum.pb(c);

// グループ番号をインクリメント.

n++;

}

// for(auto &v : g){

// for(auto &u : v) printf("%d ", u);

// puts("");

// }

// repx(i, 1, N + 1) printf("%d ", idx[i]);

// puts("");

// for(auto &v : gCum){

// for(auto &u : v) printf("%lld ", u);

// puts("");

// }

// 3. 各グループごとに, ゲーム終了時のスコアとして, 有り得る最大値を計算.

LL ans = -202020202020202020;

repx(i, 1, N + 1){

// 3-1. 出発点の所属グループ.

int sg = idx[i];

// 3-2. 出発点の所属グループのサイズ.

int gSize = g[sg].size();

// 3-3. 周期を計算.

LL q = K / (LL)gSize, r = K % (LL)gSize;

// 3-4. 項数 1 ～ r 個までの累積和を全探索.

// [gIdx[sg], gIdx[sg] + 1], ..., [gIdx[sg], gIdx[sg] + r] の r個の区間を確認.

LL t1 = -202020202020202020;

repx(j, 1, r + 1) t1 = max(t1, gCum[sg][gIdx[sg] + j] - gCum[sg][gIdx[sg]]);

// 3-5. 1周期以上ある場合.

LL t2 = -202020202020202020, t3 = -202020202020202020;

if(q){

// 1周期以下.

// [gIdx[sg], gIdx[sg] + r + 1], ..., [gIdx[sg], gIdx[sg] + gSize] の (gSize - r)個の区間も確認.

repx(j, r + 1, gSize + 1) t2 = max(t2, gCum[sg][gIdx[sg] + j] - gCum[sg][gIdx[sg]]);

// 1周期を超える場合.

if(gCum[sg][gSize] > 0){

// t2 の結果を優先しない場合.

t3 = max(t3, t1 + q * gCum[sg][gSize]);

// t2 の結果を優先する場合.

t3 = max(t3, t2 + (q - 1) * gCum[sg][gSize]);

}

// 3-6. 出発点の所属グループにおけるインデックスをインクリメント.

gIdx[sg]++;

// 3-7. ゲーム終了時のスコアの最大値更新.

ans = max({ans, t1, t2, t3});

}

// 4. 出力.

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

return 0;

}

[入力例]
5 2
2 4 5 1 3
3 4 -10 -8 8

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

[入力例]
2 3
2 1
10 -7

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

[入力例]
3 3
3 1 2
-1000 -2000 -3000

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

[入力例]
10 58
9 1 6 7 8 4 3 2 10 5
695279662 988782657 -119067776 382975538 -151885171 -177220596 -169777795 37619092 389386780 980092719

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

[入力例]
2 123456789
2 1
17 19

[出力例]
2222222203

[入力例]
2 123456789
2 1
-17 -19

[出力例]
-17

[入力例]
20 123456789
5 11 20 13 8 9 6 1 10 7 17 14 12 16 18 4 19 15 3 2
345187005 572801974 -382445110 761382796 101509048 -359543532 364774926 728781897 486471031 -718645708 674368659 224291754 273642964 154343820 -192054356 328493076 499148737 -321680953 162142316 73149572

[出力例]
48373577749100850

[入力例]
30 314159265
5 11 23 13 8 22 6 1 21 9 17 14 12 16 18 26 19 15 3 2 27 24 20 29 10 4 25 30 7 28
784 707 -116 125 903 -249 630 183 373 -392 478 172 673 -925 697 -590 546 484 -412 953 530 -918 756 -397 36 -818 670 -237 207 77

[出力例]
195825941850

[入力例]
6 2
2 1 4 3 6 5
1 1 2 1 2 3

[出力例]
5

[入力例]
7 15
2 3 1 5 6 7 4
2 -1 3 1 2 12 -10

[出力例]
30

[入力例]

5 2

2 4 5 1 3

3 4 -10 -8 8

[出力例]

※AtCoderテストケースより

[入力例]

2 3

2 1

10 -7

[出力例]

※AtCoderテストケースより

[入力例]

3 3

3 1 2

-1000 -2000 -3000

[出力例]

-1000

※AtCoderテストケースより

[入力例]

10 58

9 1 6 7 8 4 3 2 10 5

695279662 988782657 -119067776 382975538 -151885171 -177220596 -169777795 37619092 389386780 980092719

[出力例]

29507023469

※AtCoderテストケースより

[入力例]

2 123456789

2 1

17 19

[出力例]

2222222203

[入力例]

2 123456789

2 1

-17 -19

[出力例]

-17

[入力例]

20 123456789

5 11 20 13 8 9 6 1 10 7 17 14 12 16 18 4 19 15 3 2

345187005 572801974 -382445110 761382796 101509048 -359543532 364774926 728781897 486471031 -718645708 674368659 224291754 273642964 154343820 -192054356 328493076 499148737 -321680953 162142316 73149572

[出力例]

48373577749100850

[入力例]

30 314159265

5 11 23 13 8 22 6 1 21 9 17 14 12 16 18 26 19 15 3 2 27 24 20 29 10 4 25 30 7 28

784 707 -116 125 903 -249 630 183 373 -392 478 172 673 -925 697 -590 546 484 -412 953 530 -918 756 -397 36 -818 670 -237 207 77

[出力例]

195825941850

[入力例]

6 2

2 1 4 3 6 5

1 1 2 1 2 3

[出力例]

[入力例]

7 15

2 3 1 5 6 7 4

2 -1 3 1 2 12 -10

[出力例]

■参照サイト
AtCoder Beginner Contest 175

C++の練習を兼ねて, AtCoder Beginner Contest 175 の 問題D (Moving Piece) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 175 の問題D (Moving Piece) を解いてみた.

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