個人用メモ帳

2023年8月27日

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

C++の練習を兼ねて, AtCoder Grand Contest 049 の問題A (Erasing Vertices) ～問題B (Flip Digits) を解いてみた.

■感想.
1. 問題A, Bは, 方針が見えなかったので, 解説を参考に, AC版に到達できた.
2. 問題A で, 幅優先探索の訓練を積めたので, 非常に良かったと思う.
3. 個人的には, 問題A, B のいずれも, 解説のロジックが, 非常に不思議な印象を受けた.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/agc049/editorial/281
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vvi G(N);
    rep(i, N){
        char c[101];
        scanf("%s", c);
        rep(j, N) if(c[j] == '1') G[i].pb(j); // 有向辺.
    }
    
    // 2. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, int* d){
        // 空のキュー.
        queue<int> q;
        
        // 距離ゼロを設定.
        d[s] = 0;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 隣接頂点をチェック.
            for(auto &v : G[u]) if(d[v] == -1 && v != s) d[v] = d[u] + 1, q.push(v);
        }
    };
    
    // 3. S[v] の 計算(解説通り).
    vvi S(N);
    rep(i, N){
        // 頂点 i から, 到達可能な頂点は？
        int d[N];
        rep(j, N) d[j] = -1;
        bfs(G, i, d);
        
        // S[v] に 保存.
        rep(v, N) if(d[v] != -1) S[v].pb(i);
    }
    
    // 4. 集計.
    double ans = 0.0;
    rep(v, N) ans += 1.0 / (double)S[v].size();
    
    // 5. 出力.
    printf("%.12lf\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/agc049/editorial/281

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

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

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

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

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

#define pb push_back

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vvi G(N);

rep(i, N){

char c[101];

scanf("%s", c);

rep(j, N) if(c[j] == '1') G[i].pb(j); // 有向辺.

}

// 2. bfs.

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

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

// 空のキュー.

queue<int> q;

// 距離ゼロを設定.

d[s] = 0;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

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

}

};

// 3. S[v] の計算(解説通り).

vvi S(N);

rep(i, N){

// 頂点 i から, 到達可能な頂点は？

int d[N];

rep(j, N) d[j] = -1;

bfs(G, i, d);

// S[v] に保存.

rep(v, N) if(d[v] != -1) S[v].pb(i);

}

// 4. 集計.

double ans = 0.0;

rep(v, N) ans += 1.0 / (double)S[v].size();

// 5. 出力.

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

return 0;

}

[入力例]
3
010
001
010

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

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

[入力例]
3
000
000
000

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

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

[入力例]
3
011
101
110

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

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

[入力例]
4
0100
0010
0001
0100

[出力例]
1.750000000000

[入力例]
5
01001
00100
00010
01000
00000

[出力例]
2.250000000000

[入力例]
10
0100000100
0010010000
0001000001
0000100000
0000000000
0000001000
0000000000
0000000010
0000000000
0000000000

[出力例]
3.950000000000

[入力例]
15
010000000010000
000000000000000
000100000000100
000010000000010
000000000100001
000000000000100
000000000010001
000000000000000
000000010000000
000001000000000
000010000000000
000100000000000
000000000000010
010000000000000
110000000000000

[出力例]
5.795609945610

[入力例]

010

001

010

[出力例]

1.66666666666666666667

※AtCoderのテストケースより

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

1.666666666667

[入力例]

000

[出力例]

3.00000000000000000000

※AtCoderのテストケースより

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

3.000000000000

[入力例]

011

101

110

[出力例]

1.00000000000000000000

※AtCoderのテストケースより

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

1.000000000000

[入力例]

0100

0010

0001

0100

[出力例]

1.750000000000

[入力例]

01001

00100

00010

01000

00000

[出力例]

2.250000000000

[入力例]

0100000100

0010010000

0001000001

0000100000

0000000000

0000001000

0000000000

0000000010

0000000000

[出力例]

3.950000000000

[入力例]

010000000010000

000000000000000

000100000000100

000010000000010

000000000100001

000000000000100

000000000010001

000000000000000

000000010000000

000001000000000

000010000000000

000100000000000

000000000000010

010000000000000

110000000000000

[出力例]

5.795609945610

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

// 解き直し.
// https://atcoder.jp/contests/agc049/editorial/330
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
int sXorCum[505050], tXorCum[505050], cur[2];

int main(){
    
    // 1. 入力情報.
    int N;
    char s[505050], t[505050];
    scanf("%d %s %s", &N, s, t);
    
    // 2. 累積XOR.
    rep(i, N){
        sXorCum[i + 1] = sXorCum[i] ^ (s[i] == '1');
        tXorCum[i + 1] = tXorCum[i] ^ (t[i] == '1');
    }
    
    // 3. 操作(解説通り).
    int k = -1, jMax = -1;
    LL ans = 0;
    bool ok = true;
    repx(i, 1, N + 1){
        // すでに, tXorCum と sXorCum が 一致しているときは, Skip.
        if(cur[tXorCum[i]] >= i) continue;
        
        // 探索開始位置(今回分).
        k = max(jMax, i);
        
        // 探索済みにも関わらず, tXorCum と sXorCum が 一致しない場合は, NG.
        if(k == N + 1) ok = false;
        
        // tXorCum の i番目 と sXorCum の j番目 が 等しくなるものは？
        repx(j, k, N + 1){
            // 探索開始位置(次回分).
            jMax = max(jMax, j + 1);
            
            // 見つかった.
            if(tXorCum[i] == sXorCum[j]){
                // 集計.
                ans += (j - i);
                
                // 操作履歴保存.
                cur[tXorCum[i]] = j;
                cur[!tXorCum[i]] = -1;
                
                // 次へ.
                break;
            }
            
            // 見つからなかった.
            if(jMax == N + 1) ok = false;
        }
    }
    
    // 4. 出力.
    printf("%lld\n", ok ? ans : -1);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/agc049/editorial/330

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

int sXorCum[505050], tXorCum[505050], cur[2];

int main(){

// 1. 入力情報.

int N;

char s[505050], t[505050];

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

// 2. 累積XOR.

rep(i, N){

sXorCum[i + 1] = sXorCum[i] ^ (s[i] == '1');

tXorCum[i + 1] = tXorCum[i] ^ (t[i] == '1');

}

// 3. 操作(解説通り).

int k = -1, jMax = -1;

LL ans = 0;

bool ok = true;

repx(i, 1, N + 1){

// すでに, tXorCum と sXorCum が一致しているときは, Skip.

if(cur[tXorCum[i]] >= i) continue;

// 探索開始位置(今回分).

k = max(jMax, i);

// 探索済みにも関わらず, tXorCum と sXorCum が一致しない場合は, NG.

if(k == N + 1) ok = false;

// tXorCum の i番目と sXorCum の j番目が等しくなるものは？

repx(j, k, N + 1){

// 探索開始位置(次回分).

jMax = max(jMax, j + 1);

// 見つかった.

if(tXorCum[i] == sXorCum[j]){

// 集計.

ans += (j - i);

// 操作履歴保存.

cur[tXorCum[i]] = j;

cur[!tXorCum[i]] = -1;

// 次へ.

break;

}

// 見つからなかった.

if(jMax == N + 1) ok = false;

}

// 4. 出力.

printf("%lld\n", ok ? ans : -1);

return 0;

}

[入力例]
3
001
100

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

[入力例]
3
001
110

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

[入力例]
5
10111
01010

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

[入力例]
7
0101101
1001100

[出力例]
-1

[入力例]
7
0111101
1001100

[出力例]
5

[入力例]
10
1010111101
1000101100

[出力例]
-1

[入力例]
10
1010111101
1100101100

[出力例]
5

[入力例]
30
001010001110011100110110111101
110001010100011100100110011000

[出力例]
18

[入力例]

001

100

[出力例]

※AtCoderのテストケースより

[入力例]

001

110

[出力例]

-1

※AtCoderのテストケースより

[入力例]

10111

01010

[出力例]

※AtCoderのテストケースより

[入力例]

0101101

1001100

[出力例]

-1

[入力例]

0111101

1001100

[出力例]

[入力例]

1010111101

1000101100

[出力例]

-1

[入力例]

1010111101

1100101100

[出力例]

[入力例]

001010001110011100110110111101

110001010100011100100110011000

[出力例]

■参照サイト
AtCoder Grand Contest 049

2023年8月20日

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

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

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

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

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

// 解き直し.
// https://atcoder.jp/contests/abc189/editorial/541
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
int a[202020];
double dp[202020], dpCum[202020], pd[202020], pdCum[202020];

int main(){
    
    // 1. 入力情報.
    int N, M, K;
    scanf("%d %d %d", &N, &M, &K);
    vi v;
    rep(i, K){
        int idx;
        scanf("%d", &idx);
        ++a[idx];
        v.pb(idx);
    }
    
    // 2. マス N に, 到達不可能.
    if(K >= M){
        rep(i, K - M + 1){
            if(v[i + M - 1] - v[i] == M - 1){
                puts("-1");
                return 0;
            }
        }
    }
    
    // 3. dp更新.
    repr(i, N - 1, 0){
        // 振り出しに戻るマス.
        if(a[i]){
            // g[i].
            dp[i] = 0.0;
            dpCum[i] = dp[i] + dpCum[i + 1];
            
            // x の 係数.
            pd[i] = 1.0;
            pdCum[i] = pd[i] + pdCum[i + 1];
            
            // 次へ.
            continue;
        }
        
        // それ以外.
        // g[i].
        dp[i] = 1.0 / M * (dpCum[i + 1] - dpCum[i + M + 1]) + 1.0;
        dpCum[i] = dp[i] + dpCum[i + 1];
        
        // x の 係数.
        pd[i] = 1.0 / M * (pdCum[i + 1] - pdCum[i + M + 1]);
        pdCum[i] = pd[i] + pdCum[i + 1];
    }
    
    // 4. 出力.
    printf("%.6lf\n", dp[0] / (1.0 - pd[0]));
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc189/editorial/541

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

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

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

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

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

#define pb push_back

int a[202020];

double dp[202020], dpCum[202020], pd[202020], pdCum[202020];

int main(){

// 1. 入力情報.

int N, M, K;

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

vi v;

rep(i, K){

int idx;

scanf("%d", &idx);

++a[idx];

v.pb(idx);

}

// 2. マス N に, 到達不可能.

if(K >= M){

rep(i, K - M + 1){

if(v[i + M - 1] - v[i] == M - 1){

puts("-1");

return 0;

}

// 3. dp更新.

repr(i, N - 1, 0){

// 振り出しに戻るマス.

if(a[i]){

// g[i].

dp[i] = 0.0;

dpCum[i] = dp[i] + dpCum[i + 1];

// x の係数.

pd[i] = 1.0;

pdCum[i] = pd[i] + pdCum[i + 1];

// 次へ.

continue;

}

// それ以外.

// g[i].

dp[i] = 1.0 / M * (dpCum[i + 1] - dpCum[i + M + 1]) + 1.0;

dpCum[i] = dp[i] + dpCum[i + 1];

// x の係数.

pd[i] = 1.0 / M * (pdCum[i + 1] - pdCum[i + M + 1]);

pdCum[i] = pd[i] + pdCum[i + 1];

}

// 4. 出力.

printf("%.6lf\n", dp[0] / (1.0 - pd[0]));

return 0;

}

[入力例]
2 2 0

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

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

[入力例]
2 2 1
1

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

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

[入力例]
100 6 10
11 12 13 14 15 16 17 18 19 20

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

[入力例]
100000 2 2
2997 92458

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

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

[入力例]
5 4 2
2 3

[出力例]
4.166667

[入力例]
5 3 3
2 4 5

[出力例]
6.000000

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

[出力例]
-1

[入力例]
7 5 3
1 4 5

[出力例]
6.821429

[入力例]
2023 3 8
123 234 345 456 567 678 789 890 

[出力例]
30397.833333

[入力例]
12345 3 5
1234 2345 3456 4567 5678

[出力例]
39742.833332

[入力例]

2 2 0

[出力例]

1.5000

※AtCoderテストケースより

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

1.500000

[入力例]

2 2 1

[出力例]

2.0000

※AtCoderテストケースより

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

2.000000

[入力例]

100 6 10

11 12 13 14 15 16 17 18 19 20

[出力例]

-1

※AtCoderテストケースより

[入力例]

100000 2 2

2997 92458

[出力例]

201932.2222

※AtCoderテストケースより

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

201932.225051

[入力例]

5 4 2

2 3

[出力例]

4.166667

[入力例]

5 3 3

2 4 5

[出力例]

6.000000

[入力例]

6 3 4

1 3 4 5

[出力例]

-1

[入力例]

7 5 3

1 4 5

[出力例]

6.821429

[入力例]

2023 3 8

123 234 345 456 567 678 789 890

[出力例]

30397.833333

[入力例]

12345 3 5

1234 2345 3456 4567 5678

[出力例]

39742.833332

■参照サイト
AtCoder Beginner Contest 189

2023年8月18日2023年8月18日

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

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

■感想.
1. 問題Fは, 方針が見えなかったので, 解説を参考に, AC版に到達できた.
2. Dinic法に触れることが出来たので, 非常に良かったと思う.
※ 競プロ典型 90 問のライブラリを拝借させて頂いてます.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc205/editorial/2057
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using P = pair<int, int>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
const int MAX = 2020;
int PA[101], PB[101], PC[101], PD[101];

struct Edge{
    int to, cap, rev;
};

// Dinic
// https://github.com/E869120/kyopro_educational_90/blob/main/sol/077-04a.cpp
// -> 一部改変(2022/04/23).
struct Dinic{
    int size_;
    vi level, iter;
    vector<Edge> G[MAX];
    
    Dinic(int n = 0) : size_(n), level(n + 1), iter(n + 1) {}
    void edge(int u, int v, int c){
        G[u].pb(Edge{v, c, (int)G[v].size()});
        G[v].pb(Edge{u, 0, (int)G[u].size() - 1});
    }
    void bfs(int s){
        rep(i, size_ + 1) level[i] = -1;
        queue<int> q;
        q.push(s);
        level[s] = 0;
        while(!q.empty()){
            int pos = q.front();
            q.pop();
            rep(i, G[pos].size()){
                if(G[pos][i].cap == 0 || level[G[pos][i].to] != -1) continue;
                q.push(G[pos][i].to);
                level[G[pos][i].to] = level[pos] + 1;
            }
        }
    }
    int dfs(int pos, int to, int f){
        if(pos == to) return f;
        for(int& i = iter[pos]; i < G[pos].size(); i++){
            if(G[pos][i].cap > 0 && level[pos] < level[G[pos][i].to]){
                int z = dfs(G[pos][i].to, to, min(f, G[pos][i].cap));
                if(z > 0){
                    G[pos][i].cap -= z;
                    G[G[pos][i].to][G[pos][i].rev].cap += z;
                    return z;
                }
            }
        }
        return 0;
    }
    int maxFlow(int s, int t){
        int ret = 0;
        while(1){
            bfs(s);
            if(level[t] == -1) break;
            rep(i, size_ + 1) iter[i] = 0;
            while(1){
                int f = dfs(s, t, 1000000007);
                if(f == 0) break;
                ret += f;
            }
        }
        return ret;
    }
};

int main(){
    
    // 1. 入力情報.
    int H, W, N;
    scanf("%d %d %d", &H, &W, &N);
    rep(i, N) scanf("%d %d %d %d", &PA[i], &PB[i], &PC[i], &PD[i]);
    rep(i, N){
        PB[i] += H;
        PD[i] += H;
    }
    
    // 2. グラフ構築(解説通り).
    // -> 頂点番号は, 以下のように設定.
    // src = 0
    // R = 1 ～ H
    // C = H + 1 ～ H + W
    // U = H + W + 1 ～ H + W + N
    // V = H + W + N + 1 ～ H + W + N + N
    // dst = H + W + N + N + 1
    // 
    int src = 0, dst = H + W + N + N + 1;
    Dinic D(H + W + N + N + 5);
    repx(r, 1, H + 1) D.edge(src, r, 1);
    rep(i, N){
        int u = H + W + i + 1;
        repx(r, PA[i], PC[i] + 1) D.edge(r, u, 1);
    }
    rep(i, N){
        int u = H + W + i + 1;
        int v = H + W + N + i + 1;
        D.edge(u, v, 1);
    }
    rep(i, N){
        int v = H + W + N + i + 1;
        repx(c, PB[i], PD[i] + 1) D.edge(v, c, 1);
    }
    repx(c, H + 1, H + W + 1) D.edge(c, dst, 1);
    
    // 3. 出力.
    printf("%d\n", D.maxFlow(src, dst));
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

// 解き直し.

// https://atcoder.jp/contests/abc205/editorial/2057

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using P = pair<int, int>;

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

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

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

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

#define pb push_back

const int MAX = 2020;

int PA[101], PB[101], PC[101], PD[101];

struct Edge{

int to, cap, rev;

};

// Dinic

// https://github.com/E869120/kyopro_educational_90/blob/main/sol/077-04a.cpp

// -> 一部改変(2022/04/23).

struct Dinic{

int size_;

vi level, iter;

vector<Edge> G[MAX];

Dinic(int n = 0) : size_(n), level(n + 1), iter(n + 1) {}

void edge(int u, int v, int c){

G[u].pb(Edge{v, c, (int)G[v].size()});

G[v].pb(Edge{u, 0, (int)G[u].size() - 1});

}

void bfs(int s){

rep(i, size_ + 1) level[i] = -1;

queue<int> q;

q.push(s);

level[s] = 0;

while(!q.empty()){

int pos = q.front();

q.pop();

rep(i, G[pos].size()){

if(G[pos][i].cap == 0 || level[G[pos][i].to] != -1) continue;

q.push(G[pos][i].to);

level[G[pos][i].to] = level[pos] + 1;

}

int dfs(int pos, int to, int f){

if(pos == to) return f;

for(int& i = iter[pos]; i < G[pos].size(); i++){

if(G[pos][i].cap > 0 && level[pos] < level[G[pos][i].to]){

int z = dfs(G[pos][i].to, to, min(f, G[pos][i].cap));

if(z > 0){

G[pos][i].cap -= z;

G[G[pos][i].to][G[pos][i].rev].cap += z;

return z;

}

return 0;

}

int maxFlow(int s, int t){

int ret = 0;

while(1){

bfs(s);

if(level[t] == -1) break;

rep(i, size_ + 1) iter[i] = 0;

while(1){

int f = dfs(s, t, 1000000007);

if(f == 0) break;

ret += f;

}

return ret;

}

};

int main(){

// 1. 入力情報.

int H, W, N;

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

rep(i, N) scanf("%d %d %d %d", &PA[i], &PB[i], &PC[i], &PD[i]);

rep(i, N){

PB[i] += H;

PD[i] += H;

}

// 2. グラフ構築(解説通り).

// -> 頂点番号は, 以下のように設定.

// src = 0

// R = 1 ～ H

// C = H + 1 ～ H + W

// U = H + W + 1 ～ H + W + N

// V = H + W + N + 1 ～ H + W + N + N

// dst = H + W + N + N + 1

int src = 0, dst = H + W + N + N + 1;

Dinic D(H + W + N + N + 5);

repx(r, 1, H + 1) D.edge(src, r, 1);

rep(i, N){

int u = H + W + i + 1;

repx(r, PA[i], PC[i] + 1) D.edge(r, u, 1);

}

rep(i, N){

int u = H + W + i + 1;

int v = H + W + N + i + 1;

D.edge(u, v, 1);

}

rep(i, N){

int v = H + W + N + i + 1;

repx(c, PB[i], PD[i] + 1) D.edge(v, c, 1);

}

repx(c, H + 1, H + W + 1) D.edge(c, dst, 1);

// 3. 出力.

printf("%d\n", D.maxFlow(src, dst));

return 0;

}

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

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

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

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

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

[出力例]
2

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

[出力例]
6

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

[出力例]
10

[入力例]

2 3 3

1 1 2 2

1 2 2 3

1 1 1 3

[出力例]

※AtCoderテストケースより

[入力例]

5 5 3

1 1 5 5

1 1 4 4

2 2 3 3

[出力例]

※AtCoderテストケースより

[入力例]

2 2 2

1 1 1 1

1 1 2 2

[出力例]

[入力例]

7 10 12

3 3 6 4

3 3 5 5

3 8 4 10

2 9 5 10

3 3 5 5

2 7 3 8

3 8 3 10

2 9 7 10

3 4 5 5

3 5 5 5

2 3 3 6

2 9 6 10

[出力例]

[入力例]

12 15 18

5 4 7 7

5 5 6 6

5 4 7 8

4 5 5 7

3 5 9 6

3 6 10 6

3 5 9 7

2 6 8 7

2 7 7 8

2 8 7 9

1 6 5 7

1 5 6 7

1 6 7 9

1 3 3 4

1 5 2 6

10 12 12 12

10 12 11 13

10 11 11 13

[出力例]

■参照サイト
AtCoder Beginner Contest 205
競プロ典型 90 問の問題077

2023年8月16日

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

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

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

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

// 解き直し.
// https://atcoder.jp/contests/abc182/editorial/293
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define a first
const LL INF = 202020202020202020;
LL a[55], b[55];

int main(){
    
    // 1. 入力情報.
    int N;
    LL X;
    scanf("%d %lld", &N, &X);
    rep(i, N) scanf("%lld", &a[i]);
    rep(i, N - 1) b[i] = a[i + 1] / a[i];
    b[N - 1] = INF;
    
    // 2. dp更新.
    map<LL, LL> dp[N + 1];
    dp[N][-X] = 1;
    repr(i, N - 1, 0){
        for(auto &j : dp[i + 1]){
            // x の 出現チェック.
            set<LL> st;
            
            // x を -2 ～ 2 の差分に渡り, 余分に見る.
            for(auto &p : {-2, -1, 0, 1, 2}){
                // x, d の 計算.
                LL x = -j.a / a[i] + p;
                LL d = a[i] * x + j.a;
                
                // 条件を満たすか？
                if(!st.count(x) && abs(d) < a[i] && abs(x) < b[i]){
                    // dp更新.
                    dp[i][d] += dp[i + 1][j.a];
                    
                    // 出現済.
                    st.insert(x);
                }
            }
        }
    }
    
    // 3. 出力.
    printf("%lld\n", dp[0][0]);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc182/editorial/293

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

#define a first

const LL INF = 202020202020202020;

LL a[55], b[55];

int main(){

// 1. 入力情報.

int N;

LL X;

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

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

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

b[N - 1] = INF;

// 2. dp更新.

map<LL, LL> dp[N + 1];

dp[N][-X] = 1;

repr(i, N - 1, 0){

for(auto &j : dp[i + 1]){

// x の出現チェック.

set<LL> st;

// x を -2 ～ 2 の差分に渡り, 余分に見る.

for(auto &p : {-2, -1, 0, 1, 2}){

// x, d の計算.

LL x = -j.a / a[i] + p;

LL d = a[i] * x + j.a;

// 条件を満たすか？

if(!st.count(x) && abs(d) < a[i] && abs(x) < b[i]){

// dp更新.

dp[i][d] += dp[i + 1][j.a];

// 出現済.

st.insert(x);

}

// 3. 出力.

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

return 0;

}

[入力例]
3 9
1 5 10

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

[入力例]
5 198
1 5 10 50 100

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

[入力例]
4 44
1 4 20 100

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

[入力例]
9 11837029798
1 942454037 2827362111 19791534777 257289952101 771869856303 3859349281515 30874794252120 216123559764840

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

[入力例]
15 304050607080
1 111 333 1665 11655 34965 244755 734265 2202795 11013975 33041925 99125775 198251550 396503100 1189509300

[出力例]
2160

[入力例]
23 20230816
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304

[出力例]
2675

[入力例]
25 202011082100
1 3 9 27 81 243 729 2187 6561 19683 59049 177147 531441 1594323 4782969 14348907 43046721 129140163 387420489 1162261467 3486784401 10460353203 31381059609 94143178827 282429536481

[出力例]
1075200

[入力例]

3 9

1 5 10

[出力例]

※AtCoderテストケースより

[入力例]

5 198

1 5 10 50 100

[出力例]

※AtCoderテストケースより

[入力例]

4 44

1 4 20 100

[出力例]

※AtCoderテストケースより

[入力例]

9 11837029798

1 942454037 2827362111 19791534777 257289952101 771869856303 3859349281515 30874794252120 216123559764840

[出力例]

※AtCoderテストケースより

[入力例]

15 304050607080

1 111 333 1665 11655 34965 244755 734265 2202795 11013975 33041925 99125775 198251550 396503100 1189509300

[出力例]

2160

[入力例]

23 20230816

1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304

[出力例]

2675

[入力例]

25 202011082100

1 3 9 27 81 243 729 2187 6561 19683 59049 177147 531441 1594323 4782969 14348907 43046721 129140163 387420489 1162261467 3486784401 10460353203 31381059609 94143178827 282429536481

[出力例]

1075200

■参照サイト
AtCoder Beginner Contest 182

2023年8月13日

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

C++の練習を兼ねて, AtCoder Beginner Contest 306 の問題C (Centers) ～問題E (Best Performances) を解いてみた.

■感想.
1. 問題C ～問題E は, 方針を絞り込めたので, AC版に到達できたと思う.
2. 問題Dで, 苦手な動的計画法の訓練が積めたので, 非常に良かったと思う.
3. 問題Eで, 実装に苦労したものの, std::multiset の復習が出来たので, 非常に良かったと思う.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

■C++版プログラム(問題C／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 pb push_back
#define all(x) x.begin(), x.end()
#define a first
#define b second
int a[303030], c[101010];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N * 3) scanf("%d", &a[i]);
    
    // 2. f[i].
    vp f;
    rep(i, N * 3) if(++c[a[i]] == 2) f.pb({i, a[i]});
    
    // 3. sort.
    sort(all(f));
    
    // 4. 出力.
    rep(i, N) printf("%d%s", f[i].b, (i < N - 1) ? " " : "\n");
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using P = pair<int, int>;

using vp = vector;

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

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

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

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

#define pb push_back

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

#define a first

#define b second

int a[303030], c[101010];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

// 2. f[i].

vp f;

rep(i, N * 3) if(++c[a[i]] == 2) f.pb({i, a[i]});

// 3. sort.

sort(all(f));

// 4. 出力.

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

return 0;

}

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

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

[入力例]
1
1 1 1

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

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

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

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

[出力例]
5 1 2 3 4

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

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

[入力例]

1 1 3 2 3 2 2 3 1

[出力例]

1 3 2

※AtCoderテストケースより

[入力例]

1 1 1

[出力例]

※AtCoderテストケースより

[入力例]

2 3 4 3 4 1 3 1 1 4 2 2

[出力例]

3 4 1 2

※AtCoderテストケースより

[入力例]

5 1 5 1 2 2 3 4 1 3 4 4 5 3 2

[出力例]

5 1 2 3 4

[入力例]

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

[出力例]

7 10 9 1 2 5 6 3 4 8

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
int x[303030], y[303030];
LL dp[303030][2]; // (第二成分) 0: お腹を壊してない, 1: お腹を壊している.

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d %d", &x[i], &y[i]);
    
    // 2. dp更新.
    repx(i, 1, N + 1){
        // 前回分.
        dp[i][0] = dp[i - 1][0];
        dp[i][1] = dp[i - 1][1];
        
        // 解毒剤入りの料理.
        if(x[i - 1] == 0){
            // 下げてもらう, お腹を壊していない時, お腹を壊している時.
            dp[i][0] = max({dp[i][0], dp[i - 1][0] + y[i - 1], dp[i - 1][1] + y[i - 1]});
        }
        
        // 毒入りの料理.
        if(x[i - 1] == 1){
            // 下げてもらう, お腹を壊していない時.
            dp[i][1] = max(dp[i][1], dp[i - 1][0] + y[i - 1]);
        }
    }
    
    // 3. 出力.
    printf("%lld\n", max(dp[N][0], dp[N][1]));
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

int x[303030], y[303030];

LL dp[303030][2]; // (第二成分) 0: お腹を壊してない, 1: お腹を壊している.

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

// 2. dp更新.

repx(i, 1, N + 1){

// 前回分.

dp[i][0] = dp[i - 1][0];

dp[i][1] = dp[i - 1][1];

// 解毒剤入りの料理.

if(x[i - 1] == 0){

// 下げてもらう, お腹を壊していない時, お腹を壊している時.

dp[i][0] = max({dp[i][0], dp[i - 1][0] + y[i - 1], dp[i - 1][1] + y[i - 1]});

}

// 毒入りの料理.

if(x[i - 1] == 1){

// 下げてもらう, お腹を壊していない時.

dp[i][1] = max(dp[i][1], dp[i - 1][0] + y[i - 1]);

}

// 3. 出力.

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

return 0;

}

[入力例]
5
1 100
1 300
0 -200
1 500
1 300

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

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

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

[入力例]
15
1 900000000
0 600000000
1 -300000000
0 -700000000
1 200000000
1 300000000
0 -600000000
1 -900000000
1 600000000
1 -100000000
1 -400000000
0 900000000
0 200000000
1 -500000000
1 900000000

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

[入力例]
5
0 -47
1 37
1 47
0 -1
1 31

[出力例]
77

[入力例]
17
1 -5927
0 -5083
1 -4874
0 2133
0 -3008
1 -4097
0 -6399
1 -7708
0 5110
1 3952
1 -8882
0 415
1 2652
0 -8000
1 6377
1 2607
0 2013

[出力例]
20000

[入力例]
50
1 443328
0 73836
1 935506
0 167707
1 -721984
1 868820
1 935436
1 -837258
0 -178397
1 466026
0 256747
1 598834
0 -346502
1 245871
1 -448547
1 -840209
1 -322995
0 858559
1 953866
1 -601510
1 402645
0 737038
0 -305937
0 617873
0 370498
1 -526848
1 434673
0 784215
1 860840
1 73853
1 299615
1 777998
0 -811686
0 -532055
1 -347241
0 181457
0 -180547
1 -156049
1 -701547
0 198698
1 423549
1 -408934
1 -584618
0 19276
1 226669
0 -728976
1 690256
0 297078
1 873101
1 530457

[出力例]
12000000

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

[入力例]

1 100

1 300

0 -200

1 500

1 300

[出力例]

600

※AtCoderテストケースより

[入力例]

0 -1

1 -2

0 -3

1 -4

[出力例]

※AtCoderテストケースより

[入力例]

1 900000000

0 600000000

1 -300000000

0 -700000000

1 200000000

1 300000000

0 -600000000

1 -900000000

1 600000000

1 -100000000

1 -400000000

0 900000000

0 200000000

1 -500000000

1 900000000

[出力例]

4100000000

※AtCoderテストケースより

[入力例]

0 -47

1 37

1 47

0 -1

1 31

[出力例]

[入力例]

1 -5927

0 -5083

1 -4874

0 2133

0 -3008

1 -4097

0 -6399

1 -7708

0 5110

1 3952

1 -8882

0 415

1 2652

0 -8000

1 6377

1 2607

0 2013

[出力例]

20000

[入力例]

1 443328

0 73836

1 935506

0 167707

1 -721984

1 868820

1 935436

1 -837258

0 -178397

1 466026

0 256747

1 598834

0 -346502

1 245871

1 -448547

1 -840209

1 -322995

0 858559

1 953866

1 -601510

1 402645

0 737038

0 -305937

0 617873

0 370498

1 -526848

1 434673

0 784215

1 860840

1 73853

1 299615

1 777998

0 -811686

0 -532055

1 -347241

0 181457

0 -180547

1 -156049

1 -701547

0 198698

1 423549

1 -408934

1 -584618

0 19276

1 226669

0 -728976

1 690256

0 297078

1 873101

1 530457

[出力例]

12000000

■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--)
LL a[505050];

int main(){
    
    // 1. 入力情報.
    int N, K, Q;
    scanf("%d %d %d", &N, &K, &Q);
    
    // 2. 事前準備.
    multiset<LL> lMst, rMst;
    rep(i, N){
        if(i < N - K) lMst.insert(0);
        else          rMst.insert(0);
    }
    
    // 3. クエリ回答.
    LL f = 0;
    rep(i, Q){
        // クエリ入力情報.
        int x, y;
        scanf("%d %d", &x, &y);
        --x;
        
        // 更新予定の値.
        LL cur = a[x];
        
        // 更新.
        a[x] = y;
        
        // 左側.
        bool isSwap = false;
        if(!lMst.empty()){
            auto lItr = lMst.find(cur);
            if(lItr != lMst.end()){
                // 入れ替え.
                lMst.erase(lItr);
                lMst.insert(y);
                isSwap = !isSwap;
            }
        }
        
        // 右側.
        auto rItr = rMst.find(cur);
        if(!isSwap && rItr != rMst.end()){
            // 入れ替え.
            rMst.erase(rItr);
            rMst.insert(y);
            
            // f 更新.
            f += y;
            f -= cur;
        }
        
        // 最大値チェック.
        if(!lMst.empty()){
            LL lMax = *(--lMst.end());
            LL rMin = *rMst.begin();
            if(lMax > rMin){
                // 削除.
                auto lDel = lMst.find(lMax);
                lMst.erase(lDel);
                auto rDel = rMst.find(rMin);
                rMst.erase(rDel);
                
                // 追加.
                lMst.insert(rMin);
                rMst.insert(lMax);
                
                // f 更新.
                f += lMax;
                f -= rMin;
            }
        }
        
        // 出力.
        printf("%lld\n", f);
    }
    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--)

LL a[505050];

int main(){

// 1. 入力情報.

int N, K, Q;

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

// 2. 事前準備.

multiset<LL> lMst, rMst;

rep(i, N){

if(i < N - K) lMst.insert(0);

else rMst.insert(0);

}

// 3. クエリ回答.

LL f = 0;

rep(i, Q){

// クエリ入力情報.

int x, y;

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

--x;

// 更新予定の値.

LL cur = a[x];

// 更新.

a[x] = y;

// 左側.

bool isSwap = false;

if(!lMst.empty()){

auto lItr = lMst.find(cur);

if(lItr != lMst.end()){

// 入れ替え.

lMst.erase(lItr);

lMst.insert(y);

isSwap = !isSwap;

}

// 右側.

auto rItr = rMst.find(cur);

if(!isSwap && rItr != rMst.end()){

// 入れ替え.

rMst.erase(rItr);

rMst.insert(y);

// f 更新.

f += y;

f -= cur;

}

// 最大値チェック.

if(!lMst.empty()){

LL lMax = *(--lMst.end());

LL rMin = *rMst.begin();

if(lMax > rMin){

// 削除.

auto lDel = lMst.find(lMax);

lMst.erase(lDel);

auto rDel = rMst.find(rMin);

rMst.erase(rDel);

// 追加.

lMst.insert(rMin);

rMst.insert(lMax);

// f 更新.

f += lMax;

f -= rMin;

}

// 出力.

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

}

return 0;

}

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

[出力例]
5
6
8
8
15
13
13
11
1
0
※AtCoderテストケースより

[入力例]
10 3 30
2 120
7 114
1 36
9 99
1 8
7 122
2 45
1 58
6 88
9 74
7 69
2 6
3 10
5 31
3 116
3 73
9 32
2 43
7 38
7 41
9 61
4 14
6 28
4 110
8 10
6 91
7 100
1 53
5 112
6 79

[出力例]
120
234
270
333
333
341
266
279
309
284
231
231
231
231
278
235
230
230
219
219
222
222
192
244
244
274
301
301
322
322

[入力例]
20 5 100
6 8520
9 1903
7 10099
2 655
8 9326
16 2653
19 6018
13 4188
7 4612
7 5699
18 7730
5 383
12 3149
6 764
7 3043
7 1626
8 2701
17 9019
1 2749
17 8514
18 89
4 1192
8 2974
3 9292
18 7511
7 8047
19 2216
20 1991
11 5850
5 7479
12 11977
20 63
6 12325
8 7013
6 7715
5 2225
6 5161
6 9220
14 10668
9 7839
19 5285
17 7557
7 2664
13 1823
6 3766
3 7557
17 9157
6 9224
5 3799
9 10820
4 10364
6 9731
16 9634
1 3711
2 1061
8 704
1 405
3 17
4 8014
8 4445
1 4903
4 11265
18 2861
20 12261
7 1500
20 6723
7 9299
14 7574
20 5920
18 5223
6 10318
14 6469
17 6790
17 1844
18 4048
18 11912
7 5035
17 11880
13 2837
4 6373
20 1383
12 12308
14 11816
7 2600
10 6148
4 5572
14 3855
12 2960
19 2854
11 8674
6 5111
20 7973
3 3969
4 5009
15 10535
12 2267
4 10367
5 9390
11 6519
10 7310

[出力例]
8520
10423
20522
21177
30503
32501
36616
38151
32664
33751
37293
37293
37293
32961
30411
30411
23786
30104
30104
29599
24618
24618
24843
31161
35523
39382
37552
37552
39214
40843
45341
45341
50155
50155
45545
45545
45341
47050
49671
49671
49671
49204
48996
48996
47333
45598
47198
48865
48865
51846
53053
53560
53560
53560
53560
53560
53560
53560
52830
52830
52830
54461
54461
56991
56991
54461
54461
53427
53427
53427
54014
54014
54014
54014
54014
56292
56292
57854
57854
56907
56907
57238
58736
58736
58736
58736
57238
54564
54564
54564
52920
52920
52920
52920
54781
54781
55514
55514
55514
55514

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

[入力例]

4 2 10

1 5

2 1

3 3

4 2

2 10

1 0

4 0

3 1

2 0

3 0

[出力例]

※AtCoderテストケースより

[入力例]

10 3 30

2 120

7 114

1 36

9 99

1 8

7 122

2 45

1 58

6 88

9 74

7 69

2 6

3 10

5 31

3 116

3 73

9 32

2 43

7 38

7 41

9 61

4 14

6 28

4 110

8 10

6 91

7 100

1 53

5 112

6 79

[出力例]

120

234

270

333

341

266

279

309

284

231

278

235

230

219

222

192

244

274

301

322

[入力例]

20 5 100

6 8520

9 1903

7 10099

2 655

8 9326

16 2653

19 6018

13 4188

7 4612

7 5699

18 7730

5 383

12 3149

6 764

7 3043

7 1626

8 2701

17 9019

1 2749

17 8514

18 89

4 1192

8 2974

3 9292

18 7511

7 8047

19 2216

20 1991

11 5850

5 7479

12 11977

20 63

6 12325

8 7013

6 7715

5 2225

6 5161

6 9220

14 10668

9 7839

19 5285

17 7557

7 2664

13 1823

6 3766

3 7557

17 9157

6 9224

5 3799

9 10820

4 10364

6 9731

16 9634

1 3711

2 1061

8 704

1 405

3 17

4 8014

8 4445

1 4903

4 11265

18 2861

20 12261

7 1500

20 6723

7 9299

14 7574

20 5920

18 5223

6 10318

14 6469

17 6790

17 1844

18 4048

18 11912

7 5035

17 11880

13 2837

4 6373

20 1383

12 12308

14 11816

7 2600

10 6148

4 5572

14 3855

12 2960

19 2854

11 8674

6 5111

20 7973

3 3969

4 5009

15 10535

12 2267

4 10367

5 9390

11 6519

10 7310

[出力例]

8520

10423

20522

21177

30503

32501

36616

38151

32664

33751

37293

32961

30411

23786

30104

29599

24618

24843

31161

35523

39382

37552

39214

40843

45341

50155

45545

45341

47050

49671

49204

48996

47333

45598

47198

48865

51846

53053

53560

52830

54461

56991

54461

53427

54014

56292

57854

56907

57238

58736

57238

54564

52920

54781

55514

■参照サイト
トヨタ自動車プログラミングコンテスト2023#3(AtCoder Beginner Contest 306)

2023年8月5日

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

C++の練習を兼ねて, AtCoder Regular Contest 143 の問題C (Piles of Pebbles) を解いてみた.

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

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

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

// 解き直し.
// https://atcoder.jp/contests/arc143/editorial/4194
// 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 all(x) x.begin(), x.end()

int main(){
    
    // 1. 入力情報.
    int N, X, Y;
    scanf("%d %d %d", &N, &X, &Y);
    vi a(N);
    rep(i, N) scanf("%d", &a[i]);
    
    // 2. B の 計算.
    vi b(N);
    rep(i, N) b[i] = a[i] % (X + Y);
    
    // 3. sort.
    sort(all(b));
    
    // 4. B[i] が, すべて X より小さい.
    if(b.back() < X){
        puts("Second");
        return 0;
    }
    
    // 5. X <= Y で, ある b[i] が X 以上.
    if(X <= Y){
        if(b.back() >= X){
            puts("First");
            return 0;
        }
    }
    
    // 6. X > Y.
    // 6-1. 先手が, X個以上の山(一つ)から, X個取り除く.
    b.back() -= X;
    
    // 6-2. sort.
    sort(all(b));
    
    // 6-3. B[i] が, すべて Y より小さい.
    if(b.back() < Y){
        puts("First");
        return 0;
    }
    
    // 6-4. ある b[i] が Y 以上.
    puts("Second");
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc143/editorial/4194

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

int main(){

// 1. 入力情報.

int N, X, Y;

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

vi a(N);

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

// 2. B の計算.

vi b(N);

rep(i, N) b[i] = a[i] % (X + Y);

// 3. sort.

sort(all(b));

// 4. B[i] が, すべて X より小さい.

if(b.back() < X){

puts("Second");

return 0;

}

// 5. X <= Y で, ある b[i] が X 以上.

if(X <= Y){

if(b.back() >= X){

puts("First");

return 0;

}

// 6. X > Y.

// 6-1. 先手が, X個以上の山(一つ)から, X個取り除く.

b.back() -= X;

// 6-2. sort.

sort(all(b));

// 6-3. B[i] が, すべて Y より小さい.

if(b.back() < Y){

puts("First");

return 0;

}

// 6-4. ある b[i] が Y 以上.

puts("Second");

return 0;

}

[入力例]
2 1 1
3 3

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

[入力例]
2 1 2
3 3

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

[入力例]
3 1 2
2 5 6

[出力例]
First

[入力例]
5 5 3
19 20 21 22 23

[出力例]
Second

[入力例]
5 5 3
16 17 18 23 24

[出力例]
First

[入力例]
10 7 9
37 22 21 17 49 65 82 20 18 19

[出力例]
Second

[入力例]
20 12 13
25 36 25 13 13 29 21 17 37 27 27 24 34 21 24 22 34 14 17 24

[出力例]
First

[入力例]
30 55 50
489 550 368 440 541 255 423 509 378 496 296 466 315 380 404 397 322 296 346 283 492 430 438 517 541 411 426 477 331 347

[出力例]
Second

[入力例]
50 2023 2020
8586 8043 4543 12629 21215 17172 4543 9086 16672 13129 12629 8586 13129 20715 16672 5043 5043 8586 21215 9086 20715 17172 5043 21215 20715 17172 21215 12629 16672 4543 12629 9086 12629 12629 20715 17172 9086 4543 9086 5043 12629 4543 12629 17172 12629 13129 21215 4543 17172 17172

[出力例]
First

[入力例]

2 1 1

3 3

[出力例]

First

※AtCoderのテストケースより

[入力例]

2 1 2

3 3

[出力例]

Second

※AtCoderのテストケースより

[入力例]

3 1 2

2 5 6

[出力例]

First

[入力例]

5 5 3

19 20 21 22 23

[出力例]

Second

[入力例]

5 5 3

16 17 18 23 24

[出力例]

First

[入力例]

10 7 9

37 22 21 17 49 65 82 20 18 19

[出力例]

Second

[入力例]

20 12 13

25 36 25 13 13 29 21 17 37 27 27 24 34 21 24 22 34 14 17 24

[出力例]

First

[入力例]

30 55 50

489 550 368 440 541 255 423 509 378 496 296 466 315 380 404 397 322 296 346 283 492 430 438 517 541 411 426 477 331 347

[出力例]

Second

[入力例]

50 2023 2020

8586 8043 4543 12629 21215 17172 4543 9086 16672 13129 12629 8586 13129 20715 16672 5043 5043 8586 21215 9086 20715 17172 5043 21215 20715 17172 21215 12629 16672 4543 12629 9086 12629 12629 20715 17172 9086 4543 9086 5043 12629 4543 12629 17172 12629 13129 21215 4543 17172 17172

[出力例]

First

■参照サイト
AtCoder Regular Contest 143

2023年7月30日

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

C++の練習を兼ねて, AtCoder Beginner Contest 301 の問題E (Pac-Takahashi) を解いてみた.

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 幅優先探索, 苦手な動的計画法(bitDP, 巡回セールスマン問題)の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc301/editorial/6343
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
using vp = vector<P>;
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 a first
#define b second
const int INF = 1010101010;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
char board[303][303];
int memo[22][22];

int main(){
    
    // 1. 入力情報.
    int H, W, T;
    scanf("%d %d %d", &H, &W, &T);
    rep(i, H){
        char c[303];
        scanf("%s", c);
        rep(j, W) board[i][j] = c[j];
    }
    
    // 2. マス(スタート, お菓子, ゴール)を保存.
    vp cells;
    rep(i, H) rep(j, W) if(board[i][j] == 'S') cells.pb({i, j});
    rep(i, H) rep(j, W) if(board[i][j] == 'o') cells.pb({i, j});
    rep(i, H) rep(j, W) if(board[i][j] == 'G') cells.pb({i, j});
    int n = cells.size();
    
    // 3. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](P s, int x) -> void {
        // 訪問フラグ.
        int v[303][303];
        rep(i, H) rep(j, W) v[i][j] = INF;
        
        // 空のキュー.
        queue<P> q;
        
        // 訪問済みフラグ設定.
        v[s.a][s.b] = 0;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // キューから取り出す.
            P c = q.front();
            q.pop();
            
            // 取り出した要素を処理.
            // x: 列方向, y: 行方向 で考える.
            rep(i, 4){
                int nx = c.b + dx[i];
                int ny = c.a + dy[i];
                
                // 訪問不可能なマスは, スキップ.
                if(nx < 0 || nx >= W || ny < 0 || ny >= H || board[ny][nx] == '#') continue;
                
                // 未訪問のマスは, 最短距離を設定.
                if(v[ny][nx] == INF) v[ny][nx] = v[c.a][c.b] + 1, q.push({ny, nx});
            }
        }
        
        // 結果の保存.
        rep(i, n) memo[x][i] = v[cells[i].a][cells[i].b];
    };
    
    // 4. 全探索(指定した二地点間).
    rep(i, n) bfs(cells[i], i);
    
    // 5. bitDP(巡回セールスマン問題).
    // AtCoder Beginner Contest 180 (E - Traveling Salesman among Aerial Cities) 参照.
    // https://atcoder.jp/contests/abc180/editorial/154
    // スタート(0), お菓子の数(1 ～ n - 2 まで), ゴール(n - 1).
    // スタートは, フラグ(1) を 立てておく.
    // ex. 
    // n = 9
    // 訪問済マスの部分集合(s) が 10010010G -> 10010011G に変化する場合は, マス 3 or 6 から マス 7 へ 移動と解釈.
    int ans = -1;
    int dp[n - 1][1 << (n - 1)];
    rep(i, n - 1) rep(j, 1 << (n - 1)) dp[i][j] = INF;
    dp[0][1 << (n - 2)] = 0;
    repx(p, 1, n){
        // 5-1. (p + 1)個目 の マス を 訪問する場合は？
        repx(s, 1 << (n - 2), 1 << (n - 1)){
            // 訪問済マスの部分集合が, p個でない場合, Skip.
            if(__builtin_popcount(s) != p) continue;
            
            // 移動元 を マス i とする.
            rep(i, n - 1){
                int bef = 1 << (n - 2 - i);
                if(s & bef){
                    // 移動先 を マス j とする.
                    repx(j, 1, n - 1){
                        int cur = 1 << (n - 2 - j);
                        
                        // 未訪問の場合は, dp更新.
                        if(!(s & cur)) dp[j][s + cur] = min(dp[j][s + cur], dp[i][s] + memo[i][j]);
                    }
                }
            }
        }
        
        // 5-2. ゴール に 到着.
        int d = INF;
        repx(s, 1 << (n - 2), 1 << (n - 1)){
            // 訪問済マスの部分集合が, p個でない場合, Skip.
            if(__builtin_popcount(s) != p) continue;
            
            // ゴール直前のマスを全探索.
            rep(j, n - 1){
                int bef = 1 << (n - 2 - j);
                if(s & bef) d = min(d, dp[j][s] + memo[j][n - 1]);
            }
        }
        
        // 5-3. 最大値更新.
        // -> p は, スタート地点を含むので, 1個少ない値を指定.
        if(d <= T) ans = p - 1;
    }
    
    // 6. 出力.
    printf("%d\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

// 解き直し.

// https://atcoder.jp/contests/abc301/editorial/6343

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using P = pair<int, int>;

using vp = vector;

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

#define b second

const int INF = 1010101010;

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

char board[303][303];

int memo[22][22];

int main(){

// 1. 入力情報.

int H, W, T;

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

rep(i, H){

char c[303];

scanf("%s", c);

rep(j, W) board[i][j] = c[j];

}

// 2. マス(スタート, お菓子, ゴール)を保存.

vp cells;

rep(i, H) rep(j, W) if(board[i][j] == 'S') cells.pb({i, j});

rep(i, H) rep(j, W) if(board[i][j] == 'o') cells.pb({i, j});

rep(i, H) rep(j, W) if(board[i][j] == 'G') cells.pb({i, j});

int n = cells.size();

// 3. bfs.

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

auto bfs = [&](P s, int x) -> void {

// 訪問フラグ.

int v[303][303];

rep(i, H) rep(j, W) v[i][j] = INF;

// 空のキュー.

queue q;

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

v[s.a][s.b] = 0;

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

q.push(s);

while(!q.empty()){

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

P c = q.front();

q.pop();

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

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

rep(i, 4){

int nx = c.b + dx[i];

int ny = c.a + dy[i];

// 訪問不可能なマスは, スキップ.

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

// 未訪問のマスは, 最短距離を設定.

if(v[ny][nx] == INF) v[ny][nx] = v[c.a][c.b] + 1, q.push({ny, nx});

}

// 結果の保存.

rep(i, n) memo[x][i] = v[cells[i].a][cells[i].b];

};

// 4. 全探索(指定した二地点間).

rep(i, n) bfs(cells[i], i);

// 5. bitDP(巡回セールスマン問題).

// AtCoder Beginner Contest 180 (E - Traveling Salesman among Aerial Cities) 参照.

// https://atcoder.jp/contests/abc180/editorial/154

// スタート(0), お菓子の数(1 ～ n - 2 まで), ゴール(n - 1).

// スタートは, フラグ(1) を立てておく.

// ex.

// n = 9

// 訪問済マスの部分集合(s) が 10010010G -> 10010011G に変化する場合は, マス 3 or 6 からマス 7 へ移動と解釈.

int ans = -1;

int dp[n - 1][1 << (n - 1)];

rep(i, n - 1) rep(j, 1 << (n - 1)) dp[i][j] = INF;

dp[0][1 << (n - 2)] = 0;

repx(p, 1, n){

// 5-1. (p + 1)個目のマスを訪問する場合は？

repx(s, 1 << (n - 2), 1 << (n - 1)){

// 訪問済マスの部分集合が, p個でない場合, Skip.

if(__builtin_popcount(s) != p) continue;

// 移動元をマス i とする.

rep(i, n - 1){

int bef = 1 << (n - 2 - i);

if(s & bef){

// 移動先をマス j とする.

repx(j, 1, n - 1){

int cur = 1 << (n - 2 - j);

// 未訪問の場合は, dp更新.

if(!(s & cur)) dp[j][s + cur] = min(dp[j][s + cur], dp[i][s] + memo[i][j]);

}

// 5-2. ゴールに到着.

int d = INF;

repx(s, 1 << (n - 2), 1 << (n - 1)){

// 訪問済マスの部分集合が, p個でない場合, Skip.

if(__builtin_popcount(s) != p) continue;

// ゴール直前のマスを全探索.

rep(j, n - 1){

int bef = 1 << (n - 2 - j);

if(s & bef) d = min(d, dp[j][s] + memo[j][n - 1]);

}

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

// -> p は, スタート地点を含むので, 1個少ない値を指定.

if(d <= T) ans = p - 1;

}

// 6. 出力.

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

return 0;

}

[入力例]
3 3 5
S.G
o#o
.#.

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

[入力例]
3 3 1
S.G
.#o
o#.

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

[入力例]
5 10 2000000
S.o..ooo..
..o..o.o..
..o..ooo..
..o..o.o..
..o..ooo.G

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

[入力例]
12 10 15
......o.#.
##..#.....
.#..o..#..
.o........
..#...o#..
..S....#..
....o.....
#.#....#..
......o...
..#....#..
....G.o...
..#..#..#.

[出力例]
4

[入力例]
16 30 123
....#..............o.......G..
...o#..######.................
.............######....#......
#####........o....#....#......
.............#....#......o....
......#.#....#.........#.#.#..
......#.o.#................#..
........#.........#........#..
..........#.......#....#...#..
..........#............#......
..........#............#......
..........#............#......
###.#.....#............#......
...o#.....#............#......
....#.....#............#.#....
....#....S#............#.o....

[出力例]
7

[入力例]
100 100 2023
....................................................................................................
...........o........................................................................................
#################################################################################################.##
.................................#.o.#..............................................................
....S............................#...#....................................#...#.....................
..........................................................................#.o.#.....................
#################################################################################################.##
....................................................................................................
....................................................................................................
#############.##################################.######################################.############
.............................#......................................................................
#################################################################################################.##
.............................#............................................#.........................
.............................#...................o........................#.........................
................o............#............................................#.........................
..........................................................................#.........................
#########.###################################################.#####################################.
....................................................................................................
......#######.......................................................................................
......#.....#.......................................................................................
......#..o..#................................................................................o......
......#.....#.......................................................................................
......#.....#.......................................................................................
....................................................................................................
###.#########################################.#################################.####################
....................................................................................................
....................................................................................................
#################################################################################################.##
....................................................................................................
....................................................................................................
###############################################.####################################################
....................................................................................................
....................................................................................................
#################################################################################################.##
....................................................................................................
....................................................................................................
##.#################################################################################################
....................................................................................................
....................................................................................................
#################################################################################################.##
....................................................................................................
....................................................................................................
##.#################################################################################################
.....................................................................o..............................
....................................................................................................
..................................o.................................................................
....................................................................................................
#################################################################################################.##
....................................................................................................
....................................................................................................
##.#################################################################################################
....................................................................................................
....................................................................................................
..................................................................#######..................#...#....
.................###..#...........................................#..o..#..................#.o.#....
.................#....#...........................................#.....#..................#####....
.................#.o..#.............................................................................
#################################################################################################.##
....................................................................................................
....................................................................................................
##.#################################################################################################
............................................#o......................................................
............................................##......................................................
....................................................................................................
#################################################################################################.##
....................#...............................................................................
................#o..................................................................................
##.#################################################################################################
.......................................................................................#.o..#.......
.......................................................................................#....#.......
.......................................................................................#....#.......
.......................................................................................###..#.......
....................................................................................................
....................................................................................................
#################################################################################################.##
....................................................................................................
###.################################################################################################
....................................................................................................
.............................................................................##.#...................
.............................................................................#..#...................
.............................................................................#.o#...................
.............................................................................#..#...................
##.#################################################################################################
....................................................................................................
....................................................................................................
....................................................................................................
.####...............................................................................................
.#.o#...............................................................................................
.#..#...............................................................................................
....#............................................#..................................................
#################################################################################################.##
...........................#........#........#......................................................
..................................#.................................................................
..........................#....#.........#.......#..................................................
##.#################################################################################################
..................#............................................................................G....
........#....#............#.........................................................................
#################################################################################################.##
............................o..#....#.......#.......##........###...................................
...........................###........#.........##.......###........................................

[出力例]
15

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

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

[入力例]

3 3 5

S.G

o#o

.#.

[出力例]

※AtCoderテストケースより

[入力例]

3 3 1

S.G

.#o

o#.

[出力例]

-1

※AtCoderテストケースより

[入力例]

5 10 2000000

S.o..ooo..

..o..o.o..

..o..ooo..

..o..o.o..

..o..ooo.G

[出力例]

※AtCoderテストケースより

[入力例]

12 10 15

......o.#.

##..#.....

.#..o..#..

.o........

..#...o#..

..S....#..

....o.....

#.#....#..

......o...

..#....#..

....G.o...

..#..#..#.

[出力例]

[入力例]

16 30 123

....#..............o.......G..

...o#..######.................

.............######....#......

#####........o....#....#......

.............#....#......o....

......#.#....#.........#.#.#..

......#.o.#................#..

........#.........#........#..

..........#.......#....#...#..

..........#............#......

###.#.....#............#......

...o#.....#............#......

....#.....#............#.#....

....#....S#............#.o....

[出力例]

[入力例]

100 100 2023

....................................................................................................

...........o........................................................................................

#################################################################################################.##

.................................#.o.#..............................................................

....S............................#...#....................................#...#.....................

..........................................................................#.o.#.....................

#################################################################################################.##

....................................................................................................

#############.##################################.######################################.############

.............................#......................................................................

#################################################################################################.##

.............................#............................................#.........................

.............................#...................o........................#.........................

................o............#............................................#.........................

..........................................................................#.........................

#########.###################################################.#####################################.

....................................................................................................

......#######.......................................................................................

......#.....#.......................................................................................

......#..o..#................................................................................o......

......#.....#.......................................................................................

....................................................................................................

###.#########################################.#################################.####################

....................................................................................................

#################################################################################################.##

....................................................................................................

###############################################.####################################################

....................................................................................................

#################################################################################################.##

....................................................................................................

##.#################################################################################################

....................................................................................................

#################################################################################################.##

....................................................................................................

##.#################################################################################################

.....................................................................o..............................

....................................................................................................

..................................o.................................................................

....................................................................................................

#################################################################################################.##

....................................................................................................

##.#################################################################################################

....................................................................................................

..................................................................#######..................#...#....

.................###..#...........................................#..o..#..................#.o.#....

.................#....#...........................................#.....#..................#####....

.................#.o..#.............................................................................

#################################################################################################.##

....................................................................................................

##.#################################################################################################

............................................#o......................................................

............................................##......................................................

....................................................................................................

#################################################################################################.##

....................#...............................................................................

................#o..................................................................................

##.#################################################################################################

.......................................................................................#.o..#.......

.......................................................................................#....#.......

.......................................................................................###..#.......

....................................................................................................

#################################################################################################.##

....................................................................................................

###.################################################################################################

....................................................................................................

.............................................................................##.#...................

.............................................................................#..#...................

.............................................................................#.o#...................

.............................................................................#..#...................

##.#################################################################################################

....................................................................................................

.####...............................................................................................

.#.o#...............................................................................................

.#..#...............................................................................................

....#............................................#..................................................

#################################################################################################.##

...........................#........#........#......................................................

..................................#.................................................................

..........................#....#.........#.......#..................................................

##.#################################################################################################

..................#............................................................................G....

........#....#............#.........................................................................

#################################################################################################.##

............................o..#....#.......#.......##........###...................................

...........................###........#.........##.......###........................................

[出力例]

■参照サイト
パナソニックグループプログラミングコンテスト2023（AtCoder Beginner Contest 301）

2023年7月29日

C++ の動作確認をしてみた（９４８）

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

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

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

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
int cs[27], ct[27];

int main(){
    
    // 1. 入力情報.
    char s[202020], t[202020];
    scanf("%s %s", s, t);
    string S(s), T(t);
    int n = S.size();
    
    // 2. 出現数.
    rep(i, n){
        if(S[i] == '@') ++cs[26];
        else            ++cs[S[i] - 'a'];
        if(T[i] == '@') ++ct[26];
        else            ++ct[T[i] - 'a'];
    }
    
    // 3. atcoderのインデックス.
    set<int> st;
    st.insert('a' - 'a');
    st.insert('t' - 'a');
    st.insert('c' - 'a');
    st.insert('o' - 'a');
    st.insert('d' - 'a');
    st.insert('e' - 'a');
    st.insert('r' - 'a');
    
    // 4. atcoder以外の出現数が異なるか？
    rep(i, 26){
        if(st.count(i)) continue;
        if(cs[i] != ct[i]){
            puts("No");
            return 0;
        }
    }
    
    // 5. atcoderの出現数をチェック.
    // -> 過不足分を, 各文字列の '@' で補充.
    rep(i, 26){
        if(st.count(i)){
            if(cs[i] > ct[i]) ct[26] -= (cs[i] - ct[i]);
            if(cs[i] < ct[i]) cs[26] -= (ct[i] - cs[i]);
        }
    }
    
    // 6. 出力.
    printf("%s\n", (cs[26] >= 0 && ct[26] >= 0) ? "Yes" : "No");
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

int cs[27], ct[27];

int main(){

// 1. 入力情報.

char s[202020], t[202020];

scanf("%s %s", s, t);

string S(s), T(t);

int n = S.size();

// 2. 出現数.

rep(i, n){

if(S[i] == '@') ++cs[26];

else ++cs[S[i] - 'a'];

if(T[i] == '@') ++ct[26];

else ++ct[T[i] - 'a'];

}

// 3. atcoderのインデックス.

set<int> st;

st.insert('a' - 'a');

st.insert('t' - 'a');

st.insert('c' - 'a');

st.insert('o' - 'a');

st.insert('d' - 'a');

st.insert('e' - 'a');

st.insert('r' - 'a');

// 4. atcoder以外の出現数が異なるか？

rep(i, 26){

if(st.count(i)) continue;

if(cs[i] != ct[i]){

puts("No");

return 0;

}

// 5. atcoderの出現数をチェック.

// -> 過不足分を, 各文字列の '@' で補充.

rep(i, 26){

if(st.count(i)){

if(cs[i] > ct[i]) ct[26] -= (cs[i] - ct[i]);

if(cs[i] < ct[i]) cs[26] -= (ct[i] - cs[i]);

}

// 6. 出力.

printf("%s\n", (cs[26] >= 0 && ct[26] >= 0) ? "Yes" : "No");

return 0;

}

[入力例]
ch@ku@ai
choku@@i

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

[入力例]
ch@kud@i
akidu@ho

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

[入力例]
aoki
@ok@

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

[入力例]
aa
bb

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

[入力例]
innioiyauamrsaltuyuotyuurmiyfn
zlujjiziowsduanthdsfleopefpjwp

[出力例]
No

[入力例]
pqratcoder@@oo@@@aaaaa
@@@@pqr@@tt@@@@atcoder

[出力例]
Yes

[入力例]

ch@ku@ai

choku@@i

[出力例]

Yes

※AtCoderテストケースより

[入力例]

ch@kud@i

akidu@ho

[出力例]

Yes

※AtCoderテストケースより

[入力例]

aoki

@ok@

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

innioiyauamrsaltuyuotyuurmiyfn

zlujjiziowsduanthdsfleopefpjwp

[出力例]

[入力例]

pqratcoder@@oo@@@aaaaa

@@@@pqr@@tt@@@@atcoder

[出力例]

Yes

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

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

int main(){
    
    // 1. 入力情報.
    char s[66];
    LL N;
    scanf("%s %lld", s, &N);
    string S(s);
    int n = S.size();
    
    // 2. '1' を '0' に 読み替える.
    LL extra = 0;
    rep(i, n) if(S[i] == '1') extra += 1LL << (n - 1 - i);
    
    // 3. 例外.
    if(N < extra){
        puts("-1");
        return 0;
    }
    
    // 4. '?' を 決めていく.
    LL ans = 0, res = N - extra;
    rep(i, n){
        if(S[i] == '?'){
            LL bit = 1LL << (n - 1 - i);
            if(res >= bit){
                res -= bit;
                ans += bit;
            }
        }
    }
    
    // 5. '1' を 復元.
    ans += extra;
    
    // 6. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

int main(){

// 1. 入力情報.

char s[66];

LL N;

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

string S(s);

int n = S.size();

// 2. '1' を '0' に読み替える.

LL extra = 0;

rep(i, n) if(S[i] == '1') extra += 1LL << (n - 1 - i);

// 3. 例外.

if(N < extra){

puts("-1");

return 0;

}

// 4. '?' を決めていく.

LL ans = 0, res = N - extra;

rep(i, n){

if(S[i] == '?'){

LL bit = 1LL << (n - 1 - i);

if(res >= bit){

res -= bit;

ans += bit;

}

// 5. '1' を復元.

ans += extra;

// 6. 出力.

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

return 0;

}

[入力例]
?0?
2

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

[入力例]
101
4

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

[入力例]
?0?
1000000000000000000

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

[入力例]
?0?1?
20

[出力例]
19

[入力例]
??10?11??
365

[出力例]
351

[入力例]
?0?100?101??11??100?011??
20230729

[出力例]
19332911

[入力例]
??0????0010?0101??0?0?1?0?1001??1?1?10?0
202305132100

[出力例]
130289199098

[入力例]
1?0?1?1??01??101??1010?0101??0?0?1?0?1001??1?1?10?0?01?1??00
1000000000000000000

[出力例]
989629372091594108

[入力例]

?0?

[出力例]

※AtCoderテストケースより

[入力例]

101

[出力例]

-1

※AtCoderテストケースより

[入力例]

?0?

1000000000000000000

[出力例]

※AtCoderテストケースより

[入力例]

?0?1?

[出力例]

[入力例]

??10?11??

365

[出力例]

351

[入力例]

?0?100?101??11??100?011??

20230729

[出力例]

19332911

[入力例]

??0????0010?0101??0?0?1?0?1001??1?1?10?0

202305132100

[出力例]

130289199098

[入力例]

1?0?1?1??01??101??1010?0101??0?0?1?0?1001??1?1?10?0?01?1??00

1000000000000000000

[出力例]

989629372091594108

■参照サイト
パナソニックグループプログラミングコンテスト2023（AtCoder Beginner Contest 301）

2023年7月22日

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

C++の練習を兼ねて, AtCoder Regular Contest 164 の問題A (Ternary Decomposition) ～問題C (Reversible Card Game) を解いてみた.

■感想.
1. 問題A ～ C は, 方針が見えなかったので, 解説を参考に実装したところ, AC版に到達出来た.
2. 個人的には, 各問とも, 解説のロジックで解ける点が, 興味深く思った.
3. Union-Find木の復習が出来たので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc164/editorial/6635
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vl = vector<LL>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back

int main(){
    
    // 1. 入力情報.
    int T;
    scanf("%d", &T);
    
    // 2. 3 の 冪乗.
    vl pow3;
    pow3.pb(1);
    while(pow3.back() < 1e18) pow3.pb(pow3.back() * 3);
    // for(auto &x : pow3) printf("%lld\n", x);
    
    // 3. テストケース.
    rep(i, T){
        // 3-1. 各テストケース.
        LL N, K;
        scanf("%lld %lld", &N, &K);
        
        // 3-2. L を 計算.
        LL L = 0, cur = N;
        repr(i, pow3.size() - 1, 0){
            L += cur / pow3[i];
            cur %= pow3[i];
        }
        
        // 3-3. 判定.
        bool ok = true;
        if((N - K) & 1) ok = false;
        if(K < L)       ok = false;
        
        // 3-4. 出力.
        printf("%s\n", ok ? "Yes" : "No");
    }
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc164/editorial/6635

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vl = vector<LL>;

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

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

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

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

#define pb push_back

int main(){

// 1. 入力情報.

int T;

scanf("%d", &T);

// 2. 3 の冪乗.

vl pow3;

pow3.pb(1);

while(pow3.back() < 1e18) pow3.pb(pow3.back() * 3);

// for(auto &x : pow3) printf("%lld\n", x);

// 3. テストケース.

rep(i, T){

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

LL N, K;

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

// 3-2. L を計算.

LL L = 0, cur = N;

repr(i, pow3.size() - 1, 0){

L += cur / pow3[i];

cur %= pow3[i];

}

// 3-3. 判定.

bool ok = true;

if((N - K) & 1) ok = false;

if(K < L) ok = false;

// 3-4. 出力.

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

}

return 0;

}

[入力例]
4
5 3
17 2
163 79
1000000000000000000 1000000000000000000

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

[入力例]
20
7426863 17
10150951 5639271
9778798 15
5512894 2095080
10651982 5864016
11070422 3178139
5512162 9
2323820 550448
7350312 3507402
7220916 3729451
10744158 4787482
7857992 6880983
10461811 2006563
4086887 330608
5970335 1062393
6005971 2674798
12290876 9857165
11758323 9377833
4830691 10
11705751 1232255

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

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

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

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

[入力例]

5 3

17 2

163 79

1000000000000000000 1000000000000000000

[出力例]

Yes

※AtCoderのテストケースより

[入力例]

7426863 17

10150951 5639271

9778798 15

5512894 2095080

10651982 5864016

11070422 3178139

5512162 9

2323820 550448

7350312 3507402

7220916 3729451

10744158 4787482

7857992 6880983

10461811 2006563

4086887 330608

5970335 1062393

6005971 2674798

12290876 9857165

11758323 9377833

4830691 10

11705751 1232255

[出力例]

Yes

[入力例]

2023 1

2023 2

2023 3

2023 4

2023 5

2023 6

2023 7

2023 8

2023 9

2023 10

2023 11

2023 12

2023 13

2023 14

2023 15

2023 16

2023 17

2023 18

2023 19

2023 20

2023 21

2023 22

2023 23

2023 24

2023 25

2023 26

2023 27

2023 28

2023 29

2023 30

[出力例]

Yes

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

// 解き直し.
// https://atcoder.jp/contests/arc164/editorial/6633
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
using vi = vector<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

// 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);
    vp e(M);
    rep(i, M){
        scanf("%d %d", &e[i].a, &e[i].b);
        --e[i].a;
        --e[i].b;
    }
    int c[N];
    rep(i, N) scanf("%d", &c[i]);
    
    // 2. 異なる色の頂点間のみ辺を結ぶ.
    UnionFind uf(N + 2);
    rep(i, M) if(c[e[i].a] != c[e[i].b]) uf.unite(e[i].a, e[i].b);
    
    // 3. 同じ連結成分内に, 同じ色の頂点間の辺が存在するか？
    bool ok = false;
    rep(i, M){
        if(c[e[i].a] == c[e[i].b]){
            if(uf.same(e[i].a, e[i].b)){
                ok = true;
                break;
            }
        }
    }
    
    // 4. 出力.
    printf("%s\n", ok ? "Yes" : "No");
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc164/editorial/6633

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using P = pair<int, int>;

using vi = vector<int>;

using vp = vector;

#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

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

vp e(M);

rep(i, M){

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

--e[i].a;

--e[i].b;

}

int c[N];

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

// 2. 異なる色の頂点間のみ辺を結ぶ.

UnionFind uf(N + 2);

rep(i, M) if(c[e[i].a] != c[e[i].b]) uf.unite(e[i].a, e[i].b);

// 3. 同じ連結成分内に, 同じ色の頂点間の辺が存在するか？

bool ok = false;

rep(i, M){

if(c[e[i].a] == c[e[i].b]){

if(uf.same(e[i].a, e[i].b)){

ok = true;

break;

}

// 4. 出力.

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

return 0;

}

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

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

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

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

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

[出力例]
Yes

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

[出力例]
Yes

[入力例]

4 4

1 2

2 3

3 4

4 2

0 1 0 1

[出力例]

Yes

※AtCoderのテストケースより

[入力例]

5 6

1 2

2 3

3 4

4 5

1 4

2 5

0 1 0 1 0

[出力例]

※AtCoderのテストケースより

[入力例]

10 12

1 2

1 4

4 2

3 2

3 4

6 4

6 5

7 6

7 5

10 7

8 5

9 8

1 0 1 0 0 0 0 0 1 1

[出力例]

Yes

[入力例]

20 30

1 2

3 2

4 2

1 6

4 3

3 17

17 5

5 3

5 4

7 4

7 6

14 6

16 14

16 15

15 8

8 6

8 7

9 7

9 8

10 5

10 9

18 9

19 18

12 10

12 18

11 10

13 11

13 12

12 20

20 19

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

[出力例]

Yes

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

// 解き直し.
// https://atcoder.jp/contests/arc164/editorial/6632
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using P = pair<int, int>;
using vp = vector<P>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define a first
#define b second
const LL INF = 202020202020202020;

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vp v(N);
    rep(i, N) scanf("%d %d", &v[i].a, &v[i].b);
    
    // 2. A[i] > B[i] の 枚数は？
    int c = 0;
    rep(i, N) c += (v[i].a > v[i].b);
    
    // 3. 合計.
    LL ans = 0;
    rep(i, N) ans += max(v[i].a, v[i].b);
    
    // 4. c が 奇数.
    if(c & 1){
        LL a = 0, b = 0, d = INF;
        rep(i, N){
            if(d > abs(v[i].a - v[i].b)){
                d = abs(v[i].a - v[i].b);
                a = v[i].a;
                b = v[i].b;
            }
        }
        if(a < b) swap(a, b);
        ans -= a;
        ans += b;
    }
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc164/editorial/6632

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using P = pair<int, int>;

using vp = vector;

#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

const LL INF = 202020202020202020;

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vp v(N);

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

// 2. A[i] > B[i] の枚数は？

int c = 0;

rep(i, N) c += (v[i].a > v[i].b);

// 3. 合計.

LL ans = 0;

rep(i, N) ans += max(v[i].a, v[i].b);

// 4. c が奇数.

if(c & 1){

LL a = 0, b = 0, d = INF;

rep(i, N){

if(d > abs(v[i].a - v[i].b)){

d = abs(v[i].a - v[i].b);

a = v[i].a;

b = v[i].b;

}

if(a < b) swap(a, b);

ans -= a;

ans += b;

}

// 5. 出力.

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

return 0;

}

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

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

[入力例]
5
166971716 552987438
219878198 619875818
918378176 518975015
610749017 285601372
701849287 307601390

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

[入力例]
7
52 59
135 122
139 30
6 65
14 117
25 120
149 2

[出力例]
777

[入力例]
15
4862323 6596410
10091334 9475430
8026286 3722785
9697285 9634926
6126041 6139508
7726831 7922969
6938205 10026399
7559913 8125061
944108 555259
10266617 3004763
3333758 10086811
4775931 8535374
10116049 7211752
8485351 6963035
417896 8410694

[出力例]
123456789

[入力例]

6 4

2 1

5 3

[出力例]

※AtCoderのテストケースより

[入力例]

166971716 552987438

219878198 619875818

918378176 518975015

610749017 285601372

701849287 307601390

[出力例]

3078692091

※AtCoderのテストケースより

[入力例]

52 59

135 122

139 30

6 65

14 117

25 120

149 2

[出力例]

777

[入力例]

4862323 6596410

10091334 9475430

8026286 3722785

9697285 9634926

6126041 6139508

7726831 7922969

6938205 10026399

7559913 8125061

944108 555259

10266617 3004763

3333758 10086811

4775931 8535374

10116049 7211752

8485351 6963035

417896 8410694

[出力例]

123456789

■参照サイト
AtCoder Regular Contest 164
Union-Find木

2023年7月19日

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

C++の練習を兼ねて, AtCoder Beginner Contest 309 の問題C (Medicine) ～問題E (Family and Insurance) を解いてみた.

■感想.
1. 問題C ～ E は, 方針を絞り込めたので, AC版に到達できたと思う.
2. 個人的には, 幅優先探索, 深さ優先探索の訓練を積めたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

■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 a first
#define b second

int main(){
    
    // 1. 入力情報.
    int N;
    LL K;
    scanf("%d %lld", &N, &K);
    map<LL, LL> m;
    rep(i, N){
        LL a, b;
        scanf("%lld %lld", &a, &b);
        m[1] += b;
        m[a + 1] -= b;
    }
    
    // 2. K 錠以下となる日は？
    LL ans = 0, bef = 0;
    for(auto &x : m){
        if(bef + x.b <= K){
            ans = x.a;
            break;
        }
        bef += x.b;
    }
    
    // 3. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

#define a first

#define b second

int main(){

// 1. 入力情報.

int N;

LL K;

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

map<LL, LL> m;

rep(i, N){

LL a, b;

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

m[1] += b;

m[a + 1] -= b;

}

// 2. K 錠以下となる日は？

LL ans = 0, bef = 0;

for(auto &x : m){

if(bef + x.b <= K){

ans = x.a;

break;

}

bef += x.b;

}

// 3. 出力.

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

return 0;

}

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

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

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

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

[入力例]
15 158260522
877914575 2436426
24979445 61648772
623690081 33933447
476190629 62703497
211047202 71407775
628894325 31963982
822804784 50968417
430302156 82631932
161735902 80895728
923078537 7723857
189330739 10286918
802329211 4539679
303238506 17063340
492686568 73361868
125660016 50287940

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

[入力例]
20 50
35 89
113 68
12 91
47 39
50 102
31 44
113 70
45 66
100 93
80 68
51 93
105 17
74 99
112 68
47 106
119 121
86 36
95 13
76 48
17 10

[出力例]
120

[入力例]
30 123456789
7243344 39645001
110611721 58764066
54943571 7858259
27652310 45631404
108885402 58254068
63309952 54581014
14961992 64159015
50683657 90394950
114601656 67985265
27910507 21684920
14643649 75065657
81812380 68477230
99446454 110995892
28245926 89882812
19853288 72407860
9336074 108313969
56279010 58943019
32548337 96665548
90304960 21889493
32324555 100548176
50649146 67321897
14707156 3434551
119127221 33695514
70909013 99071221
15471945 54145916
110898063 49158872
15649382 75510226
21230601 28253500
71654589 9111419
120392263 8725587

[出力例]
110898064

100

101

102

103

104

105

[入力例]

4 8

6 3

2 5

1 9

4 2

[出力例]

※AtCoderテストケースより

[入力例]

4 100

6 3

2 5

1 9

4 2

[出力例]

※AtCoderテストケースより

[入力例]

15 158260522

877914575 2436426

24979445 61648772

623690081 33933447

476190629 62703497

211047202 71407775

628894325 31963982

822804784 50968417

430302156 82631932

161735902 80895728

923078537 7723857

189330739 10286918

802329211 4539679

303238506 17063340

492686568 73361868

125660016 50287940

[出力例]

492686569

※AtCoderテストケースより

[入力例]

20 50

35 89

113 68

12 91

47 39

50 102

31 44

113 70

45 66

100 93

80 68

51 93

105 17

74 99

112 68

47 106

119 121

86 36

95 13

76 48

17 10

[出力例]

120

[入力例]

30 123456789

7243344 39645001

110611721 58764066

54943571 7858259

27652310 45631404

108885402 58254068

63309952 54581014

14961992 64159015

50683657 90394950

114601656 67985265

27910507 21684920

14643649 75065657

81812380 68477230

99446454 110995892

28245926 89882812

19853288 72407860

9336074 108313969

56279010 58943019

32548337 96665548

90304960 21889493

32324555 100548176

50649146 67321897

14707156 3434551

119127221 33695514

70909013 99071221

15471945 54145916

110898063 49158872

15649382 75510226

21230601 28253500

71654589 9111419

120392263 8725587

[出力例]

110898064

■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

int main(){
    
    // 1. 入力情報.
    int N1, N2, M;
    scanf("%d %d %d", &N1, &N2, &M);
    int N = N1 + N2;
    vvi G(N);
    rep(i, M){
        int a, b;
        scanf("%d %d", &a, &b);
        --a;
        --b;
        G[a].pb(b);
        G[b].pb(a);
    }
    
    // 2. 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 &v : G[u]) if(!d[v] && v != s) d[v] = d[u] + 1, q.push(v);
        }
    };
    int d1[N], d2[N];
    rep(i, N) d1[i] = d2[i] = 0;
    bfs(G, 0, d1);
    bfs(G, N - 1, d2);
    
    // 3. 最大値は？
    int ans1 = 0, ans2 = 0;
    rep(i, N) ans1 = max(ans1, d1[i]);
    rep(i, N) ans2 = max(ans2, d2[i]);
    
    // 4. 出力.
    printf("%d\n", ans1 + ans2 + 1);
    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

int main(){

// 1. 入力情報.

int N1, N2, M;

scanf("%d %d %d", &N1, &N2, &M);

int N = N1 + N2;

vvi G(N);

rep(i, M){

int a, b;

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

--a;

--b;

G[a].pb(b);

G[b].pb(a);

}

// 2. 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 &v : G[u]) if(!d[v] && v != s) d[v] = d[u] + 1, q.push(v);

}

};

int d1[N], d2[N];

rep(i, N) d1[i] = d2[i] = 0;

bfs(G, 0, d1);

bfs(G, N - 1, d2);

// 3. 最大値は？

int ans1 = 0, ans2 = 0;

rep(i, N) ans1 = max(ans1, d1[i]);

rep(i, N) ans2 = max(ans2, d2[i]);

// 4. 出力.

printf("%d\n", ans1 + ans2 + 1);

return 0;

}

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

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

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

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

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

[出力例]
11

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

[出力例]
9

[入力例]

3 4 6

1 2

2 3

4 5

4 6

1 3

6 7

[出力例]

※AtCoderテストケースより

[入力例]

7 5 20

10 11

4 5

10 12

1 2

1 5

5 6

2 4

3 5

9 10

2 5

1 4

11 12

9 12

8 9

5 7

3 7

3 6

3 4

8 12

9 11

[出力例]

※AtCoderテストケースより

[入力例]

5 7 10

1 2

2 5

3 4

4 5

6 7

6 8

8 10

9 10

11 9

11 12

[出力例]

[入力例]

6 9 13

2 1

3 1

3 4

5 3

4 6

8 7

7 10

10 9

9 14

13 14

11 10

12 11

15 11

[出力例]

■C++版プログラム(問題E／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
int memo[303030], insurance[303030];

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    vvi G(N);
    repx(i, 1, N){
        int p;
        scanf("%d", &p);
        --p;
        G[i].pb(p);
        G[p].pb(i);
    }
    int y[N];
    rep(i, N) y[i] = -1;
    rep(i, M){
        int a, b;
        scanf("%d %d", &a, &b);
        --a;
        y[a] = max(y[a], b);
    }
    
    // 2. dfs.
    // https://ja.wikipedia.org/wiki/深さ優先探索
    function<void(vvi&, int, int, int)> dfs = [&](vvi &G, int cur, int bef, int d) {
        // 終了条件.
        if(memo[cur]) return;
        
        // 訪問済みフラグ.
        memo[cur] = 1;
        
        // 補償対象者か？
        if(d >= 0) ++insurance[cur];
        
        // 隣接頂点.
        for(auto &nex : G[cur]){
            if(nex == bef) continue;
            dfs(G, nex, cur, max(d - 1, y[nex]));
        }
    };
    dfs(G, 0, -1, y[0]);
    /*
    rep(i, N) printf("%d ", insurance[i]);
    puts("");
    */
    
    // 3. 集計.
    int ans = 0;
    rep(i, N) ans += (insurance[i] > 0);
    
    // 4. 出力.
    printf("%d\n", ans);
    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

int memo[303030], insurance[303030];

int main(){

// 1. 入力情報.

int N, M;

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

vvi G(N);

repx(i, 1, N){

int p;

scanf("%d", &p);

--p;

G[i].pb(p);

G[p].pb(i);

}

int y[N];

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

rep(i, M){

int a, b;

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

--a;

y[a] = max(y[a], b);

}

// 2. dfs.

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

function<void(vvi&, int, int, int)> dfs = [&](vvi &G, int cur, int bef, int d) {

// 終了条件.

if(memo[cur]) return;

// 訪問済みフラグ.

memo[cur] = 1;

// 補償対象者か？

if(d >= 0) ++insurance[cur];

// 隣接頂点.

for(auto &nex : G[cur]){

if(nex == bef) continue;

dfs(G, nex, cur, max(d - 1, y[nex]));

}

};

dfs(G, 0, -1, y[0]);

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

puts("");

// 3. 集計.

int ans = 0;

rep(i, N) ans += (insurance[i] > 0);

// 4. 出力.

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

return 0;

}

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

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

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

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

[入力例]
15 5
1 2 5 1 5 6 6 4 4 8 8 3 13 14
1 1
4 1
12 1
8 2
14 1

[出力例]
11

[入力例]
25 7
1 2 2 1 1 6 6 5 4 4 7 7 8 8 3 3 11 11 19 19 12 22 22 24
3 1
16 1
19 1
18 2
22 2
14 1
12 1

[出力例]
13

[入力例]

7 3

1 2 1 3 3 3

1 1

1 2

4 3

[出力例]

※AtCoderテストケースより

[入力例]

10 10

1 1 3 1 2 3 3 5 7

2 1

5 1

4 3

6 3

2 1

7 3

9 2

1 2

6 2

8 1

[出力例]

※AtCoderテストケースより

[入力例]

15 5

1 2 5 1 5 6 6 4 4 8 8 3 13 14

1 1

4 1

12 1

8 2

14 1

[出力例]

[入力例]

25 7

1 2 2 1 1 6 6 5 4 4 7 7 8 8 3 3 11 11 19 19 12 22 22 24

3 1

16 1

19 1

18 2

22 2

14 1

12 1

[出力例]

■参照サイト
デンソークリエイトプログラミングコンテスト2023（AtCoder Beginner Contest 309）

C++の練習を兼ねて, AtCoder Grand Contest 049 の 問題A (Erasing Vertices) ～ 問題B (Flip Digits) を解いてみた.

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

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

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

C++の練習を兼ねて, AtCoder Beginner Contest 306 の 問題C (Centers) ～ 問題E (Best Performances) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 143 の 問題C (Piles of Pebbles) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 301 の 問題E (Pac-Takahashi) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 164 の 問題A (Ternary Decomposition) ～ 問題C (Reversible Card Game) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 309 の 問題C (Medicine) ～ 問題E (Family and Insurance) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 049 の問題A (Erasing Vertices) ～問題B (Flip Digits) を解いてみた.

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

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

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

C++の練習を兼ねて, AtCoder Beginner Contest 306 の問題C (Centers) ～問題E (Best Performances) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 143 の問題C (Piles of Pebbles) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 301 の問題E (Pac-Takahashi) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 164 の問題A (Ternary Decomposition) ～問題C (Reversible Card Game) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 309 の問題C (Medicine) ～問題E (Family and Insurance) を解いてみた.