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

C++の練習を兼ねて, AtCoder Beginner Contest 260 の問題F (Find 4-cycle) を解いてみた.

■感想.
1. 問題Fは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 解説のロジックで, 4-cycle の存在をチェックできる点が興味深く思った.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト AtCoder Beginner Contest 260 解説の各リンクをご覧下さい.

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

// 解き直し.
// https://atcoder.jp/contests/abc260/editorial/4437
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
#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 main(){
    
    // 1. 入力情報.
    int S, T, M;
    scanf("%d %d %d", &S, &T, &M);
    vvi L(S);
    rep(i, M){
        int u, v;
        scanf("%d %d", &u, &v);
        --u, --v;
        
        // 隣接リスト.
        L[u].pb(v);
    }
    
    // 2. 二次元配列.
    int matrix[3030][3030];
    rep(i, 3030) rep(j, 3030) matrix[i][j] = -1;
    
    // 3. 探索.
    rep(z, S){
        for(auto &x : L[z]){
            for(auto &y : L[z]){
                // Skip.
                if(x == y) continue;
                
                // -1 の 場合.
                if(matrix[x - S][y - S] == -1){
                    matrix[x - S][y - S] = z;
                    continue;
                }
                
                // 4-cycle あり.
                int w = matrix[x - S][y - S];
                printf("%d %d %d %d\n", x + 1, y + 1, z + 1, w + 1);
                return 0;
            }
        }
    }
    
    // 4. 4-cycle なし.
    puts("-1");
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc260/editorial/4437

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

#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 main(){

// 1. 入力情報.

int S, T, M;

scanf("%d %d %d", &S, &T, &M);

vvi L(S);

rep(i, M){

int u, v;

scanf("%d %d", &u, &v);

--u, --v;

// 隣接リスト.

L[u].pb(v);

}

// 2. 二次元配列.

int matrix[3030][3030];

rep(i, 3030) rep(j, 3030) matrix[i][j] = -1;

// 3. 探索.

rep(z, S){

for(auto &x : L[z]){

for(auto &y : L[z]){

// Skip.

if(x == y) continue;

// -1 の場合.

if(matrix[x - S][y - S] == -1){

matrix[x - S][y - S] = z;

continue;

}

// 4-cycle あり.

int w = matrix[x - S][y - S];

printf("%d %d %d %d\n", x + 1, y + 1, z + 1, w + 1);

return 0;

}

// 4. 4-cycle なし.

puts("-1");

return 0;

}

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

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

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

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

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

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

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

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

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

[出力例]
4 5 3 1

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

[出力例]
-1

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

[出力例]
7 11 5 3

[入力例]

2 3 5

1 3

1 4

1 5

2 4

2 5

[出力例]

1 2 4 5

※AtCoderテストケースより

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

4 5 2 1

[入力例]

3 2 4

1 4

1 5

2 5

3 5

[出力例]

-1

※AtCoderテストケースより

[入力例]

4 5 9

3 5

1 8

3 7

1 9

4 6

2 7

4 8

1 7

2 9

[出力例]

1 7 2 9

※AtCoderテストケースより

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

7 9 2 1

[入力例]

3 2 5

1 4

1 5

2 4

3 4

3 5

[出力例]

4 5 3 1

[入力例]

7 5 8

1 8

1 11

3 8

3 9

5 9

5 11

6 9

7 10

[出力例]

-1

[入力例]

5 6 9

1 10

2 7

3 6

3 7

3 11

4 8

4 10

5 7

5 11

[出力例]

7 11 5 3

■参照サイト
AtCoder Beginner Contest 260

C++の練習を兼ねて, AtCoder Beginner Contest 260 の 問題F (Find 4-cycle) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 260 の問題F (Find 4-cycle) を解いてみた.

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