C++ | 個人用メモ帳

2022年2月5日

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

C++の練習を兼ねて, AtCoder Beginner Contest 020 の問題C (壁抜け) を解いてみた.

■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 二分探索, ワーシャル–フロイド法の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://www.slideshare.net/chokudai/abc020
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vs = vector<string>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back

int main() {
    
    // 1. 入力情報.
    int H, W, T;
    scanf("%d %d %d", &H, &W, &T);
    int sx, sy, gx, gy, A = H * W;
    vs board;
    rep(i, H){
        char c[22];
        scanf("%s", c);
        string s(c);
        rep(j, W){
            // スタート地点, ゴール地点を設定.
            if(s[j] == 'S') sx = i, sy = j, s[j] = '.';
            if(s[j] == 'G') gx = i, gy = j, s[j] = '.';
        }
        board.pb(s);
    }
    
    // 2. スタート地点, ゴール地点.
    int s = sx * W + sy;
    int g = gx * W + gy;
    
    // 3. 評価関数.
    auto f = [&](LL m) -> bool {
        // 3-1. グラフ作成.
        LL G[A][A];
        rep(i, A) rep(j, A) G[i][j] = 2e10 + 1;
        rep(i, H){
            rep(j, W){
                // 出発地点.
                int cur = i * W + j;
                
                // 到達地点(上).
                if(i) G[cur][cur - W] = (board[i][j] == '#') ? m : 1;
                
                // 到達地点(下).
                if(i < H - 1) G[cur][cur + W] = (board[i][j] == '#') ? m : 1;
                
                // 到達地点(左).
                if(j) G[cur][cur - 1] = (board[i][j] == '#') ? m : 1;
                
                // 到達地点(右).
                if(j < W - 1) G[cur][cur + 1] = (board[i][j] == '#') ? m : 1;
            }
        }
        
        // 3-2. Warshall–Floyd法(※各頂点間の最短距離を保存).
        rep(k, A) rep(i, A) rep(j, A) G[i][j] = min(G[i][j], G[i][k] + G[k][j]);
        
        // 3-3. 判定結果.
        return (G[s][g] <= (LL)T);
    };
    
    // 4. 二分探索で確認してみる.
    LL l = 0, h = 2e9 + 1;
    while(l + 1 < h){
        LL m = (h + l) >> 1;
        if(f(m)) l = m;
        else     h = m;
        // printf("h=%lld l=%lld m=%lld\n", h, l, m);
    }
    
    // 5. 出力.
    printf("%lld\n", l);
    return 0;
    
}

// 解き直し.

// https://www.slideshare.net/chokudai/abc020

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vs = vector<string>;

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

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

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

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

#define pb push_back

int main() {

// 1. 入力情報.

int H, W, T;

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

int sx, sy, gx, gy, A = H * W;

vs board;

rep(i, H){

char c[22];

scanf("%s", c);

string s(c);

rep(j, W){

// スタート地点, ゴール地点を設定.

if(s[j] == 'S') sx = i, sy = j, s[j] = '.';

if(s[j] == 'G') gx = i, gy = j, s[j] = '.';

}

board.pb(s);

}

// 2. スタート地点, ゴール地点.

int s = sx * W + sy;

int g = gx * W + gy;

// 3. 評価関数.

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

// 3-1. グラフ作成.

LL G[A][A];

rep(i, A) rep(j, A) G[i][j] = 2e10 + 1;

rep(i, H){

rep(j, W){

// 出発地点.

int cur = i * W + j;

// 到達地点(上).

if(i) G[cur][cur - W] = (board[i][j] == '#') ? m : 1;

// 到達地点(下).

if(i < H - 1) G[cur][cur + W] = (board[i][j] == '#') ? m : 1;

// 到達地点(左).

if(j) G[cur][cur - 1] = (board[i][j] == '#') ? m : 1;

// 到達地点(右).

if(j < W - 1) G[cur][cur + 1] = (board[i][j] == '#') ? m : 1;

}

// 3-2. Warshall–Floyd法(※各頂点間の最短距離を保存).

rep(k, A) rep(i, A) rep(j, A) G[i][j] = min(G[i][j], G[i][k] + G[k][j]);

// 3-3. 判定結果.

return (G[s][g] <= (LL)T);

};

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

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

while(l + 1 < h){

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

if(f(m)) l = m;

else h = m;

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

}

// 5. 出力.

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

return 0;

}

[入力例]
2 3 10
S##
.#G

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

[入力例]
3 4 7
S##G
.##.
..#.

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

[入力例]
4 4 1000000000
S###
####
####
###G

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

[入力例]
7 9 30
.#.#.#...
S...#.#.#
.#.#.#...
....#.#.#
.#.#.#...
....#.#.#
.#.#.#.G.

[出力例]
10

[入力例]
7 8 2022
###.####
..#.#..#
S.#.#..#
###.#.G#
#...#..#
#...#..#
###.####

[出力例]
1008

[入力例]
15 19 20220205
.#.#.#.#.#.#.#.#.#.
#S#.#.#.#.#.#.#.#.#
.#.#.#.#.#.#.#.#.#.
####.####.####.####
#..#.#..#.#..#.#..#
...#.#..#....#....#
...#.#..#....#....#
####.#..#.####.####
#....#..#.#....#...
#....#..#.#....#.G.
#..#.#..#.#..#.#..#
####.####.####.####
.#.#.#.#.#.#.#.#.#.
#.#.#.#.#.#.#.#.#.#
.#.#.#.#.#.#.#.#.#.

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

[入力例]

2 3 10

S##

.#G

[出力例]

※AtCoderテストケースより

[入力例]

3 4 7

S##G

.##.

..#.

[出力例]

※AtCoderテストケースより

[入力例]

4 4 1000000000

S###

####

###G

[出力例]

199999999

※AtCoderテストケースより

[入力例]

7 9 30

.#.#.#...

S...#.#.#

.#.#.#...

....#.#.#

.#.#.#...

....#.#.#

.#.#.#.G.

[出力例]

[入力例]

7 8 2022

###.####

..#.#..#

S.#.#..#

###.#.G#

#...#..#

###.####

[出力例]

1008

[入力例]

15 19 20220205

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[出力例]

3370031

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

■参照サイト
AtCoder Beginner Contest 020

2022年2月4日2022年2月4日

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

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

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

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

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

// 解き直し.
// https://img.atcoder.jp/arc075/editorial.pdf
// 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 h[101010];

int main(){
    
    // 1. 入力情報.
    int N;
    LL A, B, C;
    scanf("%d %lld %lld", &N, &A, &B);
    rep(i, N) scanf("%lld", &h[i]);
    C = A - B;
    
    // 2. 評価関数.
    auto f = [&](LL m) -> bool {
        // 2-1. すべての魔物を消すまでに必要な追加ダメージの回数.
        LL c = 0;
        rep(i, N){
            // オーバーフロー注意(b05など).
            if(h[i] / B < m) continue;
            
            // h[i] - B * m が マイナスになる場合があるので, 最小値が, 0以上になるように設定.
            c += (max(0LL, h[i] - B * m) + C - 1) / C;
        }
        
        // 2-2. 判定結果.
        return (c > m);
    };
    
    // 3. 二分探索で確認してみる.
    LL l = 0, h = 2e14 + 1;
    while(l + 1 < h){
        LL m = (h + l) >> 1;
        if(f(m)) l = m;
        else     h = m;
    }
    
    // 4. 出力.
    printf("%lld\n", h);
    return 0;
    
}

// 解き直し.

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

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

int main(){

// 1. 入力情報.

int N;

LL A, B, C;

scanf("%d %lld %lld", &N, &A, &B);

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

C = A - B;

// 2. 評価関数.

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

// 2-1. すべての魔物を消すまでに必要な追加ダメージの回数.

LL c = 0;

rep(i, N){

// オーバーフロー注意(b05など).

if(h[i] / B < m) continue;

// h[i] - B * m がマイナスになる場合があるので, 最小値が, 0以上になるように設定.

c += (max(0LL, h[i] - B * m) + C - 1) / C;

}

// 2-2. 判定結果.

return (c > m);

};

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

LL l = 0, h = 2e14 + 1;

while(l + 1 < h){

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

if(f(m)) l = m;

else h = m;

}

// 4. 出力.

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

return 0;

}

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

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

[入力例]
2 10 4
20
20

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

[入力例]
5 2 1
900000000
900000000
1000000000
1000000000
1000000000

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

[入力例]
7 8 3
23
32
25
37
17
41
38

[出力例]
9

[入力例]
12 100 55
1733
1817
268
1888
1777
825
1721
540
577
1878
1196
1460

[出力例]
30

[入力例]
25 2022 204
205123
154135
42005
6863
69228
141645
116545
215186
148147
172380
26341
156062
182894
61486
9438
166504
195100
58700
15849
59630
90575
204007
165483
17712
39094

[出力例]
500

[入力例]

4 5 3

[出力例]

※AtCoderテストケースより

[入力例]

2 10 4

[出力例]

※AtCoderテストケースより

[入力例]

5 2 1

900000000

1000000000

[出力例]

800000000

※AtCoderテストケースより

[入力例]

7 8 3

[出力例]

[入力例]

12 100 55

1733

1817

268

1888

1777

825

1721

540

577

1878

1196

1460

[出力例]

[入力例]

25 2022 204

205123

154135

42005

6863

69228

141645

116545

215186

148147

172380

26341

156062

182894

61486

9438

166504

195100

58700

15849

59630

90575

204007

165483

17712

39094

[出力例]

500

■参照サイト
AtCoder Regular Contest 075

2022年2月4日

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

C++の練習を兼ねて, AtCoder Beginner Contest 099 の問題C (Strange Bank) を解いてみた.

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

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

■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 bank[12] = {59049, 46656, 7776, 6561, 1296, 729, 216, 81, 36, 9, 6, 1};
int dp[101010][12];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    
    // 2. 初期化.
    repx(i, 1, N + 1) rep(j, 12) dp[i][j] = 101010;
    
    // 3. dp更新.
    // -> 銀行で取引可能な, 12通りの金額を, i円 に 着目して, 見ていく.
    rep(i, N + 1){
        rep(j, 12){
            rep(k, 12){
                int c = bank[j] + i;
                if(c <= N) dp[c][j] = min(dp[c][j], dp[i][k] + 1);
            }
        }
    }
    
    // 4. 操作回数の最小値は？
    int ans = 101010;
    rep(j, 12) ans = min(ans, dp[N][j]);
    
    // 5. 出力.
    printf("%d\n", ans);
    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 bank[12] = {59049, 46656, 7776, 6561, 1296, 729, 216, 81, 36, 9, 6, 1};

int dp[101010][12];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

// 2. 初期化.

repx(i, 1, N + 1) rep(j, 12) dp[i][j] = 101010;

// 3. dp更新.

// -> 銀行で取引可能な, 12通りの金額を, i円に着目して, 見ていく.

rep(i, N + 1){

rep(j, 12){

rep(k, 12){

int c = bank[j] + i;

if(c <= N) dp[c][j] = min(dp[c][j], dp[i][k] + 1);

}

// 4. 操作回数の最小値は？

int ans = 101010;

rep(j, 12) ans = min(ans, dp[N][j]);

// 5. 出力.

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

return 0;

}

[入力例]
127

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

[入力例]
3

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

[入力例]
44852

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

[入力例]
2022

[出力例]
7

[入力例]
100000

[出力例]
7

[入力例]
70707

[出力例]
11

[入力例]

127

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

44852

[出力例]

※AtCoderテストケースより

[入力例]

2022

[出力例]

[入力例]

100000

[出力例]

[入力例]

70707

[出力例]

■参照サイト
AtCoder Beginner Contest 099

2022年2月2日

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

C++の練習を兼ねて, AtCoder Beginner Contest 120 の問題D (Decayed Bridges) を解いてみた.

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

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

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

// 解き直し.
// https://img.atcoder.jp/abc120/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
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 ans[101010];
int a[101010], b[101010];

// 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);
    rep(i, M){
        scanf("%d %d", &a[i], &b[i]);
        --a[i];
        --b[i];
    }
    
    // 2. 不便さは？
    ans[M] = (LL)N * (LL)(N - 1) / 2;
    UnionFind uf(N + 2);
    repr(i, M - 1, 0){
        // 2-1. 頂点情報.
        int u = a[i];
        int v = b[i];
        
        // 2-2. 連結だった.
        // -> 不便さ変わらない.
        if(uf.same(u, v)) ans[i] = ans[i + 1];
        
        // 2-3. 連結でなかった.
        if(!uf.same(u, v)){
            // グループ番号.
            int g1 = uf.find(u);
            int g2 = uf.find(v);
            
            // グループサイズ.
            LL n1 = (LL)uf.size(g1);
            LL n2 = (LL)uf.size(g2);
            
            // 不便さ更新.
            ans[i] = ans[i + 1] - n1 * n2;
            
            // 連結.
            uf.unite(u, v);
        }
    }
    
    // 3. 出力.
    repx(i, 1, M + 1) printf("%lld\n", ans[i]);
    return 0;
    
}

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

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

int a[101010], b[101010];

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

rep(i, M){

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

--a[i];

--b[i];

}

// 2. 不便さは？

ans[M] = (LL)N * (LL)(N - 1) / 2;

UnionFind uf(N + 2);

repr(i, M - 1, 0){

// 2-1. 頂点情報.

int u = a[i];

int v = b[i];

// 2-2. 連結だった.

// -> 不便さ変わらない.

if(uf.same(u, v)) ans[i] = ans[i + 1];

// 2-3. 連結でなかった.

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

// グループ番号.

int g1 = uf.find(u);

int g2 = uf.find(v);

// グループサイズ.

LL n1 = (LL)uf.size(g1);

LL n2 = (LL)uf.size(g2);

// 不便さ更新.

ans[i] = ans[i + 1] - n1 * n2;

// 連結.

uf.unite(u, v);

}

// 3. 出力.

repx(i, 1, M + 1) printf("%lld\n", ans[i]);

return 0;

}

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

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

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

[出力例]
8
9
12
14
15
※AtCoderテストケースより

[入力例]
2 1
1 2

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

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

[出力例]
12
14
17
18
20
21

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

[出力例]
9
17
24
30
35
41
42
44
45

[入力例]

4 5

1 2

3 4

1 3

2 3

1 4

[出力例]

※AtCoderテストケースより

[入力例]

6 5

2 3

1 2

5 6

3 4

4 5

[出力例]

※AtCoderテストケースより

[入力例]

2 1

1 2

[出力例]

※AtCoderテストケースより

[入力例]

7 6

1 2

1 3

2 4

3 5

4 6

6 7

[出力例]

[入力例]

10 9

1 2

3 4

2 5

5 7

5 6

6 8

8 9

6 10

3 6

[出力例]

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

2022年2月1日2022年2月1日

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

C++の練習を兼ねて, AtCoder Beginner Contest 235 の問題F (Variety of Digits) を解いてみた.

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

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

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

// 解き直し.
// https://atcoder.jp/contests/abc235/editorial/3247
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vi = vector<int>;
using vl = vector<LL>;
using P = pair<LL, LL>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define a first
#define b second
const LL MOD = 998244353;
// { 上からの桁数, 出現した数字の集合, N より小さいか？ }
P dp[10101][1 << 10][2];

int main(){
    
    // 1. 入力情報.
    char c[10101];
    int M;
    scanf("%s %d", c, &M);
    vi C(M);
    rep(i, M) scanf("%d", &C[i]);
    string N(c);
    int n = N.size();
    
    // 2. 検証用プログラム.
    // ex.
    // 20220201
    // 5
    // 0 1 2 5 7
    // -> 7288259901580 となるが, MOD で見ると, 77880327 となるはず.
    /*
    if(n < 9){
        LL t = 0;
        int x = stoi(N);
        repx(i, 1, x + 1){
            string si = to_string(i);
            int ok = 0;
            for(auto &p : C){
                rep(j, n){
                    if((si[j] - '0') == p){
                        ok++;
                        break;
                    }
                }
            }
            if(ok >= M) t += i;
        }
        printf("t=%lld\n", t);
    }
    */
    
    // 3. 10 の 冪乗.
    vl mPow10;
    mPow10.pb(1);
    while(mPow10.size() <= n) mPow10.pb(10 * mPow10.back() % MOD);
    // for(auto &p : mPow10) printf("%lld\n", p);
    
    // 4. 桁DP.
    // 4-1. 0桁目(空集合).
    dp[0][0][0] = {1, 0};
    
    // 4-2. i桁目(1 ～ N桁).
    rep(i, n){
        // 出現した数字(i桁目).
        int d = N[i] - '0';
        
        // 前回分反映.
        dp[i + 1][0][0] = dp[i][0][0];
        
        // 出現した数字(0 ～ 9).
        rep(j, 10){
            // 数字の集合(前回分反映).
            rep(s, 1 << 10){
                // 今まで, すべて 0 だった場合で, 今回も 0 だった場合.
                if(!j && !s) continue;
                
                // 数字の集合(今回分反映).
                int ns = s | (1 << (9 - j));
                
                // 1桁目.
                if(!s && !i){
                    // 出現した数字未満.
                    if(j < d){
                        dp[i + 1][ns][0].a = 1;
                        dp[i + 1][ns][0].b = mPow10[n - 1 - i] * j;
                    }
                    
                    // 出現した数字.
                    if(j == d){
                        dp[i + 1][ns][1].a = 1;
                        dp[i + 1][ns][1].b = mPow10[n - 1 - i] * j;
                    }
                }
                
                // 2桁目以降.
                if(i){
                    // 既に, N より小さいと確定していれば, 0 ～ 9 まで見て, OK.
                    if(dp[i][s][0].a){
                        dp[i + 1][ns][0].a += dp[i][s][0].a;
                        dp[i + 1][ns][0].a %= MOD;
                        dp[i + 1][ns][0].b += (mPow10[n - 1 - i] * j * dp[i][s][0].a + dp[i][s][0].b);
                        dp[i + 1][ns][0].b %= MOD;
                    }
                    
                    // N より小さいと確定するか, 確認.
                    if(dp[i][s][1].a){
                        // N より小さいと確定する場合, 出現した数字未満 まで見て, OK.
                        if(j < d){
                            dp[i + 1][ns][0].a += dp[i][s][1].a;
                            dp[i + 1][ns][0].a %= MOD;
                            dp[i + 1][ns][0].b += (mPow10[n - 1 - i] * j * dp[i][s][1].a + dp[i][s][1].b);
                            dp[i + 1][ns][0].b %= MOD;
                        }
                        
                        // 既に, N より小さいと確定してなければ, 出現した数字を, 未確定に反映.
                        if(j == d){
                            dp[i + 1][ns][1].a += dp[i][s][1].a;
                            dp[i + 1][ns][1].a %= MOD;
                            dp[i + 1][ns][1].b += (mPow10[n - 1 - i] * j * dp[i][s][1].a + dp[i][s][1].b);
                            dp[i + 1][ns][1].b %= MOD;
                        }
                        
                        // 出現した数字よりも大きい.
                        // 何もしない.
                    }
                }
            }
        }
    }
    
    // 5. 集計.
    LL ans = 0;
    rep(i, 1 << 10){
        bool ok = true;
        for(auto &p : C) if(!(i & (1 << (10 - 1 - p)))) ok = false;
        if(ok) rep(k, 2) ans += dp[n][i][k].b, ans %= MOD;
    }
    
    // 6. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vi = vector<int>;

using vl = vector<LL>;

using P = pair<LL, LL>;

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

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

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

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

#define pb push_back

#define a first

#define b second

const LL MOD = 998244353;

// { 上からの桁数, 出現した数字の集合, N より小さいか？ }

P dp[10101][1 << 10][2];

int main(){

// 1. 入力情報.

char c[10101];

int M;

scanf("%s %d", c, &M);

vi C(M);

rep(i, M) scanf("%d", &C[i]);

string N(c);

int n = N.size();

// 2. 検証用プログラム.

// ex.

// 20220201

// 5

// 0 1 2 5 7

// -> 7288259901580 となるが, MOD で見ると, 77880327 となるはず.

if(n < 9){

LL t = 0;

int x = stoi(N);

repx(i, 1, x + 1){

string si = to_string(i);

int ok = 0;

for(auto &p : C){

rep(j, n){

if((si[j] - '0') == p){

ok++;

break;

}

if(ok >= M) t += i;

}

printf("t=%lld\n", t);

}

// 3. 10 の冪乗.

vl mPow10;

mPow10.pb(1);

while(mPow10.size() <= n) mPow10.pb(10 * mPow10.back() % MOD);

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

// 4. 桁DP.

// 4-1. 0桁目(空集合).

dp[0][0][0] = {1, 0};

// 4-2. i桁目(1 ～ N桁).

rep(i, n){

// 出現した数字(i桁目).

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

// 前回分反映.

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

// 出現した数字(0 ～ 9).

rep(j, 10){

// 数字の集合(前回分反映).

rep(s, 1 << 10){

// 今まで, すべて 0 だった場合で, 今回も 0 だった場合.

if(!j && !s) continue;

// 数字の集合(今回分反映).

int ns = s | (1 << (9 - j));

// 1桁目.

if(!s && !i){

// 出現した数字未満.

if(j < d){

dp[i + 1][ns][0].a = 1;

dp[i + 1][ns][0].b = mPow10[n - 1 - i] * j;

}

// 出現した数字.

if(j == d){

dp[i + 1][ns][1].a = 1;

dp[i + 1][ns][1].b = mPow10[n - 1 - i] * j;

}

// 2桁目以降.

if(i){

// 既に, N より小さいと確定していれば, 0 ～ 9 まで見て, OK.

if(dp[i][s][0].a){

dp[i + 1][ns][0].a += dp[i][s][0].a;

dp[i + 1][ns][0].a %= MOD;

dp[i + 1][ns][0].b += (mPow10[n - 1 - i] * j * dp[i][s][0].a + dp[i][s][0].b);

dp[i + 1][ns][0].b %= MOD;

}

// N より小さいと確定するか, 確認.

if(dp[i][s][1].a){

// N より小さいと確定する場合, 出現した数字未満まで見て, OK.

if(j < d){

dp[i + 1][ns][0].a += dp[i][s][1].a;

dp[i + 1][ns][0].a %= MOD;

dp[i + 1][ns][0].b += (mPow10[n - 1 - i] * j * dp[i][s][1].a + dp[i][s][1].b);

dp[i + 1][ns][0].b %= MOD;

}

// 既に, N より小さいと確定してなければ, 出現した数字を, 未確定に反映.

if(j == d){

dp[i + 1][ns][1].a += dp[i][s][1].a;

dp[i + 1][ns][1].a %= MOD;

dp[i + 1][ns][1].b += (mPow10[n - 1 - i] * j * dp[i][s][1].a + dp[i][s][1].b);

dp[i + 1][ns][1].b %= MOD;

}

// 出現した数字よりも大きい.

// 何もしない.

}

// 5. 集計.

LL ans = 0;

rep(i, 1 << 10){

bool ok = true;

for(auto &p : C) if(!(i & (1 << (10 - 1 - p)))) ok = false;

if(ok) rep(k, 2) ans += dp[n][i][k].b, ans %= MOD;

}

// 6. 出力.

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

return 0;

}

[入力例]
104
2
0 1

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

[入力例]
999
4
1 2 3 4

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

[入力例]
1234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890
5
0 2 4 6 8

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

[入力例]
200
2
1 3

[出力例]
2736

[入力例]
213
2
1 3

[出力例]
2949

[入力例]
333
2
1 7

[出力例]
3981

[入力例]
1234
3
2 5 7

[出力例]
3108

[入力例]
2022
4
1 2 5 8

[出力例]
9330

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

[出力例]
77880327

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

[出力例]
124345832

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

[出力例]
149319298

[入力例]
31415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823066470938446095505822317253594081284811174502841027019385211055596446229489549303819644288109756659334461284756482337867831652712019091456485669234603486104543266482133936072602491412737245870066063155881748815209209628292540917153643678925903600113305305488204665213841469519415116094330572703657595919530921861173819326117931051185480744623799627495673518857527248912279381830119491
7
0 1 2 3 5 7 8

[出力例]
736535933

[入力例]

104

0 1

[出力例]

520

※AtCoderテストケースより

[入力例]

999

1 2 3 4

[出力例]

※AtCoderテストケースより

[入力例]

1234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890

0 2 4 6 8

[出力例]

397365274

※AtCoderテストケースより

[入力例]

200

1 3

[出力例]

2736

[入力例]

213

1 3

[出力例]

2949

[入力例]

333

1 7

[出力例]

3981

[入力例]

1234

2 5 7

[出力例]

3108

[入力例]

2022

1 2 5 8

[出力例]

9330

[入力例]

20220201

0 1 2 5 7

[出力例]

77880327

[入力例]

22360679

1 2 3 4 5

[出力例]

124345832

[入力例]

32100123

0 1 3 5 7 9

[出力例]

149319298

[入力例]

31415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823066470938446095505822317253594081284811174502841027019385211055596446229489549303819644288109756659334461284756482337867831652712019091456485669234603486104543266482133936072602491412737245870066063155881748815209209628292540917153643678925903600113305305488204665213841469519415116094330572703657595919530921861173819326117931051185480744623799627495673518857527248912279381830119491

0 1 2 3 5 7 8

[出力例]

736535933

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

2022年1月31日

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

C++の練習を兼ねて, AtCoder Beginner Contest 237 の問題C (kasaka) ～問題D (LR insertion) を解いてみた.

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

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

■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 main(){
    
    // 1. 入力情報.
    char s[1010101];
    scanf("%s", s);
    string S(s);
    int n = S.size();
    
    // 2. 左側, 右側の連続する a の 個数.
    int l = 0, r = 0;
    rep(i, n){
        if(S[i] == 'a') l++;
        else            break;
    }
    repr(i, n - 1, 0){
        if(S[i] == 'a') r++;
        else            break;
    }
    
    // 3. 先頭に, "a" を 追加.
    string a(max(0, r - l), 'a');
    S = a + S;
    
    // 4. 回文判定.
    bool ok = true;
    n = S.size();
    rep(i, n / 2){
        if(S[i] != S[n - 1 - i]){
            ok = false;
            break;
        }
    }
    
    // 5. 出力.
    printf("%s\n", ok ? "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 main(){

// 1. 入力情報.

char s[1010101];

scanf("%s", s);

string S(s);

int n = S.size();

// 2. 左側, 右側の連続する a の個数.

int l = 0, r = 0;

rep(i, n){

if(S[i] == 'a') l++;

else break;

}

repr(i, n - 1, 0){

if(S[i] == 'a') r++;

else break;

}

// 3. 先頭に, "a" を追加.

string a(max(0, r - l), 'a');

S = a + S;

// 4. 回文判定.

bool ok = true;

n = S.size();

rep(i, n / 2){

if(S[i] != S[n - 1 - i]){

ok = false;

break;

}

// 5. 出力.

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

return 0;

}

[入力例]
kasaka

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

[入力例]
atcoder

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

[入力例]
php

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

[入力例]
atblhqkpcahhacpkqhlbtaaaa

[出力例]
Yes

[入力例]
adfyrropcrwceybofnluxjsjxulnfobyecwrcporryfdaaaa

[出力例]
Yes

[入力例]

kasaka

[出力例]

Yes

※AtCoderテストケースより

[入力例]

atcoder

[出力例]

※AtCoderテストケースより

[入力例]

php

[出力例]

Yes

※AtCoderテストケースより

[入力例]

atblhqkpcahhacpkqhlbtaaaa

[出力例]

Yes

[入力例]

adfyrropcrwceybofnluxjsjxulnfobyecwrcporryfdaaaa

[出力例]

Yes

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pob pop_back
#define pof pop_front
#define pub push_back
#define puf push_front

int main(){
    
    // 1. 入力情報.
    int N;
    char s[505050];
    scanf("%d %s", &N, s);
    
    // 2. 操作.
    deque<int> dqL, dqR;
    dqL.pub(0);
    rep(i, N){
        // 'L' の 時.
        if(s[i] == 'L'){
            // 左側に, i が ある.
            if(dqL.back() == i){
                dqR.puf(i);
                dqL.pob();
                dqL.pub(i + 1);
                continue;
            }
            
            // 右側に, i が ある.
            if(dqR.front() == i) dqL.pub(i + 1);
        }
        
        // 'R' の 時.
        if(s[i] == 'R'){
            // 右側が, 空の場合.
            // -> 001.txt などで, WA版となったため, 修正.
            if(dqR.empty()){
                dqR.puf(i + 1);
                continue;
            }
            
            // 右側に, i が ある.
            if(dqR.front() == i){
                dqL.pub(i);
                dqR.pof();
                dqR.puf(i + 1);
                continue;
            }
            
            // 左側に, i が ある.
            if(dqL.back() == i) dqR.puf(i + 1);
        }
    }
    
    // 3. 数列 A.
    vi ans;
    while(!dqL.empty()){
        ans.pub(dqL.front());
        dqL.pof();
    }
    while(!dqR.empty()){
        ans.pub(dqR.front());
        dqR.pof();
    }
    
    // 4. 出力.
    int n = ans.size();
    rep(i, n){
        printf("%d", ans[i]);
        printf("%s", (i < n - 1) ? " " : "\n");
    }
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

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

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

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

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

#define pob pop_back

#define pof pop_front

#define pub push_back

#define puf push_front

int main(){

// 1. 入力情報.

int N;

char s[505050];

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

// 2. 操作.

deque<int> dqL, dqR;

dqL.pub(0);

rep(i, N){

// 'L' の時.

if(s[i] == 'L'){

// 左側に, i がある.

if(dqL.back() == i){

dqR.puf(i);

dqL.pob();

dqL.pub(i + 1);

continue;

}

// 右側に, i がある.

if(dqR.front() == i) dqL.pub(i + 1);

}

// 'R' の時.

if(s[i] == 'R'){

// 右側が, 空の場合.

// -> 001.txt などで, WA版となったため, 修正.

if(dqR.empty()){

dqR.puf(i + 1);

continue;

}

// 右側に, i がある.

if(dqR.front() == i){

dqL.pub(i);

dqR.pof();

dqR.puf(i + 1);

continue;

}

// 左側に, i がある.

if(dqL.back() == i) dqR.puf(i + 1);

}

// 3. 数列 A.

vi ans;

while(!dqL.empty()){

ans.pub(dqL.front());

dqL.pof();

}

while(!dqR.empty()){

ans.pub(dqR.front());

dqR.pof();

}

// 4. 出力.

int n = ans.size();

rep(i, n){

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

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

}

return 0;

}

[入力例]
5
LRRLR

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

[入力例]
7
LLLLLLL

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

[入力例]
10
LLRLRRRLRL

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

[入力例]
30
LLRRLLRLRRLRRRLLRRLRRRRLLLRRLL

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

[入力例]
50
RRLRLLLRRLRRLLLLRRLRLLRLRLLLLRLRLLLLRRLRRRLRRLRLRL

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

[入力例]

LRRLR

[出力例]

1 2 4 5 3 0

※AtCoderテストケースより

[入力例]

LLLLLLL

[出力例]

7 6 5 4 3 2 1 0

※AtCoderテストケースより

[入力例]

LLRLRRRLRL

[出力例]

2 4 5 6 8 10 9 7 3 1 0

[入力例]

LLRRLLRLRRLRRRLLRRLRRRRLLLRRLL

[出力例]

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

[入力例]

RRLRLLLRRLRRLLLLRRLRLLRLRLLLLRLRLLLLRRLRRRLRRLRLRL

[出力例]

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

■参照サイト
AtCoder Beginner Contest 237

2022年1月30日

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

C++の練習を兼ねて, AtCoder Regular Contest 133 の問題C (Row Column Sums) を解いてみた.

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

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

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

// 解き直し.
// https://atcoder.jp/contests/arc133/editorial/3282
// 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. 入力情報.
    int H, W;
    LL K;
    scanf("%d %d %lld", &H, &W, &K);
    LL a, b, ta = 0, tb = 0, C = 0, D = 0;
    rep(i, H){
        scanf("%lld", &a);
        ta += a;
        C += ((K - 1) * (LL)W - a) % K;
    }
    rep(i, W){
        scanf("%lld", &b);
        tb += b;
        D += ((K - 1) * (LL)H - b) % K;
    }
    
    // 2. 例外.
    if(ta % K != tb % K){
        puts("-1");
        return 0;
    }
    
    // 3. 出力.
    printf("%lld\n", (LL)H * (LL)W * (K - 1) - max(C, D));
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc133/editorial/3282

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

int H, W;

LL K;

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

LL a, b, ta = 0, tb = 0, C = 0, D = 0;

rep(i, H){

scanf("%lld", &a);

ta += a;

C += ((K - 1) * (LL)W - a) % K;

}

rep(i, W){

scanf("%lld", &b);

tb += b;

D += ((K - 1) * (LL)H - b) % K;

}

// 2. 例外.

if(ta % K != tb % K){

puts("-1");

return 0;

}

// 3. 出力.

printf("%lld\n", (LL)H * (LL)W * (K - 1) - max(C, D));

return 0;

}

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

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

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

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

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

[出力例]
75

[入力例]
31 41 59
26 5 35 8 9 7 9 32 38 46 26 43 38 32 7 9 50 28 8 41 9 7 16 9 39 9 37 5 10 58 20
9 7 4 9 44 5 9 23 0 7 8 16 4 0 6 28 6 20 8 9 9 8 6 28 0 34 8 25 3 4 2 11 7 0 6 7 9 8 2 14 8

[出力例]
72873

[入力例]
123 234 345
309 226 171 216 1 176 264 188 212 318 50 40 92 124 29 320 297 338 251 26 133 271 90 155 217 252 212 136 43 247 141 141 18 290 91 176 239 47 120 326 182 62 18 149 18 266 109 192 229 188 153 162 115 13 145 219 132 281 309 250 221 270 136 5 5 138 307 301 333 42 222 122 20 304 178 24 42 182 316 122 245 311 316 305 47 66 211 155 35 196 149 128 297 160 213 27 228 59 258 156 142 295 216 240 178 201 19 94 248 63 247 187 225 242 321 162 339 143 148 160 10 135 15
164 243 102 226 16 65 212 291 311 159 342 251 195 195 326 165 39 266 242 44 213 28 34 165 127 228 252 189 153 234 23 225 279 101 263 150 165 333 204 83 307 153 74 162 298 343 63 4 92 55 1 16 109 115 175 174 33 169 116 66 67 119 123 115 138 132 320 285 157 142 58 44 229 212 122 138 260 189 104 194 216 248 94 151 275 211 310 130 248 303 195 20 116 238 331 190 241 103 223 238 64 185 247 10 89 74 146 55 39 16 75 0 304 85 25 122 27 301 255 243 129 125 172 109 276 255 261 213 12 38 167 286 260 50 265 129 92 236 249 192 230 338 123 240 5 268 205 288 32 132 105 117 21 209 7 107 5 217 38 297 166 243 293 310 38 171 110 82 102 41 271 245 16 60 192 211 132 201 169 47 14 232 216 307 34 334 284 12 27 245 315 336 65 192 189 57 46 79 245 74 281 247 126 84 201 3 205 51 313 274 34 197 289 330 65 32 159 296 45 204 42 93 60 141 256 231 58 191 84 50 326 107 335 240

[出力例]
9860467

[入力例]

2 4 3

0 2

1 2 2 0

[出力例]

※AtCoderのテストケースより

[入力例]

3 3 4

0 1 2

1 2 3

[出力例]

-1

※AtCoderのテストケースより

[入力例]

3 5 7

3 4 5

3 1 3 2 3

[出力例]

[入力例]

31 41 59

26 5 35 8 9 7 9 32 38 46 26 43 38 32 7 9 50 28 8 41 9 7 16 9 39 9 37 5 10 58 20

9 7 4 9 44 5 9 23 0 7 8 16 4 0 6 28 6 20 8 9 9 8 6 28 0 34 8 25 3 4 2 11 7 0 6 7 9 8 2 14 8

[出力例]

72873

[入力例]

123 234 345

309 226 171 216 1 176 264 188 212 318 50 40 92 124 29 320 297 338 251 26 133 271 90 155 217 252 212 136 43 247 141 141 18 290 91 176 239 47 120 326 182 62 18 149 18 266 109 192 229 188 153 162 115 13 145 219 132 281 309 250 221 270 136 5 5 138 307 301 333 42 222 122 20 304 178 24 42 182 316 122 245 311 316 305 47 66 211 155 35 196 149 128 297 160 213 27 228 59 258 156 142 295 216 240 178 201 19 94 248 63 247 187 225 242 321 162 339 143 148 160 10 135 15

164 243 102 226 16 65 212 291 311 159 342 251 195 195 326 165 39 266 242 44 213 28 34 165 127 228 252 189 153 234 23 225 279 101 263 150 165 333 204 83 307 153 74 162 298 343 63 4 92 55 1 16 109 115 175 174 33 169 116 66 67 119 123 115 138 132 320 285 157 142 58 44 229 212 122 138 260 189 104 194 216 248 94 151 275 211 310 130 248 303 195 20 116 238 331 190 241 103 223 238 64 185 247 10 89 74 146 55 39 16 75 0 304 85 25 122 27 301 255 243 129 125 172 109 276 255 261 213 12 38 167 286 260 50 265 129 92 236 249 192 230 338 123 240 5 268 205 288 32 132 105 117 21 209 7 107 5 217 38 297 166 243 293 310 38 171 110 82 102 41 271 245 16 60 192 211 132 201 169 47 14 232 216 307 34 334 284 12 27 245 315 336 65 192 189 57 46 79 245 74 281 247 126 84 201 3 205 51 313 274 34 197 289 330 65 32 159 296 45 204 42 93 60 141 256 231 58 191 84 50 326 107 335 240

[出力例]

9860467

■参照サイト
AtCoder Regular Contest 133

2022年1月29日

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

C++の練習を兼ねて, AtCoder Beginner Contest 236 の問題E (Average and Median) を解いてみた.

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

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

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

// 解き直し.
// https://atcoder.jp/contests/abc236/editorial/3279
// 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--)
LL a[101010];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%lld", &a[i]);
    
    // 2. 評価関数(平均値).
    auto f = [&](LL m) -> bool {
        // 2-1. 平均値を, m以上にできるか？
        vl dp(N + 1), pd(N + 1);
        rep(i, N){
            dp[i + 1] = max(dp[i], pd[i]) + (1000 * a[i] - m);
            pd[i + 1] = dp[i];
        }
        
        // 2-2. 判定結果.
        return (max(dp[N], pd[N]) >= 0);
    };
    
    // 3. 評価関数(中央値).
    auto g = [&](LL m) -> bool {
        // 3-1. 中央値を, m以上にできるか？
        vl dp(N + 1), pd(N + 1);
        rep(i, N){
            dp[i + 1] = max(dp[i], pd[i]) + ((a[i] >= m) ? 1 : -1);
            pd[i + 1] = dp[i];
        }
        
        // 3-2. 判定結果.
        return (max(dp[N], pd[N]) > 0);
    };
    
    // 4. 二分探索で確認してみる(平均値).
    LL l = 0, h = 2e12 + 1;
    while(l + 1 < h){
        LL m = (h + l) >> 1;
        if(f(m)) l = m;
        else     h = m;
        // printf("h=%lld l=%lld m=%lld\n", h, l, m);
    }
    LL maxMean = l;
    
    // 5. 二分探索で確認してみる(中央値).
    l = 0, h = 2e9 + 1;
    while(l + 1 < h){
        LL m = (h + l) >> 1;
        if(g(m)) l = m;
        else     h = m;
        // printf("h=%lld l=%lld m=%lld\n", h, l, m);
    }
    LL maxMedian = l;
    
    // 6. 出力.
    printf("%.3lf\n%lld\n", (double)maxMean / 1000.0, maxMedian);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc236/editorial/3279

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

LL a[101010];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

// 2. 評価関数(平均値).

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

// 2-1. 平均値を, m以上にできるか？

vl dp(N + 1), pd(N + 1);

rep(i, N){

dp[i + 1] = max(dp[i], pd[i]) + (1000 * a[i] - m);

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

}

// 2-2. 判定結果.

return (max(dp[N], pd[N]) >= 0);

};

// 3. 評価関数(中央値).

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

// 3-1. 中央値を, m以上にできるか？

vl dp(N + 1), pd(N + 1);

rep(i, N){

dp[i + 1] = max(dp[i], pd[i]) + ((a[i] >= m) ? 1 : -1);

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

}

// 3-2. 判定結果.

return (max(dp[N], pd[N]) > 0);

};

// 4. 二分探索で確認してみる(平均値).

LL l = 0, h = 2e12 + 1;

while(l + 1 < h){

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

if(f(m)) l = m;

else h = m;

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

}

LL maxMean = l;

// 5. 二分探索で確認してみる(中央値).

l = 0, h = 2e9 + 1;

while(l + 1 < h){

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

if(g(m)) l = m;

else h = m;

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

}

LL maxMedian = l;

// 6. 出力.

printf("%.3lf\n%lld\n", (double)maxMean / 1000.0, maxMedian);

return 0;

}

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

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

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

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

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

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

[入力例]
10
8 18 28 2 18 20 15 17 12 21

[出力例]
20.333
18

[入力例]
50
1534 1993 842 127 172 1834 409 510 1117 1172 804 157 516 1644 1877 505 1468 1204 1752 1445 960 1807 1335 1189 199 1117 394 98 1193 1221 496 470 1391 986 1665 820 447 1229 1454 86 1272 690 136 1853 488 728 1886 380 1221 1779

[出力例]
1259.096
1391

[入力例]
150
93302 62538 89452 42425 44435 71496 29725 90563 8793 99500 92586 16243 86849 53851 22514 39271 69471 80528 64641 58584 19431 66758 49676 47265 93718 1327 64433 13729 69773 84893 95444 15668 14975 81144 48397 32389 16928 97314 13842 16956 130 72861 65377 88928 28591 86404 72886 99434 29164 61853 91776 10823 23759 41434 71850 51656 19927 64536 16592 451 70065 35886 79105 53865 13176 37295 7871 17574 64756 92886 97573 31391 10596 98653 39374 34673 49248 41525 46520 60125 50024 92813 93518 30639 82782 59796 55623 69102 36042 36794 80653 85233 52208 40492 73530 35112 57254 6463 87848 49361 20681 61948 4737 50429 42490 30610 99179 13068 53455 84426 3921 22226 49329 48002 18928 84734 86630 10502 32007 57934 31180 11383 37728 26371 70605 20101 56202 91981 29667 702 96602 74258 50209 26074 86719 9891 99463 24847 52501 56676 38125 85244 3337 59419 75076 5607 4647 38281 49673 3307

[出力例]
65380.076
70065

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

[出力例]
67.476
77

[入力例]

2 1 2 1 1 10

[出力例]

※AtCoderテストケースより

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

4.000

[入力例]

3 1 4 1 5 9 2

[出力例]

5.250000000

※AtCoderテストケースより

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

5.250

[入力例]

8 18 28 2 18 20 15 17 12 21

[出力例]

20.333

[入力例]

1534 1993 842 127 172 1834 409 510 1117 1172 804 157 516 1644 1877 505 1468 1204 1752 1445 960 1807 1335 1189 199 1117 394 98 1193 1221 496 470 1391 986 1665 820 447 1229 1454 86 1272 690 136 1853 488 728 1886 380 1221 1779

[出力例]

1259.096

1391

[入力例]

150

93302 62538 89452 42425 44435 71496 29725 90563 8793 99500 92586 16243 86849 53851 22514 39271 69471 80528 64641 58584 19431 66758 49676 47265 93718 1327 64433 13729 69773 84893 95444 15668 14975 81144 48397 32389 16928 97314 13842 16956 130 72861 65377 88928 28591 86404 72886 99434 29164 61853 91776 10823 23759 41434 71850 51656 19927 64536 16592 451 70065 35886 79105 53865 13176 37295 7871 17574 64756 92886 97573 31391 10596 98653 39374 34673 49248 41525 46520 60125 50024 92813 93518 30639 82782 59796 55623 69102 36042 36794 80653 85233 52208 40492 73530 35112 57254 6463 87848 49361 20681 61948 4737 50429 42490 30610 99179 13068 53455 84426 3921 22226 49329 48002 18928 84734 86630 10502 32007 57934 31180 11383 37728 26371 70605 20101 56202 91981 29667 702 96602 74258 50209 26074 86719 9891 99463 24847 52501 56676 38125 85244 3337 59419 75076 5607 4647 38281 49673 3307

[出力例]

65380.076

70065

[入力例]

300

45 48 70 79 96 86 5 89 21 48 45 25 97 45 75 87 11 89 97 93 34 80 77 54 14 68 83 25 33 70 47 95 52 26 29 46 47 58 67 20 66 89 69 42 67 51 57 14 82 62 30 39 89 35 43 57 14 61 14 33 15 66 10 45 90 21 83 39 2 92 24 94 76 73 39 34 95 60 68 77 57 47 79 34 56 14 15 23 51 80 79 2 93 16 16 93 6 67 19 4 1 37 83 99 27 54 36 1 10 76 12 19 86 87 78 23 89 5 27 16 56 19 81 72 46 82 77 94 8 85 33 24 70 59 71 46 71 87 4 18 51 11 48 14 74 83 37 57 82 60 23 60 23 93 97 33 14 11 24 19 42 93 99 63 79 45 5 46 98 14 60 21 87 29 89 55 51 52 44 31 83 93 74 86 58 49 92 99 7 86 94 80 24 53 3 64 35 29 58 27 48 1 53 83 57 6 74 19 78 21 37 13 92 95 84 8 85 39 4 59 74 87 85 97 86 32 28 34 42 5 6 64 15 81 8 2 35 57 32 99 64 34 89 12 54 81 17 91 57 14 99 52 81 91 69 82 88 99 40 34 45 92 9 30 54 80 70 55 62 85 41 65 38 46 82 69 92 18 52 17 19 81 66 21 2 32 3 93 14 26 70 37 94 18 89 50 1 64 92 8

[出力例]

67.476

■参照サイト
AtCoder Beginner Contest 236

2022年1月29日

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

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

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

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

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

// 解き直し.
// https://atcoder.jp/contests/abc236/editorial/3287
// 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>;
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 a first
#define b second
#define pb push_back
#define all(x) x.begin(), x.end()
int b[1 << 16], c[1 << 16];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vp v;
    repx(i, 1, 1 << N){
        scanf("%d", &c[i]);
        v.pb({c[i], i});
    }
    
    // 2. sort.
    sort(all(v));
    
    // 3. 貪欲アルゴリズム(解説通り).
    vi S;
    b[0] = 1;
    for(auto &p : v){
        // S の 要素から, 辛さ p.b を 作れる場合.
        if(b[p.b]) continue;
        
        // S の 要素から, 辛さ p.b を 作れない場合. 
        // -> S に 要素を追加し, フラグ b を 更新.
        S.pb(p.b);
        rep(i, 1 << N) if(b[i]) b[i ^ p.b] = 1;
    }
    
    // 4. 集計.
    LL ans = 0;
    for(auto &p : S) ans += (LL)c[p];
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc236/editorial/3287

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

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

#define b second

#define pb push_back

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

int b[1 << 16], c[1 << 16];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vp v;

repx(i, 1, 1 << N){

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

v.pb({c[i], i});

}

// 2. sort.

sort(all(v));

// 3. 貪欲アルゴリズム(解説通り).

vi S;

b[0] = 1;

for(auto &p : v){

// S の要素から, 辛さ p.b を作れる場合.

if(b[p.b]) continue;

// S の要素から, 辛さ p.b を作れない場合.

// -> S に要素を追加し, フラグ b を更新.

S.pb(p.b);

rep(i, 1 << N) if(b[i]) b[i ^ p.b] = 1;

}

// 4. 集計.

LL ans = 0;

for(auto &p : S) ans += (LL)c[p];

// 5. 出力.

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

return 0;

}

[入力例]
2
4 5 3

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

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

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

[入力例]
1
10

[出力例]
10

[入力例]
3
16 30 26 6 33 18 27

[出力例]
40

[入力例]
7
129 290 138 144 521 138 541 413 255 462 202 497 245 7 414 246 529 547 342 366 442 348 509 166 67 140 40 115 129 34 476 62 312 390 461 194 352 518 21 436 426 146 220 403 207 152 309 44 472 293 50 133 322 374 544 311 553 499 549 90 293 59 109 279 338 475 307 162 527 404 282 498 258 220 126 268 341 355 160 301 480 331 263 289 393 187 528 182 285 471 345 395 454 209 419 551 137 242 282 186 466 361 63 358 199 209 308 371 31 369 141 534 213 515 262 335 56 103 153 284 218 518 541 15 418 190 435

[出力例]
192

[入力例]
10
858 582 452 236 475 298 137 74 213 307 808 73 141 585 5 561 770 524 416 663 180 822 70 769 248 730 254 363 19 667 280 235 328 715 291 404 668 496 202 862 56 230 664 582 428 793 559 795 71 891 532 902 582 341 216 519 819 899 968 380 402 405 828 66 472 959 224 204 599 711 651 962 414 33 412 654 689 370 528 512 570 140 114 407 779 945 271 48 168 856 221 279 737 307 957 994 646 214 336 25 760 968 934 318 341 42 780 863 941 507 64 179 315 379 411 612 610 48 831 533 938 525 344 695 420 363 176 824 354 180 787 324 13 729 504 456 996 631 250 840 708 161 620 595 689 316 761 458 60 127 703 701 90 539 156 432 483 540 274 845 416 259 55 133 143 786 969 826 853 195 757 171 963 316 842 744 84 465 281 432 527 146 896 897 507 960 312 997 941 584 524 526 11 663 148 344 53 315 838 486 708 555 273 830 820 346 506 37 485 133 159 417 394 211 73 862 886 930 550 446 550 626 145 624 854 615 624 598 840 895 817 646 640 425 628 434 831 165 993 434 897 248 427 646 936 349 270 512 683 921 961 699 823 79 570 507 923 105 56 826 23 768 562 705 976 25 481 653 511 682 313 945 472 174 858 137 760 540 59 546 983 6 940 236 657 877 863 457 374 791 153 839 709 688 871 333 634 395 66 443 397 659 12 696 993 661 452 795 606 407 582 439 756 31 651 738 858 151 451 565 193 677 112 590 736 734 53 537 192 862 870 352 725 349 936 988 388 639 96 356 156 938 708 335 323 937 986 621 950 33 837 571 958 333 374 873 222 892 96 819 980 542 748 231 161 786 244 441 639 358 843 734 102 802 249 42 222 407 142 564 54 876 430 278 592 498 119 125 451 317 678 814 150 927 887 10 93 916 708 729 669 724 296 733 533 834 412 940 488 529 887 982 915 958 769 977 432 800 995 443 76 164 182 653 40 631 737 249 863 955 199 545 288 396 454 129 905 908 130 389 173 474 257 997 164 74 444 171 465 363 848 689 225 30 26 515 185 477 141 47 293 199 515 362 752 875 500 513 397 602 468 834 758 832 129 878 82 510 651 23 28 369 224 227 962 201 779 596 270 247 328 749 910 803 14 563 561 344 49 3 869 742 874 800 448 109 659 231 986 792 183 831 920 575 460 311 99 306 762 696 370 58 35 306 534 731 128 446 187 113 143 547 149 404 613 816 567 785 367 702 703 881 494 37 931 579 572 572 387 294 74 54 283 265 356 764 364 124 66 202 287 609 350 40 680 344 272 763 311 447 276 782 975 637 98 660 260 545 834 678 865 563 701 773 837 380 592 22 441 608 554 87 421 13 261 48 959 409 955 763 672 438 284 77 86 112 886 528 464 484 801 188 161 301 140 296 252 35 655 115 89 673 915 860 911 980 271 493 876 183 806 719 568 62 187 211 145 66 895 50 13 992 758 710 832 221 949 645 874 86 745 953 369 730 715 389 427 725 633 15 950 318 160 248 290 979 225 550 285 139 231 414 673 853 264 219 33 352 823 430 526 679 489 855 998 638 148 345 976 189 668 336 938 880 567 90 481 847 189 952 151 55 702 956 23 550 647 125 7 276 721 961 556 498 774 448 794 333 100 705 156 714 414 259 534 645 356 140 767 54 691 827 716 742 824 77 694 701 336 212 366 285 148 871 531 487 920 936 442 778 960 928 524 642 460 163 795 334 793 644 890 392 180 683 464 490 397 776 20 718 668 344 408 890 714 399 627 775 276 612 460 336 772 634 302 257 944 695 636 995 116 709 183 397 40 694 101 564 598 720 457 439 56 904 657 161 471 625 262 68 437 883 833 443 758 883 660 435 693 618 21 456 163 238 16 568 173 28 548 844 608 814 69 842 917 788 774 106 585 704 950 115 802 56 457 135 496 193 658 687 355 912 573 91 515 976 182 764 510 505 461 216 376 474 886 731 460 934 520 503 202 331 82 178 752 559 177 787 657 911 877 687 644 636 440 862 139 835 200 399 769 455 109 752 742 412 20 636 418 211 523 758 798 163 329 906 789 282 748 992 322 531 15 761 478 522 610 859 206 893 738 81 229 305 788 775 45 514 505 1 854 699 916 320 476 239 736 815 856 745 215 91 502 962 232 154 287 258 354 133 476 101 540 784 104 489 459 589 984 198 907 958 721 183 529 243 306 184 420 533 334 916 410 192 603 919 348 133 575 337 697 325 718 279 533 117 362 324 320 531 862 668 109 883 225 57 735 62 313 229 641 943 402 488 9 242 415 202 906 412 624 149 584 265 321 40 554 299 453 392 205 72 99

[出力例]
77

[入力例]

4 5 3

[出力例]

※AtCoderテストケースより

[入力例]

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

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

[入力例]

16 30 26 6 33 18 27

[出力例]

[入力例]

129 290 138 144 521 138 541 413 255 462 202 497 245 7 414 246 529 547 342 366 442 348 509 166 67 140 40 115 129 34 476 62 312 390 461 194 352 518 21 436 426 146 220 403 207 152 309 44 472 293 50 133 322 374 544 311 553 499 549 90 293 59 109 279 338 475 307 162 527 404 282 498 258 220 126 268 341 355 160 301 480 331 263 289 393 187 528 182 285 471 345 395 454 209 419 551 137 242 282 186 466 361 63 358 199 209 308 371 31 369 141 534 213 515 262 335 56 103 153 284 218 518 541 15 418 190 435

[出力例]

192

[入力例]

858 582 452 236 475 298 137 74 213 307 808 73 141 585 5 561 770 524 416 663 180 822 70 769 248 730 254 363 19 667 280 235 328 715 291 404 668 496 202 862 56 230 664 582 428 793 559 795 71 891 532 902 582 341 216 519 819 899 968 380 402 405 828 66 472 959 224 204 599 711 651 962 414 33 412 654 689 370 528 512 570 140 114 407 779 945 271 48 168 856 221 279 737 307 957 994 646 214 336 25 760 968 934 318 341 42 780 863 941 507 64 179 315 379 411 612 610 48 831 533 938 525 344 695 420 363 176 824 354 180 787 324 13 729 504 456 996 631 250 840 708 161 620 595 689 316 761 458 60 127 703 701 90 539 156 432 483 540 274 845 416 259 55 133 143 786 969 826 853 195 757 171 963 316 842 744 84 465 281 432 527 146 896 897 507 960 312 997 941 584 524 526 11 663 148 344 53 315 838 486 708 555 273 830 820 346 506 37 485 133 159 417 394 211 73 862 886 930 550 446 550 626 145 624 854 615 624 598 840 895 817 646 640 425 628 434 831 165 993 434 897 248 427 646 936 349 270 512 683 921 961 699 823 79 570 507 923 105 56 826 23 768 562 705 976 25 481 653 511 682 313 945 472 174 858 137 760 540 59 546 983 6 940 236 657 877 863 457 374 791 153 839 709 688 871 333 634 395 66 443 397 659 12 696 993 661 452 795 606 407 582 439 756 31 651 738 858 151 451 565 193 677 112 590 736 734 53 537 192 862 870 352 725 349 936 988 388 639 96 356 156 938 708 335 323 937 986 621 950 33 837 571 958 333 374 873 222 892 96 819 980 542 748 231 161 786 244 441 639 358 843 734 102 802 249 42 222 407 142 564 54 876 430 278 592 498 119 125 451 317 678 814 150 927 887 10 93 916 708 729 669 724 296 733 533 834 412 940 488 529 887 982 915 958 769 977 432 800 995 443 76 164 182 653 40 631 737 249 863 955 199 545 288 396 454 129 905 908 130 389 173 474 257 997 164 74 444 171 465 363 848 689 225 30 26 515 185 477 141 47 293 199 515 362 752 875 500 513 397 602 468 834 758 832 129 878 82 510 651 23 28 369 224 227 962 201 779 596 270 247 328 749 910 803 14 563 561 344 49 3 869 742 874 800 448 109 659 231 986 792 183 831 920 575 460 311 99 306 762 696 370 58 35 306 534 731 128 446 187 113 143 547 149 404 613 816 567 785 367 702 703 881 494 37 931 579 572 572 387 294 74 54 283 265 356 764 364 124 66 202 287 609 350 40 680 344 272 763 311 447 276 782 975 637 98 660 260 545 834 678 865 563 701 773 837 380 592 22 441 608 554 87 421 13 261 48 959 409 955 763 672 438 284 77 86 112 886 528 464 484 801 188 161 301 140 296 252 35 655 115 89 673 915 860 911 980 271 493 876 183 806 719 568 62 187 211 145 66 895 50 13 992 758 710 832 221 949 645 874 86 745 953 369 730 715 389 427 725 633 15 950 318 160 248 290 979 225 550 285 139 231 414 673 853 264 219 33 352 823 430 526 679 489 855 998 638 148 345 976 189 668 336 938 880 567 90 481 847 189 952 151 55 702 956 23 550 647 125 7 276 721 961 556 498 774 448 794 333 100 705 156 714 414 259 534 645 356 140 767 54 691 827 716 742 824 77 694 701 336 212 366 285 148 871 531 487 920 936 442 778 960 928 524 642 460 163 795 334 793 644 890 392 180 683 464 490 397 776 20 718 668 344 408 890 714 399 627 775 276 612 460 336 772 634 302 257 944 695 636 995 116 709 183 397 40 694 101 564 598 720 457 439 56 904 657 161 471 625 262 68 437 883 833 443 758 883 660 435 693 618 21 456 163 238 16 568 173 28 548 844 608 814 69 842 917 788 774 106 585 704 950 115 802 56 457 135 496 193 658 687 355 912 573 91 515 976 182 764 510 505 461 216 376 474 886 731 460 934 520 503 202 331 82 178 752 559 177 787 657 911 877 687 644 636 440 862 139 835 200 399 769 455 109 752 742 412 20 636 418 211 523 758 798 163 329 906 789 282 748 992 322 531 15 761 478 522 610 859 206 893 738 81 229 305 788 775 45 514 505 1 854 699 916 320 476 239 736 815 856 745 215 91 502 962 232 154 287 258 354 133 476 101 540 784 104 489 459 589 984 198 907 958 721 183 529 243 306 184 420 533 334 916 410 192 603 919 348 133 575 337 697 325 718 279 533 117 362 324 320 531 862 668 109 883 225 57 735 62 313 229 641 943 402 488 9 242 415 202 906 412 624 149 584 265 321 40 554 299 453 392 205 72 99

[出力例]

■参照サイト
AtCoder Beginner Contest 236

2022年1月28日

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

C++の練習を兼ねて, AtCoder Beginner Contest 236 の問題C (Route Map) ～問題D (Dance) を解いてみた.

■感想.
1. 問題Dは, 計算量を絞り込む方針が見えなかったので, 解説を参考に実装して, AC版に到達できたと思う.
2. 問題Dは, 何度も提出する羽目になったが, WA原因が, 入力情報を保存する配列サイズが, 小さすぎて, エラーとなっていることが判明し, 今後の教訓となったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    set<string> st;
    vs v;
    rep(i, N){
        char s[22];
        scanf("%s", s);
        string S(s);
        v.pb(S);
    }
    rep(i, M){
        char t[22];
        scanf("%s", t);
        string T(t);
        st.insert(T);
    }
    
    // 2. クエリ回答.
    for(auto &p : v) printf("%s\n", (st.count(p)) ? "Yes" : "No");
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vs = vector<string>;

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

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

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

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

#define pb push_back

int main(){

// 1. 入力情報.

int N, M;

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

set<string> st;

vs v;

rep(i, N){

char s[22];

scanf("%s", s);

string S(s);

v.pb(S);

}

rep(i, M){

char t[22];

scanf("%s", t);

string T(t);

st.insert(T);

}

// 2. クエリ回答.

for(auto &p : v) printf("%s\n", (st.count(p)) ? "Yes" : "No");

return 0;

}

[入力例]
5 3
tokyo kanda akiba okachi ueno
tokyo akiba ueno

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

[入力例]
7 7
a t c o d e r
a t c o d e r

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

[入力例]
20 9
lcwgenqipr zfrbunslev pdibkpbtdd pwtmemygdc cmvyepxc rfkmmxednu oomsfllbru ezrbdhcf uvgylorliw sieuyjsnnr txbywcr rdjnwydjbh ropmkcmqqq ogtovwoy ckeptdqojl mrprnbxomt aldlg usryxisqok utlcwszbci farwbcne
lcwgenqipr pdibkpbtdd cmvyepxc oomsfllbru ezrbdhcf txbywcr ogtovwoy aldlg farwbcne

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

[入力例]

5 3

tokyo kanda akiba okachi ueno

tokyo akiba ueno

[出力例]

Yes

※AtCoderテストケースより

[入力例]

7 7

a t c o d e r

[出力例]

Yes

※AtCoderテストケースより

[入力例]

20 9

lcwgenqipr zfrbunslev pdibkpbtdd pwtmemygdc cmvyepxc rfkmmxednu oomsfllbru ezrbdhcf uvgylorliw sieuyjsnnr txbywcr rdjnwydjbh ropmkcmqqq ogtovwoy ckeptdqojl mrprnbxomt aldlg usryxisqok utlcwszbci farwbcne

lcwgenqipr pdibkpbtdd cmvyepxc oomsfllbru ezrbdhcf txbywcr ogtovwoy aldlg farwbcne

[出力例]

Yes

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

// 解き直し.
// https://atcoder.jp/contests/abc236/editorial/3285
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
int a[33][33]; // 配列サイズ要注意.

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, 2 * N - 1) repx(j, i + 1, 2 * N) scanf("%d", &a[i][j]);
    
    // 2. dfs.
    // https://ja.wikipedia.org/wiki/深さ優先探索
    auto dfs = [&](auto&& self, int befMemo, int curXor, int d) -> int{
        // 2-1. 終了条件.
        if(d == N) return curXor;
        
        // 2-2. ペア一人目を探す.
        int p1 = 0;
        rep(i, 2 * N){
            if(!(befMemo & (1 << (2 * N - i)))){
                p1 = i;
                break;
            }
        }
        
        // 2-3. ペア二人目を探しながら, XOR を 計算.
        int ret = 0;
        int curMemo = befMemo | (1 << (2 * N - p1));
        repx(p2, p1 + 1, 2 * N){
            if(!(curMemo & (1 << (2 * N - p2)))){
                int nexXor = curXor ^ a[p1][p2];
                int nexMemo = curMemo | (1 << (2 * N - p2));
                ret = max(ret, self(self, nexMemo, nexXor, d + 1));
            }
        }
        
        // 2-4. 返却.
        return ret;
    };
    
    // 3. 出力.
    printf("%d\n", dfs(dfs, 0, 0, 0));
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc236/editorial/3285

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

int a[33][33]; // 配列サイズ要注意.

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, 2 * N - 1) repx(j, i + 1, 2 * N) scanf("%d", &a[i][j]);

// 2. dfs.

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

auto dfs = [&](auto&& self, int befMemo, int curXor, int d) -> int{

// 2-1. 終了条件.

if(d == N) return curXor;

// 2-2. ペア一人目を探す.

int p1 = 0;

rep(i, 2 * N){

if(!(befMemo & (1 << (2 * N - i)))){

p1 = i;

break;

}

// 2-3. ペア二人目を探しながら, XOR を計算.

int ret = 0;

int curMemo = befMemo | (1 << (2 * N - p1));

repx(p2, p1 + 1, 2 * N){

if(!(curMemo & (1 << (2 * N - p2)))){

int nexXor = curXor ^ a[p1][p2];

int nexMemo = curMemo | (1 << (2 * N - p2));

ret = max(ret, self(self, nexMemo, nexXor, d + 1));

}

// 2-4. 返却.

return ret;

};

// 3. 出力.

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

return 0;

}

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

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

[入力例]
1
5

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

[入力例]
5
900606388 317329110 665451442 1045743214 260775845 726039763 57365372 741277060 944347467
369646735 642395945 599952146 86221147 523579390 591944369 911198494 695097136
138172503 571268336 111747377 595746631 934427285 840101927 757856472
655483844 580613112 445614713 607825444 252585196 725229185
827291247 105489451 58628521 1032791417 152042357
919691140 703307785 100772330 370415195
666350287 691977663 987658020
1039679956 218233643
70938785

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

[入力例]
3
14 15 92 65 35
89 79 32 38
46 26 43
38 32
79

[出力例]
118

[入力例]
5
123 234 345 456 567 678 789 890 901
234 345 456 567 678 789 890 901
345 456 567 678 789 890 901
456 567 678 789 890 901
567 678 789 890 901
678 789 890 901
789 890 901
890 901
901

[出力例]
1002

[入力例]
8
33 41 74 34 17 120 63 28 60 15 66 109 72 71 43
122 115 4 87 94 44 44 75 100 54 12 82 51 41
111 92 39 97 98 104 33 72 77 57 14 99 56
47 89 97 84 36 7 87 116 55 117 13 66
93 18 61 42 99 63 75 10 105 31 70
14 59 97 91 112 119 68 69 109 17
70 34 37 9 113 59 105 47 48
97 50 117 33 93 29 11 83
67 49 38 54 99 45 40
64 71 112 113 19 97
39 95 96 40 107
28 38 49 78
60 69 111
93 13
81

[出力例]
127

[入力例]
8
487139 861602 238520 164035 219099 446008 57720 1070750 1221210 1188858 1219203 923136 864732 363177 954566
419922 652427 810787 1183029 56796 255648 943313 1021792 1106533 34949 1184033 1039329 255017 864084
978644 1234010 1094491 762205 547977 553838 409861 103892 685576 804096 90883 796024 262869
1085316 365039 174833 856988 852486 84100 986363 112387 114824 750889 447938 189952
1134885 325412 522196 35294 257017 223135 1024726 325755 645126 451627 136648
707360 1080890 1205504 178100 1053562 977147 1201855 3036 814479 474568
939809 1138580 1218464 550648 854137 220126 805878 679119 834341
30933 962583 578866 212608 808809 1142922 290941 553016
303617 915128 488234 479671 855889 1136571 643387
26759 1033397 569716 382522 1012306 830053
885272 857909 677947 773771 48951
840700 48568 912933 328071
522956 796084 837213
1158942 370742
182683

[出力例]
2097151

100

101

[入力例]

4 0 1

5 3

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

900606388 317329110 665451442 1045743214 260775845 726039763 57365372 741277060 944347467

369646735 642395945 599952146 86221147 523579390 591944369 911198494 695097136

138172503 571268336 111747377 595746631 934427285 840101927 757856472

655483844 580613112 445614713 607825444 252585196 725229185

827291247 105489451 58628521 1032791417 152042357

919691140 703307785 100772330 370415195

666350287 691977663 987658020

1039679956 218233643

70938785

[出力例]

1073289207

※AtCoderテストケースより

[入力例]

14 15 92 65 35

89 79 32 38

46 26 43

38 32

[出力例]

118

[入力例]

123 234 345 456 567 678 789 890 901

234 345 456 567 678 789 890 901

345 456 567 678 789 890 901

456 567 678 789 890 901

567 678 789 890 901

678 789 890 901

789 890 901

890 901

901

[出力例]

1002

[入力例]

33 41 74 34 17 120 63 28 60 15 66 109 72 71 43

122 115 4 87 94 44 44 75 100 54 12 82 51 41

111 92 39 97 98 104 33 72 77 57 14 99 56

47 89 97 84 36 7 87 116 55 117 13 66

93 18 61 42 99 63 75 10 105 31 70

14 59 97 91 112 119 68 69 109 17

70 34 37 9 113 59 105 47 48

97 50 117 33 93 29 11 83

67 49 38 54 99 45 40

64 71 112 113 19 97

39 95 96 40 107

28 38 49 78

60 69 111

93 13

[出力例]

127

[入力例]

487139 861602 238520 164035 219099 446008 57720 1070750 1221210 1188858 1219203 923136 864732 363177 954566

419922 652427 810787 1183029 56796 255648 943313 1021792 1106533 34949 1184033 1039329 255017 864084

978644 1234010 1094491 762205 547977 553838 409861 103892 685576 804096 90883 796024 262869

1085316 365039 174833 856988 852486 84100 986363 112387 114824 750889 447938 189952

1134885 325412 522196 35294 257017 223135 1024726 325755 645126 451627 136648

707360 1080890 1205504 178100 1053562 977147 1201855 3036 814479 474568

939809 1138580 1218464 550648 854137 220126 805878 679119 834341

30933 962583 578866 212608 808809 1142922 290941 553016

303617 915128 488234 479671 855889 1136571 643387

26759 1033397 569716 382522 1012306 830053

885272 857909 677947 773771 48951

840700 48568 912933 328071

522956 796084 837213

1158942 370742

182683

[出力例]

2097151

■参照サイト
AtCoder Beginner Contest 236

C++の練習を兼ねて, AtCoder Beginner Contest 020 の 問題C (壁抜け) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 099 の 問題C (Strange Bank) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 120 の 問題D (Decayed Bridges) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 235 の 問題F (Variety of Digits) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 237 の 問題C (kasaka) ～ 問題D (LR insertion) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 133 の 問題C (Row Column Sums) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 236 の 問題E (Average and Median) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 236 の 問題C (Route Map) ～ 問題D (Dance) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 020 の問題C (壁抜け) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 099 の問題C (Strange Bank) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 120 の問題D (Decayed Bridges) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 235 の問題F (Variety of Digits) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 237 の問題C (kasaka) ～問題D (LR insertion) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 133 の問題C (Row Column Sums) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 236 の問題E (Average and Median) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 236 の問題C (Route Map) ～問題D (Dance) を解いてみた.