C++ | 個人用メモ帳

2022年6月7日2022年6月7日

C++ の動作確認をしてみた（７３６）

C++の練習を兼ねて, AtCoder Regular Contest 126 の問題C (Maximize GCD) を解いてみた.

■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 解説のロジックで, 操作後の最大値を計算できることに, 非常に興味深い印象を受けた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc126/editorial/2635
// 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 a[303030];
LL c[606060], s[606060];

int main(){
    
    // 1. 入力情報.
    int N, aMax = 0;
    LL K;
    scanf("%d %lld", &N, &K);
    rep(i, N){
        scanf("%d", &a[i]);
        aMax = max(aMax, a[i]);
        ++c[a[i]];
        s[a[i]] += (LL)a[i];
    }
    
    // 2. 累積和.
    rep(i, aMax * 2){
        s[i + 1] += s[i];
        c[i + 1] += c[i];
    }
    
    // 3. cost(x).
    LL ans = 0;
    repx(x, 1, aMax + 1){
        // 3-1. x の 倍数にするために必要な操作回数.
        LL op = 0;
        
        // 3-2. k の 上限.
        int kMax = aMax / x + ((aMax % x) > 0);
        repx(k, 1, kMax + 1){
            // 解説上に記載されている k * x * c - s の 計算.
            int r = k * x;
            int l = (k - 1) * x;
            op += k * x * (c[r] - c[l]) - (s[r] - s[l]);
        }
        
        // 3-3. 最大値更新.
        if(op <= K) ans = max(ans, (LL)x);
    }
    
    // 4. x > aMax.
    LL y = (K + s[aMax]) / (LL)N;
    if(y > (LL)aMax) ans = max(ans, y);
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc126/editorial/2635

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

LL c[606060], s[606060];

int main(){

// 1. 入力情報.

int N, aMax = 0;

LL K;

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

rep(i, N){

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

aMax = max(aMax, a[i]);

++c[a[i]];

s[a[i]] += (LL)a[i];

}

// 2. 累積和.

rep(i, aMax * 2){

s[i + 1] += s[i];

c[i + 1] += c[i];

}

// 3. cost(x).

LL ans = 0;

repx(x, 1, aMax + 1){

// 3-1. x の倍数にするために必要な操作回数.

LL op = 0;

// 3-2. k の上限.

int kMax = aMax / x + ((aMax % x) > 0);

repx(k, 1, kMax + 1){

// 解説上に記載されている k * x * c - s の計算.

int r = k * x;

int l = (k - 1) * x;

op += k * x * (c[r] - c[l]) - (s[r] - s[l]);

}

// 3-3. 最大値更新.

if(op <= K) ans = max(ans, (LL)x);

}

// 4. x > aMax.

LL y = (K + s[aMax]) / (LL)N;

if(y > (LL)aMax) ans = max(ans, y);

// 5. 出力.

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

return 0;

}

[入力例]
3 6
3 4 9

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

[入力例]
3 4
30 10 20

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

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

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

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

[出力例]
3

[入力例]
20 100
76 37 41 50 123 24 9 20 61 8 111 121 72 112 86 36 117 70 51 55

[出力例]
13

[入力例]
50 2022
99 64 74 87 90 81 57 14 59 10 71 74 81 10 26 57 99 30 7 101 102 58 121 118 102 5 78 74 55 18 112 85 74 37 109 112 49 3 18 100 67 55 28 50 93 85 81 116 122 73

[出力例]
75

[入力例]
100 20220607
3884 4387 31206 34567 30467 7730 12541 20631 5592 17213 15420 111 11550 17721 4442 16553 27015 16988 18479 15529 18142 16303 8626 30524 16723 2598 26485 28292 9613 16874 25869 30508 9667 17443 1214 4692 28455 18285 16191 18791 4031 16178 12238 22222 20362 21558 27707 3961 7103 8346 26037 1205 30867 19156 806 27366 13291 16768 9366 3908 21931 5649 980 7743 10574 23456 12345 32145 5075 931 10312 13317 11260 21399 14398 10319 11983 8833 4212 30249 8072 5908 1583 7312 12140 25860 4076 1239 24414 3716 33300 23456 13347 25872 7858 954 2292 782 17718 12628

[出力例]
216600

[入力例]

3 6

3 4 9

[出力例]

※AtCoderのテストケースより

[入力例]

3 4

30 10 20

[出力例]

※AtCoderのテストケースより

[入力例]

5 12345

1 2 3 4 5

[出力例]

2472

※AtCoderのテストケースより

[入力例]

7 12

3 1 4 1 5 9 2

[出力例]

[入力例]

20 100

76 37 41 50 123 24 9 20 61 8 111 121 72 112 86 36 117 70 51 55

[出力例]

[入力例]

50 2022

99 64 74 87 90 81 57 14 59 10 71 74 81 10 26 57 99 30 7 101 102 58 121 118 102 5 78 74 55 18 112 85 74 37 109 112 49 3 18 100 67 55 28 50 93 85 81 116 122 73

[出力例]

[入力例]

100 20220607

3884 4387 31206 34567 30467 7730 12541 20631 5592 17213 15420 111 11550 17721 4442 16553 27015 16988 18479 15529 18142 16303 8626 30524 16723 2598 26485 28292 9613 16874 25869 30508 9667 17443 1214 4692 28455 18285 16191 18791 4031 16178 12238 22222 20362 21558 27707 3961 7103 8346 26037 1205 30867 19156 806 27366 13291 16768 9366 3908 21931 5649 980 7743 10574 23456 12345 32145 5075 931 10312 13317 11260 21399 14398 10319 11983 8833 4212 30249 8072 5908 1583 7312 12140 25860 4076 1239 24414 3716 33300 23456 13347 25872 7858 954 2292 782 17718 12628

[出力例]

216600

■参照サイト
AtCoder Regular Contest 126

2022年6月6日2022年6月6日

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

C++の練習を兼ねて, AtCoder Regular Contest 128 の問題C (Max Dot) を解いてみた.

■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 解説のロジックで, スコアを計算できることに, 非常に興味深い印象を受けた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc128/editorial/2785
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using P = pair<LL, 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 a first
#define b second
LL a[5050], aCum[5050];

int main(){
    
    // 1. 入力情報.
    int N;
    LL M, S;
    scanf("%d %lld %lld", &N, &M, &S);
    rep(i, N) scanf("%lld", &a[i]);
    
    // 2. 累積和.
    rep(i, N) aCum[i + 1] = aCum[i] + a[i];
    
    // 3. 集計.
    LL a1 = 0;
    double a2 = 0.0;
    int r = N;
    while(r > 0){
        // 3-1. sum[i] / i を 最大化する i は？
        P f = {-1, 1};
        int c = 0, m = 0;
        repr(j, r - 1, 0){
            LL d = aCum[r] - aCum[j];
            ++c;
            
            // 最大値更新.
            if(c * f.a < d * f.b){
                f = {(LL)d, (LL)c};
                m = c;
            }
        }
        
        // 3-2. 集計.
        // 後ろ m 項 が S / m.
        if(S <= (LL)m * M){
            a2 += (double)((aCum[r] - aCum[r - m]) * S) / (double)m;
            break;
        }
        
        // 後ろ m 項 が M.
        if(S > (LL)m * M){
            a1 += (aCum[r] - aCum[r - m]) * M;
            S -= (LL)m * M;
        }
        
        // 3-3. 次へ.
        r -= m;
    }
    
    // 4. 合算.
    double ans = (double)a1 + a2;
    
    // 5. 出力.
    printf("%.12lf\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc128/editorial/2785

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using P = pair<LL, 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 a first

#define b second

LL a[5050], aCum[5050];

int main(){

// 1. 入力情報.

int N;

LL M, S;

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

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

// 2. 累積和.

rep(i, N) aCum[i + 1] = aCum[i] + a[i];

// 3. 集計.

LL a1 = 0;

double a2 = 0.0;

int r = N;

while(r > 0){

// 3-1. sum[i] / i を最大化する i は？

P f = {-1, 1};

int c = 0, m = 0;

repr(j, r - 1, 0){

LL d = aCum[r] - aCum[j];

++c;

// 最大値更新.

if(c * f.a < d * f.b){

f = {(LL)d, (LL)c};

m = c;

}

// 3-2. 集計.

// 後ろ m 項が S / m.

if(S <= (LL)m * M){

a2 += (double)((aCum[r] - aCum[r - m]) * S) / (double)m;

break;

}

// 後ろ m 項が M.

if(S > (LL)m * M){

a1 += (aCum[r] - aCum[r - m]) * M;

S -= (LL)m * M;

}

// 3-3. 次へ.

r -= m;

}

// 4. 合算.

double ans = (double)a1 + a2;

// 5. 出力.

printf("%.12lf\n", ans);

return 0;

}

[入力例]
3 2 3
1 2 3

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

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

[入力例]
3 3 2
5 1 1

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

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

[入力例]
10 234567 1000000
353239 53676 45485 617014 886590 423581 172670 928532 312338 981241

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

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

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

[出力例]
40.000000000000

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

[出力例]
31.900000000000

[入力例]
30 7 32
12 10 47 31 61 78 56 110 93 35 49 20 105 81 118 70 38 100 53 96 111 39 125 75 14 82 102 11 121 112

[出力例]
3003.500000000000

[入力例]
77 11 23
500 491 151 557 745 448 1107 591 870 1196 204 206 559 1014 349 588 95 181 627 1228 559 618 659 870 476 126 737 706 578 910 1105 1108 563 926 388 947 479 920 7 996 985 339 113 429 782 322 782 646 996 73 705 1208 840 369 449 709 732 401 784 1053 546 1023 697 497 1008 166 1026 500 1010 99 10 11 222 111 333 777 666

[出力例]
16495.964912280702

[入力例]

3 2 3

1 2 3

[出力例]

8.00000000000000000000

※AtCoderのテストケースより

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

8.000000000000

[入力例]

3 3 2

5 1 1

[出力例]

4.66666666666666666667

※AtCoderのテストケースより

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

4.666666666667

[入力例]

10 234567 1000000

353239 53676 45485 617014 886590 423581 172670 928532 312338 981241

[出力例]

676780145098.25000000000000000000

※AtCoderのテストケースより

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

676780145098.250000000000

[入力例]

5 7 9

3 1 4 1 5

[出力例]

40.000000000000

[入力例]

10 7 11

5 1 8 2 5 1 1 2 3 1

[出力例]

31.900000000000

[入力例]

30 7 32

12 10 47 31 61 78 56 110 93 35 49 20 105 81 118 70 38 100 53 96 111 39 125 75 14 82 102 11 121 112

[出力例]

3003.500000000000

[入力例]

77 11 23

500 491 151 557 745 448 1107 591 870 1196 204 206 559 1014 349 588 95 181 627 1228 559 618 659 870 476 126 737 706 578 910 1105 1108 563 926 388 947 479 920 7 996 985 339 113 429 782 322 782 646 996 73 705 1208 840 369 449 709 732 401 784 1053 546 1023 697 497 1008 166 1026 500 1010 99 10 11 222 111 333 777 666

[出力例]

16495.964912280702

■参照サイト
大和証券プログラミングコンテスト2021（AtCoder Regular Contest 128）

2022年6月5日

C++ の動作確認をしてみた（７３４）

C++の練習を兼ねて, AtCoder Regular Contest 125 の問題C (LIS to Original Sequence) を解いてみた.

■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 解説のロジックで, 辞書順最小の順列を計算できることが, 非常に興味深く思った.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc125/editorial/2499
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = 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 a[202020];

int main(){
    
    // 1. 入力情報.
    int N, K;
    scanf("%d %d", &N, &K);
    rep(i, N) scanf("%d", &a[i]);
    
    // 2. 未使用リスト.
    set<int> st;
    rep(i, N) st.insert(i + 1);
    
    // 3. 順列を構築.
    vi ans;
    rep(i, N){
        // K が 1.
        if(--K == 0){
            for(auto i = st.rbegin(), e = st.rend(); i != e; ++i) ans.pb(*i);
            break;
        }
        
        // 整数列 A の 要素.
        if(st.count(a[i])){
            // 保存.
            ans.pb(a[i]);
            
            // 例外.
            int f = *st.begin();
            if(a[i] > f){
                ans.pb(f);
                st.erase(f);
            }
        }
        
        // 未使用リストから除外.
        st.erase(a[i]);
    }
    
    // 4. 出力
    rep(i, N) printf("%d%s", ans[i], (i < N - 1) ? " " : "\n");
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc125/editorial/2499

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = 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 a[202020];

int main(){

// 1. 入力情報.

int N, K;

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

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

// 2. 未使用リスト.

set<int> st;

rep(i, N) st.insert(i + 1);

// 3. 順列を構築.

vi ans;

rep(i, N){

// K が 1.

if(--K == 0){

for(auto i = st.rbegin(), e = st.rend(); i != e; ++i) ans.pb(*i);

break;

}

// 整数列 A の要素.

if(st.count(a[i])){

// 保存.

ans.pb(a[i]);

// 例外.

int f = *st.begin();

if(a[i] > f){

ans.pb(f);

st.erase(f);

}

// 未使用リストから除外.

st.erase(a[i]);

}

// 4. 出力

rep(i, N) printf("%d%s", ans[i], (i < N - 1) ? " " : "\n");

return 0;

}

[入力例]
3 2
2 3

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

[入力例]
5 1
4

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

[入力例]
3 1
3

[出力例]
3 2 1

[入力例]
7 4
3 5 6 7

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

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

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

[入力例]
20 7
3 4 7 8 9 12 15

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

[入力例]
50 10
5 7 11 25 28 31 34 43 47 48

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

[入力例]

3 2

2 3

[出力例]

2 1 3

※AtCoderのテストケースより

[入力例]

5 1

[出力例]

5 4 3 2 1

※AtCoderのテストケースより

[入力例]

3 1

[出力例]

3 2 1

[入力例]

7 4

3 5 6 7

[出力例]

3 1 5 2 6 4 7

[入力例]

10 5

2 4 6 8 9

[出力例]

2 1 4 3 6 5 8 7 10 9

[入力例]

20 7

3 4 7 8 9 12 15

[出力例]

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

[入力例]

50 10

5 7 11 25 28 31 34 43 47 48

[出力例]

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

■参照サイト
AtCoder Regular Contest 125

2022年6月5日

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

C++の練習を兼ねて, AtCoder Beginner Contest 254 の問題C (K Swap) ～問題D (Together Square) を解いてみた.

■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 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 main(){
    
    // 1. 入力情報.
    int N, K;
    scanf("%d %d", &N, &K);
    vi o;
    vvi t(K);
    rep(i, N){
        int x;
        scanf("%d", &x);
        o.pb(x);
        t[i % K].pb(x);
    }
    
    // 2. 並び替え.
    sort(all(o));
    rep(i, K) sort(all(t[i]));
    
    // 3. 復元.
    vi a(N);
    rep(i, K) rep(j, t[i].size()) a[i + j * K] = t[i][j];
    
    // 4. 出力.
    printf("%s\n", (a == o) ? "Yes" : "No");
    return 0;
    
}

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

// 1. 入力情報.

int N, K;

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

vi o;

vvi t(K);

rep(i, N){

int x;

scanf("%d", &x);

o.pb(x);

t[i % K].pb(x);

}

// 2. 並び替え.

sort(all(o));

rep(i, K) sort(all(t[i]));

// 3. 復元.

vi a(N);

rep(i, K) rep(j, t[i].size()) a[i + j * K] = t[i][j];

// 4. 出力.

printf("%s\n", (a == o) ? "Yes" : "No");

return 0;

}

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

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

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

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

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

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

[入力例]
3 1
3 2 1

[出力例]
Yes

[入力例]
3 1
2 1 3

[出力例]
Yes

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

[出力例]
No

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

[出力例]
Yes

[入力例]

5 2

3 4 1 3 4

[出力例]

Yes

※AtCoderテストケースより

[入力例]

5 3

3 4 1 3 4

[出力例]

※AtCoderテストケースより

[入力例]

7 5

1 2 3 4 5 5 10

[出力例]

Yes

※AtCoderテストケースより

[入力例]

3 1

3 2 1

[出力例]

Yes

[入力例]

3 1

2 1 3

[出力例]

Yes

[入力例]

7 2

6 7 1 3 2 4 9

[出力例]

[入力例]

7 2

10 7 6 5 3 2 1

[出力例]

Yes

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

// 解き直し.
// https://atcoder.jp/contests/abc254/editorial/4065
// 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 f[202020], g[202020];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    
    // 2. f を 計算.
    int u = sqrt(N) + 1;
    repx(i, 1, u + 1){
        // 基準とする平方数.
        int sq = i * i;
        
        // sq を約数に持つ整数で, f を 更新.
        repex(j, sq, N + 1, sq) f[j] = max(f[j], sq);
    }
    
    // 3. f[i] / i の カウントアップ.
    repx(i, 1, N + 1) ++g[i / f[i]];
    
    // 4. 集計.
    int ans = N;
    rep(i, N + 1) ans += g[i] * (g[i] - 1);
    
    // 5. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc254/editorial/4065

// 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 f[202020], g[202020];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

// 2. f を計算.

int u = sqrt(N) + 1;

repx(i, 1, u + 1){

// 基準とする平方数.

int sq = i * i;

// sq を約数に持つ整数で, f を更新.

repex(j, sq, N + 1, sq) f[j] = max(f[j], sq);

}

// 3. f[i] / i のカウントアップ.

repx(i, 1, N + 1) ++g[i / f[i]];

// 4. 集計.

int ans = N;

rep(i, N + 1) ans += g[i] * (g[i] - 1);

// 5. 出力.

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

return 0;

}

[入力例]
4

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

[入力例]
254

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

[入力例]
100

[出力例]
310

[入力例]
1000

[出力例]
4344

[入力例]
2022

[出力例]
9564

[入力例]
10000

[出力例]
57296

[入力例]
200000

[出力例]
1512912

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

254

[出力例]

896

※AtCoderテストケースより

[入力例]

100

[出力例]

310

[入力例]

1000

[出力例]

4344

[入力例]

2022

[出力例]

9564

[入力例]

10000

[出力例]

57296

[入力例]

200000

[出力例]

1512912

■参照サイト
AtCoder Beginner Contest 254

2022年6月4日2022年6月4日

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

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

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

本家のサイト AtCoder Beginner Contest 155 解説をご覧下さい.

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

// 解き直し.
// https://img.atcoder.jp/abc155/editorial.pdf
// 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 dp[1010101][2]; // 第一成分: ビッタリ払う, 第二成分: 1 余分払う.

int main(){
    
    // 1. 入力情報.
    char c[1010101];
    scanf("%s", c);
    string N(c);
    
    // 2. 先頭桁調整.
    // -> 最上位を, 0 として, 1 余分に払うパターンを考慮できるようにする.
    N = "0" + N;
    
    // 3. 初期化.
    int n = N.size();
    dp[0][0] = N[0] - '0';
    dp[0][1] = N[0] - '0' + 1;
    
    // 4. dp更新.
    repx(i, 1, n){
        // 4-1. i桁目.
        int d = N[i] - '0';
        
        // 4-2. ビッタリ払う.
        dp[i][0] = min(dp[i - 1][0] + d, dp[i - 1][1] + (10 - d));
        
        // 4-3. 最終桁調整(最後の桁は, 1 余分に払うパターンを除外).
        int one = 1 * (i != n - 1);
        
        // 4-4. 1 余分払う.
        dp[i][1] = min(dp[i - 1][1] + (10 - d - one), dp[i - 1][0] + d + one);
    }
    
    // 5. 出力.
    printf("%d\n", min(dp[n - 1][0], dp[n - 1][1]));
    return 0;
    
}

// 解き直し.

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

// 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 dp[1010101][2]; // 第一成分: ビッタリ払う, 第二成分: 1 余分払う.

int main(){

// 1. 入力情報.

char c[1010101];

scanf("%s", c);

string N(c);

// 2. 先頭桁調整.

// -> 最上位を, 0 として, 1 余分に払うパターンを考慮できるようにする.

N = "0" + N;

// 3. 初期化.

int n = N.size();

dp[0][0] = N[0] - '0';

dp[0][1] = N[0] - '0' + 1;

// 4. dp更新.

repx(i, 1, n){

// 4-1. i桁目.

int d = N[i] - '0';

// 4-2. ビッタリ払う.

dp[i][0] = min(dp[i - 1][0] + d, dp[i - 1][1] + (10 - d));

// 4-3. 最終桁調整(最後の桁は, 1 余分に払うパターンを除外).

int one = 1 * (i != n - 1);

// 4-4. 1 余分払う.

dp[i][1] = min(dp[i - 1][1] + (10 - d - one), dp[i - 1][0] + d + one);

}

// 5. 出力.

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

return 0;

}

[入力例]
36

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

[入力例]
91

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

[入力例]
314159265358979323846264338327950288419716939937551058209749445923078164062862089986280348253421170

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

[入力例]
55

[出力例]
10

[入力例]
2022

[出力例]
6

[入力例]
20220604

[出力例]
15

[入力例]
865

[出力例]
10

[入力例]
7303757170859110488253090166330591255584950648690495237568073417200248460609313772306159454783496207

[出力例]
250

[入力例]
70724236466682625983016007650618881977929720811339637123932889561587123865534594622908595022197867223711960026404451240970288911416387630615546871416353142099273847546794603912894032648233372930248274810021639656516270709975272305731817534338372670653812535382705418865350491561024438040752395240366745848586089405483319432991636452524649751165371256967896598248596768697535534954072556144874581365149044725352118618897521264905211964582621496071657993373871053636780385438537020885511873338571352435

[出力例]
1296

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

314159265358979323846264338327950288419716939937551058209749445923078164062862089986280348253421170

[出力例]

243

※AtCoderテストケースより

[入力例]

[出力例]

[入力例]

2022

[出力例]

[入力例]

20220604

[出力例]

[入力例]

865

[出力例]

[入力例]

7303757170859110488253090166330591255584950648690495237568073417200248460609313772306159454783496207

[出力例]

250

[入力例]

70724236466682625983016007650618881977929720811339637123932889561587123865534594622908595022197867223711960026404451240970288911416387630615546871416353142099273847546794603912894032648233372930248274810021639656516270709975272305731817534338372670653812535382705418865350491561024438040752395240366745848586089405483319432991636452524649751165371256967896598248596768697535534954072556144874581365149044725352118618897521264905211964582621496071657993373871053636780385438537020885511873338571352435

[出力例]

1296

■参照サイト
AtCoder Beginner Contest 155

2022年5月31日

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

C++の練習を兼ねて, AtCoder Regular Contest 141 の問題B (Increasing Prefix XOR) を解いてみた.

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

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

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

// 解き直し.
// https://atcoder.jp/contests/arc141/editorial/4022
// 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--)
const LL MOD = 998244353;
LL dp[66][66];

int main(){
    
    // 1. 入力情報.
    LL N, M;
    scanf("%lld %lld", &N, &M);
    
    // 2. 例外.
    if(N > 60){
        puts("0");
        return 0;
    }
    
    // 3. 初期化.
    LL cPow2 = 1;
    int d = 0;
    repx(k, 1, 61){
        // 設定.
        dp[1][k] = (cPow2 <= M) ? cPow2 : M;
        dp[1][k] %= MOD;
        
        // 減算.
        M -= cPow2;
        
        // 終了条件.
        if(M <= 0){
            d = k;
            break;
        }
        
        // 2倍.
        cPow2 <<= 1LL;
    }
    
    // 4. dp更新.
    repx(i, 2, (int)N + 1){
        repx(k1, 1, d + 1){
            repx(k2, k1 + 1, d + 1){
                dp[i][k2] += (dp[i - 1][k1] * dp[1][k2] % MOD);
                dp[i][k2] %= MOD;
            }
        }
    }
    
    // 5. 集計.
    LL ans = 0;
    repx(k, (int)N, d + 1) ans = (ans + dp[(int)N][k]) % MOD;
    
    // 6. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc141/editorial/4022

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

const LL MOD = 998244353;

LL dp[66][66];

int main(){

// 1. 入力情報.

LL N, M;

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

// 2. 例外.

if(N > 60){

puts("0");

return 0;

}

// 3. 初期化.

LL cPow2 = 1;

int d = 0;

repx(k, 1, 61){

// 設定.

dp[1][k] = (cPow2 <= M) ? cPow2 : M;

dp[1][k] %= MOD;

// 減算.

M -= cPow2;

// 終了条件.

if(M <= 0){

d = k;

break;

}

// 2倍.

cPow2 <<= 1LL;

}

// 4. dp更新.

repx(i, 2, (int)N + 1){

repx(k1, 1, d + 1){

repx(k2, k1 + 1, d + 1){

dp[i][k2] += (dp[i - 1][k1] * dp[1][k2] % MOD);

dp[i][k2] %= MOD;

}

// 5. 集計.

LL ans = 0;

repx(k, (int)N, d + 1) ans = (ans + dp[(int)N][k]) % MOD;

// 6. 出力.

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

return 0;

}

[入力例]
2 4

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

[入力例]
4 4

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

[入力例]
10 123456789

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

[入力例]
3 14

[出力例]
106

[入力例]
5 123

[出力例]
2564352

[入力例]
3 234

[出力例]
665226

[入力例]
12 34567

[出力例]
340820379

[入力例]
50 12345678987654321

[出力例]
967073402

[入力例]

2 4

[出力例]

※AtCoderのテストケースより

[入力例]

4 4

[出力例]

※AtCoderのテストケースより

[入力例]

10 123456789

[出力例]

205695670

※AtCoderのテストケースより

[入力例]

3 14

[出力例]

106

[入力例]

5 123

[出力例]

2564352

[入力例]

3 234

[出力例]

665226

[入力例]

12 34567

[出力例]

340820379

[入力例]

50 12345678987654321

[出力例]

967073402

■参照サイト
AtCoder Regular Contest 141

2022年5月30日

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

C++の練習を兼ねて, AtCoder Regular Contest 141 の問題A (Periodic Number) を解いてみた.

■感想.
1. 問題Aは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc141/editorial/4021
// 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

int main(){
    
    // 1. 入力情報.
    int T;
    scanf("%d", &T);
    
    // 2. 10の冪乗.
    vl cPow;
    cPow.pb(1);
    while(cPow.back() < 1e18){
        // 最大値を10倍.
        LL p = 10 * cPow.back();
        
        // 保存.
        cPow.pb(p);
    }
    
    // 3. テストケース.
    rep(i, T){
        // 3-1. 各テストケース.
        LL N;
        scanf("%lld", &N);
        string s = to_string(N);
        int sl = s.size();
        
        // 3-2. 例外.
        // -> 予め, 999...999 の ケース を 保存.
        LL ans = 0;
        for(auto &p : cPow) if(p <= N) ans = p - 1;
        
        // 3-3. 周期的な数は？
        for(auto &d : {1, 2, 3, 4, 5, 6, 7, 8, 9}){
            // d 桁ずつ分けることができるか？
            if(sl % d) continue;
            
            // 2個以上に分割できるか？
            if((sl / d) < 2) continue;
            
            // パターン①.
            string c1 = s.substr(0, d);
            string sCur1 = "";
            rep(i, sl / d) sCur1 += c1;
            LL cur1 = stoll(sCur1);
            if(cur1 <= N) ans = max(ans, cur1);
            
            // パターン②.
            string c2 = to_string(stoll(c1) - 1);
            string sCur2 = "";
            rep(i, sl / d) sCur2 += c2;
            LL cur2 = stoll(sCur2);
            ans = max(ans, cur2);
        }
        
        // 3-4. 出力.
        printf("%lld\n", ans);
    }
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc141/editorial/4021

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

int main(){

// 1. 入力情報.

int T;

scanf("%d", &T);

// 2. 10の冪乗.

vl cPow;

cPow.pb(1);

while(cPow.back() < 1e18){

// 最大値を10倍.

LL p = 10 * cPow.back();

// 保存.

cPow.pb(p);

}

// 3. テストケース.

rep(i, T){

// 3-1. 各テストケース.

LL N;

scanf("%lld", &N);

string s = to_string(N);

int sl = s.size();

// 3-2. 例外.

// -> 予め, 999...999 のケースを保存.

LL ans = 0;

for(auto &p : cPow) if(p <= N) ans = p - 1;

// 3-3. 周期的な数は？

for(auto &d : {1, 2, 3, 4, 5, 6, 7, 8, 9}){

// d 桁ずつ分けることができるか？

if(sl % d) continue;

// 2個以上に分割できるか？

if((sl / d) < 2) continue;

// パターン①.

string c1 = s.substr(0, d);

string sCur1 = "";

rep(i, sl / d) sCur1 += c1;

LL cur1 = stoll(sCur1);

if(cur1 <= N) ans = max(ans, cur1);

// パターン②.

string c2 = to_string(stoll(c1) - 1);

string sCur2 = "";

rep(i, sl / d) sCur2 += c2;

LL cur2 = stoll(sCur2);

ans = max(ans, cur2);

}

// 3-4. 出力.

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

}

return 0;

}

[入力例]
3
1412
23
498650499498649123

[出力例]
1313
22
498650498650498650
※AtCoderのテストケースより

[入力例]
12
11
12
100
1001
1010
2021
33333
100010
20220530
1110545233
176166110176166110
102030102030102030

[出力例]
11
11
99
999
1010
2020
33333
99999
20212021
1110511105
176166110176166110
102030102030102030

[入力例]
16
314
1592
65358
979323
8462643
38327950
288419716
9399375105
82097494459
230781640628
6208998628034
82534211706798
214808651328230
6647093844609550
58223172535940812
848111745028410270

[出力例]
222
1515
55555
978978
7777777
38323832
288288288
9399293992
77777777777
230781230781
5555555555555
82534208253420
214802148021480
6647093766470937
55555555555555555
848111744848111744

[入力例]

1412

498650499498649123

[出力例]

1313

498650498650498650

※AtCoderのテストケースより

[入力例]

100

1001

1010

2021

33333

100010

20220530

1110545233

176166110176166110

102030102030102030

[出力例]

999

1010

2020

33333

99999

20212021

1110511105

176166110176166110

102030102030102030

[入力例]

314

1592

65358

979323

8462643

38327950

288419716

9399375105

82097494459

230781640628

6208998628034

82534211706798

214808651328230

6647093844609550

58223172535940812

848111745028410270

[出力例]

222

1515

55555

978978

7777777

38323832

288288288

9399293992

77777777777

230781230781

5555555555555

82534208253420

214802148021480

6647093766470937

55555555555555555

848111744848111744

■参照サイト
AtCoder Regular Contest 141

2022年5月29日

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

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

■感想.
1. 問題Fは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 解説されているロジックで最小コストが計算できる点が, 非常に面白く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc252/editorial/3998
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using PQ = priority_queue<LL, vector<LL>, greater<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--)

int main(){
    
    // 1. 入力情報.
    int N;
    LL L, a, b = 0;
    scanf("%d %lld", &N, &L);
    PQ pq;
    rep(i, N){
        scanf("%lld", &a);
        pq.push(a);
        b += a;
    }
    
    // 2. L が a の 合計よりも大きい.
    if(L > b) pq.push(L - b);
    
    // 3. 最小のコストは？
    LL ans = 0;
    while(pq.size() > 1){
        LL s1 = pq.top();
        pq.pop();
        LL s2 = pq.top();
        pq.pop();
        ans += (s1 + s2);
        pq.push(s1 + s2);
    }
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc252/editorial/3998

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using PQ = priority_queue<LL, vector<LL>, greater<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--)

int main(){

// 1. 入力情報.

int N;

LL L, a, b = 0;

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

PQ pq;

rep(i, N){

scanf("%lld", &a);

pq.push(a);

b += a;

}

// 2. L が a の合計よりも大きい.

if(L > b) pq.push(L - b);

// 3. 最小のコストは？

LL ans = 0;

while(pq.size() > 1){

LL s1 = pq.top();

pq.pop();

LL s2 = pq.top();

pq.pop();

ans += (s1 + s2);

pq.push(s1 + s2);

}

// 4. 出力.

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

return 0;

}

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

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

[入力例]
3 1000000000000000
1000000000 1000000000 1000000000

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

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

[出力例]
176

[入力例]
25 1040
2 23 60 67 9 77 4 99 78 96 9 6 40 91 73 6 68 73 12 7 6 2 3 54 40

[出力例]
4322

[入力例]
75 5050
19 10 36 97 97 80 12 68 20 20 84 62 71 26 110 85 15 105 64 90 108 40 119 43 14 50 68 83 43 81 37 80 96 25 90 10 23 38 7 90 46 25 120 11 96 92 18 110 22 82 79 58 26 44 117 110 105 70 34 76 78 89 111 20 23 41 86 25 113 100 29 110 59 70 39

[出力例]
30000

[入力例]

5 7

1 2 1 2 1

[出力例]

※AtCoderテストケースより

[入力例]

3 1000000000000000

1000000000 1000000000 1000000000

[出力例]

1000005000000000

※AtCoderテストケースより

[入力例]

12 52

3 1 4 1 5 9 2 6 5 3 5 8

[出力例]

176

[入力例]

25 1040

2 23 60 67 9 77 4 99 78 96 9 6 40 91 73 6 68 73 12 7 6 2 3 54 40

[出力例]

4322

[入力例]

75 5050

19 10 36 97 97 80 12 68 20 20 84 62 71 26 110 85 15 105 64 90 108 40 119 43 14 50 68 83 43 81 37 80 96 25 90 10 23 38 7 90 46 25 120 11 96 92 18 110 22 82 79 58 26 44 117 110 105 70 34 76 78 89 111 20 23 41 86 25 113 100 29 110 59 70 39

[出力例]

30000

■参照サイト
AtCoder Beginner Contest 252

2022年5月28日

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

C++の練習を兼ねて, AtCoder Beginner Contest 252 の問題C (Slot Strategy) ～問題E (Road Reduction) を解いてみた.

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 問題Eは, ダイクストラ法(応用版, 経路記録)の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vs = vector<string>;
using vi = 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
#define all(x) x.begin(), x.end()
int t[101][10];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vs v;
    rep(i, N){
        char c[22];
        scanf("%s", c);
        string s(c);
        v.pb(s);
    }
    
    // 2. 各文字列の各数字が, 先頭に来る秒数は？
    rep(i, N) rep(j, 10) t[i][v[i][j] - '0'] = j;
    
    // 3. 各数字を揃えるために必要な時間から, 最小秒数を計算.
    int ans = 2020;
    rep(j, 10){
        // N 回分保存.
        vi v;
        rep(i, N) v.pb(t[i][j]);
        
        // sort.
        sort(all(v));
        
        // 必要秒数は？
        int bef = -1, c = 0, tCur = 0;
        for(auto &cur : v){
            // 比較(指定された秒数に, 最大1回までしかボタンが押せない).
            c = (bef == cur) ? (c + 1) : 0;
            
            // 前回分更新.
            bef = cur;
            
            // 必要秒数更新.
            tCur = max(tCur, cur + 10 * c);
        }
        
        // 更新.
        ans = min(ans, tCur);
    }
    
    // 4. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vs = vector<string>;

using vi = 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

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

int t[101][10];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vs v;

rep(i, N){

char c[22];

scanf("%s", c);

string s(c);

v.pb(s);

}

// 2. 各文字列の各数字が, 先頭に来る秒数は？

rep(i, N) rep(j, 10) t[i][v[i][j] - '0'] = j;

// 3. 各数字を揃えるために必要な時間から, 最小秒数を計算.

int ans = 2020;

rep(j, 10){

// N 回分保存.

vi v;

rep(i, N) v.pb(t[i][j]);

// sort.

sort(all(v));

// 必要秒数は？

int bef = -1, c = 0, tCur = 0;

for(auto &cur : v){

// 比較(指定された秒数に, 最大1回までしかボタンが押せない).

c = (bef == cur) ? (c + 1) : 0;

// 前回分更新.

bef = cur;

// 必要秒数更新.

tCur = max(tCur, cur + 10 * c);

}

// 更新.

ans = min(ans, tCur);

}

// 4. 出力.

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

return 0;

}

[入力例]
3
1937458062
8124690357
2385760149

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

[入力例]
5
0123456789
0123456789
0123456789
0123456789
0123456789

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

[入力例]
10
8321907546
0536427819
1457309682
8706139524
5289170463
4936027185
3481720596
2054783619
3976250481
7614398250

[出力例]
14

[入力例]
15
0254873961
9653248701
0193462758
6835104792
7058943261
2638104759
4081523679
8421075639
8042157369
0963187254
7623908541
3786590241
9201536748
7218543096
6584972103

[出力例]
23

[入力例]
20
1240369587
1490623857
7649508321
3158479026
0368712459
3501426987
5692407318
7063941852
8943571026
4208173695
4206973158
1795638204
1905843672
9806257314
3402817659
5943806127
0634597182
7205693481
5823940761
0461823579

[出力例]
27

[入力例]

1937458062

8124690357

2385760149

[出力例]

※AtCoderテストケースより

[入力例]

0123456789

[出力例]

※AtCoderテストケースより

[入力例]

8321907546

0536427819

1457309682

8706139524

5289170463

4936027185

3481720596

2054783619

3976250481

7614398250

[出力例]

[入力例]

0254873961

9653248701

0193462758

6835104792

7058943261

2638104759

4081523679

8421075639

8042157369

0963187254

7623908541

3786590241

9201536748

7218543096

6584972103

[出力例]

[入力例]

1240369587

1490623857

7649508321

3158479026

0368712459

3501426987

5692407318

7063941852

8943571026

4208173695

4206973158

1795638204

1905843672

9806257314

3402817659

5943806127

0634597182

7205693481

5823940761

0461823579

[出力例]

■C++版プログラム(問題D／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--)
#define a first
#define b second
int a[202020];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    map<int, int> mc, mi;
    rep(i, N){
        scanf("%d", &a[i]);
        mi[a[i]] = 0;
    }
    
    // 2. 座標圧縮.
    int idx = -1;
    for(auto &p : mi) p.b = ++idx;
    
    // 3. 各整数の出現回数は？
    rep(i, N) ++mc[mi[a[i]]];
    
    // 4. 集計.
    // 4-1. 1種類で構成される場合.
    LL ans = (LL)N * (LL)(N - 1) * (LL)(N - 2) / 6;
    for(auto &p : mc) ans -= (LL)p.b * (LL)(p.b - 1) * (LL)(p.b - 2) / 6;
    
    // 4-2. 2種類で構成される場合.
    for(auto &p : mc) ans -= (LL)p.b * (LL)(p.b - 1) / 2 * (LL)(N - p.b);
    
    // 5. 出力.
    printf("%lld\n", ans);
    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--)

#define a first

#define b second

int a[202020];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

map<int, int> mc, mi;

rep(i, N){

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

mi[a[i]] = 0;

}

// 2. 座標圧縮.

int idx = -1;

for(auto &p : mi) p.b = ++idx;

// 3. 各整数の出現回数は？

rep(i, N) ++mc[mi[a[i]]];

// 4. 集計.

// 4-1. 1種類で構成される場合.

LL ans = (LL)N * (LL)(N - 1) * (LL)(N - 2) / 6;

for(auto &p : mc) ans -= (LL)p.b * (LL)(p.b - 1) * (LL)(p.b - 2) / 6;

// 4-2. 2種類で構成される場合.

for(auto &p : mc) ans -= (LL)p.b * (LL)(p.b - 1) / 2 * (LL)(N - p.b);

// 5. 出力.

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

return 0;

}

[入力例]
4
3 1 4 1

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

[入力例]
10
99999 99998 99997 99996 99995 99994 99993 99992 99991 99990

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

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

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

[入力例]
20
9 3 15 2 14 12 13 10 9 10 5 9 1 7 7 10 13 11 1 11

[出力例]
964

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

[出力例]
130654

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

[出力例]
17714610

[入力例]

3 1 4 1

[出力例]

※AtCoderテストケースより

[入力例]

99999 99998 99997 99996 99995 99994 99993 99992 99991 99990

[出力例]

120

※AtCoderテストケースより

[入力例]

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

[出力例]

355

※AtCoderテストケースより

[入力例]

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

[出力例]

964

[入力例]

100

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

[出力例]

130654

[入力例]

500

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

[出力例]

17714610

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

// 解き直し.
// https://atcoder.jp/contests/abc252/editorial/3980
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vi = 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
const LL INF = 202020202020202020;
int route[202020];

struct edge{
    int n; // 次の頂点.
    LL c;  // コスト.
    bool operator < (const edge &E) const{ return c > E.c; }
};

vector<edge> G[202020];

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    map<P, int> me;
    rep(i, M){
        int a, b;
        LL c;
        scanf("%d %d %lld", &a, &b, &c);
        --a;
        --b;
        G[a].pb(edge{b, c});
        G[b].pb(edge{a, c});
        
        // 辺情報.
        me[{a, b}] = me[{b, a}] = i + 1;
    }
    
    // 2. ダイクストラ法.
    // https://ja.wikipedia.org/wiki/ダイクストラ法
    auto dijkstra = [&](int s, LL* d, int* memo){
        // 初期化.
        priority_queue<edge> pq;
        
        // 始点設定.
        d[s] = 0;
        pq.push({s, 0LL});
        
        // キュー pq が 空になるまで, 探索.
        while(!pq.empty()){
            // 探索を継続するために, 頂点を取得.
            edge e = pq.top();
            pq.pop();
            int cn = e.n;
            LL cc = e.c;
            
            // 訪問済みフラグ設定.
            if(memo[cn]) continue;
            memo[cn]++;
            
            // 各隣接する頂点について, 距離を確認し, 移動コストを更新.
            for(auto &g : G[cn]){
                // 移動コスト更新.
                int nn = g.n;
                LL nc = cc + g.c;
                if(d[nn] > nc){
                    d[nn] = nc;
                    pq.push({nn, nc});
                    
                    // 各都市に到達する直前の道路を記録(最大, 1個まで).
                    route[nn] = cn;
                }
            }
        }
    };
    
    // 3. 各都市までの, 最小コスト.
    LL d[N];
    int memo[N];
    rep(i, N) d[i] = INF, memo[i] = 0;
    dijkstra(0, d, memo);
    
    // 4. 辺情報に変換.
    vi ans;
    repx(i, 1, N) ans.pb(me[{i, route[i]}]);
    
    // 5. 出力.
    rep(i, N - 1) printf("%d%s", ans[i], (i < N - 2) ? " " : "\n");
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc252/editorial/3980

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vi = 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

const LL INF = 202020202020202020;

int route[202020];

struct edge{

int n; // 次の頂点.

LL c; // コスト.

bool operator < (const edge &E) const{ return c > E.c; }

};

vector<edge> G[202020];

int main(){

// 1. 入力情報.

int N, M;

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

map<P, int> me;

rep(i, M){

int a, b;

LL c;

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

--a;

--b;

G[a].pb(edge{b, c});

G[b].pb(edge{a, c});

// 辺情報.

me[{a, b}] = me[{b, a}] = i + 1;

}

// 2. ダイクストラ法.

// https://ja.wikipedia.org/wiki/ダイクストラ法

auto dijkstra = [&](int s, LL* d, int* memo){

// 初期化.

priority_queue<edge> pq;

// 始点設定.

d[s] = 0;

pq.push({s, 0LL});

// キュー pq が空になるまで, 探索.

while(!pq.empty()){

// 探索を継続するために, 頂点を取得.

edge e = pq.top();

pq.pop();

int cn = e.n;

LL cc = e.c;

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

if(memo[cn]) continue;

memo[cn]++;

// 各隣接する頂点について, 距離を確認し, 移動コストを更新.

for(auto &g : G[cn]){

// 移動コスト更新.

int nn = g.n;

LL nc = cc + g.c;

if(d[nn] > nc){

d[nn] = nc;

pq.push({nn, nc});

// 各都市に到達する直前の道路を記録(最大, 1個まで).

route[nn] = cn;

}

};

// 3. 各都市までの, 最小コスト.

LL d[N];

int memo[N];

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

dijkstra(0, d, memo);

// 4. 辺情報に変換.

vi ans;

repx(i, 1, N) ans.pb(me[{i, route[i]}]);

// 5. 出力.

rep(i, N - 1) printf("%d%s", ans[i], (i < N - 2) ? " " : "\n");

return 0;

}

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

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

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

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

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

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

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

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

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

[入力例]

3 3

1 2 1

2 3 2

1 3 10

[出力例]

1 2

※AtCoderテストケースより

[入力例]

4 6

1 2 1

1 3 1

1 4 1

2 3 1

2 4 1

3 4 1

[出力例]

3 1 2

※AtCoderテストケースより

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

1 2 3

[入力例]

10 12

2 3 1

2 6 1

1 3 1

3 6 1

6 7 3

8 10 1

7 10 1

5 8 6

5 9 3

8 9 1

4 5 1

1 4 1

[出力例]

1 3 12 11 4 5 10 9 7

[入力例]

15 19

1 2 3

2 10 1

2 9 4

8 9 5

8 11 1

9 11 2

5 9 1

5 6 3

1 6 1

1 12 2

12 15 7

12 13 1

13 15 2

4 6 1

4 7 3

3 7 1

3 4 5

4 14 6

5 14 8

[出力例]

1 16 14 8 9 15 5 7 2 6 10 12 18 13

■参照サイト
AtCoder Beginner Contest 252

2022年5月26日

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

C++の練習を兼ねて, AtCoder Beginner Contest 198 の問題E (Unique Color) を解いてみた.

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 深さ優先探索の訓練を積めたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc198/editorial/540
// 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
const int MAX = 101010;
int c[MAX], memo[MAX], g[MAX], ans[MAX];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d", &c[i]);
    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. dfs.
    // https://ja.wikipedia.org/wiki/深さ優先探索
    auto dfs = [&](auto&& self, vvi &G, int cur, int bef) -> void {
        // 終了条件.
        if(memo[cur]) return;
        
        // 訪問済み.
        ++memo[cur];
        
        // 往路(カウントアップ).
        ++g[c[cur]];
        
        // よい頂点か？
        if(g[c[cur]] == 1) ++ans[cur];
        
        // 隣接頂点.
        for(auto &nex : G[cur]) if(bef != nex) self(self, G, nex, cur);
        
        // 復路(カウントダウン).
        --g[c[cur]];
    };
    dfs(dfs, G, 0, -1);
    
    // 3. 出力.
    rep(i, N) if(ans[i]) printf("%d\n", i + 1);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc198/editorial/540

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

const int MAX = 101010;

int c[MAX], memo[MAX], g[MAX], ans[MAX];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

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. dfs.

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

auto dfs = [&](auto&& self, vvi &G, int cur, int bef) -> void {

// 終了条件.

if(memo[cur]) return;

// 訪問済み.

++memo[cur];

// 往路(カウントアップ).

++g[c[cur]];

// よい頂点か？

if(g[c[cur]] == 1) ++ans[cur];

// 隣接頂点.

for(auto &nex : G[cur]) if(bef != nex) self(self, G, nex, cur);

// 復路(カウントダウン).

--g[c[cur]];

};

dfs(dfs, G, 0, -1);

// 3. 出力.

rep(i, N) if(ans[i]) printf("%d\n", i + 1);

return 0;

}

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

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

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

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

[入力例]
2
2 1
1 2

[出力例]
1
2

[入力例]
2
3 3
1 2

[出力例]
1

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

[出力例]
1
2
3

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

[出力例]
1
2
4
6

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

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

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

[出力例]
1
2
3
4
5
6
7
8
9
10
12
14
15
16
17
18
19
20
23
24
26
27
28
29

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

[出力例]
1
2
3
7
8
10
11
12
15
16
17
18
20
22
25
27
29
30
31
33
35
36
38
40

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

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

[入力例]

2 7 1 8 2 8

1 2

3 6

3 2

4 3

2 5

[出力例]

※AtCoderテストケースより

[入力例]

3 1 4 1 5 9 2 6 5 3

1 2

2 3

3 4

4 5

5 6

6 7

7 8

8 9

9 10

[出力例]

※AtCoderテストケースより

[入力例]

2 1

1 2

[出力例]

[入力例]

3 3

1 2

[出力例]

[入力例]

2 1 1 2 1

1 2

1 3

4 3

5 3

[出力例]

[入力例]

1 2 1 2 1 2 1

1 2

1 3

1 4

5 1

6 1

7 1

[出力例]

[入力例]

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

1 2

1 5

1 10

2 3

2 4

4 6

9 4

5 8

5 7

10 11

10 12

17 11

18 11

12 13

12 14

15 14

16 14

19 15

20 15

[出力例]

[入力例]

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

1 2

1 3

1 4

2 10

2 5

3 9

3 6

4 7

4 8

5 12

5 11

9 14

9 13

13 15

13 16

15 17

15 18

7 21

7 20

7 19

8 22

8 23

8 24

23 25

23 26

26 27

26 28

28 29

28 30

[出力例]

[入力例]

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

1 2

1 12

2 3

3 4

5 3

4 34

35 4

12 13

14 13

5 6

6 7

6 8

8 9

9 10

11 7

11 20

11 21

14 15

16 14

16 17

17 18

17 19

22 10

23 22

24 22

25 22

26 22

27 22

28 25

29 25

36 28

37 28

30 26

31 26

32 27

33 27

38 31

39 31

40 39

41 39

[出力例]

■参照サイト
AtCoder Beginner Contest 198

C++の練習を兼ねて, AtCoder Regular Contest 126 の 問題C (Maximize GCD) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 128 の 問題C (Max Dot) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 125 の 問題C (LIS to Original Sequence) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 254 の 問題C (K Swap) ～ 問題D (Together Square) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 141 の 問題B (Increasing Prefix XOR) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 141 の 問題A (Periodic Number) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 252 の 問題C (Slot Strategy) ～ 問題E (Road Reduction) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 198 の 問題E (Unique Color) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 126 の問題C (Maximize GCD) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 128 の問題C (Max Dot) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 125 の問題C (LIS to Original Sequence) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 254 の問題C (K Swap) ～問題D (Together Square) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 141 の問題B (Increasing Prefix XOR) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 141 の問題A (Periodic Number) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 252 の問題C (Slot Strategy) ～問題E (Road Reduction) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 198 の問題E (Unique Color) を解いてみた.