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

C++の練習を兼ねて, AtCoder Beginner Contest 131 の問題E (E – Friendships) を解いてみた.

■感想.
1. スターを作成すると, (N – 1) * (N – 2) / 2 となることまでは, 気付いたものの, 本問との結びつけが見えなかったので, 解答を参考に実装した.
2. 非常に面白い問題だと感じた, グラフ理論の知識を少しずつ増やしていく必要があると感じた.

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

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

// 解き直し.
// ABC 131解説.
// https://img.atcoder.jp/abc131/editorial.pdf
#include <bits/stdc++.h>
using namespace std;

int main() {
    
    // 1. 入力情報取得.
    int N, K;
    scanf("%d %d", &N, &K);
    
    // 2. 以下, 解説通り.
    // -> 解が存在しない場合は, 終了.
    int upper = (N - 1) * (N - 2) / 2;
    if(K > upper){
        printf("%d\n", -1);
        return 0;
    }
    
    // 3. 頂点 1 を中心とするスターを作成後, 
    // 頂点 2 ～ 頂点 N の間に, 必要な本数だけ, 辺を追加し, 出力.
    // -> 必要な本数は, (upper - K)本 とする.
    int M = (N - 1) + (upper - K);
    printf("%d\n", M);
    for(int i = 1; i < N; i++) for(int j = i + 1; j <= N; j++) if(M > 0) printf("%d %d\n", i, j), M--;
    
    // 4. 後処理.
    return 0;
    
}

// 解き直し.

// ABC 131解説.

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

#include <bits/stdc++.h>

using namespace std;

int main() {

// 1. 入力情報取得.

int N, K;

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

// 2. 以下, 解説通り.

// -> 解が存在しない場合は, 終了.

int upper = (N - 1) * (N - 2) / 2;

if(K > upper){

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

return 0;

}

// 3. 頂点 1 を中心とするスターを作成後,

// 頂点 2 ～頂点 N の間に, 必要な本数だけ, 辺を追加し, 出力.

// -> 必要な本数は, (upper - K)本とする.

int M = (N - 1) + (upper - K);

printf("%d\n", M);

for(int i = 1; i < N; i++) for(int j = i + 1; j <= N; j++) if(M > 0) printf("%d %d\n", i, j), M--;

// 4. 後処理.

return 0;

}

[入力例]
5 3

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

[入力例]
5 8

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

[入力例]
5 6

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

[入力例]
2 0

[出力例]
1
1 2

[入力例]
2 1

[出力例]
-1

[入力例]
15 25

[出力例]
80
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 12
2 13
2 14
2 15
3 4
3 5
3 6
3 7
3 8
3 9
3 10
3 11
3 12
3 13
3 14
3 15
4 5
4 6
4 7
4 8
4 9
4 10
4 11
4 12
4 13
4 14
4 15
5 6
5 7
5 8
5 9
5 10
5 11
5 12
5 13
5 14
5 15
6 7
6 8
6 9
6 10
6 11
6 12
6 13
6 14
6 15
7 8
7 9
7 10
7 11
7 12
7 13
7 14
7 15
8 9
8 10
8 11

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

[入力例]

5 3

[出力例]

1 2

1 3

1 4

1 5

2 3

2 4

2 5

※AtCoderテストケースより

[入力例]

5 8

[出力例]

-1

※AtCoderテストケースより

[入力例]

5 6

[出力例]

1 2

1 3

1 4

1 5

[入力例]

2 0

[出力例]

1 2

[入力例]

2 1

[出力例]

-1

[入力例]

15 25

[出力例]

1 2

1 3

1 4

1 5

1 6

1 7

1 8

1 9

1 10

1 11

1 12

1 13

1 14

1 15

2 3

2 4

2 5

2 6

2 7

2 8

2 9

2 10

2 11

2 12

2 13

2 14

2 15

3 4

3 5

3 6

3 7

3 8

3 9

3 10

3 11

3 12

3 13

3 14

3 15

4 5

4 6

4 7

4 8

4 9

4 10

4 11

4 12

4 13

4 14

4 15

5 6

5 7

5 8

5 9

5 10

5 11

5 12

5 13

5 14

5 15

6 7

6 8

6 9

6 10

6 11

6 12

6 13

6 14

6 15

7 8

7 9

7 10

7 11

7 12

7 13

7 14

7 15

8 9

8 10

8 11

■参照サイト
AtCoder Beginner Contest 131

C++の練習を兼ねて, AtCoder Beginner Contest 131 の 問題E (E – Friendships) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 131 の問題E (E – Friendships) を解いてみた.

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