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

C++の練習を兼ねて, AtCoder Regular Contest 111 の問題C (Too Heavy) を解いてみた.

■感想.
1. 問題Bは, 方針が見えなかったので, 解説を参考に実装して, AC版に到達できたので, 良かったと思う.
2. 個人的には, 実装に非常に苦労したものの, 非常に面白い問題に感じた.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc111/editorial/520
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
using PQ = priority_queue<P, vector<P>, greater<P>>;
using vPQ = vector<PQ>;
using vp = vector<P>;
#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
#define a first
#define b second
int a[202020];  // 人 i の 体重.
int b[202020];  // 荷物 j の 重さ.
int ip[202020]; // 荷物 の index.
int op[202020]; // 人 i に置くべき荷物が, どこ(index)にあるか？

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d", &a[i]);
    rep(i, N) scanf("%d", &b[i]);
    rep(i, N){
        scanf("%d", &ip[i]);
        ip[i]--;
        op[ip[i]] = i;
    }
    
    // 2. 特殊パターン(※すでに条件を満たしている場合).
    bool ok = true;
    rep(i, N){
        if(ip[i] != i){
            ok = false;
            break;
        }
    }
    if(ok){
        puts("0");
        return 0;
    }
    
    // 3. 初期状態チェック.
    ok = true;
    // rep(i, N) if(a[i] <= b[ip[i]]) ok = false;
    rep(i, N){
        // 1_026.txt対応.
        if(ip[i] != i && a[i] <= b[ip[i]]){
            ok = false;
            break;
        }
    }
    if(!ok){
        puts("-1");
        return 0;
    }
    
    // 4. サイクルを抽出.
    int cycle[N], cur;
    memset(cycle, 0, sizeof(cycle));
    vPQ C;
    rep(i, N){
        // 4-1. サイクル保存用.
        PQ c;
        
        // 4-2. 頂点 i から スタート.
        cur = i;
        
        // 4-3. サイクルをチェック.
        while(!cycle[cur]){
            // 4-4. 訪問済みフラグを立てる.
            cycle[cur] = 1;
            
            // 4-5. サイクルに頂点を保存.
            c.push({a[cur], cur}); // { 人 cur の 体重, 頂点 cur }.
            
            // 4-6. 現在頂点を更新し, 次の頂点へ.
            cur = ip[cur];
        }
        
        // 4-7. サイクルを追加.
        if(c.size()) C.pb(c);
    }
    // rep(i, C.size()){
    //     puts("----- start -----");
    //     PQ pq = C[i];
    //     while(!pq.empty()){
    //         int ta = pq.top().a, tb = pq.top().b;
    //         pq.pop();
    //         printf("a=%d b=%d\n", ta, tb);
    //     }
    //     puts("-----  end  -----");
    // }
    
    // 5. 各サイクル.
    // -> 軽い人から順番に確定させる.
    vp ans;
    int memo[N]; // 訪問済フラグ.
    memset(memo, 0, sizeof(memo));
    rep(i, C.size()){
        // 5-1. サイクル取得.
        PQ pq = C[i];
        
        // 5-2. サイクルの頂点をチェック.
        // -> 頂点数が, 1 に なったら終了.
        while(pq.size() > 1){
            // 5-3. 人 j を 取得.
            int j = pq.top().b;
            pq.pop();
            
            // 5-4. 人 j の 荷物(※人 l が 持つべきもの).
            int l = ip[j];
            
            // 5-5. 人 j の 荷物 を 確定.
            if(!memo[j]){
                // 訪問済みフラグ設定.
                memo[j] = 1;
                
                // 人 j の 荷物の場所(※人 k が 持っている).
                int k = op[j];
                
                // 人 j, k の 荷物 を 交換.
                swap(ip[j], ip[k]); // 人 j, k の 持っている荷物を交換.
                swap(op[j], op[l]); // 荷物の場所に対応する 人 の 番号 を 交換.
                
                // 操作情報を追加.
                ans.pb({j, k});
            }
        }
    }
    
    // 6. 出力.
    int al = ans.size();
    printf("%d\n", al);
    rep(i, al) printf("%d %d\n", ans[i].a + 1, ans[i].b + 1);
    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

132

133

134

135

136

137

138

139

140

141

142

143

// 解き直し.

// https://atcoder.jp/contests/arc111/editorial/520

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using P = pair<int, int>;

using PQ = priority_queue<P, vector<P>, greater<P>>;

using vPQ = vector<PQ>;

using vp = vector<P>;

#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

#define a first

#define b second

int a[202020]; // 人 i の体重.

int b[202020]; // 荷物 j の重さ.

int ip[202020]; // 荷物の index.

int op[202020]; // 人 i に置くべき荷物が, どこ(index)にあるか？

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N) scanf("%d", &a[i]);

rep(i, N) scanf("%d", &b[i]);

rep(i, N){

scanf("%d", &ip[i]);

ip[i]--;

op[ip[i]] = i;

}

// 2. 特殊パターン(※すでに条件を満たしている場合).

bool ok = true;

rep(i, N){

if(ip[i] != i){

ok = false;

break;

}

if(ok){

puts("0");

return 0;

}

// 3. 初期状態チェック.

ok = true;

// rep(i, N) if(a[i] <= b[ip[i]]) ok = false;

rep(i, N){

// 1_026.txt対応.

if(ip[i] != i && a[i] <= b[ip[i]]){

ok = false;

break;

}

if(!ok){

puts("-1");

return 0;

}

// 4. サイクルを抽出.

int cycle[N], cur;

memset(cycle, 0, sizeof(cycle));

vPQ C;

rep(i, N){

// 4-1. サイクル保存用.

PQ c;

// 4-2. 頂点 i からスタート.

cur = i;

// 4-3. サイクルをチェック.

while(!cycle[cur]){

// 4-4. 訪問済みフラグを立てる.

cycle[cur] = 1;

// 4-5. サイクルに頂点を保存.

c.push({a[cur], cur}); // { 人 cur の体重, 頂点 cur }.

// 4-6. 現在頂点を更新し, 次の頂点へ.

cur = ip[cur];

}

// 4-7. サイクルを追加.

if(c.size()) C.pb(c);

}

// rep(i, C.size()){

// puts("----- start -----");

// PQ pq = C[i];

// while(!pq.empty()){

// int ta = pq.top().a, tb = pq.top().b;

// pq.pop();

// printf("a=%d b=%d\n", ta, tb);

// }

// puts("----- end -----");

// }

// 5. 各サイクル.

// -> 軽い人から順番に確定させる.

vp ans;

int memo[N]; // 訪問済フラグ.

memset(memo, 0, sizeof(memo));

rep(i, C.size()){

// 5-1. サイクル取得.

PQ pq = C[i];

// 5-2. サイクルの頂点をチェック.

// -> 頂点数が, 1 になったら終了.

while(pq.size() > 1){

// 5-3. 人 j を取得.

int j = pq.top().b;

pq.pop();

// 5-4. 人 j の荷物(※人 l が持つべきもの).

int l = ip[j];

// 5-5. 人 j の荷物を確定.

if(!memo[j]){

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

memo[j] = 1;

// 人 j の荷物の場所(※人 k が持っている).

int k = op[j];

// 人 j, k の荷物を交換.

swap(ip[j], ip[k]); // 人 j, k の持っている荷物を交換.

swap(op[j], op[l]); // 荷物の場所に対応する人の番号を交換.

// 操作情報を追加.

ans.pb({j, k});

}

// 6. 出力.

int al = ans.size();

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

rep(i, al) printf("%d %d\n", ans[i].a + 1, ans[i].b + 1);

return 0;

}

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

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

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

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

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

[入力例]
1
58
998244353
1

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

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

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

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

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

[入力例]

3 4 8 6

5 3 1 3

3 4 2 1

[出力例]

3 4

1 3

4 2

※AtCoderのテストケースより

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

1 4

2 3

4 3

[入力例]

1 2 3 4

4 3 2 1

[出力例]

-1

※AtCoderのテストケースより

[入力例]

998244353

[出力例]

※AtCoderのテストケースより

[入力例]

10 9 11 20 17 8 7 6 19 18

5 3 1 3 4 2 6 1 2 6

2 3 1 6 7 5 4 9 10 8

[出力例]

2 1

1 3

7 5

6 4

5 4

8 10

10 9

[入力例]

11 10 9 13 12 5 13 12 11 19 10 18 11 1 17

1 2 3 4 5 6 7 8 7 6 5 4 3 2 1

4 1 2 5 3 6 8 9 7 11 15 10 12 14 13

[出力例]

3 5

2 5

1 5

5 4

9 8

8 7

11 10

13 15

15 10

12 10

■参照サイト
AtCoder Regular Contest 111

C++の練習を兼ねて, AtCoder Regular Contest 111 の 問題C (Too Heavy) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 111 の問題C (Too Heavy) を解いてみた.

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