C++ | 個人用メモ帳

2022年1月16日

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

C++の練習を兼ねて, 第七回アルゴリズム実技検定の問題H (折れ線グラフ) を解いてみた.

■感想.
1. 問題Hは, 方針が見えなかったので, 解説のdp更新式を参照し, AC版に到達できた.
2. 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. 個人的には, 折れ線グラフの最短距離が, 動的計画法を使って求めることができるロジックが, 非常に興味深く感じた.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト第七回アルゴリズム実技検定の各リンクをご覧下さい.

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

// 解き直し.
// https://atcoder.jp/contests/past202107-open/editorial/2194
// 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[101];
double dp[101][101][101];

int main(){

    // 1. 入力情報.
    int N, S = 0;
    scanf("%d", &N);
    rep(i, N){
        scanf("%d", &a[i]);
        S += a[i];
    }
    
    // 2. dp更新.
    rep(i, 101) rep(j, 101) rep(k, 101) dp[i][j][k] = 2020202020.0;
    dp[1][0][0] = 0.0;
    repx(i, 2, N + 1){
        rep(s, S + 1){
            rep(l, s + 1){
                rep(j, s - l + 1){
                    dp[i][s][l] = min(dp[i][s][l], dp[i - 1][s - l][j] + sqrt(1 + (j - l) * (j - l)));
                }
            }
        }
    }
    
    // 3. 出力.
    printf("%.16lf\n", dp[N][S][0]);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/past202107-open/editorial/2194

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

double dp[101][101][101];

int main(){

// 1. 入力情報.

int N, S = 0;

scanf("%d", &N);

rep(i, N){

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

S += a[i];

}

// 2. dp更新.

rep(i, 101) rep(j, 101) rep(k, 101) dp[i][j][k] = 2020202020.0;

dp[1][0][0] = 0.0;

repx(i, 2, N + 1){

rep(s, S + 1){

rep(l, s + 1){

rep(j, s - l + 1){

dp[i][s][l] = min(dp[i][s][l], dp[i - 1][s - l][j] + sqrt(1 + (j - l) * (j - l)));

}

// 3. 出力.

printf("%.16lf\n", dp[N][S][0]);

return 0;

}

[入力例]
4
0 3 0 0

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

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

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

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

[出力例]
10.6568542494923797

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

[出力例]
16.3650581819917491

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

[出力例]
32.3137084989847594

[入力例]

0 3 0 0

[出力例]

5.0644951022459797

※AtCoderテストケースより

[入力例]

0 1 2 3 4 5 0

[出力例]

10.3245553203367599

※AtCoderテストケースより

[入力例]

0 1 2 3 3 0 1 0 0 0

[出力例]

10.6568542494923797

[入力例]

0 3 1 4 1 5 9 2 6 5 3 0

[出力例]

16.3650581819917491

[入力例]

0 6 1 0 6 0 2 1 5 0 3 6 8 4 3 2 0 5 2 1 5 6 5 3 0 3 5 2 1 0

[出力例]

32.3137084989847594

■参照サイト
第七回アルゴリズム実技検定

2022年1月15日

■感想.
1. 問題Gは, 方針が見えなかったので, 解説の漸化式を参考の上, AC版に到達できた.
2. 個人的には, 深さ優先探索の訓練を積めたので, 理解を深めることが出来たと思う.
3. 解説にある漸化式を実装すると, 数列内に重複要素が出てこないことが, 非常に不思議な印象を受けた.
※ 解説を見る前は, 数列内の重複要素を排除する方法が分からなかったため.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト第七回アルゴリズム実技検定の各リンクをご覧下さい.

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

// 解き直し.
// https://atcoder.jp/contests/past202107-open/editorial/1826
// 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. 入力情報.
    LL N;
    scanf("%lld", &N);
    
    // 2. dfs(解説通り).
    // https://ja.wikipedia.org/wiki/深さ優先探索
    auto dfs = [&](auto&& self, LL x) -> vl{
        // 2-1. x が 0.
        vl ret = {};
        if(x == 0) return ret;
        
        // 2-2. x = 0 (mod 3).
        if(x % 3 == 0){
            ret = self(self, x / 3);
            for(auto &x : ret) x *= 3;
        }
        
        // 2-3. x = 1 (mod 3).
        if(x % 3 == 1){
            ret = self(self, (x - 1) / 3);
            for(auto &x : ret) x *= 3;
            ret.pb(1);
        }
        
        // 2-4. x = 2 (mod 3).
        if(x % 3 == 2){
            ret = self(self, (x + 1) / 3);
            for(auto &x : ret) x *= 3;
            ret.pb(-1);
        }
        
        // 2-5. 返却.
        return ret;
    };
    vl ans = dfs(dfs, N);
    
    // 3. 出力.
    int M = ans.size();
    printf("%d\n", M);
    rep(i, M) printf("%lld%s", ans[i], (i < M - 1) ? " " : "\n");
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/past202107-open/editorial/1826

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

LL N;

scanf("%lld", &N);

// 2. dfs(解説通り).

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

auto dfs = [&](auto&& self, LL x) -> vl{

// 2-1. x が 0.

vl ret = {};

if(x == 0) return ret;

// 2-2. x = 0 (mod 3).

if(x % 3 == 0){

ret = self(self, x / 3);

for(auto &x : ret) x *= 3;

}

// 2-3. x = 1 (mod 3).

if(x % 3 == 1){

ret = self(self, (x - 1) / 3);

for(auto &x : ret) x *= 3;

ret.pb(1);

}

// 2-4. x = 2 (mod 3).

if(x % 3 == 2){

ret = self(self, (x + 1) / 3);

for(auto &x : ret) x *= 3;

ret.pb(-1);

}

// 2-5. 返却.

return ret;

};

vl ans = dfs(dfs, N);

// 3. 出力.

int M = ans.size();

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

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

return 0;

}

[入力例]
6

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

[入力例]
9193

[出力例]
9
2187 27 1 -243 3 9 -81 6561 729 
※AtCoderのテストケースより

※但し, 上記のプログラムでは, 以下の内容が出力される.
9
6561 2187 729 -243 -81 27 9 3 1

[入力例]
10120190919012

[出力例]
16
-1594323 9 -177147 -531441 1162261467 -4782969 387420489 -6561 -2187 2541865828329 -27 7625597484987 3486784401 10460353203 -94143178827 31381059609 

※但し, 上記のプログラムでは, 以下の内容が出力される.
16
7625597484987 2541865828329 -94143178827 31381059609 10460353203 3486784401 1162261467 387420489 -4782969 -1594323 -531441 -177147 -6561 -2187 -27 9

[入力例]
5

[出力例]
3
9 -3 -1

[入力例]
111

[出力例]
3
81 27 3

[入力例]
2022

[出力例]
4
2187 -243 81 -3

[入力例]
20220115

[出力例]
11
14348907 4782969 1594323 -531441 19683 6561 -729 -243 81 3 1

[入力例]
202107031300

[出力例]
14
282429536481 -94143178827 10460353203 3486784401 -129140163 4782969 -1594323 -531441 19683 -729 81 -27 -9 1

[入力例]
314159265358979

[出力例]
23
617673396283947 -205891132094649 -68630377364883 -22876792454961 -7625597484987 2541865828329 -847288609443 -282429536481 94143178827 3486784401 -14348907 4782969 531441 -177147 59049 -19683 2187 -729 -243 -81 27 -3 -1

[入力例]

[出力例]

9 -3

※AtCoderのテストケースより

[入力例]

9193

[出力例]

2187 27 1 -243 3 9 -81 6561 729

※AtCoderのテストケースより

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

6561 2187 729 -243 -81 27 9 3 1

[入力例]

10120190919012

[出力例]

-1594323 9 -177147 -531441 1162261467 -4782969 387420489 -6561 -2187 2541865828329 -27 7625597484987 3486784401 10460353203 -94143178827 31381059609

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

7625597484987 2541865828329 -94143178827 31381059609 10460353203 3486784401 1162261467 387420489 -4782969 -1594323 -531441 -177147 -6561 -2187 -27 9

[入力例]

[出力例]

9 -3 -1

[入力例]

111

[出力例]

81 27 3

[入力例]

2022

[出力例]

2187 -243 81 -3

[入力例]

20220115

[出力例]

14348907 4782969 1594323 -531441 19683 6561 -729 -243 81 3 1

[入力例]

202107031300

[出力例]

282429536481 -94143178827 10460353203 3486784401 -129140163 4782969 -1594323 -531441 19683 -729 81 -27 -9 1

[入力例]

314159265358979

[出力例]

617673396283947 -205891132094649 -68630377364883 -22876792454961 -7625597484987 2541865828329 -847288609443 -282429536481 94143178827 3486784401 -14348907 4782969 531441 -177147 59049 -19683 2187 -729 -243 -81 27 -3 -1

■参照サイト
第七回アルゴリズム実技検定

2022年1月14日

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

C++の練習を兼ねて, AtCoder Regular Contest 076 の問題D (Built?) を解いてみた.

■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考に, AC版に到達できた.
2. 最小全域木(Kruskal’s Algorithm) の復習が出来たので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/arc076/editorial.pdf
// 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>;
using vp = vector<P>;
using T3 = tuple<LL, 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
#define all(x) x.begin(), x.end()

// 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;
    scanf("%d", &N);
    vp cxy, cyx;
    map<P, int> m;
    rep(i, N){
        int x, y;
        scanf("%d %d", &x, &y);
        
        // 街情報(座標).
        cxy.pb({x, y});
        cyx.pb({y, x});
        
        // 街情報(番号).
        m[{x, y}] = i;
    }
    
    // 2. sort.
    // 2-1. X座標ソート.
    sort(all(cxy));
    
    // 2-2. Y座標ソート.
    sort(all(cyx));
    
    // 3. グラフ情報.
    // 3-1. X座標ソート版.
    vector<T3> t;
    rep(i, N - 1){
        // 出発地点.
        int sx = cxy[i].a;
        int sy = cxy[i].b;
        int sn = m[{sx, sy}];
        
        // 到着地点.
        int gx = cxy[i + 1].a;
        int gy = cxy[i + 1].b;
        int gn = m[{gx, gy}];
        
        // コスト.
        LL c = (LL)min(abs(sx - gx), abs(sy - gy));
        
        // 保存.
        t.emplace_back(c, sn, gn);
    }
    
    // 3-2. Y座標ソート版.
    rep(i, N - 1){
        // 出発地点.
        int sx = cyx[i].a;
        int sy = cyx[i].b;
        int sn = m[{sy, sx}];
        
        // 到着地点.
        int gx = cyx[i + 1].a;
        int gy = cyx[i + 1].b;
        int gn = m[{gy, gx}];
        
        // コスト.
        LL c = (LL)min(abs(sx - gx), abs(sy - gy));
        
        // 保存.
        t.emplace_back(c, sn, gn);
    }
    
    // 4. sort.
    sort(all(t));
    
    // 5. 最小全域木(Kruskal's Algorithm) の 構築.
    // 競プロ典型 90 問 (049 - Flip Digits 2)
    // https://github.com/E869120/kyopro_educational_90/blob/main/sol/049.cpp
    LL ans = 0;
    UnionFind uf(2 * N);
    rep(i, t.size()){
        // グラフ情報.
        int u = get<1>(t[i]);
        int v = get<2>(t[i]);
        LL c = get<0>(t[i]);
        
        // 最小全域木を構成する辺の追加, コスト計算.
        if(!uf.same(u, v)){
            uf.unite(u, v);
            ans += c;
        }
    }
    
    // 6. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

// 解き直し.

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

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

using vp = vector<P>;

using T3 = tuple<LL, 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

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

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

scanf("%d", &N);

vp cxy, cyx;

map<P, int> m;

rep(i, N){

int x, y;

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

// 街情報(座標).

cxy.pb({x, y});

cyx.pb({y, x});

// 街情報(番号).

m[{x, y}] = i;

}

// 2. sort.

// 2-1. X座標ソート.

sort(all(cxy));

// 2-2. Y座標ソート.

sort(all(cyx));

// 3. グラフ情報.

// 3-1. X座標ソート版.

vector<T3> t;

rep(i, N - 1){

// 出発地点.

int sx = cxy[i].a;

int sy = cxy[i].b;

int sn = m[{sx, sy}];

// 到着地点.

int gx = cxy[i + 1].a;

int gy = cxy[i + 1].b;

int gn = m[{gx, gy}];

// コスト.

LL c = (LL)min(abs(sx - gx), abs(sy - gy));

// 保存.

t.emplace_back(c, sn, gn);

}

// 3-2. Y座標ソート版.

rep(i, N - 1){

// 出発地点.

int sx = cyx[i].a;

int sy = cyx[i].b;

int sn = m[{sy, sx}];

// 到着地点.

int gx = cyx[i + 1].a;

int gy = cyx[i + 1].b;

int gn = m[{gy, gx}];

// コスト.

LL c = (LL)min(abs(sx - gx), abs(sy - gy));

// 保存.

t.emplace_back(c, sn, gn);

}

// 4. sort.

sort(all(t));

// 5. 最小全域木(Kruskal's Algorithm) の構築.

// 競プロ典型 90 問 (049 - Flip Digits 2)

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

LL ans = 0;

UnionFind uf(2 * N);

rep(i, t.size()){

// グラフ情報.

int u = get<1>(t[i]);

int v = get<2>(t[i]);

LL c = get<0>(t[i]);

// 最小全域木を構成する辺の追加, コスト計算.

if(!uf.same(u, v)){

uf.unite(u, v);

ans += c;

}

// 6. 出力.

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

return 0;

}

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

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

[入力例]
6
8 3
4 9
12 19
18 1
13 5
7 6

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

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

[出力例]
3

[入力例]
7
26 21
10 5
13 1
10 15
21 8
13 31
31 21

[出力例]
11

[入力例]
15
77 61
109 11
70 122
56 31
60 78
39 105
119 36
27 111
50 94
61 80
89 36
65 51
122 117
92 63
70 98

[出力例]
53

[入力例]
33
535841 392830
886700 439965
980165 242002
378567 1221215
718227 1116388
934737 507531
1177697 811662
1025786 532997
49250 130344
265694 220194
303104 128236
1016944 846327
210484 186383
1177345 96975
696687 122028
844685 896757
406707 69786
179549 172311
982700 1013573
908740 937724
568591 807355
649431 707575
911233 87617
169621 162873
562404 419802
560962 400670
827597 836935
746791 45279
242558 344460
547802 479310
791097 1131673
573639 1094305
1228744 350660

[出力例]
480000

100

101

102

103

104

105

106

[入力例]

1 5

3 9

7 8

[出力例]

※AtCoderテストケースより

[入力例]

8 3

4 9

12 19

18 1

13 5

7 6

[出力例]

※AtCoderテストケースより

[入力例]

1 3

5 8

10 3

11 1

6 2

[出力例]

[入力例]

26 21

10 5

13 1

10 15

21 8

13 31

31 21

[出力例]

[入力例]

77 61

109 11

70 122

56 31

60 78

39 105

119 36

27 111

50 94

61 80

89 36

65 51

122 117

92 63

70 98

[出力例]

[入力例]

535841 392830

886700 439965

980165 242002

378567 1221215

718227 1116388

934737 507531

1177697 811662

1025786 532997

49250 130344

265694 220194

303104 128236

1016944 846327

210484 186383

1177345 96975

696687 122028

844685 896757

406707 69786

179549 172311

982700 1013573

908740 937724

568591 807355

649431 707575

911233 87617

169621 162873

562404 419802

560962 400670

827597 836935

746791 45279

242558 344460

547802 479310

791097 1131673

573639 1094305

1228744 350660

[出力例]

480000

■参照サイト
AtCoder Regular Contest 076
Union-Find木
 競プロ典型 90 問の問題049

2022年1月14日

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

C++の練習を兼ねて, AtCoder Beginner Contest 233 の問題F (Swap and Sort) を解いてみた.

■感想.
1. 問題Fは, グラフを使う方針で, 規則性を抽出できたので, AC版に到達できたと思う.
2. 実装に苦労したものの, Union-Find木, および, 幅優先探索の復習が出来たので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
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 a first
#define b second
#define all(x) x.begin(), x.end()

// 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, M;
    scanf("%d", &N);
    vi io(N); // 指定場所の数字.
    vi oi(N); // 数字の場所.
    rep(i, N){
        scanf("%d", &io[i]);
        io[i]--;
        oi[io[i]] = i;
    }
    scanf("%d", &M);
    
    // 2. グラフ作成.
    vvi G(N);
    UnionFind uf(N + 2);
    map<P, int> op;
    rep(i, M){
        int a, b;
        scanf("%d %d", &a, &b);
        a--;
        b--;
        
        // 各連結成分が, すべて木になるように調整.
        if(!uf.same(a, b)){
            // 辺を追加.
            uf.unite(a, b);
            G[a].pb(b);
            G[b].pb(a);
            
            // 操作番号保存.
            op[{a, b}] = i + 1;
        }
    }
    
    // 3. 並び替えできるか？
    bool ok = true;
    rep(i, N){
        if(i != io[i] && !uf.same(i, io[i])){
            ok = false;
            break;
        }
    }
    
    // 4. 例外.
    if(!ok){
        puts("-1");
        return 0;
    }
    
    // 5. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, int* d){
        // 空のキュー.
        queue<int> q;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 隣接頂点をチェック.
            for(auto &e : G[u]) if(!d[e] && e != s) d[e] = d[u] + 1, q.push(e);
        }
    };
    
    // 6. 二数の入れ替えに関する操作手順.
    // -> 最短経路を取得するロジックを流用.
    auto f = [&](vvi &G, int s, int* d) -> vp{
        // 利用経路.
        vp route;
        
        // 空のキュー.
        queue<int> q;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 取り出した要素を処理.
            for(auto &e : G[u]){
                // 距離 が 1 小さい場合に, 最短経路として保存.
                if(d[e] == d[u] - 1){
                    P p = {e, u};
                    if(p.a > p.b) swap(p.a, p.b);
                    route.pb(p);
                    q.push(e);
                    break;
                }
            }
        }
        
        // 往路・復路を考慮.
        vp ret = route;
        int rl = route.size();
        repr(i, rl - 2, 0) ret.pb(route[i]);
        
        // 返却.
        return ret;
    };
    
    // 7. 並び替え実行.
    vi z(N), ans;
    iota(all(z), 0);
    rep(i, N){
        // 終了条件.
        if(z == io) break;
        
        // 並び替え.
        if(i != io[i]){
            // 数字 i の 置いてある場所 を スタート地点としたときの最短距離.
            int d[N];
            rep(j, N) d[j] = 0;
            int s = oi[i]; // スタート地点.
            int g = i;     // ゴール地点.
            bfs(G, s, d);
            
            // 操作手順.
            vp route = f(G, g, d);
            
            // 二数を入れ替える.
            // 一時的に, 移動先の数字を保管.
            int j = io[i];
            
            // 数字 i を 移動.
            io[i] = i;
            
            // 数字 j を もともと i が 置いてあった位置 io[oi[i]] に 設定.
            io[oi[i]] = j;
            
            // 数字の場所を更新.
            oi[j] = oi[i];
            oi[i] = i;
            
            // 保存.
            for(auto &p : route) ans.pb(op[p]);
        }
    }
    
    // 8. 出力.
    int al = ans.size();
    assert(al <= 500000);
    printf("%d\n", al);
    rep(i, al){
        printf("%d", ans[i]);
        printf("%s", (i < al - 1) ? " " : "\n");
    }
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

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

#define b second

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

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

scanf("%d", &N);

vi io(N); // 指定場所の数字.

vi oi(N); // 数字の場所.

rep(i, N){

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

io[i]--;

oi[io[i]] = i;

}

scanf("%d", &M);

// 2. グラフ作成.

vvi G(N);

UnionFind uf(N + 2);

map<P, int> op;

rep(i, M){

int a, b;

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

a--;

b--;

// 各連結成分が, すべて木になるように調整.

if(!uf.same(a, b)){

// 辺を追加.

uf.unite(a, b);

G[a].pb(b);

G[b].pb(a);

// 操作番号保存.

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

}

// 3. 並び替えできるか？

bool ok = true;

rep(i, N){

if(i != io[i] && !uf.same(i, io[i])){

ok = false;

break;

}

// 4. 例外.

if(!ok){

puts("-1");

return 0;

}

// 5. bfs.

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

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

// 空のキュー.

queue<int> q;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

// 隣接頂点をチェック.

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

}

};

// 6. 二数の入れ替えに関する操作手順.

// -> 最短経路を取得するロジックを流用.

auto f = [&](vvi &G, int s, int* d) -> vp{

// 利用経路.

vp route;

// 空のキュー.

queue<int> q;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

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

// 距離が 1 小さい場合に, 最短経路として保存.

if(d[e] == d[u] - 1){

P p = {e, u};

if(p.a > p.b) swap(p.a, p.b);

route.pb(p);

q.push(e);

break;

}

// 往路・復路を考慮.

vp ret = route;

int rl = route.size();

repr(i, rl - 2, 0) ret.pb(route[i]);

// 返却.

return ret;

};

// 7. 並び替え実行.

vi z(N), ans;

iota(all(z), 0);

rep(i, N){

// 終了条件.

if(z == io) break;

// 並び替え.

if(i != io[i]){

// 数字 i の置いてある場所をスタート地点としたときの最短距離.

int d[N];

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

int s = oi[i]; // スタート地点.

int g = i; // ゴール地点.

bfs(G, s, d);

// 操作手順.

vp route = f(G, g, d);

// 二数を入れ替える.

// 一時的に, 移動先の数字を保管.

int j = io[i];

// 数字 i を移動.

io[i] = i;

// 数字 j をもともと i が置いてあった位置 io[oi[i]] に設定.

io[oi[i]] = j;

// 数字の場所を更新.

oi[j] = oi[i];

oi[i] = i;

// 保存.

for(auto &p : route) ans.pb(op[p]);

}

// 8. 出力.

int al = ans.size();

assert(al <= 500000);

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

rep(i, al){

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

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

}

return 0;

}

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

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

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

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

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

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

[出力例]
0

※AtCoderテストケースより

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

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

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

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

[入力例]

5 3 2 4 6 1

1 5

5 6

1 2

2 3

[出力例]

4 2 1

※AtCoderテストケースより

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

1 2 1 4 2

[入力例]

3 4 1 2 5

1 3

2 5

[出力例]

-1

※AtCoderテストケースより

[入力例]

1 2 3 4

1 2

1 3

1 4

2 3

2 4

3 4

[出力例]

※AtCoderテストケースより

[入力例]

5 4 7 1 3 2 6

1 2

2 4

1 3

3 4

4 6

2 5

2 7

[出力例]

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

[入力例]

8 5 2 10 4 7 1 6 3 9

1 2

1 3

1 7

6 7

6 8

2 5

3 4

3 6

4 9

4 5

5 10

9 10

[出力例]

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

■参照サイト
AtCoder Beginner Contest 233
Union-Find木

2022年1月13日2022年1月13日

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

C++の練習を兼ねて, AtCoder Beginner Contest 233 の問題E (Σ[k=0..10^100]floor(X／10^k)) を解いてみた.

■感想.
1. 問題Eは, 規則性を抽出できたので, AC版に到達できたと思う.
2. 個人的には, 文字列操作で, 数式の値を計算できる点が, 非常に面白いと感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

■C++版プログラム(問題E／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 pb push_back
#define all(x) x.begin(), x.end()
LL xCum[505050];

int main(){
    
    // 1. 入力情報.
    char X[505050];
    scanf("%s", X);
    int xl = strlen(X);
    
    // 2. 累積和.
    rep(i, xl) xCum[i + 1] = xCum[i] + (X[i] - '0');
    
    // 3. 数式計算.
    LL cur = 0;
    string ans, sCur;
    rep(i, xl){
        // cur(一の位) を 連結.
        cur += xCum[xl - i];
        sCur = to_string(cur);
        ans.pb(sCur.back());
        
        // cur更新.
        sCur.pop_back();
        cur = sCur.empty() ? 0 : stoll(sCur);
    }
    
    // 4. sCur の 残り部分.
    while(!sCur.empty()){
        ans.pb(sCur.back());
        sCur.pop_back();
    }
    
    // 5. 反転.
    reverse(all(ans));
    
    // 6. 出力.
    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--)

#define pb push_back

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

LL xCum[505050];

int main(){

// 1. 入力情報.

char X[505050];

scanf("%s", X);

int xl = strlen(X);

// 2. 累積和.

rep(i, xl) xCum[i + 1] = xCum[i] + (X[i] - '0');

// 3. 数式計算.

LL cur = 0;

string ans, sCur;

rep(i, xl){

// cur(一の位) を連結.

cur += xCum[xl - i];

sCur = to_string(cur);

ans.pb(sCur.back());

// cur更新.

sCur.pop_back();

cur = sCur.empty() ? 0 : stoll(sCur);

}

// 4. sCur の残り部分.

while(!sCur.empty()){

ans.pb(sCur.back());

sCur.pop_back();

}

// 5. 反転.

reverse(all(ans));

// 6. 出力.

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

return 0;

}

[入力例]
1225

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

[入力例]
99999

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

[入力例]
314159265358979323846264338327950288419716939937510

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

[入力例]
2022

[出力例]
2246

[入力例]
20220113

[出力例]
22466791

[入力例]
99999999999999999999999999999999999999999999999999

[出力例]
111111111111111111111111111111111111111111111111060

[入力例]
1414213562373095048801688724209698078569671875376948073176679737990732478462107038850387534327641572

[出力例]
1571348402636772276446320804677442309521857639307720081307421931100813864957896709833763927030712805

[入力例]
9465039690052544287964210336050825544228009679340871984835320413138656028459737281236623910738318475221197599613262364812464866655324755821221092211133037516274251841210630051432736133150976832522422811910498103749718745467191658641434790862939619763285208867362914075814532379135342728574115700744736237670180291229335790961022435254588241322299644479124403665543873560838123902436045250773389704122393280276096137717904710238337845435209435565053211109596812055736852625864819104366036314395508017917284938196552386978929495097296123356714573475388624043832849619380113505044143557656041303934449636641560423687119165574111093463814413079614034373343396851681468981704840409761380396202541959237702953945058736591307184716535752522570421388219253081124048134322102930668723327553258017981593648669365309578446323005570228846649186185670506105605174070813173766429797749090127411781445934740635316646127229912315074634805283767052428230698613659200015308575040330926336887197767402712076391971685069

[出力例]
10516710766725049208849122595612028382475566310378746649817022681265173364955263645818471011931464972467997332903624849791627629617027506468023435790147819462526946490234033390480817925723307591691580902122775670833020828296879620712705323181044021959205787630403237862016147087928158587304573000827484708522422545810373101067802705838431379246999604976804892961715415067597915447151161389748210782358214755862329041908783011375930939372454928405614679010663124506374280695405354560406707015995008908796983264662835985532143883441440137063016192750431804493147610688200126116715715064062268115482721818490622692985687961749012326070904903421793371525937107612979409979672044899734867106891713288041892171050065262879230205240595280580633801542465836756804497927024558811854137030614731131090659609632628121753829247783966920940721317984078340117339082300903526407144219721211252679757162149711817018495696922124794527372005870852280475811887348510222239231750044812140374319108630447457862657746316268

[入力例]

1225

[出力例]

1360

※AtCoderテストケースより

[入力例]

99999

[出力例]

111105

※AtCoderテストケースより

[入力例]

314159265358979323846264338327950288419716939937510

[出力例]

349065850398865915384738153697722542688574377708317

※AtCoderテストケースより

[入力例]

2022

[出力例]

2246

[入力例]

20220113

[出力例]

22466791

[入力例]

99999999999999999999999999999999999999999999999999

[出力例]

111111111111111111111111111111111111111111111111060

[入力例]

1414213562373095048801688724209698078569671875376948073176679737990732478462107038850387534327641572

[出力例]

1571348402636772276446320804677442309521857639307720081307421931100813864957896709833763927030712805

[入力例]

9465039690052544287964210336050825544228009679340871984835320413138656028459737281236623910738318475221197599613262364812464866655324755821221092211133037516274251841210630051432736133150976832522422811910498103749718745467191658641434790862939619763285208867362914075814532379135342728574115700744736237670180291229335790961022435254588241322299644479124403665543873560838123902436045250773389704122393280276096137717904710238337845435209435565053211109596812055736852625864819104366036314395508017917284938196552386978929495097296123356714573475388624043832849619380113505044143557656041303934449636641560423687119165574111093463814413079614034373343396851681468981704840409761380396202541959237702953945058736591307184716535752522570421388219253081124048134322102930668723327553258017981593648669365309578446323005570228846649186185670506105605174070813173766429797749090127411781445934740635316646127229912315074634805283767052428230698613659200015308575040330926336887197767402712076391971685069

[出力例]

10516710766725049208849122595612028382475566310378746649817022681265173364955263645818471011931464972467997332903624849791627629617027506468023435790147819462526946490234033390480817925723307591691580902122775670833020828296879620712705323181044021959205787630403237862016147087928158587304573000827484708522422545810373101067802705838431379246999604976804892961715415067597915447151161389748210782358214755862329041908783011375930939372454928405614679010663124506374280695405354560406707015995008908796983264662835985532143883441440137063016192750431804493147610688200126116715715064062268115482721818490622692985687961749012326070904903421793371525937107612979409979672044899734867106891713288041892171050065262879230205240595280580633801542465836756804497927024558811854137030614731131090659609632628121753829247783966920940721317984078340117339082300903526407144219721211252679757162149711817018495696922124794527372005870852280475811887348510222239231750044812140374319108630447457862657746316268

■参照サイト
AtCoder Beginner Contest 233

2022年1月12日

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

C++の練習を兼ねて, AtCoder Beginner Contest 233 の問題C (Product) ～問題D (Count Interval) を解いてみた.

■感想.
1. 問題Dは, 連想配列による実装を試みたが, AC版に届かなかったので, 解説を参考の上, 修正版にて, AC版に到達できた.
2. 問題Cで, 深さ優先探索の訓練を積めたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vl = vector<LL>;
using vvl = vector<vl>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back

int main(){
    
    // 1. 入力情報.
    int N;
    LL X;
    scanf("%d %lld", &N, &X);
    vvl bags;
    rep(i, N){
        int L;
        scanf("%d", &L);
        vl bag;
        rep(j, L){
            LL a;
            scanf("%lld", &a);
            bag.pb(a);
        }
        bags.pb(bag);
    }
    
    // 2. dfs.
    // https://ja.wikipedia.org/wiki/深さ優先探索
    auto dfs = [&](auto&& self, LL cX, int cDepth) -> int{
        // 2-1. 終了条件.
        if(cDepth == N) return (cX == 1);
        
        // 2-2. ボールの取り出し方を数える.
        int ret = 0;
        rep(i, bags[cDepth].size()){
            if(cX % bags[cDepth][i] == 0){
                LL nX = cX / bags[cDepth][i];
                ret += self(self, nX, cDepth + 1);
            }
        }
        
        // 2-3. 返却.
        return ret;
    };
    
    // 3. 出力.
    printf("%d\n", dfs(dfs, X, 0));
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vl = vector<LL>;

using vvl = vector<vl>;

#define repex(i, a, b, c) for(int i = a; i < b; i += c)

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

#define repr(i, a, b) for(int i = a; i >= b; i--)

#define pb push_back

int main(){

// 1. 入力情報.

int N;

LL X;

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

vvl bags;

rep(i, N){

int L;

scanf("%d", &L);

vl bag;

rep(j, L){

LL a;

scanf("%lld", &a);

bag.pb(a);

}

bags.pb(bag);

}

// 2. dfs.

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

auto dfs = [&](auto&& self, LL cX, int cDepth) -> int{

// 2-1. 終了条件.

if(cDepth == N) return (cX == 1);

// 2-2. ボールの取り出し方を数える.

int ret = 0;

rep(i, bags[cDepth].size()){

if(cX % bags[cDepth][i] == 0){

LL nX = cX / bags[cDepth][i];

ret += self(self, nX, cDepth + 1);

}

// 2-3. 返却.

return ret;

};

// 3. 出力.

printf("%d\n", dfs(dfs, X, 0));

return 0;

}

[入力例]
2 40
3 1 8 4
2 10 5

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

[入力例]
3 200
3 10 10 10
3 10 10 10
5 2 2 2 2 2

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

[入力例]
3 1000000000000000000
2 1000000000 1000000000
2 1000000000 1000000000
2 1000000000 1000000000

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

[入力例]
5 2020
5 2 5 10 20 40
11 1 2 4 5 10 15 20 40 50 101 202
3 1 10 202
8 1 2 2 5 8 10 10 20
12 1 1 2 2 5 5 7 10 12 20 101 202

[出力例]
73

[入力例]
7 20220112
5 1 2 4 8 16
3 1 2 4
2 1 877
3 1 8 131
5 1 2 4 8 16
3 1 1 11
7 1 2 4 11 16 131 877

[出力例]
79

[入力例]

2 40

3 1 8 4

2 10 5

[出力例]

※AtCoderテストケースより

[入力例]

3 200

3 10 10 10

5 2 2 2 2 2

[出力例]

※AtCoderテストケースより

[入力例]

3 1000000000000000000

2 1000000000 1000000000

[出力例]

※AtCoderテストケースより

[入力例]

5 2020

5 2 5 10 20 40

11 1 2 4 5 10 15 20 40 50 101 202

3 1 10 202

8 1 2 2 5 8 10 10 20

12 1 1 2 2 5 5 7 10 12 20 101 202

[出力例]

[入力例]

7 20220112

5 1 2 4 8 16

3 1 2 4

2 1 877

3 1 8 131

5 1 2 4 8 16

3 1 1 11

7 1 2 4 11 16 131 877

[出力例]

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

// 解き直し.
// https://atcoder.jp/contests/abc233/editorial/3163
// 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[202020], aCum[202020];

int main(){
    
    // 1. 入力情報.
    int N;
    LL K;
    scanf("%d %lld", &N, &K);
    rep(i, N) scanf("%lld", &a[i]);
    
    // 2. 累積和.
    rep(i, N) aCum[i + 1] = aCum[i] + a[i];
    
    // 3. 数え上げ(解説通り).
    LL ans = 0;
    map<LL, LL> m;
    repx(r, 1, N + 1){
        m[aCum[r - 1]]++;
        ans += m[aCum[r] - K];
    }
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc233/editorial/3163

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

int main(){

// 1. 入力情報.

int N;

LL K;

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

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

// 2. 累積和.

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

// 3. 数え上げ(解説通り).

LL ans = 0;

map<LL, LL> m;

repx(r, 1, N + 1){

m[aCum[r - 1]]++;

ans += m[aCum[r] - K];

}

// 4. 出力.

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

return 0;

}

[入力例]
6 5
8 -3 5 7 0 -4

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

[入力例]
2 -1000000000000000
1000000000 -1000000000

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

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

[出力例]
4

[入力例]
20 15
12 -21 10 14 -4 5 11 29 -6 7 -16 -10 0 14 11 -20 24 -10 1 26

[出力例]
8

[入力例]
50 123
84 3 -89 16 62 47 14 62 61 -32 24 70 29 30 -6 99 23 1 2 -18 21 90 -7 40 35 52 -4 89 -14 74 63 8 62 -84 8 109 -84 97 0 4 22 67 23 11 71 2 3 5 55 68

[出力例]
17

[入力例]

6 5

8 -3 5 7 0 -4

[出力例]

※AtCoderテストケースより

[入力例]

2 -1000000000000000

1000000000 -1000000000

[出力例]

※AtCoderテストケースより

[入力例]

12 7

0 1 -9 5 10 7 -3 2 3 -6 -11 12

[出力例]

[入力例]

20 15

12 -21 10 14 -4 5 11 29 -6 7 -16 -10 0 14 11 -20 24 -10 1 26

[出力例]

[入力例]

50 123

84 3 -89 16 62 47 14 62 61 -32 24 70 29 30 -6 99 23 1 2 -18 21 90 -7 40 35 52 -4 89 -14 74 63 8 62 -84 8 109 -84 97 0 4 22 67 23 11 71 2 3 5 55 68

[出力例]

■参照サイト
AtCoder Beginner Contest 233

2022年1月11日

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

C++の練習を兼ねて, 第九回アルゴリズム実技検定の問題L (嘘つきな生徒たち) を解いてみた.

■感想.
1. 問題Lは, LISを使う方針で実装してみたものの, ACに到達できず, 解説を参考に, 修正版にて, AC版に到達できた.
2. LIS(Longest increase subsequence) の応用版(広義単調増加列プラス追加条件) を, 確認することができたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト第九回アルゴリズム実技検定の各リンクをご覧下さい.

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

// 解き直し.
// https://atcoder.jp/contests/past202112-open/editorial/3070
// -> hand_01.txt などで, WA版となったため, 解き直しとした.
// 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
#define all(x) x.begin(), x.end()
int a[202020], b[202020];

int main(){
    
    // 1. 入力情報.
    int N, P;
    scanf("%d %d", &N, &P);
    rep(i, N) scanf("%d", &a[i]);
    
    // 2. 数列 B.
    rep(i, N) b[i] =  a[N - 1 - i] - i;
    
    // 3. "広義"単調増加な数列の長さの最大値は？
    // 以下の問題を参照, 改変.
    // https://atcoder.jp/contests/typical90/tasks/typical90_bh
    // -> LIS(Longest increase subsequence) を 利用.
    vi dp;
    rep(i, N){
        // 値が 0 以上 P - (N - 1)以下でない項は, 変更が必要(解説より).
        // 本問では, LIS の 計算過程で, 別途, 下記条件が, 必要なので注意.
        if(b[i] < 0 || b[i] > P - (N - 1)) continue;
        
        // それ以外.
        if(dp.size() == 0 || dp.back() <= b[i]){
            dp.pb(b[i]);
        }else{
            int at = upper_bound(all(dp), b[i]) - dp.begin();
            dp[at] = b[i];
        }
    }
    // rep(i, dp.size()) printf("%d\n", dp[i]);
    
    // 4. 出力.
    printf("%d\n", N - dp.size());
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/past202112-open/editorial/3070

// -> hand_01.txt などで, WA版となったため, 解き直しとした.

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

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

int a[202020], b[202020];

int main(){

// 1. 入力情報.

int N, P;

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

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

// 2. 数列 B.

rep(i, N) b[i] = a[N - 1 - i] - i;

// 3. "広義"単調増加な数列の長さの最大値は？

// 以下の問題を参照, 改変.

// https://atcoder.jp/contests/typical90/tasks/typical90_bh

// -> LIS(Longest increase subsequence) を利用.

vi dp;

rep(i, N){

// 値が 0 以上 P - (N - 1)以下でない項は, 変更が必要(解説より).

// 本問では, LIS の計算過程で, 別途, 下記条件が, 必要なので注意.

if(b[i] < 0 || b[i] > P - (N - 1)) continue;

// それ以外.

if(dp.size() == 0 || dp.back() <= b[i]){

dp.pb(b[i]);

}else{

int at = upper_bound(all(dp), b[i]) - dp.begin();

dp[at] = b[i];

}

// rep(i, dp.size()) printf("%d\n", dp[i]);

// 4. 出力.

printf("%d\n", N - dp.size());

return 0;

}

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

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

[入力例]
5 10
9 8 7 7 5

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

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

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

[入力例]
3 2
2 1 0

[出力例]
0

[入力例]
15 33
25 16 14 13 12 19 7 22 6 32 5 15 2 21 1

[出力例]
8

[入力例]
31 41
5 9 26 5 35 8 9 7 9 32 38 4 6 26 4 33 8 32 7 9 5 0 2 8 8 41 9 7 16 9 3

[出力例]
26

[入力例]
200 2020
1854 2020 1753 2019 1674 944 2017 1290 1123 2015 1392 1559 1569 2013 1017 1214 1258 2001 2000 1689 1561 1999 1667 1372 1998 1086 1140 1888 1255 1359 1850 1522 1223 1833 1645 1831 982 1799 1409 1219 1759 1357 1730 1024 1217 1700 1351 1699 1487 949 1659 1435 1650 1030 1606 1457 736 1580 809 1110 1560 866 1297 1550 950 971 1400 1185 1310 617 1221 1300 1053 1222 1158 1212 848 1200 610 1111 1100 1020 999 674 987 1017 980 608 774 970 853 1077 966 809 935 955 834 850 943 815 603 767 942 584 513 446 941 417 737 858 910 694 456 901 888 800 869 836 783 454 449 442 490 330 393 616 681 619 364 530 341 680 424 381 522 559 309 325 613 620 512 249 444 228 305 505 384 500 237 489 247 423 468 273 455 396 337 485 430 258 400 150 264 103 333 312 172 300 127 297 285 142 256 166 221 222 221 192 270 189 98 167 32 71 135 54 67 66 122 13 41 111 61 58 77 70 25 12 5 0

[出力例]
130

[入力例]
500 5050
5050 5049 5048 5047 5046 5045 5044 5043 5042 5041 4287 4147 3021 4341 1671 2034 4202 1787 1077 1787 5000 4999 4998 4997 4996 4995 4994 4993 4992 4991 2827 4990 4568 3815 4498 2679 1798 3529 1287 1122 4800 4799 4798 4797 4796 4795 4794 4793 4792 3992 3234 2468 1333 2364 4020 4376 4988 1832 3445 3052 4000 3999 3998 3997 3996 3995 3994 3993 3992 3991 1989 3990 1433 1400 1567 2967 4297 2893 3909 3770 3500 3499 3498 3497 3496 3495 3494 3493 3492 3491 2838 1761 1776 1125 2719 3355 1066 2470 3685 1125 3300 3299 3298 3297 3296 3295 3294 3293 3292 3291 3280 2207 3250 3232 2660 2604 2525 2021 3648 3000 2999 2998 2997 2996 2995 2994 2993 2992 2991 1983 1350 3797 1280 2643 2593 1177 1298 1411 2616 2500 2499 2498 2497 2496 2495 2494 2493 2492 2491 1918 1376 2689 3665 1218 3212 1481 3695 1034 2575 2300 2299 2298 2297 2296 2295 2294 2293 2292 2291 1650 1931 1012 1263 1756 1828 1327 1131 1373 1537 2000 1999 1998 1997 1996 1995 1994 1993 1992 1991 1468 1212 1143 1178 1486 1493 1599 1470 1497 1057 1900 1899 1898 1897 1896 1895 1894 1893 1892 1891 1926 1848 1043 1764 1028 1292 1451 1198 1844 1664 1700 1699 1698 1697 1696 1695 1694 1693 1692 1691 881 1328 547 646 1324 1118 1422 947 1374 1466 1500 1499 1498 1497 1496 1495 1494 1493 1492 1491 733 872 1111 1211 562 1022 653 726 806 1455 1300 1299 1298 1297 1296 1295 1294 1293 1292 1291 730 1498 695 1469 1177 1364 1065 1372 731 580 1200 1199 1198 1197 1196 1195 1194 1193 1192 1191 1190 1189 1188 1187 1186 1185 1184 1183 1182 1181 1180 1179 808 1242 1036 1147 1174 797 1255 1222 1147 708 1225 1433 1384 500 1313 1200 1003 1002 1001 1000 999 998 997 996 995 994 993 992 991 990 989 988 987 986 985 984 983 982 981 980 979 978 977 976 975 974 973 972 971 824 858 881 858 846 887 825 824 857 820 878 838 829 888 838 840 856 827 831 800 799 798 797 796 795 794 793 792 791 790 789 788 787 786 785 784 783 782 781 780 779 778 777 776 775 774 773 772 771 746 769 703 790 738 729 757 782 701 776 777 734 753 787 786 791 797 783 741 765 700 725 709 708 741 780 761 709 799 714 600 599 598 597 596 595 594 593 592 591 590 589 588 587 586 585 584 583 582 581 580 555 500 548 571 563 566 506 599 550 506 502 570 588 510 594 507 555 537 511 300 299 298 297 296 295 294 293 292 291 238 225 207 288 254 287 212 226 214 226 200 190 180 150 140 100 90 50 30 20 1

[出力例]
200

[入力例]

5 10

7 5 10 3 2

[出力例]

※AtCoderのテストケースより

[入力例]

5 10

9 8 7 7 5

[出力例]

※AtCoderのテストケースより

[入力例]

11 1000000000

0 1 10 100 1000 10000 100000 1000000 10000000 100000000 1000000000

[出力例]

※AtCoderのテストケースより

[入力例]

3 2

2 1 0

[出力例]

[入力例]

15 33

25 16 14 13 12 19 7 22 6 32 5 15 2 21 1

[出力例]

[入力例]

31 41

5 9 26 5 35 8 9 7 9 32 38 4 6 26 4 33 8 32 7 9 5 0 2 8 8 41 9 7 16 9 3

[出力例]

[入力例]

200 2020

1854 2020 1753 2019 1674 944 2017 1290 1123 2015 1392 1559 1569 2013 1017 1214 1258 2001 2000 1689 1561 1999 1667 1372 1998 1086 1140 1888 1255 1359 1850 1522 1223 1833 1645 1831 982 1799 1409 1219 1759 1357 1730 1024 1217 1700 1351 1699 1487 949 1659 1435 1650 1030 1606 1457 736 1580 809 1110 1560 866 1297 1550 950 971 1400 1185 1310 617 1221 1300 1053 1222 1158 1212 848 1200 610 1111 1100 1020 999 674 987 1017 980 608 774 970 853 1077 966 809 935 955 834 850 943 815 603 767 942 584 513 446 941 417 737 858 910 694 456 901 888 800 869 836 783 454 449 442 490 330 393 616 681 619 364 530 341 680 424 381 522 559 309 325 613 620 512 249 444 228 305 505 384 500 237 489 247 423 468 273 455 396 337 485 430 258 400 150 264 103 333 312 172 300 127 297 285 142 256 166 221 222 221 192 270 189 98 167 32 71 135 54 67 66 122 13 41 111 61 58 77 70 25 12 5 0

[出力例]

130

[入力例]

500 5050

5050 5049 5048 5047 5046 5045 5044 5043 5042 5041 4287 4147 3021 4341 1671 2034 4202 1787 1077 1787 5000 4999 4998 4997 4996 4995 4994 4993 4992 4991 2827 4990 4568 3815 4498 2679 1798 3529 1287 1122 4800 4799 4798 4797 4796 4795 4794 4793 4792 3992 3234 2468 1333 2364 4020 4376 4988 1832 3445 3052 4000 3999 3998 3997 3996 3995 3994 3993 3992 3991 1989 3990 1433 1400 1567 2967 4297 2893 3909 3770 3500 3499 3498 3497 3496 3495 3494 3493 3492 3491 2838 1761 1776 1125 2719 3355 1066 2470 3685 1125 3300 3299 3298 3297 3296 3295 3294 3293 3292 3291 3280 2207 3250 3232 2660 2604 2525 2021 3648 3000 2999 2998 2997 2996 2995 2994 2993 2992 2991 1983 1350 3797 1280 2643 2593 1177 1298 1411 2616 2500 2499 2498 2497 2496 2495 2494 2493 2492 2491 1918 1376 2689 3665 1218 3212 1481 3695 1034 2575 2300 2299 2298 2297 2296 2295 2294 2293 2292 2291 1650 1931 1012 1263 1756 1828 1327 1131 1373 1537 2000 1999 1998 1997 1996 1995 1994 1993 1992 1991 1468 1212 1143 1178 1486 1493 1599 1470 1497 1057 1900 1899 1898 1897 1896 1895 1894 1893 1892 1891 1926 1848 1043 1764 1028 1292 1451 1198 1844 1664 1700 1699 1698 1697 1696 1695 1694 1693 1692 1691 881 1328 547 646 1324 1118 1422 947 1374 1466 1500 1499 1498 1497 1496 1495 1494 1493 1492 1491 733 872 1111 1211 562 1022 653 726 806 1455 1300 1299 1298 1297 1296 1295 1294 1293 1292 1291 730 1498 695 1469 1177 1364 1065 1372 731 580 1200 1199 1198 1197 1196 1195 1194 1193 1192 1191 1190 1189 1188 1187 1186 1185 1184 1183 1182 1181 1180 1179 808 1242 1036 1147 1174 797 1255 1222 1147 708 1225 1433 1384 500 1313 1200 1003 1002 1001 1000 999 998 997 996 995 994 993 992 991 990 989 988 987 986 985 984 983 982 981 980 979 978 977 976 975 974 973 972 971 824 858 881 858 846 887 825 824 857 820 878 838 829 888 838 840 856 827 831 800 799 798 797 796 795 794 793 792 791 790 789 788 787 786 785 784 783 782 781 780 779 778 777 776 775 774 773 772 771 746 769 703 790 738 729 757 782 701 776 777 734 753 787 786 791 797 783 741 765 700 725 709 708 741 780 761 709 799 714 600 599 598 597 596 595 594 593 592 591 590 589 588 587 586 585 584 583 582 581 580 555 500 548 571 563 566 506 599 550 506 502 570 588 510 594 507 555 537 511 300 299 298 297 296 295 294 293 292 291 238 225 207 288 254 287 212 226 214 226 200 190 180 150 140 100 90 50 30 20 1

[出力例]

200

■参照サイト
第九回アルゴリズム実技検定

2022年1月10日2022年1月10日

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

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

■感想.
1. 問題Eは, 規則性を見つけることが出来たので, AC版に到達できたと思う.
2. 等差数を, 抽出してところ, 意外と少なく(ここでは, 339個だった), 非常に面白い問題と感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vl = vector<LL>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define all(x) x.begin(), x.end()

int main(){
    
    // 1. 入力情報.
    LL X;
    scanf("%lld", &X);
    
    // 2. 等差数作成.
    vl aNumber;
    rep(i, 9) aNumber.pb(i + 1);
    repx(k, 2, 19){
        // 等差数が, k桁だったと仮定.
        // -> 初項 s, 公差 t で, k項 の 等差数列 が 存在するか？
        repx(s, 1, 10){
            repx(t, -9, 10){
                // 初項.
                string seq;
                seq.pb(s + '0');
                
                // 残りの項.
                int d = s;
                bool ok = true;
                rep(i, k - 1){
                    d += t;
                    if(d < 0 || d > 9){
                        ok = false;
                        break;
                    }
                    seq.pb(d + '0');
                }
                
                // 保存.
                if(ok) aNumber.pb(stoll(seq));
            }
        }
    }
    // for(auto &p : aNumber) printf("%lld\n", p);
    
    // 3. sort.
    sort(all(aNumber));
    
    // 4. 位置検索.
    int at = lower_bound(all(aNumber), X) - aNumber.begin();
    
    // 5. 出力.
    printf("%lld\n", aNumber[at]);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vl = vector<LL>;

#define repex(i, a, b, c) for(int i = a; i < b; i += c)

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

#define repr(i, a, b) for(int i = a; i >= b; i--)

#define pb push_back

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

int main(){

// 1. 入力情報.

LL X;

scanf("%lld", &X);

// 2. 等差数作成.

vl aNumber;

rep(i, 9) aNumber.pb(i + 1);

repx(k, 2, 19){

// 等差数が, k桁だったと仮定.

// -> 初項 s, 公差 t で, k項の等差数列が存在するか？

repx(s, 1, 10){

repx(t, -9, 10){

// 初項.

string seq;

seq.pb(s + '0');

// 残りの項.

int d = s;

bool ok = true;

rep(i, k - 1){

d += t;

if(d < 0 || d > 9){

ok = false;

break;

}

seq.pb(d + '0');

}

// 保存.

if(ok) aNumber.pb(stoll(seq));

}

// for(auto &p : aNumber) printf("%lld\n", p);

// 3. sort.

sort(all(aNumber));

// 4. 位置検索.

int at = lower_bound(all(aNumber), X) - aNumber.begin();

// 5. 出力.

printf("%lld\n", aNumber[at]);

return 0;

}

[入力例]
152

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

[入力例]
88

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

[入力例]
8989898989

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

[入力例]
51

[出力例]
51

[入力例]
100

[出力例]
111

[入力例]
112

[出力例]
123

[入力例]
964

[出力例]
975

[入力例]
1248

[出力例]
1357

[入力例]
1234

[出力例]
1234

[入力例]
3141

[出力例]
3210

[入力例]
12321

[出力例]
12345

[入力例]
526718

[出力例]
543210

[入力例]
20220110

[出力例]
22222222

[入力例]
53536007464846939

[出力例]
55555555555555555

[入力例]
100000000000000000

[出力例]
111111111111111111

[入力例]

152

[出力例]

159

※AtCoderテストケースより

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

8989898989

[出力例]

9876543210

※AtCoderテストケースより

[入力例]

[出力例]

[入力例]

100

[出力例]

111

[入力例]

112

[出力例]

123

[入力例]

964

[出力例]

975

[入力例]

1248

[出力例]

1357

[入力例]

1234

[出力例]

1234

[入力例]

3141

[出力例]

3210

[入力例]

12321

[出力例]

12345

[入力例]

526718

[出力例]

543210

[入力例]

20220110

[出力例]

22222222

[入力例]

53536007464846939

[出力例]

55555555555555555

[入力例]

100000000000000000

[出力例]

111111111111111111

■参照サイト
AtCoder Beginner Contest 234

2022年1月10日

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

C++の練習を兼ねて, AtCoder Beginner Contest 234 の問題C (Happy New Year!) ～問題D (Prefix K-th Max) を解いてみた.

■感想.
1. 問題C, Dは, 規則性を見つけることが出来たので, AC版に到達できたと思う.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

int main(){
    
    // 1. 入力情報.
    LL K;
    scanf("%lld", &K);
    
    // 2. K番目に小さい正整数.
    auto f = [](LL n) -> string{
        // 返却用.
        string ret;
        
        // K番目に小さい正整数は？
        while(n){
            ret.pb((n % 2) ? '2' : '0');
            n >>= 1;
        }
        
        // 反転.
        reverse(all(ret));
        
        // 返却.
        return ret;
    };
    
    // 3. 出力.
    printf("%s\n", f(K).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--)

#define pb push_back

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

int main(){

// 1. 入力情報.

LL K;

scanf("%lld", &K);

// 2. K番目に小さい正整数.

auto f = [](LL n) -> string{

// 返却用.

string ret;

// K番目に小さい正整数は？

while(n){

ret.pb((n % 2) ? '2' : '0');

n >>= 1;

}

// 反転.

reverse(all(ret));

// 返却.

return ret;

};

// 3. 出力.

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

return 0;

}

[入力例]
3

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

[入力例]
11

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

[入力例]
923423423420220108

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

[入力例]
1

[出力例]
2

[入力例]
2022

[出力例]
22222200220

[入力例]
20220110

[出力例]
2002202002000200022002220

[入力例]
314159265358979323

[出力例]
20002022200000222200020222222220220200222202020000022222022

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

2022

※AtCoderテストケースより

[入力例]

923423423420220108

[出力例]

220022020000202020002022022000002020002222002200002022002200

※AtCoderテストケースより

[入力例]

[出力例]

[入力例]

2022

[出力例]

22222200220

[入力例]

20220110

[出力例]

2002202002000200022002220

[入力例]

314159265358979323

[出力例]

20002022200000222200020222222220220200222202020000022222022

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using PQD = priority_queue<int>;
using PQA = priority_queue<int, vector<int>, greater<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--)

int main(){
    
    // 1. 入力情報.
    int N, K;
    scanf("%d %d", &N, &K);
    
    // 2. K番目に大きい値は？
    PQA pqa; // 大きい方から, K番目までの要素.
    PQD pqd; // 残りの要素.
    rep(i, N){
        int p;
        scanf("%d", &p);
        
        // K番目まで.
        if(i < K) pqa.push(p);
        
        // K番目よりも後.
        if(i >= K){
            // 比較対象の要素.
            pqd.push(p);
            int l = pqa.top();
            int r = pqd.top();
            
            // 入れ替え.
            if(l < r){
                pqa.pop();
                pqd.pop();
                pqd.push(l);
                pqa.push(r);
            }
        }
        
        // K番目以降.
        if(i >= K - 1) printf("%d\n", pqa.top());
    }
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using PQD = priority_queue<int>;

using PQA = priority_queue<int, vector<int>, greater<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--)

int main(){

// 1. 入力情報.

int N, K;

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

// 2. K番目に大きい値は？

PQA pqa; // 大きい方から, K番目までの要素.

PQD pqd; // 残りの要素.

rep(i, N){

int p;

scanf("%d", &p);

// K番目まで.

if(i < K) pqa.push(p);

// K番目よりも後.

if(i >= K){

// 比較対象の要素.

pqd.push(p);

int l = pqa.top();

int r = pqd.top();

// 入れ替え.

if(l < r){

pqa.pop();

pqd.pop();

pqd.push(l);

pqa.push(r);

}

// K番目以降.

if(i >= K - 1) printf("%d\n", pqa.top());

}

return 0;

}

[入力例]
3 2
1 2 3

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

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

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

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

[出力例]
1
2
3

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

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

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

[出力例]
6
7
8
8
9
10
10
11
12
12
13
13
14
15
15
16

[入力例]

3 2

1 2 3

[出力例]

※AtCoderテストケースより

[入力例]

11 5

3 7 2 5 11 6 1 9 8 10 4

[出力例]

※AtCoderテストケースより

[入力例]

5 3

1 2 3 4 5

[出力例]

[入力例]

10 3

7 3 2 1 9 4 5 6 10 8

[出力例]

[入力例]

20 5

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

[出力例]

■参照サイト
AtCoder Beginner Contest 234

2022年1月9日

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

C++の練習を兼ねて, AtCoder Regular Contest 093 の問題E (Bichrome Spanning Tree) を解いてみた.

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に, AC版に到達できた.
2. 最小全域木(Kruskal’s Algorithm) の復習が出来たので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/arc093/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vs = vector<set<int>>;
using T3 = tuple<LL, 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 all(x) x.begin(), x.end()
const LL MOD = 1e9 + 7;
LL w[2020], mPow2[2020];
int u[2020], v[2020];

// 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, M;
    LL X;
    scanf("%d %d %lld", &N, &M, &X);
    map<P, LL> m;
    rep(i, M){
        scanf("%d %d %lld", &u[i], &v[i], &w[i]);
        u[i]--;
        v[i]--;
        m[{u[i], v[i]}] = w[i];
        m[{v[i], u[i]}] = w[i];
    }
    
    // 2. sort.
    vector<T3> t;
    rep(i, M) t.emplace_back(w[i], u[i], v[i]);
    sort(all(t));
    
    // 3. 最小全域木(Kruskal's Algorithm).
    // 競プロ典型 90 問 (049 - Flip Digits 2)
    // https://github.com/E869120/kyopro_educational_90/blob/main/sol/049.cpp
    LL S = 0;
    vs T(N);
    UnionFind uf(N + 2);
    rep(i, t.size()){
        int a = get<1>(t[i]);
        int b = get<2>(t[i]);
        LL c = get<0>(t[i]);
        if(!uf.same(a, b)){
            uf.unite(a, b);
            T[a].insert(b);
            T[b].insert(a);
            S += c;
        }
    }
    
    // 4. D.
    LL D = X - S;
    
    // 5. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vs &G, int s, int* d){
        // 空のキュー.
        queue<int> q;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 隣接頂点をチェック.
            for(auto &e : G[u]) if(!d[e] && e != s) d[e] = d[u] + 1, q.push(e);
        }
    };
    
    // 6. 最短経路上 の 辺の重み の 最大値.
    auto f = [&](vs &G, int g, int* d) -> LL{
        // 返却用.
        LL ret = 0;
        
        // 空のキュー.
        queue<int> q;
        
        // 探索地点 g をキュー q に追加.
        q.push(g);
        while(!q.empty()){
            // キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 隣接頂点をチェック.
            for(auto &e : G[u]){
                if(d[e] == d[u] - 1){
                    // 距離が 1 小さい頂点を追加.
                    q.push(e);
                    
                    // 最短経路を構成する辺とみて, 辺の重みの最大値 を 更新.
                    ret = max(ret, m[{u, e}]);
                }
            }
        }
        
        // 返却.
        return ret;
    };
    
    // 7. D との 比較.
    // -> グラフ G に含まれるが, グラフ T に 含まれない 辺 のみ 計算.
    int eLower = 0, eEqual = 0, eUpper = 0;
    rep(i, M){
        // グラフ T に 含まれる辺か？
        if(T[u[i]].count(v[i])) continue;
        
        // 最短距離.
        int d[1010];
        rep(j, 1010) d[j] = 0;
        bfs(T, u[i], d);
        
        // グラフ T 上で, pathMax 計算.
        LL pathMax = f(T, v[i], d);
        
        // diff の 値 に応じて, カウント.
        LL diff = w[i] - pathMax;
        if(diff < D)  eLower++;
        if(diff == D) eEqual++;
        if(diff > D)  eUpper++;
    }
    
    // 8. 2 の 冪乗.
    mPow2[0] = 1;
    repx(i, 1, 2020){
        mPow2[i] = mPow2[i - 1] << 1;
        mPow2[i] %= MOD;
    }
    
    // 9. 塗り方の個数.
    LL ans = 1;
    
    // 9-1. D < 0.
    if(D < 0) ans = 0;
    
    // 9-2. D == 0.
    if(D == 0){
        // T の 辺 に 2種類の色 を 両方用いる場合.
        LL t1 = 1;
        t1 *= (mPow2[N - 1] - 2);
        t1 %= MOD;
        t1 *= mPow2[M - N + 1];
        t1 %= MOD;
        
        // それ以外.
        LL t2 = 1;
        t2 *= 2;
        t2 %= MOD;
        t2 *= (mPow2[eEqual] - 1);
        t2 %= MOD;
        t2 *= mPow2[eUpper];
        t2 %= MOD;
        
        // 合計.
        ans = t1 + t2;
        ans %= MOD;
    }
    
    // 9-3. D > 0.
    if(D > 0){
        ans *= 2;
        ans %= MOD;
        ans *= (mPow2[eEqual] - 1);
        ans %= MOD;
        ans *= mPow2[eUpper];
        ans %= MOD;
    }
    
    // 10. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

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

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using P = pair<int, int>;

using vi = vector<int>;

using vs = vector<set<int>>;

using T3 = tuple<LL, 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 all(x) x.begin(), x.end()

const LL MOD = 1e9 + 7;

LL w[2020], mPow2[2020];

int u[2020], v[2020];

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

LL X;

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

map<P, LL> m;

rep(i, M){

scanf("%d %d %lld", &u[i], &v[i], &w[i]);

u[i]--;

v[i]--;

m[{u[i], v[i]}] = w[i];

m[{v[i], u[i]}] = w[i];

}

// 2. sort.

vector<T3> t;

rep(i, M) t.emplace_back(w[i], u[i], v[i]);

sort(all(t));

// 3. 最小全域木(Kruskal's Algorithm).

// 競プロ典型 90 問 (049 - Flip Digits 2)

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

LL S = 0;

vs T(N);

UnionFind uf(N + 2);

rep(i, t.size()){

int a = get<1>(t[i]);

int b = get<2>(t[i]);

LL c = get<0>(t[i]);

if(!uf.same(a, b)){

uf.unite(a, b);

T[a].insert(b);

T[b].insert(a);

S += c;

}

// 4. D.

LL D = X - S;

// 5. bfs.

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

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

// 空のキュー.

queue<int> q;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

// 隣接頂点をチェック.

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

}

};

// 6. 最短経路上の辺の重みの最大値.

auto f = [&](vs &G, int g, int* d) -> LL{

// 返却用.

LL ret = 0;

// 空のキュー.

queue<int> q;

// 探索地点 g をキュー q に追加.

q.push(g);

while(!q.empty()){

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

int u = q.front();

q.pop();

// 隣接頂点をチェック.

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

if(d[e] == d[u] - 1){

// 距離が 1 小さい頂点を追加.

q.push(e);

// 最短経路を構成する辺とみて, 辺の重みの最大値を更新.

ret = max(ret, m[{u, e}]);

}

// 返却.

return ret;

};

// 7. D との比較.

// -> グラフ G に含まれるが, グラフ T に含まれない辺のみ計算.

int eLower = 0, eEqual = 0, eUpper = 0;

rep(i, M){

// グラフ T に含まれる辺か？

if(T[u[i]].count(v[i])) continue;

// 最短距離.

int d[1010];

rep(j, 1010) d[j] = 0;

bfs(T, u[i], d);

// グラフ T 上で, pathMax 計算.

LL pathMax = f(T, v[i], d);

// diff の値に応じて, カウント.

LL diff = w[i] - pathMax;

if(diff < D) eLower++;

if(diff == D) eEqual++;

if(diff > D) eUpper++;

}

// 8. 2 の冪乗.

mPow2[0] = 1;

repx(i, 1, 2020){

mPow2[i] = mPow2[i - 1] << 1;

mPow2[i] %= MOD;

}

// 9. 塗り方の個数.

LL ans = 1;

// 9-1. D < 0.

if(D < 0) ans = 0;

// 9-2. D == 0.

if(D == 0){

// T の辺に 2種類の色を両方用いる場合.

LL t1 = 1;

t1 *= (mPow2[N - 1] - 2);

t1 %= MOD;

t1 *= mPow2[M - N + 1];

t1 %= MOD;

// それ以外.

LL t2 = 1;

t2 *= 2;

t2 %= MOD;

t2 *= (mPow2[eEqual] - 1);

t2 %= MOD;

t2 *= mPow2[eUpper];

t2 %= MOD;

// 合計.

ans = t1 + t2;

ans %= MOD;

}

// 9-3. D > 0.

if(D > 0){

ans *= 2;

ans %= MOD;

ans *= (mPow2[eEqual] - 1);

ans %= MOD;

ans *= mPow2[eUpper];

ans %= MOD;

}

// 10. 出力.

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

return 0;

}

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

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

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

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

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

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

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

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

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

[出力例]
8

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

[出力例]
56

[入力例]

3 3

1 2 1

2 3 1

3 1 1

[出力例]

※AtCoderテストケースより

[入力例]

3 3

1 2 1

2 3 1

3 1 2

[出力例]

※AtCoderテストケースより

[入力例]

5 4

1 2 3

1 3 3

2 4 6

2 5 8

[出力例]

※AtCoderテストケースより

[入力例]

8 10

4 6 10

8 4 11

5 8 9

1 8 10

3 8 128773450

7 8 10

4 2 4

3 4 1

3 1 13

5 2 2

[出力例]

※AtCoderテストケースより

[入力例]

7 9

1 2 2

2 3 3

1 7 3

4 1 4

7 4 5

3 4 2

6 3 3

6 5 6

5 4 1

[出力例]

[入力例]

15 22

1 3 5

3 2 11

4 3 8

1 4 6

1 5 2

5 4 9

5 10 7

10 9 8

9 8 11

8 7 5

7 4 1

4 6 7

2 6 15

15 6 7

15 12 10

6 7 3

7 12 8

12 13 3

12 11 2

13 14 4

11 14 1

11 8 6

[出力例]

■参照サイト
AtCoder Regular Contest 093
Union-Find木
 競プロ典型 90 問の問題049

カテゴリー: C++

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

C++の練習を兼ねて, 第七回アルゴリズム実技検定の問題H (折れ線グラフ) を解いてみた.

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

C++の練習を兼ねて, 第七回アルゴリズム実技検定の問題G (べき表現) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 076 の問題D (Built?) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 233 の問題F (Swap and Sort) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 233 の問題E (Σ[k=0..10^100]floor(X／10^k)) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 233 の問題C (Product) ～問題D (Count Interval) を解いてみた.

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

C++の練習を兼ねて, 第九回アルゴリズム実技検定の問題L (嘘つきな生徒たち) を解いてみた.

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

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

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

C++の練習を兼ねて, AtCoder Beginner Contest 234 の問題C (Happy New Year!) ～問題D (Prefix K-th Max) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 093 の問題E (Bichrome Spanning Tree) を解いてみた.

C++の練習を兼ねて, 第七回 アルゴリズム実技検定 の 問題H (折れ線グラフ) を解いてみた.

C++の練習を兼ねて, 第七回 アルゴリズム実技検定 の 問題G (べき表現) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 076 の 問題D (Built?) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 233 の 問題F (Swap and Sort) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 233 の 問題E (Σ[k=0..10^100]floor(X／10^k)) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 233 の 問題C (Product) ～ 問題D (Count Interval) を解いてみた.

C++の練習を兼ねて, 第九回 アルゴリズム実技検定 の 問題L (嘘つきな生徒たち) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 234 の 問題C (Happy New Year!) ～ 問題D (Prefix K-th Max) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 093 の 問題E (Bichrome Spanning Tree) を解いてみた.

C++の練習を兼ねて, 第七回アルゴリズム実技検定の問題H (折れ線グラフ) を解いてみた.

C++の練習を兼ねて, 第七回アルゴリズム実技検定の問題G (べき表現) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 076 の問題D (Built?) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 233 の問題F (Swap and Sort) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 233 の問題E (Σ[k=0..10^100]floor(X／10^k)) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 233 の問題C (Product) ～問題D (Count Interval) を解いてみた.

C++の練習を兼ねて, 第九回アルゴリズム実技検定の問題L (嘘つきな生徒たち) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 234 の問題C (Happy New Year!) ～問題D (Prefix K-th Max) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 093 の問題E (Bichrome Spanning Tree) を解いてみた.