C++ | 個人用メモ帳

2021年8月21日

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

C++の練習を兼ねて, 競プロ典型 90 問の問題074 (ABC String 2) を解いてみた.

■感想.
1. 問題074は, 方針が見えなかったので, (問題074 (ABC String 2) 解説) を参考に実装したところ, AC版に到達出来た.
2. 個人的には, 数式で計算できてしまう点が, 非常に面白い問題に感じた.
3. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.

詳細は, 本家のサイト(GitHub) 競プロ典型 90 問の問題074 をご覧下さい.

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

// 解き直し.
// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/074.jpg
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#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--)

int main(){
    
    // 1. 入力情報.
    int N;
    char c[66];
    scanf("%d %s", &N, c);
    
    // 2. 操作回数の最大値(解説通り).
    LL ans = 0;
    rep(i, N) ans += (1LL << i) * (LL)(c[i] - 'a');
    
    // 3. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/074.jpg

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

int main(){

// 1. 入力情報.

int N;

char c[66];

scanf("%d %s", &N, c);

// 2. 操作回数の最大値(解説通り).

LL ans = 0;

rep(i, N) ans += (1LL << i) * (LL)(c[i] - 'a');

// 3. 出力.

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

return 0;

}

[入力例]
3
aba

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

[入力例]
10
aaaaaaaaaa

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

[入力例]
5
baaca

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

[入力例]
24
babaacbaaabaabbaaababbac

[出力例]
20210821

[入力例]
45
cbabbabbbaaaaacaccbcbcabbbbaabbbcbaabbbaaaaaa

[出力例]
502107111900

[入力例]

aba

[出力例]

※AtCoderテストケースより

[入力例]

aaaaaaaaaa

[出力例]

※AtCoderテストケースより

[入力例]

baaca

[出力例]

※AtCoderテストケースより

[入力例]

babaacbaaabaabbaaababbac

[出力例]

20210821

[入力例]

cbabbabbbaaaaacaccbcbcabbbbaabbbcbaabbbaaaaaa

[出力例]

502107111900

■参照サイト
074 – ABC String 2
問題074 (ABC String 2) 解説

2021年8月21日2021年8月21日

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

C++の練習を兼ねて, 競プロ典型 90 問の問題062 (Paint All) を解いてみた.

■感想.
1. 問題062は, 方針が見えなかったので, (問題062 (Paint All) 解説) を参考に実装したところ, AC版に到達出来た.
2. 個人的には, 逆順から考えるという視点が, 非常に面白い問題に感じた.
3. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.

詳細は, 本家のサイト(GitHub) 競プロ典型 90 問の問題062 をご覧下さい.

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

// 解き直し.
// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/062.jpg
// 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 N;
    vi x;
    scanf("%d", &N);
    vvi G(N);
    rep(i, N){
        int a, b;
        scanf("%d %d", &a, &b);
        a--, b--;
        G[a].pb(i);
        G[b].pb(i);
        if((a == i) || (b == i)) x.pb(i);
    }
    
    // 2. 不可能な場合.
    if(x.size() == 0){
        puts("-1");
        return 0;
    }
    
    // 3. 指定した頂点から操作を進めていく.
    // https://ja.wikipedia.org/wiki/幅優先探索
    // -> 本問は, bfs に, 類似した実装で, 対応可能と見る.
    vi ans;
    auto bfs = [&](vvi &G, int s, int* d){
        // 3-1. 空のキュー.
        queue<int> q;
        
        // 3-2. 訪問済みフラグ設定.
        d[s] = 1;
        
        // 3-3. 探索地点 s をキュー q に追加.
        q.push(s);
        
        // 3-4. キューが空になるまで処理.
        while(!q.empty()){
            // 3-5. 頂点を取り出す.
            int u = q.front();
            q.pop();
            
            // 3-6. 操作の保存.
            ans.pb(u);
            
            // 3-7. 取り出した要素を処理.
            for(auto &e : G[u]){
                // 3-8. 未訪問の頂点を処理.
                if(!d[e]) d[e] = 1, q.push(e);
            }
        }
        return;
    };
    int d[N];
    rep(i, N) d[i] = 0;
    for(auto &s : x) if(!d[s]) bfs(G, s, d);
    // rep(i, N) printf("%d ", d[i]);
    // puts("");
    
    // 4. 不可能な場合.
    if(ans.size() != N){
        puts("-1");
        return 0;
    }
    
    // 5. 出力.
    repr(i, N - 1, 0) printf("%d\n", ans[i] + 1);
    return 0;
    
}

// 解き直し.

// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/062.jpg

// 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 N;

vi x;

scanf("%d", &N);

vvi G(N);

rep(i, N){

int a, b;

scanf("%d %d", &a, &b);

a--, b--;

G[a].pb(i);

G[b].pb(i);

if((a == i) || (b == i)) x.pb(i);

}

// 2. 不可能な場合.

if(x.size() == 0){

puts("-1");

return 0;

}

// 3. 指定した頂点から操作を進めていく.

// https://ja.wikipedia.org/wiki/幅優先探索

// -> 本問は, bfs に, 類似した実装で, 対応可能と見る.

vi ans;

auto bfs = [&](vvi &G, int s, int* d){

// 3-1. 空のキュー.

queue<int> q;

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

d[s] = 1;

// 3-3. 探索地点 s をキュー q に追加.

q.push(s);

// 3-4. キューが空になるまで処理.

while(!q.empty()){

// 3-5. 頂点を取り出す.

int u = q.front();

q.pop();

// 3-6. 操作の保存.

ans.pb(u);

// 3-7. 取り出した要素を処理.

for(auto &e : G[u]){

// 3-8. 未訪問の頂点を処理.

if(!d[e]) d[e] = 1, q.push(e);

}

return;

};

int d[N];

rep(i, N) d[i] = 0;

for(auto &s : x) if(!d[s]) bfs(G, s, d);

// rep(i, N) printf("%d ", d[i]);

// puts("");

// 4. 不可能な場合.

if(ans.size() != N){

puts("-1");

return 0;

}

// 5. 出力.

repr(i, N - 1, 0) printf("%d\n", ans[i] + 1);

return 0;

}

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

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

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

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

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

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

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

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

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

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

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

[出力例]
5
4
2
1
3

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

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

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

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

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

144

145

146

147

148

149

150

151

152

153

154

155

[入力例]

3 4

1 3

2 3

2 1

[出力例]

※AtCoderテストケースより

[入力例]

1 1

2 2

3 3

[出力例]

※AtCoderテストケースより

[入力例]

3 4

4 5

1 1

5 1

3 2

[出力例]

-1

※AtCoderテストケースより

[入力例]

5 5

2 4

6 6

5 2

1 3

4 1

[出力例]

※AtCoderテストケースより

[入力例]

5 1

3 9

7 8

9 3

3 7

10 10

3 5

4 7

1 1

6 6

[出力例]

-1

※AtCoderテストケースより

[入力例]

2 3

4 3

3 4

3 5

2 1

[出力例]

[入力例]

3 11

9 4

2 5

7 11

11 5

9 6

5 1

4 3

7 4

6 1

4 3

7 7

[出力例]

[入力例]

10 13

16 8

13 4

9 8

8 1

4 9

15 17

9 13

1 12

2 7

10 16

13 11

14 9

7 1

5 13

14 16

2 10

[出力例]

■参照サイト
062 – Paint All
問題062 (Paint All) 解説

2021年8月19日2021年8月19日

C++ の動作確認をしてみた（５１４）

C++の練習を兼ねて, 競プロ典型 90 問の問題057 (Flip Flap) を解いてみた.

■感想.
1. 問題057は, 方針が見えなかったので, (問題057 (Flip Flap) 解説) を参考に実装したところ, AC版に到達出来た.
2. 行列の掃き出し法について学習出来たので, 非常に良かったと思う..
3. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.

詳細は, 本家のサイト(GitHub) 競プロ典型 90 問の問題057 をご覧下さい.

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

// 解き直し.
// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/057.jpg
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vs = vector<string>;
using LL = long long;
#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 all(x) x.begin(), x.end()
const LL MOD = 998244353;

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    string z(M, '0');
    vs matrix;
    rep(i, N){
        matrix.pb(z);
        int t;
        scanf("%d", &t);
        rep(j, t){
            int a;
            scanf("%d", &a);
            a--;
            matrix[i][a] = '1';
        }
    }
    string S;
    rep(i, M){
        int c;
        scanf("%d", &c);
        S.pb(c + '0');
    }
    // puts("--- Matrix before update ---");
    // rep(i, N) printf("%s\n", matrix[i].c_str());
    // puts("--- Target string ---");
    // printf("%s\n", S.c_str());
    
    // 2. 掃き出し法(mod2版).
    // https://ja.wikipedia.org/wiki/ガウスの消去法
    // ex.
    // [変更前行列]
    // 011001
    // 001001
    // 101011
    // 010110
    // 001100
    // 
    // [変更後行列]
    // 100001
    // 010000
    // 001001
    // 000101
    // 000011
    auto gauss = [&](vs &m, int N, int M) -> vs {
        // 2-1. 戻り値設定.
        vs ret = m;
        
        // 2-2. 各行を順次確認.
        rep(i, N){
            // 降順sort.
            sort(all(ret));
            reverse(all(ret));
            
            // 最初に, '1' となる位置.
            int at = 0;
            rep(j, M){
                if(ret[i][j] == '1'){
                    at = j;
                    break;
                }
            }
            
            // i行目以外(j行目)と比較して, 前項で求めた位置(列)に, '1' が 有れば, 掃き出す.
            rep(j, N){
                if(i != j && ret[j][at] == '1'){
                    // 操作対象を設定.
                    string o = ret[i]; // i行目.
                    string n = ret[j]; // j行目.
                    
                    // j行目の掃き出し.
                    rep(k, M) n[k] = '0' + ((n[k] - '0') ^ (o[k] - '0'));
                    
                    // j行目更新.
                    ret[j] = n;
                }
            }
        }
        
        // 2-3. 返却.
        return ret;
    };
    vs gMatrix = gauss(matrix, N, M);
    // puts("--- Matrix after update ---");
    // rep(i, N) printf("%s\n", gMatrix[i].c_str());
    
    // 3. 1行目のスイッチから, 希望通りのパネルのパターンになるかチェック.
    int index = 0;
    while(index < N){
        // 文字列 S で, 最初に, '1' となる位置.
        int at = -1;
        rep(j, M){
            if(S[j] == '1'){
                at = j;
                break;
            }
        }
        
        // 文字列 S に, '1' が 含まれなかった場合.
        if(at == -1) break;
        
        // 更新後の行列で, 前項で求めた位置に, '1' が 来るものがあるか？
        while(gMatrix[index][at] != '1'){
            index++;
            if(index >= N) break;
        }
        
        // 見つからなかった場合は, 終了.
        if(index >= N) break;
        
        // 見つかった場合, 文字列 S を 更新.
        rep(k, M) S[k] = '0' + ((S[k] - '0') ^ (gMatrix[index][k] - '0'));
        
        // 次行へ.
        index++;
    }
    
    // 4. 希望通りのパネルのパターンを実現出来なかったら終了.
    if(S != z){
        puts("0");
        return 0;
    }
    
    // 5. 希望通りのパネルのパターンを実現できる場合.
    int zCount = 0;
    rep(i, N) if(gMatrix[i] == z) zCount++;
    
    // 6. ボタンの押し方の場合の数を計算.
    LL ans = 1;
    rep(i, zCount) ans <<= 1, ans %= MOD;
    
    // 7. 出力.
    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

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

144

145

146

147

148

149

150

151

152

// 解き直し.

// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/057.jpg

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vs = vector<string>;

using LL = long long;

#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 all(x) x.begin(), x.end()

const LL MOD = 998244353;

int main(){

// 1. 入力情報.

int N, M;

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

string z(M, '0');

vs matrix;

rep(i, N){

matrix.pb(z);

int t;

scanf("%d", &t);

rep(j, t){

int a;

scanf("%d", &a);

a--;

matrix[i][a] = '1';

}

string S;

rep(i, M){

int c;

scanf("%d", &c);

S.pb(c + '0');

}

// puts("--- Matrix before update ---");

// rep(i, N) printf("%s\n", matrix[i].c_str());

// puts("--- Target string ---");

// printf("%s\n", S.c_str());

// 2. 掃き出し法(mod2版).

// https://ja.wikipedia.org/wiki/ガウスの消去法

// ex.

// [変更前行列]

// 011001

// 001001

// 101011

// 010110

// 001100

// [変更後行列]

// 100001

// 010000

// 001001

// 000101

// 000011

auto gauss = [&](vs &m, int N, int M) -> vs {

// 2-1. 戻り値設定.

vs ret = m;

// 2-2. 各行を順次確認.

rep(i, N){

// 降順sort.

sort(all(ret));

reverse(all(ret));

// 最初に, '1' となる位置.

int at = 0;

rep(j, M){

if(ret[i][j] == '1'){

at = j;

break;

}

// i行目以外(j行目)と比較して, 前項で求めた位置(列)に, '1' が有れば, 掃き出す.

rep(j, N){

if(i != j && ret[j][at] == '1'){

// 操作対象を設定.

string o = ret[i]; // i行目.

string n = ret[j]; // j行目.

// j行目の掃き出し.

rep(k, M) n[k] = '0' + ((n[k] - '0') ^ (o[k] - '0'));

// j行目更新.

ret[j] = n;

}

// 2-3. 返却.

return ret;

};

vs gMatrix = gauss(matrix, N, M);

// puts("--- Matrix after update ---");

// rep(i, N) printf("%s\n", gMatrix[i].c_str());

// 3. 1行目のスイッチから, 希望通りのパネルのパターンになるかチェック.

int index = 0;

while(index < N){

// 文字列 S で, 最初に, '1' となる位置.

int at = -1;

rep(j, M){

if(S[j] == '1'){

at = j;

break;

}

// 文字列 S に, '1' が含まれなかった場合.

if(at == -1) break;

// 更新後の行列で, 前項で求めた位置に, '1' が来るものがあるか？

while(gMatrix[index][at] != '1'){

index++;

if(index >= N) break;

}

// 見つからなかった場合は, 終了.

if(index >= N) break;

// 見つかった場合, 文字列 S を更新.

rep(k, M) S[k] = '0' + ((S[k] - '0') ^ (gMatrix[index][k] - '0'));

// 次行へ.

index++;

}

// 4. 希望通りのパネルのパターンを実現出来なかったら終了.

if(S != z){

puts("0");

return 0;

}

// 5. 希望通りのパネルのパターンを実現できる場合.

int zCount = 0;

rep(i, N) if(gMatrix[i] == z) zCount++;

// 6. ボタンの押し方の場合の数を計算.

LL ans = 1;

rep(i, zCount) ans <<= 1, ans %= MOD;

// 7. 出力.

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

return 0;

}

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

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

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

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

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

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

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

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

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

[出力例]
1

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

[出力例]
1

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

[出力例]
16

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

[入力例]

2 3

1 2

2 3

1 0 1

[出力例]

※AtCoderテストケースより

[入力例]

2 3

0 1 1

[出力例]

※AtCoderテストケースより

[入力例]

3 2

1 0

[出力例]

※AtCoderテストケースより

[入力例]

13 6

1 3 5

1 4 5

3 4 5 6

2 5

1 2 3 5

3 4 6

4 5 6

1 2 3 4 5 6

1 3 5 6

1 2 4

1 5 6

1 2 3 4

1 0 0 1 0 0

[出力例]

128

※AtCoderテストケースより

[入力例]

5 6

2 3 6

3 6

1 3 5 6

2 4 5

3 4

1 0 1 1 0 1

[出力例]

[入力例]

7 10

2 3 5 6 8 9

2 4 6 7 8

3 4 5 6 7 8

1 2 3 5 8

4 5 6

1 3 4 5 6 7 8 9

5 7 8 9 10

1 0 1 0 1 1 0 0 0 1

[出力例]

[入力例]

10 15

4 6 12

9 13

4 6 13

3 9 11 12 13

4 6 13

9 13

1 2 4

3 7 8

4 6 12

0 0 1 1 0 1 1 1 1 0 0 0 0 0 0

[出力例]

■参照サイト
057 – Flip Flap
問題057 (Flip Flap) 解説

2021年8月18日

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

C++の練習を兼ねて, 競プロ典型 90 問の問題054 (Takahashi Number) を解いてみた.

■感想.
1. 問題054は, 方針が見えなかったので, (問題054 (Takahashi Number) 解説) を参考に実装したところ, AC版に到達出来た.
2. 幅優先探索(応用版, グラフの辺数削減)の復習が出来たので, 非常に良かったと思う..
3. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.

詳細は, 本家のサイト(GitHub) 競プロ典型 90 問の問題054 をご覧下さい.

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

// 解き直し.
// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/054.jpg
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vvi = vector<vector<int>>;
#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 N, M;
    scanf("%d %d", &N, &M);
    vvi G(N + M);
    rep(i, M){
        int k;
        scanf("%d", &k);
        
        // 新たに追加する頂点.
        int u = N + i;
        
        // グラフ作成.
        rep(j, k){
            int v;
            scanf("%d", &v);
            v--;
            G[u].pb(v);
            G[v].pb(u);
        }
    }
    
    // 2. 頂点 1 から 各頂点までの距離を計算.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, int* d){
        // 2-1. 空のキュー.
        queue<int> q;
        
        // 2-2. スタート地点(距離 0)を設定.
        d[s] = 0;
        
        // 2-3. 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // 2-4. キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 2-5. 取り出した要素を処理.
            for(auto &e : G[u]){
                // 2-5. 未訪問の頂点を処理.
                if((d[e] == -1) && e != s) d[e] = d[u] + 1, q.push(e);
            }
        }
        return;
    };
    int d[N + M];
    rep(i, N + M) d[i] = -1;
    bfs(G, 0, d);
    // rep(i, N + M) printf("%d ", d[i]);
    // puts("");
    
    // 3. 出力.
    rep(i, N) printf("%d\n", (d[i] != -1) ? (d[i] / 2) : -1);
    return 0;
    
}

// 解き直し.

// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/054.jpg

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vvi = vector<vector<int>>;

#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 N, M;

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

vvi G(N + M);

rep(i, M){

int k;

scanf("%d", &k);

// 新たに追加する頂点.

int u = N + i;

// グラフ作成.

rep(j, k){

int v;

scanf("%d", &v);

v--;

G[u].pb(v);

G[v].pb(u);

}

// 2. 頂点 1 から各頂点までの距離を計算.

// https://ja.wikipedia.org/wiki/幅優先探索

auto bfs = [&](vvi &G, int s, int* d){

// 2-1. 空のキュー.

queue<int> q;

// 2-2. スタート地点(距離 0)を設定.

d[s] = 0;

// 2-3. 探索地点 s をキュー q に追加.

q.push(s);

while(!q.empty()){

// 2-4. キューから取り出す.

int u = q.front();

q.pop();

// 2-5. 取り出した要素を処理.

for(auto &e : G[u]){

// 2-5. 未訪問の頂点を処理.

if((d[e] == -1) && e != s) d[e] = d[u] + 1, q.push(e);

}

return;

};

int d[N + M];

rep(i, N + M) d[i] = -1;

bfs(G, 0, d);

// rep(i, N + M) printf("%d ", d[i]);

// puts("");

// 3. 出力.

rep(i, N) printf("%d\n", (d[i] != -1) ? (d[i] / 2) : -1);

return 0;

}

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

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

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

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

[入力例]
4 1
3
2 3 4

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

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

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

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

[出力例]
0
1
1
1
1
2
2

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

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

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

144

145

146

[入力例]

6 3

1 2 3

3 4

5 6

[出力例]

-1

※AtCoderテストケースより

[入力例]

4 3

1 2

2 3

3 4

[出力例]

※AtCoderテストケースより

[入力例]

4 1

2 3 4

[出力例]

-1

※AtCoderテストケースより

[入力例]

11 5

2 6 9 10

1 3 8

2 4 6 8 10

6 7

5 6 7 8

[出力例]

-1

※AtCoderテストケースより

[入力例]

7 3

1 2 3 4

1 5

5 6 7

[出力例]

[入力例]

25 13

1 2 3 4 5

2 17

17 18 19 20

3 6

6 10

6 7

7 8 9

5 11

11 12

11 13

13 14 15 16

8 21

21 22 23 24 25

[出力例]

■参照サイト
054 – Takahashi Number
問題054 (Takahashi Number) 解説

2021年8月14日

■感想.
1. 問題045は, 実装方針が見えなかったので, (問題045 (Simple Grouping) 解説プログラム) を参考に実装したところ, AC版に到達出来た.
2. 苦手な動的計画法(本問では, bit DP)の訓練を積めたので, 非常に良かったと思う.
3. ある集合に対する部分集合を網羅する形については, いったん, 実装パターンの一つとして, 覚えてしまおうと思う.
4. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.

詳細は, 本家のサイト(GitHub) 競プロ典型 90 問の問題045 をご覧下さい.

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

// 解答不能.
// https://github.com/E869120/kyopro_educational_90/blob/main/sol/045.cpp
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#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--)
const LL INF = 2020202020202020202;
LL x[16], y[16], dp[16][1 << 16], d[16][16], dGroup[1 << 16];

int main(){
    
    // 1. 入力情報.
    int N, K;
    scanf("%d %d", &N, &K);
    rep(i, N) scanf("%lld %lld", &x[i], &y[i]);
    
    // 2. 二点間の距離を保存.
    rep(a, N) repx(b, a + 1, N) d[a][b] = (x[a] - x[b]) * (x[a] - x[b]) + (y[a] - y[b]) * (y[a] - y[b]);
    
    // 3. グループに含まれる点の集合に関する二点間距離.
    rep(bit, 1 << N){
        rep(a, N){
            repx(b, a + 1, N){
                bool ok1 = bit & (1 << a);
                bool ok2 = bit & (1 << b);
                if(ok1 && ok2) dGroup[bit] = max(dGroup[bit], d[a][b]);
            }
        }
    }
    
    // 4. dp更新(解説通り).
    rep(i, 16) rep(bit, 1 << N) dp[i][bit] = INF;
    dp[0][0] = 0;
    repx(cnt, 1, K + 1){
        repx(bit, 1, 1 << N){
            // ex. 
            // bit = 5 の 場合.
            // (1回目) b = 5 は, b = bit (= 5) で 初期化した値が, 0 でないので, 処理開始.
            // (2回目) b = 4 は, (b - 1) & bit = (5 - 1) & 5 = 100 & 101 = 100 = 4 に, 更新され, 処理を継続.
            // (3回目) b = 1 は, (b - 1) & bit = (4 - 1) & 5 = 011 & 101 = 010 = 1 に, 更新され, 処理を継続.
            // (4回目) b = 0 は, (b - 1) & bit = (1 - 1) & 5 = 000 & 101 = 000 = 0 に, 更新され, b = 0 と
            //         なるため, 処理は行わず, 終了.
            // 
            // bit = 6 の 場合.
            // (1回目) b = 6 は, b = bit (= 6) で 初期化した値が, 0 でないので, 処理開始.
            // (2回目) b = 4 は, (b - 1) & bit = (6 - 1) & 6 = 101 & 110 = 100 = 4 に, 更新され, 処理を継続.
            // (3回目) b = 2 は, (b - 1) & bit = (4 - 1) & 6 = 011 & 110 = 010 = 2 に, 更新され, 処理を継続.
            // (4回目) b = 0 は, (b - 1) & bit = (2 - 1) & 6 = 001 & 110 = 000 = 0 に, 更新され, b = 0 と
            //         なるため, 処理は行わず, 終了.
            // 
            // bit の 部分集合 b を 列挙する場合, このような実装で, 列挙可能なので, 暗記すること.
            for(int b = bit; b != 0; b = (b - 1) & bit){
                dp[cnt][bit] = min(dp[cnt][bit], max(dp[cnt - 1][bit - b], dGroup[b]));
            }
        }
    }
    
    // 5. 出力.
    printf("%lld\n", dp[K][(1 << N) - 1]);
    return 0;
    
}

// 解答不能.

// https://github.com/E869120/kyopro_educational_90/blob/main/sol/045.cpp

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

const LL INF = 2020202020202020202;

LL x[16], y[16], dp[16][1 << 16], d[16][16], dGroup[1 << 16];

int main(){

// 1. 入力情報.

int N, K;

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

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

// 2. 二点間の距離を保存.

rep(a, N) repx(b, a + 1, N) d[a][b] = (x[a] - x[b]) * (x[a] - x[b]) + (y[a] - y[b]) * (y[a] - y[b]);

// 3. グループに含まれる点の集合に関する二点間距離.

rep(bit, 1 << N){

rep(a, N){

repx(b, a + 1, N){

bool ok1 = bit & (1 << a);

bool ok2 = bit & (1 << b);

if(ok1 && ok2) dGroup[bit] = max(dGroup[bit], d[a][b]);

}

// 4. dp更新(解説通り).

rep(i, 16) rep(bit, 1 << N) dp[i][bit] = INF;

dp[0][0] = 0;

repx(cnt, 1, K + 1){

repx(bit, 1, 1 << N){

// ex.

// bit = 5 の場合.

// (1回目) b = 5 は, b = bit (= 5) で初期化した値が, 0 でないので, 処理開始.

// (2回目) b = 4 は, (b - 1) & bit = (5 - 1) & 5 = 100 & 101 = 100 = 4 に, 更新され, 処理を継続.

// (3回目) b = 1 は, (b - 1) & bit = (4 - 1) & 5 = 011 & 101 = 010 = 1 に, 更新され, 処理を継続.

// (4回目) b = 0 は, (b - 1) & bit = (1 - 1) & 5 = 000 & 101 = 000 = 0 に, 更新され, b = 0 と

// なるため, 処理は行わず, 終了.

// bit = 6 の場合.

// (1回目) b = 6 は, b = bit (= 6) で初期化した値が, 0 でないので, 処理開始.

// (2回目) b = 4 は, (b - 1) & bit = (6 - 1) & 6 = 101 & 110 = 100 = 4 に, 更新され, 処理を継続.

// (3回目) b = 2 は, (b - 1) & bit = (4 - 1) & 6 = 011 & 110 = 010 = 2 に, 更新され, 処理を継続.

// (4回目) b = 0 は, (b - 1) & bit = (2 - 1) & 6 = 001 & 110 = 000 = 0 に, 更新され, b = 0 と

// なるため, 処理は行わず, 終了.

// bit の部分集合 b を列挙する場合, このような実装で, 列挙可能なので, 暗記すること.

for(int b = bit; b != 0; b = (b - 1) & bit){

dp[cnt][bit] = min(dp[cnt][bit], max(dp[cnt - 1][bit - b], dGroup[b]));

}

// 5. 出力.

printf("%lld\n", dp[K][(1 << N) - 1]);

return 0;

}

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

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

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

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

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

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

[入力例]
3 2
0 0
500000000 500000000
1000000000 1000000000

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

[入力例]
6 3
8 17
19 0
3 11
17 2
7 9
7 8

[出力例]
25

[入力例]
15 7
9072 13350
8690 5307
10119 8053
12181 2151
13862 8198
15328 12448
201 7924
3290 3864
9639 8669
7166 13829
5017 15790
8567 6296
3668 3896
4102 5898
2976 9086

[出力例]
20211656

[入力例]

3 2

0 1

1 2

2 0

[出力例]

※AtCoderテストケースより

[入力例]

5 3

0 0

1 1

0 2

2 3

3 1

[出力例]

※AtCoderテストケースより

[入力例]

10 4

0 3

3 5

2 7

9 0

5 6

4 3

7 8

6 5

9 9

2 1

[出力例]

※AtCoderテストケースより

[入力例]

3 2

0 0

500000000 500000000

1000000000 1000000000

[出力例]

500000000000000000

※AtCoderテストケースより

[入力例]

6 3

8 17

19 0

3 11

17 2

7 9

7 8

[出力例]

[入力例]

15 7

9072 13350

8690 5307

10119 8053

12181 2151

13862 8198

15328 12448

201 7924

3290 3864

9639 8669

7166 13829

5017 15790

8567 6296

3668 3896

4102 5898

2976 9086

[出力例]

20211656

■参照サイト
045 – Simple Grouping
問題045 (Simple Grouping) 解説
 問題045 (Simple Grouping) 解説プログラム

2021年8月12日

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

C++の練習を兼ねて, AtCoder Regular Contest 121 の問題D (1 or 2) を解いてみた.

■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考に実装したところ, AC版に到達出来た.
2. 個人的には, 非常に面白い問題に感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc121/editorial/1929
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vl = vector<LL>;
#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 all(x) x.begin(), x.end()
const LL INF = 202020202020202020;

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vl a(N);
    rep(i, N) scanf("%lld", &a[i]);
    
    // 2. 解説通り.
    // ex.
    // [入力例]
    // 1
    // 1
    // 
    // [出力例]
    // 0
    // -> 下記で, 上限が, N だと, 202020202020202020 で不正解となるので, N + 1 に 修正.
    LL ans = INF;
    rep(k, N + 1){
        // 2-1. 偶奇チェック.
        bool ok = a.size() & 1;
        
        // 2-2. 偶数の場合.
        if(!ok){
            // 並び替え.
            sort(all(a));
            
            // 黒板に, おいしさの総和を書き込む.
            LL X = -INF, Y = INF;
            int l = a.size();
            rep(i, l / 2){
                X = max(X, a[i] + a[l - 1 - i]);
                Y = min(Y, a[i] + a[l - 1 - i]);
            }
            
            // 最小値更新.
            ans = min(ans, X - Y);
        }
        
        // 2-3. おいしさ 0 の 飴を追加.
        a.pb(0);
    }
    
    // 3. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc121/editorial/1929

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vl = vector<LL>;

#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 all(x) x.begin(), x.end()

const LL INF = 202020202020202020;

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vl a(N);

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

// 2. 解説通り.

// ex.

// [入力例]

// 1

// [出力例]

// 0

// -> 下記で, 上限が, N だと, 202020202020202020 で不正解となるので, N + 1 に修正.

LL ans = INF;

rep(k, N + 1){

// 2-1. 偶奇チェック.

bool ok = a.size() & 1;

// 2-2. 偶数の場合.

if(!ok){

// 並び替え.

sort(all(a));

// 黒板に, おいしさの総和を書き込む.

LL X = -INF, Y = INF;

int l = a.size();

rep(i, l / 2){

X = max(X, a[i] + a[l - 1 - i]);

Y = min(Y, a[i] + a[l - 1 - i]);

}

// 最小値更新.

ans = min(ans, X - Y);

}

// 2-3. おいしさ 0 の飴を追加.

a.pb(0);

}

// 3. 出力.

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

return 0;

}

[入力例]
3
1 2 4

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

[入力例]
2
-100 -50

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

[入力例]
20
-18 31 -16 12 -44 -5 24 17 -37 -31 46 -24 -2 11 32 16 0 -39 35 38

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

[入力例]
1
1

[出力例]
0

[入力例]
2
1 2

[出力例]
0

[入力例]
3
1 2 3

[出力例]
0

[入力例]
3
1 3 5

[出力例]
1

[入力例]
21
31 41 5 9 26 5 35 8 9 7 9 32 38 46 26 43 38 32 7 9 50

[出力例]
12

[入力例]
121
79988539 -29764516 110500823 -9553770 122052717 35889530 109122914 87835196 34199482 51003753 105345497 35959382 119883158 60097773 20957937 49029428 25797915 -82831743 96555263 99000563 81855143 100300884 -14261713 -75027269 83752596 8176453 72026484 -15715087 1520438 60245929 114012863 93846539 -5761856 122197901 -102467095 33691980 -2815053 501532 1478489 10516592 57117070 89072601 53588872 33548106 87253011 35682803 87783913 20146669 13843918 -56648138 24796951 39095602 117635420 56956793 -111049673 68792046 50431762 102414331 48179637 54500021 955443 83538932 78720093 42277483 -75511798 97301197 27628288 -24148751 59593800 112502588 103719433 82917710 13004654 69132735 -52623152 3835502 -96287081 102534147 1259795 -68930289 77198787 -58356999 72711833 -90728405 26977968 51190002 29596711 -113534566 60841814 85379197 80988643 62552677 1090506 37507199 48393534 51064674 -57321781 4704683 38101109 58287614 117085309 100840043 -48315351 57552620 84701342 -84001103 96969254 30566773 122490206 36723142 2594296 24766119 70210397 5065691 -52880436 114670894 52099704 100661123 37032890 -107154544 77854736

[出力例]
79129043

[入力例]

1 2 4

[出力例]

※AtCoderのテストケースより

[入力例]

-100 -50

[出力例]

※AtCoderのテストケースより

[入力例]

-18 31 -16 12 -44 -5 24 17 -37 -31 46 -24 -2 11 32 16 0 -39 35 38

[出力例]

※AtCoderのテストケースより

[入力例]

[出力例]

[入力例]

1 2

[出力例]

[入力例]

1 2 3

[出力例]

[入力例]

1 3 5

[出力例]

[入力例]

31 41 5 9 26 5 35 8 9 7 9 32 38 46 26 43 38 32 7 9 50

[出力例]

[入力例]

121

79988539 -29764516 110500823 -9553770 122052717 35889530 109122914 87835196 34199482 51003753 105345497 35959382 119883158 60097773 20957937 49029428 25797915 -82831743 96555263 99000563 81855143 100300884 -14261713 -75027269 83752596 8176453 72026484 -15715087 1520438 60245929 114012863 93846539 -5761856 122197901 -102467095 33691980 -2815053 501532 1478489 10516592 57117070 89072601 53588872 33548106 87253011 35682803 87783913 20146669 13843918 -56648138 24796951 39095602 117635420 56956793 -111049673 68792046 50431762 102414331 48179637 54500021 955443 83538932 78720093 42277483 -75511798 97301197 27628288 -24148751 59593800 112502588 103719433 82917710 13004654 69132735 -52623152 3835502 -96287081 102534147 1259795 -68930289 77198787 -58356999 72711833 -90728405 26977968 51190002 29596711 -113534566 60841814 85379197 80988643 62552677 1090506 37507199 48393534 51064674 -57321781 4704683 38101109 58287614 117085309 100840043 -48315351 57552620 84701342 -84001103 96969254 30566773 122490206 36723142 2594296 24766119 70210397 5065691 -52880436 114670894 52099704 100661123 37032890 -107154544 77854736

[出力例]

79129043

■参照サイト
NOMURA プログラミングコンテスト 2021(AtCoder Regular Contest 121)

2021年8月9日

C++ の動作確認をしてみた（５１０）

C++の練習を兼ねて, AtCoder Beginner Contest 213 の問題C (Reorder Cards) ～問題D (Takahashi Tour) を解いてみた.

■感想.
1. 問題Dは, 過去問, (AtCoder Beginner Contest 202 (E – Count Descendants) 解説) を参考に実装したところ, AC版に到達出来た.
2. 個人的には, 深さ優先探索の訓練を積めたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// C++(GCC 9.2.1)
#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 a first
#define b second
#define pb push_back
#define all(x) x.begin(), x.end()
int a[101010], b[101010], c[101010], d[101010];

int main(){
    
    // 1. 入力情報.
    int H, W, N;
    scanf("%d %d %d", &H, &W, &N);
    map<int, int> mx, my;
    rep(i, N){
        scanf("%d %d", &a[i], &b[i]);
        mx[a[i]] = 0;
        my[b[i]] = 0;
    }
    
    // 2. 番号付け.
    int x = 0, y = 0;
    for(auto &p : mx) p.b = ++x;
    for(auto &q : my) q.b = ++y;
    
    // 3. 操作終了後の座標を保存.
    rep(i, N){
        c[i] = mx[a[i]];
        d[i] = my[b[i]];
    }
    
    // 4. 出力.
    rep(i, N) printf("%d %d\n", c[i], d[i]);
    return 0;
    
}

// C++(GCC 9.2.1)

#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 a first

#define b second

#define pb push_back

#define all(x) x.begin(), x.end()

int a[101010], b[101010], c[101010], d[101010];

int main(){

// 1. 入力情報.

int H, W, N;

scanf("%d %d %d", &H, &W, &N);

map<int, int> mx, my;

rep(i, N){

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

mx[a[i]] = 0;

my[b[i]] = 0;

}

// 2. 番号付け.

int x = 0, y = 0;

for(auto &p : mx) p.b = ++x;

for(auto &q : my) q.b = ++y;

// 3. 操作終了後の座標を保存.

rep(i, N){

c[i] = mx[a[i]];

d[i] = my[b[i]];

}

// 4. 出力.

rep(i, N) printf("%d %d\n", c[i], d[i]);

return 0;

}

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

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

[入力例]
1000000000 1000000000 10
1 1
10 10
100 100
1000 1000
10000 10000
100000 100000
1000000 1000000
10000000 10000000
100000000 100000000
1000000000 1000000000

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

[入力例]
2020 2021 5
703 1779
590 920
833 1016
1451 159
1164 624

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

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

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

[入力例]

4 5 2

3 2

2 5

[出力例]

2 1

1 2

※AtCoderテストケースより

[入力例]

1000000000 1000000000 10

1 1

10 10

100 100

1000 1000

10000 10000

100000 100000

1000000 1000000

10000000 10000000

100000000 100000000

1000000000 1000000000

[出力例]

1 1

2 2

3 3

4 4

5 5

6 6

7 7

8 8

9 9

10 10

※AtCoderテストケースより

[入力例]

2020 2021 5

703 1779

590 920

833 1016

1451 159

1164 624

[出力例]

2 5

1 3

3 4

5 1

4 2

[入力例]

10 10 10

2 7

1 10

4 10

10 1

2 4

2 9

3 6

1 5

8 9

7 10

[出力例]

2 5

1 7

4 7

7 1

2 2

2 6

3 4

1 3

6 6

5 7

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

// 以下の(過去問)解説を参照.
// https://atcoder.jp/contests/ABC202/editorial/1864
// 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
#define all(x) x.begin(), x.end()
int memo[202020];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vvi G(N);
    rep(i, N - 1){
        int a, b;
        scanf("%d %d", &a, &b);
        a--, b--;
        G[a].pb(b);
        G[b].pb(a);
    }
    
    // 2. 探索を行い, 頂点を訪れた順に保存.
    // https://ja.wikipedia.org/wiki/深さ優先探索
    vi ans;
    auto dfs = [&](auto&& self, int c, int b) -> void{
        // 2-1. 訪問済フラグ設定.
        memo[c] = 1;
        
        // 2-2. 頂点を保存(in).
        ans.pb(c + 1);
        
        // 2-3. 隣接頂点を保存.
        vi aVertices;
        for(auto &n : G[c]) if(!memo[n]) aVertices.pb(n);
        
        // 2-4. sort.
        sort(all(aVertices));
        
        // 2-5. 取り出した要素を処理.
        for(auto &n : aVertices) self(self, n, c);
        
        // 2-6. 頂点を保存(out).
        if(b != -1) ans.pb(b + 1);
    };
    dfs(dfs, 0, -1);
    
    // 3. 出力.
    int l = ans.size();
    rep(i, l){
        printf("%d", ans[i]);
        printf("%s", (i < l - 1) ? " " : "\n");
    }
    return 0;
    
}

// 以下の(過去問)解説を参照.

// https://atcoder.jp/contests/ABC202/editorial/1864

// 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

#define all(x) x.begin(), x.end()

int memo[202020];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vvi G(N);

rep(i, N - 1){

int a, b;

scanf("%d %d", &a, &b);

a--, b--;

G[a].pb(b);

G[b].pb(a);

}

// 2. 探索を行い, 頂点を訪れた順に保存.

// https://ja.wikipedia.org/wiki/深さ優先探索

vi ans;

auto dfs = [&](auto&& self, int c, int b) -> void{

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

memo[c] = 1;

// 2-2. 頂点を保存(in).

ans.pb(c + 1);

// 2-3. 隣接頂点を保存.

vi aVertices;

for(auto &n : G[c]) if(!memo[n]) aVertices.pb(n);

// 2-4. sort.

sort(all(aVertices));

// 2-5. 取り出した要素を処理.

for(auto &n : aVertices) self(self, n, c);

// 2-6. 頂点を保存(out).

if(b != -1) ans.pb(b + 1);

};

dfs(dfs, 0, -1);

// 3. 出力.

int l = ans.size();

rep(i, l){

printf("%d", ans[i]);

printf("%s", (i < l - 1) ? " " : "\n");

}

return 0;

}

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

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

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

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

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

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

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

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

[入力例]

1 2

4 2

3 1

[出力例]

1 2 4 2 1 3 1

※AtCoderテストケースより

[入力例]

1 2

1 3

1 4

1 5

[出力例]

1 2 1 3 1 4 1 5 1

※AtCoderテストケースより

[入力例]

1 3

1 4

6 1

5 4

7 3

2 3

[出力例]

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

[入力例]

5 1

6 1

9 1

10 1

5 4

5 2

4 11

4 13

12 2

7 2

7 3

7 8

6 14

6 16

14 17

14 18

9 15

[出力例]

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

■参照サイト
AtCoder Beginner Contest 213
エイシングプログラミングコンテスト2021（AtCoder Beginner Contest 202）(E – Count Descendants)

2021年8月8日

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

C++の練習を兼ねて, 競プロ典型 90 問の問題019 (Pick Two) を解いてみた.

■感想.
1. 問題019は, 解答の方針が見えなかったので, (問題019 (Pick Two) 解説) を参考に実装したところ, AC版に到達出来た.
2. 苦手な動的計画法(本問では, 区間DP)の訓練を積めたので, 非常に良かったと思う.
3. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.

詳細は, 本家のサイト(GitHub) 競プロ典型 90 問の問題019 をご覧下さい.

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

// 解き直し.
// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/019.jpg
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#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--)
LL a[404], dp[404][404];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    int n = 2 * N;
    rep(i, n) scanf("%lld", &a[i]);
    
    // 2. dp更新(解説通り).
    // [l, r]の人だけが抜けるために必要な最小コスト.
    // 区間の長さ d が, 小さい順に計算していく.
    rep(l, n) repx(r, l + 1, n) dp[l][r] = 2020202020;
    repex(d, 1, n, 2){
        rep(i, n){
            // 2-1. 区間[l, r] を 設定.
            int l = i;
            int r = l + d;
            
            // 2-2. 区間[l, r] が 妥当であるかチェック.
            // -> 02_random_0.txt などで, WA となった理由と理解.
            if(r >= n) continue;
            
            // 2-3. 最後に, l + 1, ... , r - 1 が 抜ける場合.
            dp[l][r] = dp[l + 1][r - 1] + abs(a[l] - a[r]);
            
            // 2-4. それ以外の場合.
            repx(k, l + 1, r - 1) dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r]);
        }
    }
    
    // 3. 出力.
    printf("%lld\n", dp[0][n - 1]);
    return 0;
    
}

// 解き直し.

// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/019.jpg

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

LL a[404], dp[404][404];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

int n = 2 * N;

rep(i, n) scanf("%lld", &a[i]);

// 2. dp更新(解説通り).

// [l, r]の人だけが抜けるために必要な最小コスト.

// 区間の長さ d が, 小さい順に計算していく.

rep(l, n) repx(r, l + 1, n) dp[l][r] = 2020202020;

repex(d, 1, n, 2){

rep(i, n){

// 2-1. 区間[l, r] を設定.

int l = i;

int r = l + d;

// 2-2. 区間[l, r] が妥当であるかチェック.

// -> 02_random_0.txt などで, WA となった理由と理解.

if(r >= n) continue;

// 2-3. 最後に, l + 1, ... , r - 1 が抜ける場合.

dp[l][r] = dp[l + 1][r - 1] + abs(a[l] - a[r]);

// 2-4. それ以外の場合.

repx(k, l + 1, r - 1) dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r]);

}

// 3. 出力.

printf("%lld\n", dp[0][n - 1]);

return 0;

}

[入力例]
3
6 2 3 9 8 6

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

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

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

[入力例]
4
1 2 4 8 16 32 64 128

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

[入力例]
15
73 8 55 26 97 48 37 47 35 55 5 17 62 2 60 23 99 73 34 75 7 46 82 84 29 41 32 31 52 32

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

[入力例]
1
1 2

[出力例]
1

[入力例]
5
31 41 59 26 53 58 97 93 23 84

[出力例]
47

[入力例]
10
264 575 131 106 45 90 590 501 615 753 639 260 425 710 259 18 308 24 501 803

[出力例]
1429

[入力例]
50
84 84 116 105 20 10 45 51 0 104 15 47 78 26 101 92 76 47 96 45 108 3 119 49 74 49 64 73 14 96 51 42 16 119 111 41 108 53 88 77 62 7 88 81 11 65 116 91 40 92 108 77 116 49 117 29 36 76 49 46 76 17 33 23 59 74 36 27 1 95 30 120 106 113 109 30 46 17 114 13 2 26 27 0 32 47 121 58 11 85 31 86 79 79 92 82 14 23 37 90

[出力例]
618

[入力例]
100
95718 84211 5580 110309 97223 51987 98302 61798 19405 28227 31598 119044 45574 97347 83910 25608 19029 50278 101326 111364 91569 15702 44444 41011 119737 77777 92529 94730 114785 11111 90312 74058 121212 18155 122094 43162 33467 58431 11847 15409 79108 121306 116104 82917 60366 105221 82862 50846 31856 59924 107852 20984 112990 45907 105354 121778 26241 88446 85280 51981 2059 105918 116779 109910 82479 94077 71585 498 16291 116900 59901 1285 44875 110405 191919 92487 27667 90886 40752 61757 104421 90048 36276 99588 98668 111228 10922 47195 171717 55555 44239 181818 49837 25246 111111 37203 119593 116633 118803 12117 99617 101010 98919 110269 121298 18222 28549 100352 7035 65622 92151 83692 62514 100064 108345 3437 7223 20471 79006 99999 102996 53159 2731 93050 88888 120509 24734 98317 113659 7307 53069 161616 44184 23999 62345 2751 22105 43533 41363 76363 6796 46149 59836 107606 113362 69022 66666 100458 151515 22332 40872 100065 77941 68058 67841 108211 119605 24657 35990 73405 33953 202020 76112 27677 99916 64955 33333 3697 116214 90340 0 28684 37209 59448 44936 60426 67151 13235 72217 24709 12312 111258 98241 141414 22222 41091 21776 131313 29043 14612 53652 90915 8309 54132 60738 56930 122374 81458 4729 73764

[出力例]
1278528

[入力例]

6 2 3 9 8 6

[出力例]

※AtCoderテストケースより

[入力例]

1 3 5 5 3 1

[出力例]

※AtCoderテストケースより

[入力例]

1 2 4 8 16 32 64 128

[出力例]

※AtCoderテストケースより

[入力例]

73 8 55 26 97 48 37 47 35 55 5 17 62 2 60 23 99 73 34 75 7 46 82 84 29 41 32 31 52 32

[出力例]

207

※AtCoderテストケースより

[入力例]

1 2

[出力例]

[入力例]

31 41 59 26 53 58 97 93 23 84

[出力例]

[入力例]

264 575 131 106 45 90 590 501 615 753 639 260 425 710 259 18 308 24 501 803

[出力例]

1429

[入力例]

84 84 116 105 20 10 45 51 0 104 15 47 78 26 101 92 76 47 96 45 108 3 119 49 74 49 64 73 14 96 51 42 16 119 111 41 108 53 88 77 62 7 88 81 11 65 116 91 40 92 108 77 116 49 117 29 36 76 49 46 76 17 33 23 59 74 36 27 1 95 30 120 106 113 109 30 46 17 114 13 2 26 27 0 32 47 121 58 11 85 31 86 79 79 92 82 14 23 37 90

[出力例]

618

[入力例]

100

95718 84211 5580 110309 97223 51987 98302 61798 19405 28227 31598 119044 45574 97347 83910 25608 19029 50278 101326 111364 91569 15702 44444 41011 119737 77777 92529 94730 114785 11111 90312 74058 121212 18155 122094 43162 33467 58431 11847 15409 79108 121306 116104 82917 60366 105221 82862 50846 31856 59924 107852 20984 112990 45907 105354 121778 26241 88446 85280 51981 2059 105918 116779 109910 82479 94077 71585 498 16291 116900 59901 1285 44875 110405 191919 92487 27667 90886 40752 61757 104421 90048 36276 99588 98668 111228 10922 47195 171717 55555 44239 181818 49837 25246 111111 37203 119593 116633 118803 12117 99617 101010 98919 110269 121298 18222 28549 100352 7035 65622 92151 83692 62514 100064 108345 3437 7223 20471 79006 99999 102996 53159 2731 93050 88888 120509 24734 98317 113659 7307 53069 161616 44184 23999 62345 2751 22105 43533 41363 76363 6796 46149 59836 107606 113362 69022 66666 100458 151515 22332 40872 100065 77941 68058 67841 108211 119605 24657 35990 73405 33953 202020 76112 27677 99916 64955 33333 3697 116214 90340 0 28684 37209 59448 44936 60426 67151 13235 72217 24709 12312 111258 98241 141414 22222 41091 21776 131313 29043 14612 53652 90915 8309 54132 60738 56930 122374 81458 4729 73764

[出力例]

1278528

■参照サイト
019 – Pick Two
問題019 (Pick Two) 解説

2021年8月7日

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

C++の練習を兼ねて, 競プロ典型 90 問の問題015 (Don’t be too close) を解いてみた.

■感想.
1. 問題015は, 解答の方針が見えなかったので, (問題015 (Don’t be too close) 解説) を参考に実装したところ, AC版に到達出来た.
2. 組み合わせ計算について, 新たな性質に触れることが出来たので, 非常に良かったと思う.
3. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.

詳細は, 本家のサイト(GitHub) 競プロ典型 90 問の問題015 をご覧下さい.

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

// 解き直し.
// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/015.jpg
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#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--)
const LL MOD = 1e9 + 7;
const int LIMIT = 101010;
LL FAC[LIMIT], INV[LIMIT];

// Fermat's little theorem から, 大きな冪乗の計算を行う.
// @param a: べき乗したい正整数.
// @param b: 指数.
// @return:  べき乗した計算結果(mod版).
LL mPow(LL a, LL b){
    LL t = 1;
    while(b){
        if(b & 1) t = (t * a) % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return t % MOD;
}

// 組み合わせ(nCk)計算用(mod版).
// ※配列FAC, INV は, 事前に計算済のものを使う.
// @param n: 対象となる要素の個数.
// @param k: 選択する要素の個数.
// @return: 組み合わせ(nCk)の計算結果(mod版).
LL combination(LL n, LL k){
    if(n < 0 || k < 0 || k > n) return 0LL;
    if(n == k || k == 0LL) return 1LL;
    LL ret = FAC[n] * INV[k] % MOD * INV[n - k] % MOD;
    return ret;
}

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    FAC[0] = 1;
    repx(i, 1, LIMIT) FAC[i] = (LL)i * FAC[i - 1] % MOD;
    rep(i, LIMIT) INV[i] = mPow(FAC[i], MOD - 2);
    
    // 2. クエリ回答(解説通り).
    // -> 差が, k以上となるように, a個のボールを選択.
    repx(k, 1, N + 1){
        // 2-1. 選び方の総数.
        LL ans = 0;
        int u = N / k;
        if(N % k != 0) u++;
        repx(a, 1, u + 1){
            LL n = (LL)(N - (k - 1) * (a - 1));
            LL r = (LL)a;
            ans += combination(n, r);
            ans %= MOD;
        }
        
        // 2-2. 出力.
        printf("%lld\n", ans);
    }
    return 0;
    
}

// 解き直し.

// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/015.jpg

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

const LL MOD = 1e9 + 7;

const int LIMIT = 101010;

LL FAC[LIMIT], INV[LIMIT];

// Fermat's little theorem から, 大きな冪乗の計算を行う.

// @param a: べき乗したい正整数.

// @param b: 指数.

// @return: べき乗した計算結果(mod版).

LL mPow(LL a, LL b){

LL t = 1;

while(b){

if(b & 1) t = (t * a) % MOD;

a = a * a % MOD;

b >>= 1;

}

return t % MOD;

}

// 組み合わせ(nCk)計算用(mod版).

// ※配列FAC, INV は, 事前に計算済のものを使う.

// @param n: 対象となる要素の個数.

// @param k: 選択する要素の個数.

// @return: 組み合わせ(nCk)の計算結果(mod版).

LL combination(LL n, LL k){

if(n < 0 || k < 0 || k > n) return 0LL;

if(n == k || k == 0LL) return 1LL;

LL ret = FAC[n] * INV[k] % MOD * INV[n - k] % MOD;

return ret;

}

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

FAC[0] = 1;

repx(i, 1, LIMIT) FAC[i] = (LL)i * FAC[i - 1] % MOD;

rep(i, LIMIT) INV[i] = mPow(FAC[i], MOD - 2);

// 2. クエリ回答(解説通り).

// -> 差が, k以上となるように, a個のボールを選択.

repx(k, 1, N + 1){

// 2-1. 選び方の総数.

LL ans = 0;

int u = N / k;

if(N % k != 0) u++;

repx(a, 1, u + 1){

LL n = (LL)(N - (k - 1) * (a - 1));

LL r = (LL)a;

ans += combination(n, r);

ans %= MOD;

}

// 2-2. 出力.

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

}

return 0;

}

[入力例]
1

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

[入力例]
2

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

[入力例]
3

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

[入力例]
4

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

[入力例]
7

[出力例]
127
33
18
13
10
8
7
※AtCoderテストケースより

[入力例]
20

[出力例]
1048575
17710
2744
906
430
250
167
118
90
75
65
56
48
41
35
30
26
23
21
20
※AtCoderテストケースより

[入力例]
50

[出力例]
898961330
951279874
262271567
14341526
1985602
466851
153365
63191
30623
16687
9987
6453
4354
3070
2290
1790
1427
1138
910
735
605
512
448
405
375
350
326
303
281
260
240
221
203
186
170
155
141
128
116
105
95
86
78
71
65
60
56
53
51
50
※AtCoderテストケースより

[入力例]
5

[出力例]
31
12
8
6
5

[入力例]
10

[出力例]
1023
143
59
35
25
20
16
13
11
10

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

144

145

146

147

148

149

150

151

152

153

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

127

※AtCoderテストケースより

[入力例]

[出力例]

1048575

17710

2744

906

430

250

167

118

※AtCoderテストケースより

[入力例]

[出力例]

898961330

951279874

262271567

14341526

1985602

466851

153365

63191

30623

16687

9987

6453

4354

3070

2290

1790

1427

1138

910

735

605

512

448

405

375

350

326

303

281

260

240

221

203

186

170

155

141

128

116

105

※AtCoderテストケースより

[入力例]

[出力例]

[入力例]

[出力例]

1023

143

■参照サイト
015 – Don’t be too close
問題015 (Don’t be too close) 解説

2021年8月6日

C++ の動作確認をしてみた（５０７）

C++の練習を兼ねて, AtCoder Regular Contest 124 の問題D (Yet Another Sorting Problem) を解いてみた.

■感想.
1. 問題D は, 方針が見えなかったので, 解説を参考にして, ようやく, AC版に到達出来た.
2. 個人的には, グラフに対する操作に置き換える解法が, 非常に面白い問題に感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc124/editorial/2337
// 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 N, M;
    scanf("%d %d", &N, &M);
    vvi G(N + M);
    rep(i, N + M){
        int p;
        scanf("%d", &p);
        p--;
        // 無向グラフと仮定.
        G[i].pb(p);
        G[p].pb(i);
    }
    
    // 2. グラフを連結成分に分解.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, int* c, int l){
        // 2-1. 空のキュー.
        queue<int> q;
        
        // 2-2. 連結成分番号を設定.
        c[s] = l;
        
        // 2-3. 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // 2-4. キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 2-5. 取り出した要素を処理.
            for(auto &e : G[u]) if(!c[e] && e != s) c[e] = l, q.push(e);
        }
        return;
    };
    int c[N + M], K = 0;
    rep(i, N + M) c[i] = 0;
    rep(i, N + M) if(!c[i]) bfs(G, i, c, ++K);
    
    // 3. 連結成分を調査.
    int r[K], b[K], g[K];
    rep(i, K) r[i] = b[i] = g[i] = 0;
    rep(i, N + M){
        g[c[i] - 1]++;
        if(i < N) r[c[i] - 1]++;
        else      b[c[i] - 1]++;
    }
    
    // 4. 赤色, 青色の頂点のみからなるサイズ 2以上 の 連結成分.
    int R = 0, B = 0;
    rep(i, K){
        if(g[i] >= 2){
            if(g[i] == r[i]) R++;
            if(g[i] == b[i]) B++;
        }
    }
    
    // 5. 出力.
    int ans = N + M - K + 2 * max(R, B);
    printf("%d\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc124/editorial/2337

// 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 N, M;

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

vvi G(N + M);

rep(i, N + M){

int p;

scanf("%d", &p);

p--;

// 無向グラフと仮定.

G[i].pb(p);

G[p].pb(i);

}

// 2. グラフを連結成分に分解.

// https://ja.wikipedia.org/wiki/幅優先探索

auto bfs = [&](vvi &G, int s, int* c, int l){

// 2-1. 空のキュー.

queue<int> q;

// 2-2. 連結成分番号を設定.

c[s] = l;

// 2-3. 探索地点 s をキュー q に追加.

q.push(s);

while(!q.empty()){

// 2-4. キューから取り出す.

int u = q.front();

q.pop();

// 2-5. 取り出した要素を処理.

for(auto &e : G[u]) if(!c[e] && e != s) c[e] = l, q.push(e);

}

return;

};

int c[N + M], K = 0;

rep(i, N + M) c[i] = 0;

rep(i, N + M) if(!c[i]) bfs(G, i, c, ++K);

// 3. 連結成分を調査.

int r[K], b[K], g[K];

rep(i, K) r[i] = b[i] = g[i] = 0;

rep(i, N + M){

g[c[i] - 1]++;

if(i < N) r[c[i] - 1]++;

else b[c[i] - 1]++;

}

// 4. 赤色, 青色の頂点のみからなるサイズ 2以上の連結成分.

int R = 0, B = 0;

rep(i, K){

if(g[i] >= 2){

if(g[i] == r[i]) R++;

if(g[i] == b[i]) B++;

}

// 5. 出力.

int ans = N + M - K + 2 * max(R, B);

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

return 0;

}

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

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

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

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

[入力例]
1 2
3 1 2

[出力例]
2

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

[出力例]
5

[入力例]
20 21
10 16 22 30 40 18 31 38 1 24 2 15 19 17 33 26 11 29 21 4 41 37 20 32 27 5 34 6 28 25 35 36 3 8 7 23 12 39 13 14 9

[出力例]
36

[入力例]
36 64
17 9 3 11 8 14 16 19 12 6 4 1 13 10 7 18 20 5 15 2 22 33 31 21 28 26 27 37 25 40 24 30 32 29 36 34 35 39 23 38 52 48 42 53 57 45 41 50 43 58 49 46 51 60 55 54 44 56 47 59 70 61 78 76 73 79 77 66 69 62 71 72 63 64 65 80 74 75 68 67 82 90 94 99 87 83 95 92 89 96 81 86 84 91 85 100 93 97 98 88

[出力例]
93

[入力例]

2 3

1 4 2 5 3

[出力例]

※AtCoderのテストケースより

[入力例]

5 7

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

[出力例]

※AtCoderのテストケースより

[入力例]

1 2

3 1 2

[出力例]

[入力例]

3 4

2 1 4 3 5 7 6

[出力例]

[入力例]

20 21

10 16 22 30 40 18 31 38 1 24 2 15 19 17 33 26 11 29 21 4 41 37 20 32 27 5 34 6 28 25 35 36 3 8 7 23 12 39 13 14 9

[出力例]

[入力例]

36 64

17 9 3 11 8 14 16 19 12 6 4 1 13 10 7 18 20 5 15 2 22 33 31 21 28 26 27 37 25 40 24 30 32 29 36 34 35 39 23 38 52 48 42 53 57 45 41 50 43 58 49 46 51 60 55 54 44 56 47 59 70 61 78 76 73 79 77 66 69 62 71 72 63 64 65 80 74 75 68 67 82 90 94 99 87 83 95 92 89 96 81 86 84 91 85 100 93 97 98 88

[出力例]

■参照サイト
AtCoder Regular Contest 124

カテゴリー: C++

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

C++の練習を兼ねて, 競プロ典型 90 問の問題074 (ABC String 2) を解いてみた.

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

C++の練習を兼ねて, 競プロ典型 90 問の問題062 (Paint All) を解いてみた.

C++ の動作確認をしてみた（５１４）

C++の練習を兼ねて, 競プロ典型 90 問の問題057 (Flip Flap) を解いてみた.

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

C++の練習を兼ねて, 競プロ典型 90 問の問題054 (Takahashi Number) を解いてみた.

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

C++の練習を兼ねて, 競プロ典型 90 問の問題045 (Simple Grouping) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 121 の問題D (1 or 2) を解いてみた.

C++ の動作確認をしてみた（５１０）

C++の練習を兼ねて, AtCoder Beginner Contest 213 の問題C (Reorder Cards) ～問題D (Takahashi Tour) を解いてみた.

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

C++の練習を兼ねて, 競プロ典型 90 問の問題019 (Pick Two) を解いてみた.

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

C++の練習を兼ねて, 競プロ典型 90 問の問題015 (Don’t be too close) を解いてみた.

C++ の動作確認をしてみた（５０７）

C++の練習を兼ねて, AtCoder Regular Contest 124 の問題D (Yet Another Sorting Problem) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問 の 問題074 (ABC String 2) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問 の 問題062 (Paint All) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問 の 問題057 (Flip Flap) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問 の 問題054 (Takahashi Number) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問 の 問題045 (Simple Grouping) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 121 の 問題D (1 or 2) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 213 の 問題C (Reorder Cards) ～ 問題D (Takahashi Tour) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問 の 問題019 (Pick Two) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問 の 問題015 (Don’t be too close) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 124 の 問題D (Yet Another Sorting Problem) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問の問題074 (ABC String 2) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問の問題062 (Paint All) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問の問題057 (Flip Flap) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問の問題054 (Takahashi Number) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問の問題045 (Simple Grouping) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 121 の問題D (1 or 2) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 213 の問題C (Reorder Cards) ～問題D (Takahashi Tour) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問の問題019 (Pick Two) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問の問題015 (Don’t be too close) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 124 の問題D (Yet Another Sorting Problem) を解いてみた.