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

C++の練習を兼ねて, AtCoder Beginner Contest 026 の問題C (C – 高橋君の給料) を解いてみた.

■感想.
1. とりあえず, 解説見る前に, AC版となったので良かったと思う.
2. 個人的には, 非常に面白い問題に感じた.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

#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--)
#define pb push_back
const int INF = 123456789;
vector<int> B[33];
int C[33];

int main(){
    
    // 1. 入力情報.
    int N, b;
    scanf("%d", &N);
    rep(i, N - 1){
        scanf("%d", &b);
        B[b].pb(i + 2);
    }
    
    // 2. 部下のいない社員の給料を設定.
    rep(i, 33) C[i] = -INF;
    repx(i, 1, N + 1) if(B[i].size() == 0) C[i] = 1;
    
    // 3. 部下のいる社員の給料を設定.
    bool ok = false;
    while(1){
        // 計算済みフラグを設定.
        ok = true;
        
        // 給料の金額を更新.
        repx(i, 1, N + 1){
            // 直属の部下の給料をチェック.
            int minC = INF, maxC = -INF;
            for(auto &p : B[i]){
                minC = min(minC, C[p]);
                maxC = max(maxC, C[p]);
            }
            // 直属の部下で, -INF が いない場合は, 更新できる.
            if(minC > -INF) C[i] = maxC + minC + 1;
        }
        
        // 計算済みフラグを更新.
        repx(i, 1, N + 1) if(C[i] == -INF) ok = false;
        
        // 計算済みの場合は, 終了.
        if(ok) break;
    }
    // repx(i, 1, N + 1) printf("%d ", C[i]);
    // puts("");
    
    // 4. 出力.
    printf("%d\n", C[1]);
    return 0;
    
}

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

#define pb push_back

const int INF = 123456789;

vector<int> B[33];

int C[33];

int main(){

// 1. 入力情報.

int N, b;

scanf("%d", &N);

rep(i, N - 1){

scanf("%d", &b);

B[b].pb(i + 2);

}

// 2. 部下のいない社員の給料を設定.

rep(i, 33) C[i] = -INF;

repx(i, 1, N + 1) if(B[i].size() == 0) C[i] = 1;

// 3. 部下のいる社員の給料を設定.

bool ok = false;

while(1){

// 計算済みフラグを設定.

ok = true;

// 給料の金額を更新.

repx(i, 1, N + 1){

// 直属の部下の給料をチェック.

int minC = INF, maxC = -INF;

for(auto &p : B[i]){

minC = min(minC, C[p]);

maxC = max(maxC, C[p]);

}

// 直属の部下で, -INF がいない場合は, 更新できる.

if(minC > -INF) C[i] = maxC + minC + 1;

}

// 計算済みフラグを更新.

repx(i, 1, N + 1) if(C[i] == -INF) ok = false;

// 計算済みの場合は, 終了.

if(ok) break;

}

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

// puts("");

// 4. 出力.

printf("%d\n", C[1]);

return 0;

}

[入力例]
5
1
1
1
1

[出力例(debug版)]
3 1 1 1 1 
3
※AtCoderテストケースより

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

[出力例(debug版)]
7 3 3 1 1 1 1 
7
※AtCoderテストケースより

[入力例]
6
1
2
3
3
2

[出力例(debug版)]
11 5 3 1 1 1 
11
※AtCoderテストケースより

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

[出力例(debug版)]
1023 511 255 127 63 31 15 7 3 1 
1023
※AtCoderテストケースより

[入力例]
6
1
1
1
2
2

[出力例(debug版)]
5 3 1 1 1 1 
5

[入力例]
11
1
2
2
3
3
3
4
4
4
4

[出力例(debug版)]
15 7 3 3 1 1 1 1 1 1 1 
15

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

[出力例(debug版)]
1048575 524287 262143 131071 65535 32767 16383 8191 4095 2047 1023 511 255 127 63 31 15 7 3 1 
1048575

100

101

102

103

104

105

106

107

108

109

110

[入力例]

[出力例(debug版)]

3 1 1 1 1

※AtCoderテストケースより

[入力例]

[出力例(debug版)]

7 3 3 1 1 1 1

※AtCoderテストケースより

[入力例]

[出力例(debug版)]

11 5 3 1 1 1

※AtCoderテストケースより

[入力例]

[出力例(debug版)]

1023 511 255 127 63 31 15 7 3 1

1023

※AtCoderテストケースより

[入力例]

[出力例(debug版)]

5 3 1 1 1 1

[入力例]

[出力例(debug版)]

15 7 3 3 1 1 1 1 1 1 1

[入力例]

[出力例(debug版)]

1048575 524287 262143 131071 65535 32767 16383 8191 4095 2047 1023 511 255 127 63 31 15 7 3 1

1048575

■参照サイト
AtCoder Beginner Contest 026

C++の練習を兼ねて, AtCoder Beginner Contest 026 の 問題C (C – 高橋君の給料) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 026 の問題C (C – 高橋君の給料) を解いてみた.

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