個人用メモ帳

2022年1月22日

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

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

■感想.
1. 問題Fは, 実装方針を絞り込めたので, AC版に到達出来たと思う.
2. Binary Indexed Tree の復習が出来たので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 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 a first
#define b second
#define pb push_back
#define all(x) x.begin(), x.end()

// Binary Indexed Tree (Fenwick Tree)
// https://youtu.be/lyHk98daDJo?t=7960
template<typename T>
struct BIT{
    int n;
    vector<T> d;
    BIT(int n = 0) : n(n), d(n + 1) {}
    void add(int i, T x = 1){
        for(i++; i <= n; i += i & -i) d[i] += x;
    }
    T sum(int i){
        T x = 0;
        for(i++; i; i -= i & -i) x += d[i];
        return x;
    }
    T sum(int l, int r){
        return sum(r - 1) - sum(l - 1);
    }
};

struct joy{
   int a, b;
   bool operator < (const joy &J) const{ 
       return (a > J.a) || (a == J.a && b < J.b); 
   }
};

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vi A(N), B(N);
    map<int, int> m;
    rep(i, N) scanf("%d", &A[i]);
    rep(i, N){
        scanf("%d", &B[i]);
        m[B[i]] = 1;
    }
    
    // 2. 同一要素の出現を考慮する必要がある？
    map<P, int> mo;
    rep(i, N) mo[{A[i], B[i]}]++;
    LL ans = 0;
    for(auto &p : mo) ans += (LL)(p.b - 1) * (LL)p.b / 2;
    
    // 3. 座標圧縮(青木君の嬉しさ).
    int idx = 0;
    for(auto &p : m) p.b = ++idx;
    
    // 4. 累積和.
    vi bCum(idx + 1);
    rep(i, N) bCum[m[B[i]]]++;
    rep(i, idx) bCum[i + 1] += bCum[i];
    
    // 5. sort;
    vector<joy> v;
    rep(i, N) v.emplace_back(joy{A[i], B[i]});
    sort(all(v));
    
    // 6. 集計(i番目以降の青木君の嬉しさが, i番目の青木君の嬉しさ以上のものをカウントしたい).
    BIT<int> ft(idx + 1);
    rep(i, N){
        // 青木君 の 嬉しさ(BIT の 加算位置).
        int j = m[v[i].b];
        
        // 今回までで, 嬉しさ j以上 が, 何回出現したか？
        // -> 区間[j, idx + 1) の 合計は？
        int bCount = ft.sum(j, idx + 1);
        
        // 嬉しさ j以上 の 出現回数合計.
        int cCount = bCum[idx] - bCum[j - 1];
        
        // 次回以降で, j以上の嬉しさが, 何回出現できるか？
        ans += (LL)(cCount - bCount);
        
        // 出現回数 として 加算.
        ft.add(j, 1);
    }
    
    // 7. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

100

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

#define b second

#define pb push_back

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

// Binary Indexed Tree (Fenwick Tree)

// https://youtu.be/lyHk98daDJo?t=7960

template<typename T>

struct BIT{

int n;

vector<T> d;

BIT(int n = 0) : n(n), d(n + 1) {}

void add(int i, T x = 1){

for(i++; i <= n; i += i & -i) d[i] += x;

}

T sum(int i){

T x = 0;

for(i++; i; i -= i & -i) x += d[i];

return x;

}

T sum(int l, int r){

return sum(r - 1) - sum(l - 1);

}

};

struct joy{

int a, b;

bool operator < (const joy &J) const{

return (a > J.a) || (a == J.a && b < J.b);

}

};

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vi A(N), B(N);

map<int, int> m;

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

rep(i, N){

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

m[B[i]] = 1;

}

// 2. 同一要素の出現を考慮する必要がある？

map<P, int> mo;

rep(i, N) mo[{A[i], B[i]}]++;

LL ans = 0;

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

// 3. 座標圧縮(青木君の嬉しさ).

int idx = 0;

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

// 4. 累積和.

vi bCum(idx + 1);

rep(i, N) bCum[m[B[i]]]++;

rep(i, idx) bCum[i + 1] += bCum[i];

// 5. sort;

vector<joy> v;

rep(i, N) v.emplace_back(joy{A[i], B[i]});

sort(all(v));

// 6. 集計(i番目以降の青木君の嬉しさが, i番目の青木君の嬉しさ以上のものをカウントしたい).

BIT<int> ft(idx + 1);

rep(i, N){

// 青木君の嬉しさ(BIT の加算位置).

int j = m[v[i].b];

// 今回までで, 嬉しさ j以上が, 何回出現したか？

// -> 区間[j, idx + 1) の合計は？

int bCount = ft.sum(j, idx + 1);

// 嬉しさ j以上の出現回数合計.

int cCount = bCum[idx] - bCum[j - 1];

// 次回以降で, j以上の嬉しさが, 何回出現できるか？

ans += (LL)(cCount - bCount);

// 出現回数として加算.

ft.add(j, 1);

}

// 7. 出力.

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

return 0;

}

[入力例]
3
50 100 150
1 3 2

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

[入力例]
3
123456789 123456 123
987 987654 987654321

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

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

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

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

[出力例]
10

[入力例]
25
1 83 57 35 11 80 87 64 91 89 2 7 56 64 7 10 83 11 2 7 64 45 64 83 55
8 97 61 39 11 85 34 21 72 88 2 7 34 21 7 15 50 11 2 7 16 61 21 97 65

[出力例]
99

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

[出力例]
2500

[入力例]

50 100 150

1 3 2

[出力例]

※AtCoderテストケースより

[入力例]

123456789 123456 123

987 987654 987654321

[出力例]

※AtCoderテストケースより

[入力例]

3 1 4 1 5 9 2 6 5 3

2 7 1 8 2 8 1 8 2 8

[出力例]

※AtCoderテストケースより

[入力例]

5 9 7 3 7

0 6 1 2 1

[出力例]

[入力例]

1 83 57 35 11 80 87 64 91 89 2 7 56 64 7 10 83 11 2 7 64 45 64 83 55

8 97 61 39 11 85 34 21 72 88 2 7 34 21 7 15 50 11 2 7 16 61 21 97 65

[出力例]

[入力例]

100

54 15 84 28 42 95 87 62 81 6 44 70 58 65 92 11 10 92 40 20 33 62 64 18 64 3 15 93 52 93 71 72 27 23 79 25 9 15 55 94 0 97 46 56 20 51 24 77 4 37 55 57 90 48 53 25 74 7 76 45 60 90 30 42 84 87 25 23 0 48 62 5 88 34 77 81 17 60 88 5 15 65 13 71 45 0 15 71 63 79 2 38 76 53 91 94 18 22 36 89

56 34 20 1 66 99 72 87 78 39 83 97 26 48 88 41 49 56 24 11 87 26 63 62 65 99 19 13 99 12 34 13 37 24 53 91 3 18 15 18 62 73 56 63 46 97 62 97 66 77 90 24 19 62 25 50 24 12 49 14 33 94 79 47 78 86 3 95 16 3 99 77 18 62 22 16 60 92 49 63 53 37 19 88 28 36 26 92 54 4 12 19 30 52 19 76 98 96 27 71

[出力例]

2500

■参照サイト
パナソニックプログラミングコンテスト2021(AtCoder Beginner Contest 231)
Binary Indexed Tree (Fenwick Tree)

2022年1月22日

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

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

■感想.
1. 問題Eは, 解説を参考に, 実装を試行錯誤してみたものの, 実装方針が確定できず, 解説プログラムベースで, AC版としている.
2. メモ化再帰の復習が出来たので, 非常に良かったと思う.
但し, メモ化再帰の本質が理解出来てないので, 今後の課題だと思われる.
3. 方針が見えなかった原因として, 現在見ている硬貨だけでなく, 次回分の硬貨も見る必要がある部分, および, 現在見ている硬貨で割った余りがゼロの場合は, 再帰処理が, 一本化される部分が, 該当すると思われる.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解答不能.
// https://atcoder.jp/contests/abc231/submissions/27854173
// 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--)

int main(){
    
    // 1. 入力情報.
    int N;
    LL X;
    scanf("%d %lld", &N, &X);
    vl a(N);
    rep(i, N) scanf("%lld", &a[i]);
    
    // 2. dfs(解説通り).
    // https://ja.wikipedia.org/wiki/深さ優先探索
    // -> 正しく動作しないので, 解説プログラムを参考に, 以下のロジックに修正.
    map<LL, LL> m;
    auto dfs = [&](auto self, LL curX, int d) -> LL{
        // 2-1. 終了条件.
        if(m.count(curX)) return m[curX];
        if(d == N - 1)    return curX / a[N - 1];
        
        // 2-2. 端数処理.
        // -> 現在分, 次回分 の 数列 A の要素を考える必要があるらしい.
        LL curA = a[d];
        LL nexA = a[d + 1];
        LL rL = curX % nexA / curA;
        LL rR = nexA / curA - rL;
        
        // 2-3. 次回の支払い対象金額.
        LL nexXL = curX / nexA * nexA;
        LL nexXR = nexXL;
        if(curX % nexA) nexXR += nexA;
        
        // 2-4. 次へ.
        LL ret = rL + self(self, nexXL, d + 1);
        if(rL) ret = min(ret, rR + self(self, nexXR, d + 1));
        
        // 2-5. 返却.
        return m[curX] = ret;
    };
    
    // 3. 出力.
    printf("%lld\n", dfs(dfs, X, 0));
    return 0;
    
}

// 解答不能.

// https://atcoder.jp/contests/abc231/submissions/27854173

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

int main(){

// 1. 入力情報.

int N;

LL X;

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

vl a(N);

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

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

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

// -> 正しく動作しないので, 解説プログラムを参考に, 以下のロジックに修正.

map<LL, LL> m;

auto dfs = [&](auto self, LL curX, int d) -> LL{

// 2-1. 終了条件.

if(m.count(curX)) return m[curX];

if(d == N - 1) return curX / a[N - 1];

// 2-2. 端数処理.

// -> 現在分, 次回分の数列 A の要素を考える必要があるらしい.

LL curA = a[d];

LL nexA = a[d + 1];

LL rL = curX % nexA / curA;

LL rR = nexA / curA - rL;

// 2-3. 次回の支払い対象金額.

LL nexXL = curX / nexA * nexA;

LL nexXR = nexXL;

if(curX % nexA) nexXR += nexA;

// 2-4. 次へ.

LL ret = rL + self(self, nexXL, d + 1);

if(rL) ret = min(ret, rR + self(self, nexXR, d + 1));

// 2-5. 返却.

return m[curX] = ret;

};

// 3. 出力.

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

return 0;

}

[入力例]
3 87
1 10 100

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

[入力例]
2 49
1 7

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

[入力例]
10 123456789012345678
1 100 10000 1000000 100000000 10000000000 1000000000000 100000000000000 10000000000000000 1000000000000000000

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

[入力例]
4 234
1 5 50 250

[出力例]
5

[入力例]
11 3141592653
1 3 27 405 1215 8505 144585 1012095 17205615 326906685 3595973535

[出力例]
29

[入力例]
16 202112112100
1 3 15 45 225 1575 7875 23625 259875 5197500 36382500 254677500 2801452500 47624692500 142874077500 1571614852500

[出力例]
30

[入力例]

3 87

1 10 100

[出力例]

※AtCoderテストケースより

[入力例]

2 49

1 7

[出力例]

※AtCoderテストケースより

[入力例]

10 123456789012345678

1 100 10000 1000000 100000000 10000000000 1000000000000 100000000000000 10000000000000000 1000000000000000000

[出力例]

233

※AtCoderテストケースより

[入力例]

4 234

1 5 50 250

[出力例]

[入力例]

11 3141592653

1 3 27 405 1215 8505 144585 1012095 17205615 326906685 3595973535

[出力例]

[入力例]

16 202112112100

1 3 15 45 225 1575 7875 23625 259875 5197500 36382500 254677500 2801452500 47624692500 142874077500 1571614852500

[出力例]

■参照サイト
パナソニックプログラミングコンテスト2021(AtCoder Beginner Contest 231)

2022年1月21日

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

C++の練習を兼ねて, 第三回アルゴリズム実技検定の問題G (グリッド金移動) を解いてみた.

■感想.
1. 問題Gは, 方針を絞り込むことが出来たので, AC版に到達できたと思う.
2. 過去問(第九回アルゴリズム実技検定 F – 将棋のように) に似ている問題に見えたため, 実装を一部流用している.
3. 幅優先探索(応用版, 移動可能方向の構築)の復習が出来たので, 非常に良かったと思う.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
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 a first
#define b second
#define pb push_back
const int D1 = 505;
const int D2 = 250;
int board[(D1 + 1) * (D1 + 1)];

int main(){
    
    // 1. 入力情報.
    int N, X, Y;
    scanf("%d %d %d", &N, &X, &Y);
    X += D2;
    Y += D2;
    rep(i, N){
        int x, y;
        scanf("%d %d", &x, &y);
        x += D2;
        y += D2;
        board[D1 * x + y] = 1;
    }
    
    // 2. 移動可能な方向は？
    // 過去問参照(第九回 アルゴリズム実技検定 F - 将棋のように)
    // https://atcoder.jp/contests/past202112-open/tasks/past202112_f
    vp dir;
    dir.pb({1, 1});
    dir.pb({0, 1});
    dir.pb({-1, 1});
    dir.pb({1, 0});
    dir.pb({-1, 0});
    dir.pb({0, -1});
    
    // 3. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](int s, int H, int W, int* d) -> void{
        // 空のキュー.
        queue<int> q;
        
        // 訪問済みフラグ設定.
        d[s] = 0;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // キューから取り出す.
            int v = q.front();
            q.pop();
            
            // 取り出した要素を処理.
            // x: 列方向, y: 行方向 で考える.
            int nx, ny, n;
            int cx = v % W , cy = v / W;
            for(auto &p : dir){
                // 移動先.
                nx = cx + p.b;
                ny = cy + p.a;
                n = nx + ny * W;
                
                // 訪問不可能なマス であれば, 処理をスキップ.
                if(nx < 0 || nx >= W || ny < 0 || ny >= H || board[n]) continue;
                
                // 移動先のマスで, 訪問可能 かつ 未訪問 であれば, 最短距離を設定.
                if(d[n] == -1) d[n] = d[v] + 1, q.push(n);
            }
        }
    };
    int d[D1 * D1];
    rep(i, D1 * D1) d[i] = -1;
    bfs(D1 * D2 + D2, D1, D1, d);
    
    // 4. 出力.
    printf("%d\n", d[D1 * X + Y]);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

#define b second

#define pb push_back

const int D1 = 505;

const int D2 = 250;

int board[(D1 + 1) * (D1 + 1)];

int main(){

// 1. 入力情報.

int N, X, Y;

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

X += D2;

Y += D2;

rep(i, N){

int x, y;

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

x += D2;

y += D2;

board[D1 * x + y] = 1;

}

// 2. 移動可能な方向は？

// 過去問参照(第九回アルゴリズム実技検定 F - 将棋のように)

// https://atcoder.jp/contests/past202112-open/tasks/past202112_f

vp dir;

dir.pb({1, 1});

dir.pb({0, 1});

dir.pb({-1, 1});

dir.pb({1, 0});

dir.pb({-1, 0});

dir.pb({0, -1});

// 3. bfs.

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

auto bfs = [&](int s, int H, int W, int* d) -> void{

// 空のキュー.

queue<int> q;

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

d[s] = 0;

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

q.push(s);

while(!q.empty()){

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

int v = q.front();

q.pop();

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

// x: 列方向, y: 行方向で考える.

int nx, ny, n;

int cx = v % W , cy = v / W;

for(auto &p : dir){

// 移動先.

nx = cx + p.b;

ny = cy + p.a;

n = nx + ny * W;

// 訪問不可能なマスであれば, 処理をスキップ.

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

// 移動先のマスで, 訪問可能かつ未訪問であれば, 最短距離を設定.

if(d[n] == -1) d[n] = d[v] + 1, q.push(n);

}

};

int d[D1 * D1];

rep(i, D1 * D1) d[i] = -1;

bfs(D1 * D2 + D2, D1, D1, d);

// 4. 出力.

printf("%d\n", d[D1 * X + Y]);

return 0;

}

[入力例]
1 2 2
1 1

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

[入力例]
1 2 2
2 1

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

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

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

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

[出力例]
5

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

[出力例]
11

[入力例]

1 2 2

1 1

[出力例]

※AtCoderテストケースより

[入力例]

1 2 2

2 1

[出力例]

※AtCoderテストケースより

[入力例]

5 -2 3

1 1

-1 1

0 1

-2 1

-3 1

[出力例]

※AtCoderテストケースより

[入力例]

7 4 4

4 1

4 3

1 1

1 5

2 1

2 2

3 3

[出力例]

[入力例]

22 10 3

3 1

6 1

8 1

2 2

3 2

7 2

9 2

2 3

5 3

6 3

7 3

9 3

4 4

7 4

9 4

1 5

3 5

7 5

10 5

6 6

8 6

6 7

[出力例]

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

2022年1月19日

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

C++の練習を兼ねて, AtCoder Beginner Contest 235 の問題C (Counting 2) ～問題D (Neighbors) を解いてみた.

■感想.
1. 問題C, Dは, 方針を絞ることが出来たので, AC版に到達できたと思う.
2. UnionFind木の復習が出来たので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 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 main(){
    
    // 1. 入力情報.
    int N, Q;
    scanf("%d %d", &N, &Q);
    vi a(N);
    rep(i, N) scanf("%d", &a[i]);
    
    // 2. sort.
    sort(all(a));
    
    // 3. クエリ回答.
    rep(i, Q){
        int x;
        scanf("%d", &x);
        int ans = N - (lower_bound(all(a), x) - a.begin());
        printf("%d\n", ans);
    }
    return 0;
    
}

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

// 1. 入力情報.

int N, Q;

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

vi a(N);

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

// 2. sort.

sort(all(a));

// 3. クエリ回答.

rep(i, Q){

int x;

scanf("%d", &x);

int ans = N - (lower_bound(all(a), x) - a.begin());

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

}

return 0;

}

[入力例]
3 1
100 160 130
120

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

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

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

[入力例]
5 5
804289384 846930887 681692778 714636916 957747794
424238336
719885387
649760493
596516650
189641422

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

[入力例]
10 5
112 20 72 91 60 54 58 5 66 39
97
20
113
80
3

[出力例]
1
9
0
2
10

[入力例]

3 1

100 160 130

120

[出力例]

※AtCoderテストケースより

[入力例]

5 5

1 2 3 4 5

[出力例]

※AtCoderテストケースより

[入力例]

5 5

804289384 846930887 681692778 714636916 957747794

424238336

719885387

649760493

596516650

189641422

[出力例]

※AtCoderテストケースより

[入力例]

10 5

112 20 72 91 60 54 58 5 66 39

113

[出力例]

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

// 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 %d", &N, &M);
    
    // 2. 人 A, B が 隣り合うように出来るか？
    // -> 一列に並べる必要があることに注意.
    vvi G(N);
    UnionFind uf(N + 2);
    bool ok = true;
    rep(i, M){
        int a, b;
        scanf("%d %d", &a, &b);
        a--;
        b--;
        G[a].pb(b);
        G[b].pb(a);
        
        // 次数チェック.
        if(G[a].size() > 2 || G[b].size() > 2) ok = false;
        
        // 閉路チェック.
        // -> 閉路があると, 横一列に並べることが出来なくなる.
        if(!uf.same(a, b)) uf.unite(a, b);
        else               ok = false;
    }
    
    // 3. 出力.
    printf("%s\n", ok ? "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

// 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 %d", &N, &M);

// 2. 人 A, B が隣り合うように出来るか？

// -> 一列に並べる必要があることに注意.

vvi G(N);

UnionFind uf(N + 2);

bool ok = true;

rep(i, M){

int a, b;

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

a--;

b--;

G[a].pb(b);

G[b].pb(a);

// 次数チェック.

if(G[a].size() > 2 || G[b].size() > 2) ok = false;

// 閉路チェック.

// -> 閉路があると, 横一列に並べることが出来なくなる.

if(!uf.same(a, b)) uf.unite(a, b);

else ok = false;

}

// 3. 出力.

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

return 0;

}

[入力例]
4 2
1 3
2 3

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

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

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

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

[出力例]
Yes

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

[出力例]
No

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

[出力例]
No

[入力例]

4 2

1 3

2 3

[出力例]

Yes

※AtCoderテストケースより

[入力例]

4 3

1 4

2 4

3 4

[出力例]

※AtCoderテストケースより

[入力例]

10 5

6 7

1 2

1 10

2 6

3 5

[出力例]

Yes

[入力例]

10 7

5 8

4 5

1 4

1 7

7 9

1 6

2 3

[出力例]

[入力例]

10 10

1 10

1 2

2 3

3 4

4 5

5 6

6 7

7 8

8 9

9 10

[出力例]

■参照サイト
パナソニックプログラミングコンテスト2021(AtCoder Beginner Contest 231)
Union-Find木

2022年1月18日

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

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

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

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

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

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

// 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, Q;
    scanf("%d %d %d", &N, &M, &Q);
    vector<T4> t;
    rep(i, M + Q){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        a--, b--;
        t.emplace_back(c, a, b, (i < M) ? 0 : (i - M + 1));
    }
    
    // 2. sort.
    sort(all(t));
    
    // 3. 最小全域木(Kruskal's Algorithm) の 構築.
    // 競プロ典型 90 問 (049 - Flip Digits 2)
    // https://github.com/E869120/kyopro_educational_90/blob/main/sol/049.cpp
    int ans[Q];
    rep(i, Q) ans[i] = 0;
    UnionFind uf(N + 2);
    rep(i, t.size()){
        // 3-1. グラフ情報.
        int u = get<1>(t[i]); // 頂点.
        int v = get<2>(t[i]); // 頂点.
        int q = get<3>(t[i]); // グラフG(0) or クエリ番号(1, 2, ...).
        
        // 3-2. 最小全域木を構成する辺の追加.
        // -> 但し, クエリ情報の場合は, 辺は追加しない.
        if(!uf.same(u, v)){
            if(q) ans[q - 1] = 1;
            else  uf.unite(u, v);
        }
    }
    
    // 4. 出力.
    rep(i, Q) printf("%s\n", ans[i] ? "Yes" : "No");
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using T4 = tuple<int, int, 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()

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

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

vector<T4> t;

rep(i, M + Q){

int a, b, c;

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

a--, b--;

t.emplace_back(c, a, b, (i < M) ? 0 : (i - M + 1));

}

// 2. sort.

sort(all(t));

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

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

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

int ans[Q];

rep(i, Q) ans[i] = 0;

UnionFind uf(N + 2);

rep(i, t.size()){

// 3-1. グラフ情報.

int u = get<1>(t[i]); // 頂点.

int v = get<2>(t[i]); // 頂点.

int q = get<3>(t[i]); // グラフG(0) or クエリ番号(1, 2, ...).

// 3-2. 最小全域木を構成する辺の追加.

// -> 但し, クエリ情報の場合は, 辺は追加しない.

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

if(q) ans[q - 1] = 1;

else uf.unite(u, v);

}

// 4. 出力.

rep(i, Q) printf("%s\n", ans[i] ? "Yes" : "No");

return 0;

}

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

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

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

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

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

[出力例]
Yes
No
No
No
Yes
Yes

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

[出力例]
Yes
Yes
No
No
No
Yes
No
Yes
No
Yes

[入力例]

5 6 3

1 2 2

2 3 3

1 3 6

2 4 5

4 5 9

3 5 8

1 3 1

3 4 7

3 5 7

[出力例]

Yes

※AtCoderテストケースより

[入力例]

2 3 2

1 2 100

1 2 1000000000

1 1 1

1 2 2

1 1 5

[出力例]

Yes

※AtCoderテストケースより

[入力例]

6 12 6

1 2 7

1 4 3

6 1 5

6 1 2

1 1 8

2 5 12

2 3 5

6 5 10

5 4 6

5 4 11

4 3 13

3 2 5

1 3 5

2 4 20

3 5 7

4 6 18

5 1 3

1 2 3

[出力例]

Yes

[入力例]

10 15 10

1 2 8

9 1 2

9 6 6

2 6 1

1 5 5

2 3 2

5 3 3

5 7 11

5 10 12

7 10 8

7 4 7

3 4 1

4 8 4

3 8 10

8 10 5

1 3 5

5 4 2

7 8 17

9 6 12

3 5 6

5 9 4

6 8 7

9 8 3

1 7 10

7 2 6

[出力例]

Yes

■参照サイト
HHKB プログラミングコンテスト 2022（AtCoder Beginner Contest 235）
Union-Find木
 競プロ典型 90 問の問題049

2022年1月18日

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

C++の練習を兼ねて, AtCoder Beginner Contest 235 の問題D (Multiply and Rotate) を解いてみた.

■感想.
1. 問題Dは, とりあえず実装したものの, AC版に到達できず, 解説プログラムを参考に, 修正版で, AC版に到達できたと思う.
2. 幅優先探索(応用版, グラフの頂点数削減)の復習が出来たので, 非常に良かったと思う.
3. 実装に苦労した箇所は, プログラム上に記載した T1 ～ T4 になるが, 個人的には, 落とし穴が, たくさんある印象を受けた.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc235/editorial/3255
// 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 pob pop_back
#define pub push_back
#define all(x) x.begin(), x.end()

int main(){
    
    // 1. 入力情報.
    int a, N;
    scanf("%d %d", &a, &N);
    
    // 2. 10 の 冪乗.
    int M = 1;
    while(M <= N) M *= 10;
    
    // 3. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](int s, int* d){
        // 空のキュー.
        queue<int> q;
        
        // 距離を設定.
        d[s] = 0;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // キューから取り出す.
            LL cx = (LL)q.front();
            q.pop();
            
            // Nの桁数 プラス 1 以上になった場合, Skip.
            if(cx >= M) continue;
            
            // x を 消して, x * a を 書き込む.
            LL nx1 = cx * a;
            if(nx1 < M && d[(int)nx1] == -1){
                d[(int)nx1] = d[cx] + 1;
                q.push((int)nx1);
            }
            
            // x を 文字列と見做して, 末尾を先頭に移動.
            if(cx >= 10 && cx % 10 != 0){
                string sx = to_string(cx), snx;
                snx.pub(sx.back());
                sx.pob();
                reverse(all(sx));
                while(!sx.empty()){
                    snx.pub(sx.back());
                    sx.pob();
                }
                if(!snx.empty()){
                    LL nx2 = stoll(snx);
                    if(nx2 < M && d[(int)nx2] == -1){
                        d[(int)nx2] = d[cx] + 1;
                        q.push((int)nx2);
                    }
                }
            }
        }
    };
    // [課題]
    // T1. 01_a_eq_2_00.txt などで, TLE版 となったため, ロジック修正が必要.
    // -> 解説プログラムを参考に, map<LL, int> を 廃止し, 配列を使用する形に修正(OK).
    // T2. Runtime Error となる件に対応するため, 配列サイズを, かなり大きめに設定(OK).
    // T3. 03_random_00.txt などの Runtime Error を 防止するため, long long型 を 部分的 に 廃止(OK).
    // -> ex. d[(int)nx1] == -1 の ような実装に修正.
    // T4. bfs の 判定を, nx1 <= M, nx2 <= M から nx1 < M, nx2 < M に 修正(OK).
    int d[M * 10 + 1];
    rep(i, M * 10 + 1) d[i] = -1;
    bfs(1, d);
    
    // 4. 出力.
    printf("%d\n", d[N]);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc235/editorial/3255

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

#define pub push_back

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

int main(){

// 1. 入力情報.

int a, N;

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

// 2. 10 の冪乗.

int M = 1;

while(M <= N) M *= 10;

// 3. bfs.

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

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

// 空のキュー.

queue<int> q;

// 距離を設定.

d[s] = 0;

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

q.push(s);

while(!q.empty()){

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

LL cx = (LL)q.front();

q.pop();

// Nの桁数プラス 1 以上になった場合, Skip.

if(cx >= M) continue;

// x を消して, x * a を書き込む.

LL nx1 = cx * a;

if(nx1 < M && d[(int)nx1] == -1){

d[(int)nx1] = d[cx] + 1;

q.push((int)nx1);

}

// x を文字列と見做して, 末尾を先頭に移動.

if(cx >= 10 && cx % 10 != 0){

string sx = to_string(cx), snx;

snx.pub(sx.back());

sx.pob();

reverse(all(sx));

while(!sx.empty()){

snx.pub(sx.back());

sx.pob();

}

if(!snx.empty()){

LL nx2 = stoll(snx);

if(nx2 < M && d[(int)nx2] == -1){

d[(int)nx2] = d[cx] + 1;

q.push((int)nx2);

}

};

// [課題]

// T1. 01_a_eq_2_00.txt などで, TLE版となったため, ロジック修正が必要.

// -> 解説プログラムを参考に, map<LL, int> を廃止し, 配列を使用する形に修正(OK).

// T2. Runtime Error となる件に対応するため, 配列サイズを, かなり大きめに設定(OK).

// T3. 03_random_00.txt などの Runtime Error を防止するため, long long型を部分的に廃止(OK).

// -> ex. d[(int)nx1] == -1 のような実装に修正.

// T4. bfs の判定を, nx1 <= M, nx2 <= M から nx1 < M, nx2 < M に修正(OK).

int d[M * 10 + 1];

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

bfs(1, d);

// 4. 出力.

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

return 0;

}

[入力例]
3 72

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

[入力例]
2 5

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

[入力例]
2 611

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

[入力例]
2 767090

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

[入力例]
10 1000000

[出力例]
6

[入力例]
7 826630

[出力例]
11

[入力例]
5 320000

[出力例]
8

[入力例]
2 162578

[出力例]
17

[入力例]
3 768690

[出力例]
19

[入力例]
2 522086

[出力例]
19

[入力例]

3 72

[出力例]

※AtCoderテストケースより

[入力例]

2 5

[出力例]

-1

※AtCoderテストケースより

[入力例]

2 611

[出力例]

※AtCoderテストケースより

[入力例]

2 767090

[出力例]

111

※AtCoderテストケースより

[入力例]

10 1000000

[出力例]

[入力例]

7 826630

[出力例]

[入力例]

5 320000

[出力例]

[入力例]

2 162578

[出力例]

[入力例]

3 768690

[出力例]

[入力例]

2 522086

[出力例]

■参照サイト
HHKB プログラミングコンテスト 2022（AtCoder Beginner Contest 235）

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日

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

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

■感想.
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木

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

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

C++の練習を兼ねて, 第三回 アルゴリズム実技検定 の 問題G (グリッド金移動) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 235 の 問題C (Counting 2) ～ 問題D (Neighbors) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 235 の 問題D (Multiply and Rotate) を解いてみた.

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

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

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

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

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

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

C++の練習を兼ねて, 第三回アルゴリズム実技検定の問題G (グリッド金移動) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 235 の問題C (Counting 2) ～問題D (Neighbors) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 235 の問題D (Multiply and Rotate) を解いてみた.

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

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

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

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