個人用メモ帳

2021年9月11日

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

C++の練習を兼ねて, AtCoder Beginner Contest 216 の問題F (Max Sum Counting) を解いてみた.

■感想.
1. 問題F は, 方針が見えなかったので, 解説を参考に実装したところ, AC版に到達出来た.
2. 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc216/editorial/2560
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using P = pair<int, int>;
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 all(x) x.begin(), x.end()
#define a first
#define b second
const LL MOD = 998244353;
LL dp[5050][5050], a[5050], b[5050];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d", &a[i]);
    rep(i, N) scanf("%d", &b[i]);
    
    // 2. sort.
    vp v;
    rep(i, N) v.pb({a[i], b[i]});
    sort(all(v));
    
    // 3. dp更新.
    // Typical DP Contest (A - コンテスト) を ベース に 実装.
    // https://atcoder.jp/contests/tdpc/tasks/tdpc_contest
    dp[0][0] = 1;
    repx(i, 1, N + 1){
        // 前回分反映.
        rep(j, 5000) dp[i][j] += dp[i - 1][j];
        
        // 今回分反映.
        repr(j, 5000, 0){
            if(j + v[i - 1].b <= 5000){
                dp[i][j + v[i - 1].b] += dp[i][j];
                dp[i][j + v[i - 1].b] %= MOD;
            }
        }
    }
    
    // 4. 集計.
    LL ans = 0;
    // 並び替え前の情報を使っていたので, index も含めて, ロジック修正(000.txt などで, WA版となった).
    // repx(i, 1, N + 1){
    //     rep(j, a[i - 1] - b[i - 1] + 1){
    rep(i, N){
        rep(j, v[i].a - v[i].b + 1){
            ans += dp[i][j];
            ans %= MOD;
        }
    }
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc216/editorial/2560

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using P = pair<int, int>;

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

#define a first

#define b second

const LL MOD = 998244353;

LL dp[5050][5050], a[5050], b[5050];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

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

// 2. sort.

vp v;

rep(i, N) v.pb({a[i], b[i]});

sort(all(v));

// 3. dp更新.

// Typical DP Contest (A - コンテスト) をベースに実装.

// https://atcoder.jp/contests/tdpc/tasks/tdpc_contest

dp[0][0] = 1;

repx(i, 1, N + 1){

// 前回分反映.

rep(j, 5000) dp[i][j] += dp[i - 1][j];

// 今回分反映.

repr(j, 5000, 0){

if(j + v[i - 1].b <= 5000){

dp[i][j + v[i - 1].b] += dp[i][j];

dp[i][j + v[i - 1].b] %= MOD;

}

// 4. 集計.

LL ans = 0;

// 並び替え前の情報を使っていたので, index も含めて, ロジック修正(000.txt などで, WA版となった).

// repx(i, 1, N + 1){

// rep(j, a[i - 1] - b[i - 1] + 1){

rep(i, N){

rep(j, v[i].a - v[i].b + 1){

ans += dp[i][j];

ans %= MOD;

}

// 5. 出力.

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

return 0;

}

[入力例]
2
3 1
1 2

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

[入力例]
2
1 1
2 2

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

[入力例]
20
1937 3980 2689 1208 3640 1979 581 2271 4229 3948 3708 1522 4161 4661 3797 96 3388 3395 2920 2247
4485 2580 174 1156 3770 3396 3558 3500 3494 479 269 3383 1230 1711 3545 3919 134 475 3796 1017

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

[入力例]
5
11 7 8 10 1
8 8 5 4 1

[出力例]
9

[入力例]
31
41 59 26 53 58 97 93 23 84 62 64 33 83 27 9 50 28 84 19 71 69 39 93 75 10 58 20 97 49 44 59
2 30 78 16 40 62 86 20 89 98 62 80 34 82 53 42 11 70 67 98 21 4 80 86 51 32 82 30 66 4 70

[出力例]
858

[入力例]
50
24 65 106 21 21 8 21 93 35 83 20 21 18 104 82 13 74 53 26 84 94 97 120 44 117 115 109 26 123 11 18 54 106 53 53 79 57 111 29 92 26 25 65 28 55 86 11 76 19 74
14 8 115 35 57 118 76 48 7 41 63 49 41 29 10 51 95 47 95 4 36 106 108 115 70 116 48 62 58 39 81 66 101 53 17 68 73 35 90 9 111 91 20 64 4 96 39 101 30 123

[出力例]
11620

[入力例]
100
1540 1174 910 995 418 1478 131 730 2216 1677 1056 704 648 1114 794 276 1839 297 2082 83 566 913 458 1788 1528 287 281 1475 1998 570 1319 1719 1752 1008 88 953 599 235 1229 2067 1064 1590 306 1747 756 1277 146 1367 539 725 2139 1061 617 395 1947 194 703 100 441 1979 631 1717 1619 463 275 1283 1433 1788 1309 48 867 1758 997 37 1951 54 106 71 1621 1051 1502 1783 593 1097 900 249 511 934 944 1099 1826 1080 1430 1175 486 1056 2202 700 569 1914
1445 1448 56 875 681 807 1791 707 397 1056 1073 866 2079 598 722 1514 490 788 196 93 607 769 685 851 475 703 1924 1606 1414 1291 96 1641 1717 1500 852 1995 1198 469 122 619 2123 1417 277 1321 658 1783 855 1653 1938 752 1011 223 1134 1616 2032 2009 75 1369 114 1775 2126 549 1691 778 412 1636 1404 1822 822 1997 821 168 315 263 529 65 142 393 2090 1871 1385 1702 963 1838 1513 619 1996 1788 1750 180 35 1231 846 24 1355 1463 1354 885 582 674

[出力例]
10146452

[入力例]

3 1

1 2

[出力例]

※AtCoderテストケースより

[入力例]

1 1

2 2

[出力例]

※AtCoderテストケースより

[入力例]

1937 3980 2689 1208 3640 1979 581 2271 4229 3948 3708 1522 4161 4661 3797 96 3388 3395 2920 2247

4485 2580 174 1156 3770 3396 3558 3500 3494 479 269 3383 1230 1711 3545 3919 134 475 3796 1017

[出力例]

476

※AtCoderテストケースより

[入力例]

11 7 8 10 1

8 8 5 4 1

[出力例]

[入力例]

41 59 26 53 58 97 93 23 84 62 64 33 83 27 9 50 28 84 19 71 69 39 93 75 10 58 20 97 49 44 59

2 30 78 16 40 62 86 20 89 98 62 80 34 82 53 42 11 70 67 98 21 4 80 86 51 32 82 30 66 4 70

[出力例]

858

[入力例]

24 65 106 21 21 8 21 93 35 83 20 21 18 104 82 13 74 53 26 84 94 97 120 44 117 115 109 26 123 11 18 54 106 53 53 79 57 111 29 92 26 25 65 28 55 86 11 76 19 74

14 8 115 35 57 118 76 48 7 41 63 49 41 29 10 51 95 47 95 4 36 106 108 115 70 116 48 62 58 39 81 66 101 53 17 68 73 35 90 9 111 91 20 64 4 96 39 101 30 123

[出力例]

11620

[入力例]

100

1540 1174 910 995 418 1478 131 730 2216 1677 1056 704 648 1114 794 276 1839 297 2082 83 566 913 458 1788 1528 287 281 1475 1998 570 1319 1719 1752 1008 88 953 599 235 1229 2067 1064 1590 306 1747 756 1277 146 1367 539 725 2139 1061 617 395 1947 194 703 100 441 1979 631 1717 1619 463 275 1283 1433 1788 1309 48 867 1758 997 37 1951 54 106 71 1621 1051 1502 1783 593 1097 900 249 511 934 944 1099 1826 1080 1430 1175 486 1056 2202 700 569 1914

1445 1448 56 875 681 807 1791 707 397 1056 1073 866 2079 598 722 1514 490 788 196 93 607 769 685 851 475 703 1924 1606 1414 1291 96 1641 1717 1500 852 1995 1198 469 122 619 2123 1417 277 1321 658 1783 855 1653 1938 752 1011 223 1134 1616 2032 2009 75 1369 114 1775 2126 549 1691 778 412 1636 1404 1822 822 1997 821 168 315 263 529 65 142 393 2090 1871 1385 1702 963 1838 1513 619 1996 1788 1750 180 35 1231 846 24 1355 1463 1354 885 582 674

[出力例]

10146452

■参照サイト
AtCoder Beginner Contest 216

2021年9月10日

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

C++の練習を兼ねて, AtCoder Beginner Contest 216 の問題E (Amusement Park) を解いてみた.

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

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

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

// 解き直し.
// https://atcoder.jp/contests/abc216/editorial/2469
// 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[101010];

int main(){
    
    // 1. 入力情報.
    int N;
    LL K, b = 0, bSum = 0;
    scanf("%d %lld", &N, &K);
    rep(i, N){
        scanf("%lld", &a[i]);
        b += a[i];
        bSum += (a[i] + 1) * a[i] / 2;
    }
    
    // 2. 数列B の 項数が, K以下.
    if(b <= K){
        printf("%lld\n", bSum);
        return 0;
    }
    
    // 3. 評価関数.
    auto f = [&](LL m) -> bool {
        // 3-1. 数列B で, m以上となる個数.
        LL ret = 0;
        rep(i, N) ret += max(a[i] - m + 1, 0LL);
        
        // 3-2. 判定結果.
        return (ret <= K);
    };
    
    // 4. 二分探索で確認してみる.
    LL l = 1, h = 2e9 + 1, m;
    while(l + 1 < h){
        LL m = (h + l) >> 1;
        if(f(m)) h = m;
        else     l = m;
        // printf("h=%d l=%d m=%d\n", h, l, m);
    }
    
    // 5. 集計.
    LL t = 0, ans = 0;
    rep(i, N){
        if(a[i] >= h){
            ans += (h + a[i]) * (a[i] - h + 1) / 2; // 合計.
            t += (a[i] - h + 1);                    // 項数.
        }
    }
    
    // 6. 残り.
    if(t < K) ans += (h - 1) * (K - t);
    
    // 7. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc216/editorial/2469

// 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[101010];

int main(){

// 1. 入力情報.

int N;

LL K, b = 0, bSum = 0;

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

rep(i, N){

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

b += a[i];

bSum += (a[i] + 1) * a[i] / 2;

}

// 2. 数列B の項数が, K以下.

if(b <= K){

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

return 0;

}

// 3. 評価関数.

auto f = [&](LL m) -> bool {

// 3-1. 数列B で, m以上となる個数.

LL ret = 0;

rep(i, N) ret += max(a[i] - m + 1, 0LL);

// 3-2. 判定結果.

return (ret <= K);

};

// 4. 二分探索で確認してみる.

LL l = 1, h = 2e9 + 1, m;

while(l + 1 < h){

LL m = (h + l) >> 1;

if(f(m)) h = m;

else l = m;

// printf("h=%d l=%d m=%d\n", h, l, m);

}

// 5. 集計.

LL t = 0, ans = 0;

rep(i, N){

if(a[i] >= h){

ans += (h + a[i]) * (a[i] - h + 1) / 2; // 合計.

t += (a[i] - h + 1); // 項数.

}

// 6. 残り.

if(t < K) ans += (h - 1) * (K - t);

// 7. 出力.

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

return 0;

}

[入力例]
3 5
100 50 102

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

[入力例]
2 2021
2 3

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

[入力例]
1 5
7

[出力例]
25

[入力例]
3 5
7 5 3

[出力例]
27

[入力例]
10 314
5 75 74 87 48 102 35 18 41 21

[出力例]
15734

[入力例]
20 2021
113 23 11 120 50 116 38 168 140 169 205 190 144 81 154 169 149 210 142 180

[出力例]
192343

[入力例]
50 20210910
5511573 1823734 1537335 3718321 5263474 1794118 2046166 3165523 1869164 1553963 1194575 1642020 5484771 2214363 692014 1043993 909762 3261784 4060954 4078088 3464262 2525049 3121061 2078598 3962003 332254 1136135 4933593 4628158 4264588 3350207 4356224 3950236 2563276 4359650 4760678 2248995 1177972 2608249 389230 3856211 1569739 1668055 1712937 2083808 4737499 5340644 4022180 466263 3292659

[出力例]
82888537486520

[入力例]

3 5

100 50 102

[出力例]

502

※AtCoderテストケースより

[入力例]

2 2021

2 3

[出力例]

※AtCoderテストケースより

[入力例]

1 5

[出力例]

[入力例]

3 5

7 5 3

[出力例]

[入力例]

10 314

5 75 74 87 48 102 35 18 41 21

[出力例]

15734

[入力例]

20 2021

113 23 11 120 50 116 38 168 140 169 205 190 144 81 154 169 149 210 142 180

[出力例]

192343

[入力例]

50 20210910

5511573 1823734 1537335 3718321 5263474 1794118 2046166 3165523 1869164 1553963 1194575 1642020 5484771 2214363 692014 1043993 909762 3261784 4060954 4078088 3464262 2525049 3121061 2078598 3962003 332254 1136135 4933593 4628158 4264588 3350207 4356224 3950236 2563276 4359650 4760678 2248995 1177972 2608249 389230 3856211 1569739 1668055 1712937 2083808 4737499 5340644 4022180 466263 3292659

[出力例]

82888537486520

■参照サイト
AtCoder Beginner Contest 216

2021年9月9日

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

C++の練習を兼ねて, AtCoder Beginner Contest 216 の問題C (Many Balls) ～問題D (Pair of Balls) を解いてみた.

■感想.
1. 問題D は, 方針が見えなかったので, 解説を参考に実装したところ, AC版に到達出来た.
2. 問題D で, 計算量を減らすための, キューの利用方法が, 大変勉強になったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 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. 入力情報.
    LL N;
    scanf("%lld", &N);
    
    // 2. 魔法を使ってみる.
    string ans = "";
    while(N){
        ans = ((N % 2 > 0) ? "A" : "B") + ans;
        if(N % 2 > 0) N--;
        else          N >>= 1;
    }
    
    // 3. 出力.
    printf("%s\n", ans.c_str());
    return 0;
    
}

// 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. 入力情報.

LL N;

scanf("%lld", &N);

// 2. 魔法を使ってみる.

string ans = "";

while(N){

ans = ((N % 2 > 0) ? "A" : "B") + ans;

if(N % 2 > 0) N--;

else N >>= 1;

}

// 3. 出力.

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

return 0;

}

[入力例]
5

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

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

[入力例]
14

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

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

[入力例]
2021

[出力例]
ABABABABABABBBABBA

[入力例]
20210909

[出力例]
ABBBABABBABBBBABABBBABBBABABBABABABBA

[入力例]
999999999999999999

[出力例]
ABABBABABABABBBBBBABBABABBABABBABBABABBBABABABBABBBABABABBABABBBBABABABABABABABABABABABABABABABABABA

[入力例]
1000000000000000000

[出力例]
ABABBABABABABBBBBBABBABABBABABBABBABABBBABABABBABBBABABABBABABBBABBBBBBBBBBBBBBBBBB

[入力例]

[出力例]

AABA

※AtCoderテストケースより

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

ABBA

[入力例]

[出力例]

BBABBAAAB

※AtCoderテストケースより

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

ABABAB

[入力例]

2021

[出力例]

ABABABABABABBBABBA

[入力例]

20210909

[出力例]

ABBBABABBABBBBABABBBABBBABABBABABABBA

[入力例]

999999999999999999

[出力例]

ABABBABABABABBBBBBABBABABBABABBABBABABBBABABABBABBBABABABBABABBBBABABABABABABABABABABABABABABABABABA

[入力例]

1000000000000000000

[出力例]

ABABBABABABABBBBBBABBABABBABABBABBABABBBABABABBABBBABABABBABABBBABBBBBBBBBBBBBBBBBB

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

// 解き直し.
// https://atcoder.jp/contests/abc216/editorial/2559
// 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 pof pop_front
#define pub push_back
int c[202020];

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    vector<deque<int>> v(M), b(N);
    rep(i, M){
        int k;
        scanf("%d", &k);
        rep(j, k){
            int a;
            scanf("%d", &a);
            a--;
            v[i].pub(a); // i番目の筒に保存.
            b[a].pub(i); // 色 a のボールに, 筒の番号 i を保存.
        }
    }
    
    // 2. 筒を順番に見ていく.
    deque<int> dq;
    rep(i, M){
        // 2-1. ボールを取得.
        int t = v[i].front();
        c[t]++;
        
        // 2-2. キューに追加.
        if(c[t] == 2) dq.pub(t);
        
        // 2-3. キューが空になるまで, 筒からボールを取り除く.
        while(!dq.empty()){
            // ボールを取得.
            int u = dq.front();
            dq.pof();
            
            // 筒番号を取得.
            int p1 = b[u].front();
            b[u].pof();
            int p2 = b[u].front();
            b[u].pof();
            
            // 筒から除去.
            v[p1].pof();
            v[p2].pof();
            
            // 筒から, 一番上のボールを取得.
            int b1 = -1;
            int b2 = -1;
            if(!v[p1].empty()) b1 = v[p1].front();
            if(!v[p2].empty()) b2 = v[p2].front();
            
            // 取得したボールの出現回数を確認し, 二回であれば, キューに追加.
            if(b1 != -1){
                c[b1]++;
                if(c[b1] == 2) dq.pub(b1);
            }
            if(b2 != -1){
                c[b2]++;
                if(c[b2] == 2) dq.pub(b2);
            }
        }
    }
    
    // 3. 判定.
    bool ok = true;
    rep(i, N) if(c[i] != 2) ok = false;
    
    // 4. 出力.
    printf("%s\n", ok ? "Yes" : "No");
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc216/editorial/2559

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

#define pub push_back

int c[202020];

int main(){

// 1. 入力情報.

int N, M;

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

vector<deque<int>> v(M), b(N);

rep(i, M){

int k;

scanf("%d", &k);

rep(j, k){

int a;

scanf("%d", &a);

a--;

v[i].pub(a); // i番目の筒に保存.

b[a].pub(i); // 色 a のボールに, 筒の番号 i を保存.

}

// 2. 筒を順番に見ていく.

deque<int> dq;

rep(i, M){

// 2-1. ボールを取得.

int t = v[i].front();

c[t]++;

// 2-2. キューに追加.

if(c[t] == 2) dq.pub(t);

// 2-3. キューが空になるまで, 筒からボールを取り除く.

while(!dq.empty()){

// ボールを取得.

int u = dq.front();

dq.pof();

// 筒番号を取得.

int p1 = b[u].front();

b[u].pof();

int p2 = b[u].front();

b[u].pof();

// 筒から除去.

v[p1].pof();

v[p2].pof();

// 筒から, 一番上のボールを取得.

int b1 = -1;

int b2 = -1;

if(!v[p1].empty()) b1 = v[p1].front();

if(!v[p2].empty()) b2 = v[p2].front();

// 取得したボールの出現回数を確認し, 二回であれば, キューに追加.

if(b1 != -1){

c[b1]++;

if(c[b1] == 2) dq.pub(b1);

}

if(b2 != -1){

c[b2]++;

if(c[b2] == 2) dq.pub(b2);

}

// 3. 判定.

bool ok = true;

rep(i, N) if(c[i] != 2) ok = false;

// 4. 出力.

printf("%s\n", ok ? "Yes" : "No");

return 0;

}

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

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

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

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

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

[出力例]
Yes

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

[出力例]
No

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

[出力例]
Yes

[入力例]

2 2

1 2

[出力例]

Yes

※AtCoderテストケースより

[入力例]

2 2

1 2

2 1

[出力例]

※AtCoderテストケースより

[入力例]

10 6

9 4 2 1

10 9 8 4 2

5 3 1

8 6 5 3

7 6

10 7

[出力例]

Yes

[入力例]

3 3

2 1

3 2

1 3

[出力例]

[入力例]

25 10

17 9 1

22 9 6 2

25 23 17 16 14 10 5 1

24 20 16 8 2

18 14 11 6 3

19 18 15 10 8 3 4

24 22 19 15 13 12 11 7 4

23 20 12 5

21 13 7

25 21

[出力例]

Yes

■参照サイト
AtCoder Beginner Contest 216

2021年9月7日

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

C++の練習を兼ねて, AtCoder Beginner Contest 217 の問題F (Make Pair) を解いてみた.

■感想.
1. 問題F は, 方針が見えなかったので, 解説を参考に実装したところ, AC版に到達出来た.
2. 苦手な動的計画法(本問では, 区間DP)の訓練を積めたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc217/editorial/2584
// 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 = 998244353;
const int LIMIT = 1010;
LL FAC[LIMIT], INV[LIMIT];
int f[808][808];
LL dp[808][808];

// 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;
    // k = 0 で, 256423756 (※挙動がおかしい) が 出力されたため, ロジック修正.
    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, M;
    scanf("%d %d", &N, &M);
    rep(i, M){
        int a, b;
        scanf("%d %d", &a, &b);
        f[a][b] = 1;
        f[b][a] = 1;
    }
    
    // 2. 事前計算.
    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);
    
    // 3. dp更新.
    rep(i, N * 2 + 1) dp[i][0] = 1;
    repx(j, 1, N * 2 + 1){
        rep(i, N * 2 + 1){
            repx(k, 1, j + 1){
                LL a1 = dp[i + 1][k - 1];
                LL a2 = dp[i + k * 2][j - k];
                LL a3 = combination((LL)j, (LL)k);
                LL a4 = f[i + 1][i + k * 2];
                dp[i][j] += a1 * a2 % MOD * a3 % MOD * a4;
                dp[i][j] %= MOD;
            }
        }
    }
    
    // 4. 出力.
    printf("%lld\n", dp[0][N]);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc217/editorial/2584

// 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 = 998244353;

const int LIMIT = 1010;

LL FAC[LIMIT], INV[LIMIT];

int f[808][808];

LL dp[808][808];

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

// k = 0 で, 256423756 (※挙動がおかしい) が出力されたため, ロジック修正.

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

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

rep(i, M){

int a, b;

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

f[a][b] = 1;

f[b][a] = 1;

}

// 2. 事前計算.

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

// 3. dp更新.

rep(i, N * 2 + 1) dp[i][0] = 1;

repx(j, 1, N * 2 + 1){

rep(i, N * 2 + 1){

repx(k, 1, j + 1){

LL a1 = dp[i + 1][k - 1];

LL a2 = dp[i + k * 2][j - k];

LL a3 = combination((LL)j, (LL)k);

LL a4 = f[i + 1][i + k * 2];

dp[i][j] += a1 * a2 % MOD * a3 % MOD * a4;

dp[i][j] %= MOD;

}

// 4. 出力.

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

return 0;

}

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

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

[入力例]
2 2
1 2
3 4

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

[入力例]
2 2
1 3
2 4

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

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

[出力例]
30

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

[出力例]
604800

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

[出力例]
883463798

100

[入力例]

2 3

1 2

1 4

2 3

[出力例]

※AtCoderテストケースより

[入力例]

2 2

1 2

3 4

[出力例]

※AtCoderテストケースより

[入力例]

2 2

1 3

2 4

[出力例]

※AtCoderテストケースより

[入力例]

5 5

1 2

3 6

4 5

7 10

8 9

[出力例]

[入力例]

10 15

1 6

2 3

4 5

7 10

8 9

11 12

13 14

15 16

17 20

18 19

11 14

12 13

15 20

16 19

17 18

[出力例]

604800

[入力例]

20 35

1 2

3 4

5 6

7 8

9 10

11 12

13 14

15 16

17 18

19 20

21 22

23 24

25 26

27 28

29 30

31 32

33 34

35 36

37 38

39 40

1 10

8 9

2 7

3 6

4 5

11 30

12 29

13 28

14 27

15 26

16 25

17 24

18 23

19 22

20 21

[出力例]

883463798

■参照サイト
AtCoder Beginner Contest 217

2021年9月6日

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

C++の練習を兼ねて, AtCoder Beginner Contest 217 の問題E (Sorting Queries) を解いてみた.

■感想.
1. 問題E は, 方針を絞り込めたので, AC版に到達出来たと思う.
2. 優先順位付きキューの復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

■C++版プログラム(問題E／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 pof pop_front
#define pub push_back

int main(){
    
    // 1. 入力情報.
    int Q;
    scanf("%d", &Q);
    
    // 2. クエリ回答.
    priority_queue<int, vector<int>, greater<int>> pq;
    deque<int> dq;
    rep(i, Q){
        // 2-1. クエリ入力情報.
        int c;
        scanf("%d", &c);
        
        // 2-2. c = 1 の 場合(末尾に追加).
        if(c == 1){
            int x;
            scanf("%d", &x);
            dq.pub(x);
        }
        
        // 2-3. c = 2 の 場合(先頭要素を出力).
        if(c == 2){
            int ans = 0;
            if(!pq.empty()){
                ans = pq.top();
                pq.pop();
            }else{
                ans = dq.front();
                dq.pof();
            }
            printf("%d\n", ans);
        }
        
        // 2-4. c = 3 の 場合(昇順sort).
        if(c == 3){
            while(!dq.empty()){
                pq.push(dq.front());
                dq.pop_front();
            }
        }
    }
    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 pof pop_front

#define pub push_back

int main(){

// 1. 入力情報.

int Q;

scanf("%d", &Q);

// 2. クエリ回答.

priority_queue<int, vector<int>, greater<int>> pq;

deque<int> dq;

rep(i, Q){

// 2-1. クエリ入力情報.

int c;

scanf("%d", &c);

// 2-2. c = 1 の場合(末尾に追加).

if(c == 1){

int x;

scanf("%d", &x);

dq.pub(x);

}

// 2-3. c = 2 の場合(先頭要素を出力).

if(c == 2){

int ans = 0;

if(!pq.empty()){

ans = pq.top();

pq.pop();

}else{

ans = dq.front();

dq.pof();

}

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

}

// 2-4. c = 3 の場合(昇順sort).

if(c == 3){

while(!dq.empty()){

pq.push(dq.front());

dq.pop_front();

}

return 0;

}

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

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

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

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

[入力例]
30
1 11
2
1 9
3
1 5
1 2
1 1
3
2
1 3
3
1 0
3
1 7
2
3
1 11
1 5
2
3
2
1 6
1 3
1 10
1 0
2
3
1 5
3
2

[出力例]
11
1
0
2
3
5
0

[入力例]

1 4

1 3

1 2

1 1

1 0

[出力例]

※AtCoderテストケースより

[入力例]

1 5

1 3

1 6

[出力例]

※AtCoderテストケースより

[入力例]

1 11

1 9

1 5

1 2

1 1

1 3

1 0

1 7

1 11

1 5

1 6

1 3

1 10

1 0

1 5

[出力例]

■参照サイト
AtCoder Beginner Contest 217

2021年9月6日2021年9月6日

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

C++の練習を兼ねて, AtCoder Beginner Contest 217 の問題C (Inverse of Permutation) ～問題D (Cutting Woods) を解いてみた.

■感想.
1. 問題C, D は, 方針を絞り込めたので, AC版に到達出来たと思う.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

■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--)
int q[202020];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N){
        int p;
        scanf("%d", &p);
        q[p - 1] = i + 1;
    }
    
    // 2. 出力.
    rep(i, N){
        printf("%d", q[i]);
        printf("%s", (i < N - 1) ? " " : "\n");
    }
    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--)

int q[202020];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N){

int p;

scanf("%d", &p);

q[p - 1] = i + 1;

}

// 2. 出力.

rep(i, N){

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

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

}

return 0;

}

[入力例]
3
2 3 1

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

[入力例]
3
1 2 3

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

[入力例]
5
5 3 2 4 1

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

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

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

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

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

[入力例]

2 3 1

[出力例]

3 1 2

※AtCoderテストケースより

[入力例]

1 2 3

[出力例]

1 2 3

※AtCoderテストケースより

[入力例]

5 3 2 4 1

[出力例]

5 3 2 4 1

※AtCoderテストケースより

[入力例]

2 1 4 3 6 5 7

[出力例]

2 1 4 3 6 5 7

[入力例]

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

[出力例]

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

■C++版プログラム(問題D／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--)

int main(){
    
    // 1. 入力情報.
    int L, Q;
    scanf("%d %d", &L, &Q);
    set<int> st;
    st.insert(0);
    st.insert(L);
    
    // 2. クエリ回答.
    rep(i, Q){
        // 2-1. クエリ入力情報.
        int c, x;
        scanf("%d %d", &c, &x);
        
        // 2-2. c = 1 の 場合.
        if(c == 1) st.insert(x);
        
        // 2-3. c = 2 の 場合.
        if(c == 2){
            decltype(st)::iterator itr = st.lower_bound(x);
            int r = *itr;
            int l = *(--itr);
            printf("%d\n", r - l);
        }
    }
    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--)

int main(){

// 1. 入力情報.

int L, Q;

scanf("%d %d", &L, &Q);

set<int> st;

st.insert(0);

st.insert(L);

// 2. クエリ回答.

rep(i, Q){

// 2-1. クエリ入力情報.

int c, x;

scanf("%d %d", &c, &x);

// 2-2. c = 1 の場合.

if(c == 1) st.insert(x);

// 2-3. c = 2 の場合.

if(c == 2){

decltype(st)::iterator itr = st.lower_bound(x);

int r = *itr;

int l = *(--itr);

printf("%d\n", r - l);

}

return 0;

}

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

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

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

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

[入力例]
100 10
1 31
2 41
1 59
2 26
1 53
2 58
1 97
2 93
1 23
2 84

[出力例]
69
31
6
38
38
※AtCoderテストケースより

[入力例]
200 20
1 172
2 99
1 54
2 121
2 169
1 3
2 178
1 65
2 128
1 165
2 187
1 44
2 199
1 117
1 88
1 196
1 77
2 1
2 123
2 85

[出力例]
172
118
118
28
107
28
28
3
48
11

[入力例]

5 3

2 2

1 3

2 2

[出力例]

※AtCoderテストケースより

[入力例]

5 3

1 2

1 4

2 3

[出力例]

※AtCoderテストケースより

[入力例]

100 10

1 31

2 41

1 59

2 26

1 53

2 58

1 97

2 93

1 23

2 84

[出力例]

※AtCoderテストケースより

[入力例]

200 20

1 172

2 99

1 54

2 121

2 169

1 3

2 178

1 65

2 128

1 165

2 187

1 44

2 199

1 117

1 88

1 196

1 77

2 1

2 123

2 85

[出力例]

172

118

107

■参照サイト
AtCoder Beginner Contest 217

2021年9月5日

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

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

■感想.
1. 問題081は, 方針が見えなかったので, (問題081 (Friendly Group) 解説) を参考に実装したところ, AC版に到達出来た.
2. 二次元累積和の復習が出来たので良かったと思う.
3. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.

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

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

// 解き直し.
// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/081.jpg
// 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--)
int a[202020], b[202020], c[5050][5050];

int main(){
    
    // 1. 入力情報.
    int N, K;
    scanf("%d %d", &N, &K);
    rep(i, N) scanf("%d %d", &a[i], &b[i]);
    rep(i, N) c[a[i]][b[i]]++;
    
    // 2. 二次元累積和(解説通り).
    int ans = 0;
    repx(i, 1, 5001) repx(j, 1, 5001) c[i][j] += c[i][j - 1]; // 横方向.
    repx(j, 1, 5001) repx(i, 1, 5001) c[i][j] += c[i - 1][j]; // 縦方向.
    repx(lx, 1, 5001 - K){
        repx(ly, 1, 5001 - K){
            int rx = lx + K;
            int ry = ly + K;
            ans = max(ans, c[rx][ry] - c[lx - 1][ry] - c[rx][ly - 1] + c[lx - 1][ly - 1]);
        }
    }
    
    // 3. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// 解き直し.

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

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

int a[202020], b[202020], c[5050][5050];

int main(){

// 1. 入力情報.

int N, K;

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

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

rep(i, N) c[a[i]][b[i]]++;

// 2. 二次元累積和(解説通り).

int ans = 0;

repx(i, 1, 5001) repx(j, 1, 5001) c[i][j] += c[i][j - 1]; // 横方向.

repx(j, 1, 5001) repx(i, 1, 5001) c[i][j] += c[i - 1][j]; // 縦方向.

repx(lx, 1, 5001 - K){

repx(ly, 1, 5001 - K){

int rx = lx + K;

int ry = ly + K;

ans = max(ans, c[rx][ry] - c[lx - 1][ry] - c[rx][ly - 1] + c[lx - 1][ly - 1]);

}

// 3. 出力.

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

return 0;

}

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

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

[入力例]
2 123
4 5
678 901

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

[入力例]
7 10
20 20
20 20
20 30
20 40
30 20
30 30
40 20

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

[入力例]
20 48
168 72
182 79
193 59
176 53
145 55
158 72
129 56
148 66
206 79
150 59
172 72
200 76
197 57
136 41
157 67
127 59
199 70
157 50
157 67
141 42

[出力例]
13

[入力例]

3 4

1 1

2 5

7 4

[出力例]

※AtCoderテストケースより

[入力例]

2 123

4 5

678 901

[出力例]

※AtCoderテストケースより

[入力例]

7 10

20 20

20 30

20 40

30 20

30 30

40 20

[出力例]

※AtCoderテストケースより

[入力例]

20 48

168 72

182 79

193 59

176 53

145 55

158 72

129 56

148 66

206 79

150 59

172 72

200 76

197 57

136 41

157 67

127 59

199 70

157 50

157 67

141 42

[出力例]

■参照サイト
081 – Friendly Group
問題081 (Friendly Group) 解説

2021年9月4日

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

C++の練習を兼ねて, 競プロ典型 90 問の問題073 (We Need Both a and b) を解いてみた.

■感想.
1. 問題073は, 方針が見えなかったので, (問題073 (We Need Both a and b) 解説) を参考に実装したところ, AC版に到達出来た.
2. 苦手な動的計画法(木dp)の訓練を積めたこと, 幅優先探索の復習が出来たので, 非常に良かったと思う.
3. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.

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

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

// 解き直し.
// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/073.jpg
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vvi = vector<vector<int>>;
using P = pair<int, 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
#define a first
#define b second
const LL MOD = 1e9 + 7;
int c[101010];    // 文字 'a', 'b'.
LL dp[101010][3]; // 木dp.

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N){
        char x[11];
        scanf("%s", x);
        c[i] = (x[0] == 'b') ? 1 : 0;
    }
    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. 根(頂点 1) から 各頂点までの距離を計算.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, int* d){
        // 3-1. 空のキュー.
        queue<int> q;
        
        // 3-2. 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // 3-3. キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 3-4. 取り出した要素を処理.
            for(auto &e : G[u]) if(!d[e] && e != s) d[e] = d[u] + 1, q.push(e);
        }
        return;
    };
    int d[N];
    rep(i, N) d[i] = 0;
    bfs(G, 0, d);
    // rep(i, N) printf("%d ", d[i]);
    // puts("");
    
    // 3. 事前計算.
    // 3-1. 頂点 1 から 遠い順 に並び替え.
    priority_queue<P> pq;
    rep(i, N) pq.push({d[i], i}); // {距離, 頂点番号}
    
    // 4. 木dp.
    while(!pq.empty()){
        // 4-1. 頂点 v を一つ取り出す.
        P p = pq.top();
        pq.pop();
        
        // 4-2. 頂点 v の 頂点番号は？
        int v = p.b;
        
        // 4-3. 頂点 v が, 'a' の 場合.
        if(!c[v]){
            // 頂点 v 自身について, 更新.
            dp[v][0]++;
            dp[v][2]++;
            LL dpSum1 = 1, dpSum2 = 1;
            
            // 頂点 v の 子供 に相当する 頂点について, 更新.
            for(auto &u : G[v]){
                // 頂点 v の 子供 に 相当する頂点 u を 選択.
                if(d[u] > d[v]){
                    // 頂点 v の 周囲 の 頂点 u の 情報 を 反映.
                    // dp[v][0] への 反映用.
                    dpSum1 *= (dp[u][0] + dp[u][2]);
                    dpSum1 %= MOD;
                    
                    // dp[v][2] への 反映用.
                    dpSum2 *= (dp[u][0] + dp[u][1] + 2 * dp[u][2]);
                    dpSum2 %= MOD;
                }
            }
            
            // dp[v][0] へ 反映.
            dp[v][0] *= dpSum1;
            dp[v][0] %= MOD;
            
            // dp[v][2] へ 反映.
            dp[v][2] *= (dpSum2 + MOD - dpSum1);
            dp[v][2] %= MOD;
        }
        
        // 4-4. 頂点 v が, 'b' の 場合.
        if(c[v]){
            // 頂点 v 自身について, 更新.
            dp[v][1]++;
            dp[v][2]++;
            LL dpSum1 = 1, dpSum2 = 1;
            
            // 頂点 v の 子供 に相当する 頂点について, 更新.
            for(auto &u : G[v]){
                // 頂点 v の 子供 に 相当する頂点 u を 選択.
                if(d[u] > d[v]){
                    // 頂点 v の 周囲 の 頂点 u の 情報 を 反映.
                    // dp[v][1] への 反映用.
                    dpSum1 *= (dp[u][1] + dp[u][2]);
                    dpSum1 %= MOD;
                    
                    // dp[v][2] への 反映用.
                    dpSum2 *= (dp[u][0] + dp[u][1] + 2 * dp[u][2]);
                    dpSum2 %= MOD;
                }
            }
            
            // dp[v][1] へ 反映.
            dp[v][1] *= dpSum1;
            dp[v][1] %= MOD;
            
            // dp[v][2] へ 反映.
            dp[v][2] *= (dpSum2 + MOD - dpSum1);
            dp[v][2] %= MOD;
        }
    }
    
    // 5. 出力.
    printf("%lld\n", dp[0][2]);
    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

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vvi = vector<vector<int>>;

using P = pair<int, 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

#define a first

#define b second

const LL MOD = 1e9 + 7;

int c[101010]; // 文字 'a', 'b'.

LL dp[101010][3]; // 木dp.

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N){

char x[11];

scanf("%s", x);

c[i] = (x[0] == 'b') ? 1 : 0;

}

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. 根(頂点 1) から各頂点までの距離を計算.

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

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

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

queue<int> q;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

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

}

return;

};

int d[N];

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

bfs(G, 0, d);

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

// puts("");

// 3. 事前計算.

// 3-1. 頂点 1 から遠い順に並び替え.

priority_queue<P> pq;

rep(i, N) pq.push({d[i], i}); // {距離, 頂点番号}

// 4. 木dp.

while(!pq.empty()){

// 4-1. 頂点 v を一つ取り出す.

P p = pq.top();

pq.pop();

// 4-2. 頂点 v の頂点番号は？

int v = p.b;

// 4-3. 頂点 v が, 'a' の場合.

if(!c[v]){

// 頂点 v 自身について, 更新.

dp[v][0]++;

dp[v][2]++;

LL dpSum1 = 1, dpSum2 = 1;

// 頂点 v の子供に相当する頂点について, 更新.

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

// 頂点 v の子供に相当する頂点 u を選択.

if(d[u] > d[v]){

// 頂点 v の周囲の頂点 u の情報を反映.

// dp[v][0] への反映用.

dpSum1 *= (dp[u][0] + dp[u][2]);

dpSum1 %= MOD;

// dp[v][2] への反映用.

dpSum2 *= (dp[u][0] + dp[u][1] + 2 * dp[u][2]);

dpSum2 %= MOD;

}

// dp[v][0] へ反映.

dp[v][0] *= dpSum1;

dp[v][0] %= MOD;

// dp[v][2] へ反映.

dp[v][2] *= (dpSum2 + MOD - dpSum1);

dp[v][2] %= MOD;

}

// 4-4. 頂点 v が, 'b' の場合.

if(c[v]){

// 頂点 v 自身について, 更新.

dp[v][1]++;

dp[v][2]++;

LL dpSum1 = 1, dpSum2 = 1;

// 頂点 v の子供に相当する頂点について, 更新.

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

// 頂点 v の子供に相当する頂点 u を選択.

if(d[u] > d[v]){

// 頂点 v の周囲の頂点 u の情報を反映.

// dp[v][1] への反映用.

dpSum1 *= (dp[u][1] + dp[u][2]);

dpSum1 %= MOD;

// dp[v][2] への反映用.

dpSum2 *= (dp[u][0] + dp[u][1] + 2 * dp[u][2]);

dpSum2 %= MOD;

}

// dp[v][1] へ反映.

dp[v][1] *= dpSum1;

dp[v][1] %= MOD;

// dp[v][2] へ反映.

dp[v][2] *= (dpSum2 + MOD - dpSum1);

dp[v][2] %= MOD;

}

// 5. 出力.

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

return 0;

}

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

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

[入力例]
2
a b
1 2

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

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

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

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

[出力例]
0

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

[出力例]
6

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

[出力例]
6

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

[出力例]
5

[入力例]
31
a a b a b a a a a b a b a b b b a b b a b a b b b b b a a b a
1 3
1 5
1 7
7 23
7 6
5 2
2 15
2 16
3 4
3 8
4 24
4 25
8 9
9 10
9 11
9 12
9 13
9 14
14 20
14 21
14 22
10 17
10 18
11 19
13 26
26 27
26 28
26 29
26 30
26 31

[出力例]
1464

[入力例]
55
b b a b b b a b b a b a b b a b a b a b a b a a b b a a a b b a b a a a a b b b a a b b b b b a a b a a b a a
1 3
1 8
1 17
1 13
1 16
16 43
16 41
16 42
13 14
13 15
14 31
14 30
30 32
30 33
32 34
32 35
3 12
3 4
4 5
4 7
7 6
7 9
7 22
12 28
12 29
9 2
2 23
2 10
2 11
11 27
11 26
26 39
26 40
6 24
6 25
24 36
36 37
36 38
17 18
17 19
19 20
19 21
8 44
44 45
44 46
44 47
45 49
47 48
48 50
48 51
48 52
46 55
46 54
46 53

[出力例]
222480

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

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

[入力例]

b a b a b b a

2 1

3 7

3 2

3 4

5 4

4 6

[出力例]

※AtCoderテストケースより

[入力例]

a b

1 2

[出力例]

※AtCoderテストケースより

[入力例]

b a b b a b b b a b a a a a b b a b b a a a

1 7

4 14

12 22

2 4

21 17

3 20

7 8

20 14

15 11

8 14

9 12

17 8

6 20

11 20

18 19

10 8

22 20

13 21

5 14

19 20

16 14

[出力例]

※AtCoderテストケースより

[入力例]

a a a

1 2

1 3

[出力例]

[入力例]

a a b a b b a

1 3

1 4

3 2

4 5

4 6

6 7

[出力例]

[入力例]

a a a a b b b b b a

1 3

1 4

7 3

3 2

2 8

2 9

2 10

6 4

5 4

[出力例]

[入力例]

b b a a a a b a a a a b

1 12

4 1

1 5

5 2

5 3

8 2

9 2

4 7

6 4

6 10

6 11

[出力例]

[入力例]

a a b a b a a a a b a b a b b b a b b a b a b b b b b a a b a

1 3

1 5

1 7

7 23

7 6

5 2

2 15

2 16

3 4

3 8

4 24

4 25

8 9

9 10

9 11

9 12

9 13

9 14

14 20

14 21

14 22

10 17

10 18

11 19

13 26

26 27

26 28

26 29

26 30

26 31

[出力例]

1464

[入力例]

b b a b b b a b b a b a b b a b a b a b a b a a b b a a a b b a b a a a a b b b a a b b b b b a a b a a b a a

1 3

1 8

1 17

1 13

1 16

16 43

16 41

16 42

13 14

13 15

14 31

14 30

30 32

30 33

32 34

32 35

3 12

3 4

4 5

4 7

7 6

7 9

7 22

12 28

12 29

9 2

2 23

2 10

2 11

11 27

11 26

26 39

26 40

6 24

6 25

24 36

36 37

36 38

17 18

17 19

19 20

19 21

8 44

44 45

44 46

44 47

45 49

47 48

48 50

48 51

48 52

46 55

46 54

46 53

[出力例]

222480

■参照サイト
073 – We Need Both a and b
問題073 (We Need Both a and b) 解説

2021年9月4日2021年9月4日

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

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

■感想.
1. 問題068は, 方針が見えなかったので, (問題068 (Paired Information) 解説) を参考に実装したところ, AC版に到達出来た.
2. 実装に非常に苦労したものの, 個人的には, Ambiguous であるか否かの判定に, グラフの連結状況(Union-Find木)を考える部分が, 非常に面白いと感じた.
3. Union-Find木, 幅優先探索の復習が出来たので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
4. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.

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

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

// 解き直し.
// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/068.jpg
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
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
const int MAX = 101010;
int t[MAX], x[MAX], y[MAX];
LL v0[MAX], v1[MAX];

// https://github.com/atcoder/live_library/blob/master/uf.cpp
// UnionFind
// coding: https://youtu.be/TdR816rqc3s?t=726
// comment: https://youtu.be/TdR816rqc3s?t=6822
// -> 一部改変.
struct UnionFind{
    vi d;
    UnionFind(int n = 0): d(n, -1) {}
    int find(int x){
        return (d[x] < 0) ? x : (d[x] = find(d[x]));
    }
    bool unite(int x, int y){
        x = find(x);
        y = find(y);
        if(x == y) return false;
        if(d[x] > d[y]) swap(x, y);
        d[x] += d[y];
        d[y] = x;
        return true;
    }
    bool same(int x, int y){
        return find(x) == find(y);
    }
    int size(int x){
        return -d[find(x)];
    }
};

int main(){
    
    // 1. 入力情報.
    int N, Q;
    scanf("%d %d", &N, &Q);
    vvi G(N);
    rep(i, Q){
        LL u;
        scanf("%d %d %d %lld", &t[i], &x[i], &y[i], &u);
        x[i]--;
        y[i]--;
        if(t[i]) v1[i] = u;
        else     v0[x[i]] = u;
        
        // グラフ作成.
        if(!t[i]){
            G[x[i]].pb(y[i]);
            G[y[i]].pb(x[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(e != s && !c[e]) c[e] = l, q.push(e);
        }
        return;
    };
    int b[N], c[N], idx = 0;
    rep(i, N) b[i] = c[i] = 0;
    rep(i, N) if(!c[i]) bfs(G, i, c, ++idx);
    
    // 3. 二つのパターン作成.
    // 3-1. 0 を ベース に考える場合.
    LL a0[N];
    a0[0] = 0;
    rep(i, N - 1){
        if(c[i] == c[i + 1]) a0[i + 1] = v0[i] - a0[i];
        else                 a0[i + 1] = 0;
    }
    
    // 3-2. 1 を ベース に考える場合.
    LL a1[N];
    a1[0] = 1;
    rep(i, N - 1){
        if(c[i] == c[i + 1]) a1[i + 1] = v0[i] - a1[i];
        else                 a1[i + 1] = 1;
    }
    
    // 4. クエリ回答.
    UnionFind uf(N + 1);
    rep(i, Q){
        // 4-1. T が 0 の 場合.
        if(!t[i]) uf.unite(x[i], y[i]);
        
        // 4-2. T が 1 の 場合.
        if(t[i]){
            // 確定しない場合.
            if(!uf.same(x[i], y[i])) puts("Ambiguous");
            
            // 確定する場合.
            if(uf.same(x[i], y[i])){
                // 基準値 + 符号(対象) × 符号(基準) × 差分
                LL ans = a0[y[i]] + (a1[y[i]] - a0[y[i]]) * (a1[x[i]] - a0[x[i]]) * (v1[i] - a0[x[i]]);
                
                // 出力.
                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

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

const int MAX = 101010;

int t[MAX], x[MAX], y[MAX];

LL v0[MAX], v1[MAX];

// https://github.com/atcoder/live_library/blob/master/uf.cpp

// UnionFind

// coding: https://youtu.be/TdR816rqc3s?t=726

// comment: https://youtu.be/TdR816rqc3s?t=6822

// -> 一部改変.

struct UnionFind{

vi d;

UnionFind(int n = 0): d(n, -1) {}

int find(int x){

return (d[x] < 0) ? x : (d[x] = find(d[x]));

}

bool unite(int x, int y){

x = find(x);

y = find(y);

if(x == y) return false;

if(d[x] > d[y]) swap(x, y);

d[x] += d[y];

d[y] = x;

return true;

}

bool same(int x, int y){

return find(x) == find(y);

}

int size(int x){

return -d[find(x)];

}

};

int main(){

// 1. 入力情報.

int N, Q;

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

vvi G(N);

rep(i, Q){

LL u;

scanf("%d %d %d %lld", &t[i], &x[i], &y[i], &u);

x[i]--;

y[i]--;

if(t[i]) v1[i] = u;

else v0[x[i]] = u;

// グラフ作成.

if(!t[i]){

G[x[i]].pb(y[i]);

G[y[i]].pb(x[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(e != s && !c[e]) c[e] = l, q.push(e);

}

return;

};

int b[N], c[N], idx = 0;

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

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

// 3. 二つのパターン作成.

// 3-1. 0 をベースに考える場合.

LL a0[N];

a0[0] = 0;

rep(i, N - 1){

if(c[i] == c[i + 1]) a0[i + 1] = v0[i] - a0[i];

else a0[i + 1] = 0;

}

// 3-2. 1 をベースに考える場合.

LL a1[N];

a1[0] = 1;

rep(i, N - 1){

if(c[i] == c[i + 1]) a1[i + 1] = v0[i] - a1[i];

else a1[i + 1] = 1;

}

// 4. クエリ回答.

UnionFind uf(N + 1);

rep(i, Q){

// 4-1. T が 0 の場合.

if(!t[i]) uf.unite(x[i], y[i]);

// 4-2. T が 1 の場合.

if(t[i]){

// 確定しない場合.

if(!uf.same(x[i], y[i])) puts("Ambiguous");

// 確定する場合.

if(uf.same(x[i], y[i])){

// 基準値 + 符号(対象) × 符号(基準) × 差分

LL ans = a0[y[i]] + (a1[y[i]] - a0[y[i]]) * (a1[x[i]] - a0[x[i]]) * (v1[i] - a0[x[i]]);

// 出力.

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

}

return 0;

}

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

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

[入力例]
15
25
0 11 12 41
0 1 2 159
0 14 15 121
0 4 5 245
0 12 13 157
0 9 10 176
0 6 7 170
0 2 3 123
0 7 8 167
0 3 4 159
1 12 11 33
0 10 11 116
0 8 9 161
1 9 12 68
1 12 12 33
1 7 12 74
0 5 6 290
1 8 9 93
0 13 14 127
1 10 12 108
1 14 1 3
1 13 8 124
1 12 11 33
1 12 10 33
1 5 15 194

[出力例]
8
33
33
33
68
33
144
93
8
108
118
※AtCoderテストケースより

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

[出力例]
5
Ambiguous
Ambiguous
-2
11
-1
1
Ambiguous

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

[出力例]
-3
Ambiguous
0
Ambiguous
3
11
3
2
Ambiguous
7
-2
7
7
Ambiguous
Ambiguous
15

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

[入力例]

0 1 2 3

1 1 2 1

1 3 4 5

0 3 4 6

1 3 4 5

0 2 3 6

1 3 1 5

[出力例]

Ambiguous

※AtCoderテストケースより

[入力例]

0 11 12 41

0 1 2 159

0 14 15 121

0 4 5 245

0 12 13 157

0 9 10 176

0 6 7 170

0 2 3 123

0 7 8 167

0 3 4 159

1 12 11 33

0 10 11 116

0 8 9 161

1 9 12 68

1 12 12 33

1 7 12 74

0 5 6 290

1 8 9 93

0 13 14 127

1 10 12 108

1 14 1 3

1 13 8 124

1 12 11 33

1 12 10 33

1 5 15 194

[出力例]

144

108

118

※AtCoderテストケースより

[入力例]

0 1 2 5

1 1 2 0

1 3 2 7

0 3 4 5

1 3 5 8

1 4 3 7

0 4 5 6

1 5 3 12

1 4 3 6

0 6 7 9

1 6 7 8

1 7 5 3

[出力例]

Ambiguous

-2

-1

Ambiguous

[入力例]

0 1 2 2

1 1 2 5

1 1 3 7

0 2 3 7

1 3 1 5

1 5 3 2

0 4 5 6

1 4 5 3

0 6 7 4

0 7 8 8

1 6 8 7

1 7 8 5

1 7 6 2

0 9 10 10

1 9 6 5

1 10 9 3

0 11 12 3

0 12 13 12

1 12 11 5

1 12 13 5

1 13 11 16

0 14 15 11

1 15 10 8

1 14 4 15

1 1 3 10

[出力例]

-3

Ambiguous

-2

Ambiguous

■参照サイト
068 – Paired Information
問題068 (Paired Information) 解説
 Union-Find木

2021年9月2日2021年9月2日

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

C++の練習を兼ねて, 競プロ典型 90 問の問題072 (Loop Railway Plan) を解いてみた.

■感想.
1. 問題072は, 実装方針が見えなかったので, (問題072 (Loop Railway Plan) 解説プログラム) を参考に実装したところ, AC版に到達出来た.
2. 深さ優先探索(応用版, Backtracking) の復習が出来たので, 非常に, 良かったと思う.
但し, Backtracking について, 本質的な部分が, 理解できてないため, 引き続き, 今後の課題になると思う.
3. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.

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

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

// 解答不能.
// https://github.com/E869120/kyopro_educational_90/blob/main/sol/072.cpp
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vs = vector<string>;
#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
constexpr int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int main(){
    
    // 1. 入力情報.
    int H, W;
    scanf("%d %d", &H, &W);
    vs board;
    rep(i, H){
        char c[22];
        scanf("%s", c);
        string s(c);
        board.pb(s);
    }
    
    // 2. dfs(Backtracking).
    // https://ja.wikipedia.org/wiki/深さ優先探索
    int ans = -1;
    bool memo[20][20];
    rep(i, 20) rep(j, 20) memo[i][j] = false;
    auto dfs = [&](auto&& self, int sx, int sy, int px, int py) -> int{
        // 2-1. 終了条件.
        if(sx == px && sy == py && memo[px][py]) return 0;
        
        // 2-2. 訪問したことを記録.
        memo[px][py] = true;
        
        // 2-3. dfs.
        // -> ret の 初期値は, どのくらい小さくするかは, よく理解出来てない.
        int ret = -111;
        rep(i, 4){
            // 隣接マスを用意.
            int nx = px + dx[i];
            int ny = py + dy[i];
            
            // 隣接マスが, 到達不可能な場合(山とか).
            if(nx < 0 || ny < 0 || nx >= H || ny >= W || board[nx][ny] == '#') continue;
            
            // 隣接マスが, 開始頂点でないが, 訪問済みの場合.
            if((sx != nx || sy != ny) && memo[nx][ny]) continue;
            
            // 移動したマス数を取得.
            int v = self(self, sx, sy, nx, ny);
            
            // 最大値更新.
            ret = max(ret, v + 1);
        }
        
        // 2-4. 訪問してない状態に戻す.
        memo[px][py] = false;
        
        // 2-5. 処理終了.
        return ret;
    };
    
    // 3. 全探索.
    rep(x, H) rep(y, W) ans = max(ans, dfs(dfs, x, y, x, y));
    
    // 4. 鉄道路線が通るマスの数が, 3マス以下の場合(鉄道路線が無い場合).
    if(ans <= 3) ans = -1;
    
    // 5. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// 解答不能.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vs = vector<string>;

#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

constexpr int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int main(){

// 1. 入力情報.

int H, W;

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

vs board;

rep(i, H){

char c[22];

scanf("%s", c);

string s(c);

board.pb(s);

}

// 2. dfs(Backtracking).

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

int ans = -1;

bool memo[20][20];

rep(i, 20) rep(j, 20) memo[i][j] = false;

auto dfs = [&](auto&& self, int sx, int sy, int px, int py) -> int{

// 2-1. 終了条件.

if(sx == px && sy == py && memo[px][py]) return 0;

// 2-2. 訪問したことを記録.

memo[px][py] = true;

// 2-3. dfs.

// -> ret の初期値は, どのくらい小さくするかは, よく理解出来てない.

int ret = -111;

rep(i, 4){

// 隣接マスを用意.

int nx = px + dx[i];

int ny = py + dy[i];

// 隣接マスが, 到達不可能な場合(山とか).

if(nx < 0 || ny < 0 || nx >= H || ny >= W || board[nx][ny] == '#') continue;

// 隣接マスが, 開始頂点でないが, 訪問済みの場合.

if((sx != nx || sy != ny) && memo[nx][ny]) continue;

// 移動したマス数を取得.

int v = self(self, sx, sy, nx, ny);

// 最大値更新.

ret = max(ret, v + 1);

}

// 2-4. 訪問してない状態に戻す.

memo[px][py] = false;

// 2-5. 処理終了.

return ret;

};

// 3. 全探索.

rep(x, H) rep(y, W) ans = max(ans, dfs(dfs, x, y, x, y));

// 4. 鉄道路線が通るマスの数が, 3マス以下の場合(鉄道路線が無い場合).

if(ans <= 3) ans = -1;

// 5. 出力.

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

return 0;

}

[入力例]
3 3
...
.#.
...

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

[入力例]
1 6
......

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

[入力例]
4 4
....
#...
....
...#

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

[入力例]
5 5
.....
.#...
.....
...#.
.#...

[出力例]
20
※整数 H, W が, 問題文の制約条件から範囲外であるケース.

-> 以下のような経路で, 20 と 分かる.
@@@@@
@#@@@
@.@@@
@@@#@
.#@@@

[入力例]
6 6
.....#
.#....
......
...#.#
.#....
......

[出力例]
30
※整数 H, W が, 問題文の制約条件から範囲外であるケース.

-> 以下のような経路で, 30 と 分かる.
@@@@@#
@#@@@@
@@@.@@
@@@#@#
@#@@@@
@@@@@@

[入力例]

3 3

...

.#.

...

[出力例]

※AtCoderテストケースより

[入力例]

1 6

......

[出力例]

-1

※AtCoderテストケースより

[入力例]

4 4

....

#...

....

...#

[出力例]

※AtCoderテストケースより

[入力例]

5 5

.....

.#...

.....

...#.

.#...

[出力例]

※整数 H, W が, 問題文の制約条件から範囲外であるケース.

-> 以下のような経路で, 20 と分かる.

@@@@@

@#@@@

@.@@@

@@@#@

.#@@@

[入力例]

6 6

.....#

.#....

......

...#.#

.#....

......

[出力例]

※整数 H, W が, 問題文の制約条件から範囲外であるケース.

-> 以下のような経路で, 30 と分かる.

@@@@@#

@#@@@@

@@@.@@

@@@#@#

@#@@@@

@@@@@@

■参照サイト
072 – Loop Railway Plan
問題072 (Loop Railway Plan) 解説
 問題072 (Loop Railway Plan) 解説プログラム

C++の練習を兼ねて, AtCoder Beginner Contest 216 の 問題F (Max Sum Counting) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 216 の 問題E (Amusement Park) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 216 の 問題C (Many Balls) ～ 問題D (Pair of Balls) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 217 の 問題F (Make Pair) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 217 の 問題E (Sorting Queries) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 217 の 問題C (Inverse of Permutation) ～ 問題D (Cutting Woods) を解いてみた.

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

C++の練習を兼ねて, 競プロ典型 90 問 の 問題073 (We Need Both a and b) を解いてみた.

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

C++の練習を兼ねて, 競プロ典型 90 問 の 問題072 (Loop Railway Plan) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 216 の問題F (Max Sum Counting) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 216 の問題E (Amusement Park) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 216 の問題C (Many Balls) ～問題D (Pair of Balls) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 217 の問題F (Make Pair) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 217 の問題E (Sorting Queries) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 217 の問題C (Inverse of Permutation) ～問題D (Cutting Woods) を解いてみた.

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

C++の練習を兼ねて, 競プロ典型 90 問の問題073 (We Need Both a and b) を解いてみた.

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

C++の練習を兼ねて, 競プロ典型 90 問の問題072 (Loop Railway Plan) を解いてみた.