C++ | 個人用メモ帳

2023年3月1日

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

C++の練習を兼ねて, AtCoder Beginner Contest 291 の問題C (LRUD Instructions 2) ～問題D (Flip Cards) を解いてみた.

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

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

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    char c[202020];
    scanf("%d %s", &N, c);
    string s(c);
    
    // 2. 同じ座標にいたことがあるか？
    bool ok = false;
    set<P> st;
    P p = {0, 0};
    st.insert(p);
    rep(i, N){
        p.a += (s[i] == 'R');
        p.a -= (s[i] == 'L');
        p.b += (s[i] == 'U');
        p.b -= (s[i] == 'D');
        if(st.count(p)) ok = true;
        st.insert(p);
    }
    
    // 3. 出力.
    printf("%s\n", ok ? "Yes" : "No");
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using P = pair<int, int>;

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

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

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

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

#define a first

#define b second

int main(){

// 1. 入力情報.

int N;

char c[202020];

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

string s(c);

// 2. 同じ座標にいたことがあるか？

bool ok = false;

set<P> st;

P p = {0, 0};

st.insert(p);

rep(i, N){

p.a += (s[i] == 'R');

p.a -= (s[i] == 'L');

p.b += (s[i] == 'U');

p.b -= (s[i] == 'D');

if(st.count(p)) ok = true;

st.insert(p);

}

// 3. 出力.

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

return 0;

}

[入力例]
5
RLURU

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

[入力例]
20
URDDLLUUURRRDDDDLLLL

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

[入力例]
55
RDDLLLUUUURRRRRDDDDDDLLLLLLLUUUUUUUURRRRRRRRRDDDDDDDDDD

[出力例]
No

[入力例]
100
LDULUUUUURULUDULLRLDLLDURDRDDRDDDDURRRRRRUUDULRDDLDULULDULLDUDURLULLDDDRRLRRDDDURUDUDRLDLLDUUDULRLDL

[出力例]
Yes

[入力例]

RLURU

[出力例]

Yes

※AtCoderテストケースより

[入力例]

URDDLLUUURRRDDDDLLLL

[出力例]

※AtCoderテストケースより

[入力例]

RDDLLLUUUURRRRRDDDDDDLLLLLLLUUUUUUUURRRRRRRRRDDDDDDDDDD

[出力例]

[入力例]

100

LDULUUUUURULUDULLRLDLLDURDRDDRDDDDURRRRRRUUDULRDDLDULULDULLDUDURLULLDDDRRLRRDDDURUDUDRLDLLDUUDULRLDL

[出力例]

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--)
const LL MOD = 998244353;
int a[202020], b[202020];
LL dp[202020][2];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d %d", &a[i], &b[i]);
    
    // 2. dp更新.
    dp[0][0] = dp[0][1] = 1;
    rep(i, N - 1){
        if(a[i] != a[i + 1]) dp[i + 1][0] += dp[i][0];
        if(a[i] != b[i + 1]) dp[i + 1][1] += dp[i][0];
        if(b[i] != a[i + 1]) dp[i + 1][0] += dp[i][1];
        if(b[i] != b[i + 1]) dp[i + 1][1] += dp[i][1];
        dp[i + 1][0] %= MOD;
        dp[i + 1][1] %= MOD;
    }
    
    // 3. 出力.
    printf("%lld\n", (dp[N - 1][0] + dp[N - 1][1]) % MOD);
    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--)

const LL MOD = 998244353;

int a[202020], b[202020];

LL dp[202020][2];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

// 2. dp更新.

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

rep(i, N - 1){

if(a[i] != a[i + 1]) dp[i + 1][0] += dp[i][0];

if(a[i] != b[i + 1]) dp[i + 1][1] += dp[i][0];

if(b[i] != a[i + 1]) dp[i + 1][0] += dp[i][1];

if(b[i] != b[i + 1]) dp[i + 1][1] += dp[i][1];

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

dp[i + 1][1] %= MOD;

}

// 3. 出力.

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

return 0;

}

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

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

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

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

[入力例]
8
877914575 602436426
861648772 623690081
476190629 262703497
971407775 628894325
822804784 450968417
161735902 822804784
161735902 822804784
822804784 161735902

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

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

[出力例]
0

[入力例]
10
88 96
96 88
88 11
99 77
77 111
55 77
77 88
111 77
66 77
22 33

[出力例]
126

[入力例]
30
9999 11111
11111 10305
7777 11111
11111 7777
1750 888
888 205
888 12141
11771 888
9826 888
10702 9826
10702 10702
888 10702
6662 922
1246 250
888 250
6270 333
10393 613
7198 5555
5555 3333
11111 6666
10000 9137
2828 10000
3333 2905
6270 7777
250 6270
10000 3333
7777 10000
10000 250
7777 250
250 7777

[出力例]
907200

[入力例]
50
47659 8396
44206 66145
18843 74714
120877 56567
31519 93129
119310 103983
74529 54963
110863 109268
55344 39949
40669 7238
63635 63636
1104 113457
62546 4445
43212 105513
47795 19805
88550 24020
15554 38857
36169 87565
88907 38393
82788 107889
69552 43637
70541 13780
80576 100847
42088 31433
67767 21924
12908 64554
6376 15443
15520 70460
3698 97859
6971 3698
2958 51165
108163 113138
24818 28189
89658 90475
119113 7269
54028 5040
37553 19853
2192 104519
31460 110705
110705 111128
58218 25811
23122 68909
33085 71174
114681 74713
23519 59550
57478 76096
39447 57478
15712 100086
22588 39076
39076 87045

[出力例]
301633020

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

[入力例]

1 2

4 2

3 4

[出力例]

※AtCoderテストケースより

[入力例]

1 5

2 6

3 7

4 8

[出力例]

※AtCoderテストケースより

[入力例]

877914575 602436426

861648772 623690081

476190629 262703497

971407775 628894325

822804784 450968417

161735902 822804784

822804784 161735902

[出力例]

※AtCoderテストケースより

[入力例]

1 1

2 2

[出力例]

[入力例]

88 96

96 88

88 11

99 77

77 111

55 77

77 88

111 77

66 77

22 33

[出力例]

126

[入力例]

9999 11111

11111 10305

7777 11111

11111 7777

1750 888

888 205

888 12141

11771 888

9826 888

10702 9826

10702 10702

888 10702

6662 922

1246 250

888 250

6270 333

10393 613

7198 5555

5555 3333

11111 6666

10000 9137

2828 10000

3333 2905

6270 7777

250 6270

10000 3333

7777 10000

10000 250

7777 250

250 7777

[出力例]

907200

[入力例]

47659 8396

44206 66145

18843 74714

120877 56567

31519 93129

119310 103983

74529 54963

110863 109268

55344 39949

40669 7238

63635 63636

1104 113457

62546 4445

43212 105513

47795 19805

88550 24020

15554 38857

36169 87565

88907 38393

82788 107889

69552 43637

70541 13780

80576 100847

42088 31433

67767 21924

12908 64554

6376 15443

15520 70460

3698 97859

6971 3698

2958 51165

108163 113138

24818 28189

89658 90475

119113 7269

54028 5040

37553 19853

2192 104519

31460 110705

110705 111128

58218 25811

23122 68909

33085 71174

114681 74713

23519 59550

57478 76096

39447 57478

15712 100086

22588 39076

39076 87045

[出力例]

301633020

■参照サイト
AtCoder Beginner Contest 291（Sponsored by TOYOTA SYSTEMS）

2023年2月26日

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

C++の練習を兼ねて, AtCoder Regular Contest 156 の問題C (Tree and LCS) を解いてみた.

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

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

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

// 解き直し.
// https://atcoder.jp/contests/arc156/editorial/5724
// 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 d[5050], ans[5050];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vvi G(N);
    rep(i, N - 1){
        int u, v;
        scanf("%d %d", &u, &v);
        --u;
        --v;
        G[u].pb(v);
        G[v].pb(u);
        ++d[u];
        ++d[v];
    }
    
    // 2. 解の構築.
    queue<int> q;
    rep(i, N) if(d[i] == 1) q.push(i);
    while(q.size() >= 2){
        // 頂点を二つ取り出す.
        int u = q.front();
        q.pop();
        int v = q.front();
        q.pop();
        
        // 頂点の次数(更新).
        --d[u];
        --d[v];
        
        // 順列を保存.
        ans[u] = v;
        ans[v] = u;
        
        // 頂点 u の 隣接頂点.
        for(auto &x : G[u]){
            if(!d[x] || x == v) continue;
            if(--d[x] == 1) q.push(x);
        }
        
        // 頂点 v の 隣接頂点.
        for(auto &x : G[v]){
            if(!d[x] || x == u) continue;
            if(--d[x] == 1) q.push(x);
        }
    }
    
    // 3. N が 奇数.
    if(N & 1) ans[q.front()] = q.front();
    
    // 4. 出力.
    rep(i, N) printf("%d%s", ans[i] + 1, (i < N - 1) ? " " : "\n");
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc156/editorial/5724

// 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 d[5050], ans[5050];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vvi G(N);

rep(i, N - 1){

int u, v;

scanf("%d %d", &u, &v);

--u;

--v;

G[u].pb(v);

G[v].pb(u);

++d[u];

++d[v];

}

// 2. 解の構築.

queue<int> q;

rep(i, N) if(d[i] == 1) q.push(i);

while(q.size() >= 2){

// 頂点を二つ取り出す.

int u = q.front();

q.pop();

int v = q.front();

q.pop();

// 頂点の次数(更新).

--d[u];

--d[v];

// 順列を保存.

ans[u] = v;

ans[v] = u;

// 頂点 u の隣接頂点.

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

if(!d[x] || x == v) continue;

if(--d[x] == 1) q.push(x);

}

// 頂点 v の隣接頂点.

for(auto &x : G[v]){

if(!d[x] || x == u) continue;

if(--d[x] == 1) q.push(x);

}

// 3. N が奇数.

if(N & 1) ans[q.front()] = q.front();

// 4. 出力.

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

return 0;

}

[入力例]
3
1 2
2 3

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

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

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

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

[出力例]
1 5 4 3 2

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

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

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

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

[入力例]

1 2

2 3

[出力例]

3 2 1

※AtCoderのテストケースより

[入力例]

2 1

2 3

2 4

[出力例]

3 4 1 2

※AtCoderのテストケースより

[入力例]

2 3

1 3

4 1

5 4

[出力例]

1 5 4 3 2

[入力例]

1 3

1 5

3 2

4 3

6 5

6 7

8 6

9 4

4 10

[出力例]

3 7 1 5 4 10 2 9 8 6

[入力例]

10 1

10 4

4 5

11 4

12 5

13 5

13 9

13 17

11 7

11 16

16 15

16 6

16 18

3 1

8 1

14 3

2 3

19 8

8 20

[出力例]

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

■参照サイト
AtCoder Regular Contest 156

2023年2月25日

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

C++の練習を兼ねて, AtCoder Regular Contest 156 の問題A (Non-Adjacent Flip) ～問題B (Mex on Blackboard) を解いてみた.

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

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

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

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

int main(){
    
    // 1. 入力情報.
    int T;
    scanf("%d", &T);
    
    // 2. テストケース.
    rep(i, T){
        // 2-1. 各テストケース.
        int N;
        scanf("%d", &N);
        char c[N + 1];
        scanf("%s", c);
        string s(c);
        
        // 2-2. 1 の 個数.
        vi v;
        rep(j, N) if(s[j] == '1') v.pb(j);
        
        // 2-3. 1 が 奇数個.
        int n = v.size();
        if(n & 1){
            puts("-1");
            continue;
        }
        
        // 2-4. 1 が 0個 or 4個以上.
        if(n == 0 || n >= 4){
            printf("%d\n", n / 2);
            continue;
        }
        
        // 2-5. 1 が 2個(隣接していない).
        if(v[0] + 1 != v[1]){
            printf("%d\n", n / 2);
            continue;
        }
        
        // 2-6. 1 が 2個(隣接している).
        // N が 3.
        if(N == 3){
            puts("-1");
            continue;
        }
        
        // N が 3 より大きい(110...00, または, 00...011).
        if((v[0] == 0 && v[1] == 1) || (v[0] == N - 2 && v[1] == N - 1)){
            puts("2");
            continue;
        }
        
        // N が 4(0110).
        if(N == 4){
            puts("3");
            continue;
        }
        
        // N が 4 より大きい(00...0110...00).
        puts("2");
    }
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

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

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

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

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

#define pb push_back

int main(){

// 1. 入力情報.

int T;

scanf("%d", &T);

// 2. テストケース.

rep(i, T){

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

int N;

scanf("%d", &N);

char c[N + 1];

scanf("%s", c);

string s(c);

// 2-2. 1 の個数.

vi v;

rep(j, N) if(s[j] == '1') v.pb(j);

// 2-3. 1 が奇数個.

int n = v.size();

if(n & 1){

puts("-1");

continue;

}

// 2-4. 1 が 0個 or 4個以上.

if(n == 0 || n >= 4){

printf("%d\n", n / 2);

continue;

}

// 2-5. 1 が 2個(隣接していない).

if(v[0] + 1 != v[1]){

printf("%d\n", n / 2);

continue;

}

// 2-6. 1 が 2個(隣接している).

// N が 3.

if(N == 3){

puts("-1");

continue;

}

// N が 3 より大きい(110...00, または, 00...011).

if((v[0] == 0 && v[1] == 1) || (v[0] == N - 2 && v[1] == N - 1)){

puts("2");

continue;

}

// N が 4(0110).

if(N == 4){

puts("3");

continue;

}

// N が 4 より大きい(00...0110...00).

puts("2");

}

return 0;

}

[入力例]
5
3
101
6
101101
5
11111
6
000000
30
111011100110101100101000000111

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

[入力例]
24
3
000
3
001
3
010
3
011
3
100
3
101
3
110
3
111
4
0000
4
0001
4
0010
4
0011
4
0100
4
0101
4
0110
4
0111
4
1000
4
1001
4
1010
4
1011
4
1100
4
1101
4
1110
4
1111

[出力例]
0
-1
-1
-1
-1
1
-1
-1
0
-1
-1
2
-1
1
3
-1
-1
1
1
-1
2
-1
-1
2

[入力例]
7
5
10111
10
1011010010
15
100111000011010
20
00000000011000000000
30
011011100101110110011101100011
50
10110001111001100000000010001010011110011000000011
100
1010000110110000010110100111101011100011000100001101010110110011101010000101001010101101111001010111

[出力例]
2
-1
-1
2
9
10
25

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

[入力例]

101

101101

11111

000000

111011100110101100101000000111

[出力例]

-1

※AtCoderのテストケースより

[入力例]

000

001

010

011

100

101

110

111

0000

0001

0010

0011

0100

0101

0110

0111

1000

1001

1010

1011

1100

1101

1110

1111

[出力例]

-1

[入力例]

10111

1011010010

100111000011010

00000000011000000000

011011100101110110011101100011

10110001111001100000000010001010011110011000000011

100

1010000110110000010110100111101011100011000100001101010110110011101010000101001010101101111001010111

[出力例]

-1

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

// 解き直し.
// https://atcoder.jp/contests/arc156/editorial/5718
// 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--)
const LL MOD = 998244353;
const int LIMIT = 404040;
LL FAC[LIMIT], INV[LIMIT];
int a[LIMIT], M[LIMIT], memo[LIMIT];

// Fermat's little theorem から, 大きな冪乗の計算を行う.
// @param a: べき乗したい正整数.
// @param b: 指数.
// @return:  べき乗した計算結果(mod版).
LL mPow(LL a, LL b){
    LL t = 1;
    while(b){
        if(b & 1) t = (t * a) % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return t;
}

// 組み合わせ(nCk)計算用(mod版).
// ※配列FAC, INV は, 事前に計算済のものを使う.
// @param n: 対象となる要素の個数.
// @param k: 選択する要素の個数.
// @return: 組み合わせ(nCk)の計算結果(mod版).
LL combination(LL n, LL k){
    if(n < 0 || k < 0 || k > n) return 0LL;
    if(n == k || k == 0LL) return 1LL;
    LL ret = FAC[n] * INV[k] % MOD * INV[n - k] % MOD;
    return ret;
}

int main(){
    
    // 1. 入力情報.
    int N, K;
    scanf("%d %d", &N, &K);
    rep(i, N){
        int p;
        scanf("%d", &p);
        a[p] = 1;
    }
    
    // 2. 事前準備.
    FAC[0] = INV[0] = 1;
    repx(i, 1, LIMIT){
        FAC[i] = (LL)i * FAC[i - 1] % MOD;
        INV[i] = mPow(FAC[i], MOD - 2);
    }
    
    // 3. M の 計算.
    int mMax = 0;
    rep(i, N + K + 1){
        if(i) M[i] = M[i - 1];
        if(a[i] == 0) M[i] = ++mMax;
    }
    
    // 4. 集計.
    // 
    // ex.
    // 8 5
    // 1 2 0 2 0 5 6 9
    // (K - M) が 等しい場合は, 操作で書く最大値 x の中で, 最も大きい部分だけ, 加算する.
    // ※重複して数えることを防止するため.
    // 
    // x = 12  K - M = -2  combination =  0
    // x = 11  K - M = -1  combination =  0
    // x = 10  K - M =  0  combination =  1 <- 加算対象.
    // x =  9  K - M =  1  combination = 10 <- 加算対象.
    // x =  8  K - M =  1  combination =  9
    // x =  7  K - M =  2  combination = 36 <- 加算対象.
    // x =  6  K - M =  3  combination = 84 <- 加算対象.
    // x =  5  K - M =  3  combination = 56
    // x =  4  K - M =  3  combination = 35
    // x =  3  K - M =  4  combination = 35 <- 加算対象.
    // x =  2  K - M =  5  combination = 21 <- 加算対象.
    // x =  1  K - M =  5  combination =  6
    // x =  0  K - M =  5  combination =  1
    // ->  加算対象を集計すると, 1 + 10 + 36 + 84 + 35 + 21 = 187 を 得る.
    LL ans = 0;
    repr(x, N + K - 1, 0){
        int km = K - M[x];
        if(km < 0 || memo[km]) continue;
        
        // 加算.
        ans = (ans + combination(K - M[x] + x, x)) % MOD;
        
        // 加算済.
        ++memo[km];
    }
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

100

101

102

103

104

105

// 解き直し.

// https://atcoder.jp/contests/arc156/editorial/5718

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

const LL MOD = 998244353;

const int LIMIT = 404040;

LL FAC[LIMIT], INV[LIMIT];

int a[LIMIT], M[LIMIT], memo[LIMIT];

// Fermat's little theorem から, 大きな冪乗の計算を行う.

// @param a: べき乗したい正整数.

// @param b: 指数.

// @return: べき乗した計算結果(mod版).

LL mPow(LL a, LL b){

LL t = 1;

while(b){

if(b & 1) t = (t * a) % MOD;

a = a * a % MOD;

b >>= 1;

}

return t;

}

// 組み合わせ(nCk)計算用(mod版).

// ※配列FAC, INV は, 事前に計算済のものを使う.

// @param n: 対象となる要素の個数.

// @param k: 選択する要素の個数.

// @return: 組み合わせ(nCk)の計算結果(mod版).

LL combination(LL n, LL k){

if(n < 0 || k < 0 || k > n) return 0LL;

if(n == k || k == 0LL) return 1LL;

LL ret = FAC[n] * INV[k] % MOD * INV[n - k] % MOD;

return ret;

}

int main(){

// 1. 入力情報.

int N, K;

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

rep(i, N){

int p;

scanf("%d", &p);

a[p] = 1;

}

// 2. 事前準備.

FAC[0] = INV[0] = 1;

repx(i, 1, LIMIT){

FAC[i] = (LL)i * FAC[i - 1] % MOD;

INV[i] = mPow(FAC[i], MOD - 2);

}

// 3. M の計算.

int mMax = 0;

rep(i, N + K + 1){

if(i) M[i] = M[i - 1];

if(a[i] == 0) M[i] = ++mMax;

}

// 4. 集計.

// ex.

// 8 5

// 1 2 0 2 0 5 6 9

// (K - M) が等しい場合は, 操作で書く最大値 x の中で, 最も大きい部分だけ, 加算する.

// ※重複して数えることを防止するため.

// x = 12 K - M = -2 combination = 0

// x = 11 K - M = -1 combination = 0

// x = 10 K - M = 0 combination = 1 <- 加算対象.

// x = 9 K - M = 1 combination = 10 <- 加算対象.

// x = 8 K - M = 1 combination = 9

// x = 7 K - M = 2 combination = 36 <- 加算対象.

// x = 6 K - M = 3 combination = 84 <- 加算対象.

// x = 5 K - M = 3 combination = 56

// x = 4 K - M = 3 combination = 35

// x = 3 K - M = 4 combination = 35 <- 加算対象.

// x = 2 K - M = 5 combination = 21 <- 加算対象.

// x = 1 K - M = 5 combination = 6

// x = 0 K - M = 5 combination = 1

// -> 加算対象を集計すると, 1 + 10 + 36 + 84 + 35 + 21 = 187 を得る.

LL ans = 0;

repr(x, N + K - 1, 0){

int km = K - M[x];

if(km < 0 || memo[km]) continue;

// 加算.

ans = (ans + combination(K - M[x] + x, x)) % MOD;

// 加算済.

++memo[km];

}

// 5. 出力.

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

return 0;

}

[入力例]
3 1
0 1 3

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

[入力例]
2 1
0 0

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

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

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

[入力例]
8 5
1 2 0 2 0 5 6 9

[出力例]
187

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

[出力例]
354522

[入力例]

3 1

0 1 3

[出力例]

※AtCoderのテストケースより

[入力例]

2 1

0 0

[出力例]

※AtCoderのテストケースより

[入力例]

5 10

3 1 4 1 5

[出力例]

7109

※AtCoderのテストケースより

[入力例]

8 5

1 2 0 2 0 5 6 9

[出力例]

187

[入力例]

20 10

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

[出力例]

354522

■参照サイト
AtCoder Regular Contest 156

2023年2月23日

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

C++の練習を兼ねて, AtCoder Regular Contest 147 の問題C (Min Diff Sum) ～問題D (Sets Scores) を解いてみた.

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

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

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vl L(N), R(N);
    rep(i, N) scanf("%lld %lld", &L[i], &R[i]);
    
    // 2. sort(※解説通り).
    // -> L: 降順, R: 昇順
    // ※解説を読み間違えたように見えるため, L, R を 独立して, sortするように, ロジック変更.
    sort(all(L));
    reverse(all(L));
    sort(all(R));
    
    // 3. 集計.
    LL ans = 0;
    rep(i, N) ans += max(0LL, L[i] - R[i]) * (LL)(N - 2 * i - 1);
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc147/editorial/4667

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

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vl L(N), R(N);

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

// 2. sort(※解説通り).

// -> L: 降順, R: 昇順

// ※解説を読み間違えたように見えるため, L, R を独立して, sortするように, ロジック変更.

sort(all(L));

reverse(all(L));

sort(all(R));

// 3. 集計.

LL ans = 0;

rep(i, N) ans += max(0LL, L[i] - R[i]) * (LL)(N - 2 * i - 1);

// 4. 出力.

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

return 0;

}

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

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

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

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

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

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

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

[出力例]
8

[入力例]
10
7 16
12 22
11 19
6 20
2 9
13 14
2 21
7 25
2 10
17 19

[出力例]
93

[入力例]

1 3

2 4

5 6

[出力例]

※AtCoderテストケースより

[入力例]

1 1

[出力例]

※AtCoderテストケースより

[入力例]

1 5

2 4

1 1

4 4

3 6

3 3

[出力例]

※AtCoderテストケースより

[入力例]

1 3

1 4

5 9

2 6

3 5

[出力例]

[入力例]

7 16

12 22

11 19

6 20

2 9

13 14

2 21

7 25

2 10

17 19

[出力例]

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

// 解き直し.
// https://atcoder.jp/contests/arc147/editorial/4746
// 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--)
const LL MOD = 998244353;

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    
    // 2. 冪乗.
    LL ans = 1;
    rep(i, M) ans = (N * ans) % MOD;
    rep(i, N - 1) ans = (M * ans) % MOD;
    
    // 3. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc147/editorial/4746

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

const LL MOD = 998244353;

int main(){

// 1. 入力情報.

int N, M;

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

// 2. 冪乗.

LL ans = 1;

rep(i, M) ans = (N * ans) % MOD;

rep(i, N - 1) ans = (M * ans) % MOD;

// 3. 出力.

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

return 0;

}

[入力例]
2 3

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

[入力例]
12 34

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

[入力例]
2 5

[出力例]
160

[入力例]
7 10

[出力例]
47942884

[入力例]
20 23

[出力例]
57177154

[入力例]

2 3

[出力例]

※AtCoderテストケースより

[入力例]

12 34

[出力例]

786334067

※AtCoderテストケースより

[入力例]

2 5

[出力例]

160

[入力例]

7 10

[出力例]

47942884

[入力例]

20 23

[出力例]

57177154

■参照サイト
AtCoder Regular Contest 147

2023年2月19日2023年2月19日

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

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

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

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

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

// 解き直し.
// https://atcoder.jp/contests/arc112/editorial/719
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vs = vector<set<int>>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
int board[1010][1010];

int main(){
    
    // 1. 入力情報.
    int h, w;
    scanf("%d %d", &h, &w);
    rep(i, h){
        char c[1010];
        scanf("%s", c);
        rep(j, w) board[i][j] = (c[j] == '#');
    }
    
    // 2. スケートリンク四隅.
    board[0][0] = board[0][w - 1] = board[h - 1][0] = board[h - 1][w - 1] = 1;
    
    // 3. グラフ作成.
    // 3-1. 行方向.
    vs H(h);
    rep(j, w){
        int b = -1;
        rep(i, h){
            if(board[i][j]){
                // 辺追加.
                if(b != -1){
                    H[b].insert(i);
                    H[i].insert(b);
                }
                
                // 前回分更新.
                b = i;
            }
        }
    }
    
    // 3-2. 列方向.
    vs W(w);
    rep(i, h){
        int b = -1;
        rep(j, w){
            if(board[i][j]){
                // 辺追加.
                if(b != -1){
                    W[b].insert(j);
                    W[j].insert(b);
                }
                
                // 前回分更新.
                b = j;
            }
        }
    }
    
    // 4. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vs &G, int s, int* c, int l){
        // 空のキュー.
        queue<int> q;
        
        // 連結成分番号を設定.
        c[s] = l;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 隣接頂点をチェック.
            for(auto &e : G[u]) if(!c[e] && e != s) c[e] = l, q.push(e);
        }
    };
    
    // 5. 連結成分への分解.
    // 5-1. 行方向.
    int hc[h], hIdx = 0;
    rep(i, h) hc[i] = 0;
    rep(i, h) if(!hc[i]) bfs(H, i, hc, ++hIdx);
    
    // 5-2. 列方向.
    int wc[w], wIdx = 0;
    rep(i, w) wc[i] = 0;
    rep(i, w) if(!wc[i]) bfs(W, i, wc, ++wIdx);
    
    // 6. 出力.
    printf("%d\n", min(hIdx, wIdx) - 1);
    return 0;
    
}

100

// 解き直し.

// https://atcoder.jp/contests/arc112/editorial/719

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vs = vector<set<int>>;

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

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

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

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

int board[1010][1010];

int main(){

// 1. 入力情報.

int h, w;

scanf("%d %d", &h, &w);

rep(i, h){

char c[1010];

scanf("%s", c);

rep(j, w) board[i][j] = (c[j] == '#');

}

// 2. スケートリンク四隅.

board[0][0] = board[0][w - 1] = board[h - 1][0] = board[h - 1][w - 1] = 1;

// 3. グラフ作成.

// 3-1. 行方向.

vs H(h);

rep(j, w){

int b = -1;

rep(i, h){

if(board[i][j]){

// 辺追加.

if(b != -1){

H[b].insert(i);

H[i].insert(b);

}

// 前回分更新.

b = i;

}

// 3-2. 列方向.

vs W(w);

rep(i, h){

int b = -1;

rep(j, w){

if(board[i][j]){

// 辺追加.

if(b != -1){

W[b].insert(j);

W[j].insert(b);

}

// 前回分更新.

b = j;

}

// 4. bfs.

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

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

// 空のキュー.

queue<int> q;

// 連結成分番号を設定.

c[s] = l;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

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

}

};

// 5. 連結成分への分解.

// 5-1. 行方向.

int hc[h], hIdx = 0;

rep(i, h) hc[i] = 0;

rep(i, h) if(!hc[i]) bfs(H, i, hc, ++hIdx);

// 5-2. 列方向.

int wc[w], wIdx = 0;

rep(i, w) wc[i] = 0;

rep(i, w) if(!wc[i]) bfs(W, i, wc, ++wIdx);

// 6. 出力.

printf("%d\n", min(hIdx, wIdx) - 1);

return 0;

}

[入力例]
3 9
.........
.........
.........

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

[入力例]
10 10
..........
#...#.....
..........
..........
..........
....#.....
.#......#.
..........
..........
..........

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

[入力例]
2 2
..
..

[出力例]
0

[入力例]
3 3
...
...
...

[出力例]
1

[入力例]
8 7
.......
..#....
.##....
..#....
..#....
..#....
...#..#
.......

[出力例]
1

[入力例]
8 13
.............
.............
..#.......#..
.............
....#...#....
.............
......#......
.............

[出力例]
6

[入力例]
15 28
............................
............................
..####...###..####...####...
......#.#...#.....#......#..
......#.#...#.....#......#..
......#.#...#.....#......#..
......#.#...#.....#......#..
...###..#...#..###...#####..
..#.....#...#.#..........#..
..#.....#...#.#..........#..
..#.....#...#.#..........#..
..#.....#...#.#..........#..
...####..###...####..####...
............................
............................

[出力例]
3

[入力例]
27 75
...........................................................................
...........................................................................
...........................................................................
.......#.......#######.......#####........##.........##......########......
......#.#......#......#.....#.....#......#.#........#.#..............#.....
......#.#......#.......#...#.......#....#..#.......#..#..............#.....
.....#...#.....#......#....#...............#..........#..............#.....
.....#...#.....#.#####.....#...............#..........#.......#######......
....#.###.#....#..#........#...............#..........#......#.............
....#.....#....#...#.......#.......#.......#..........#......#.............
...#.......#...#....##......#.....#........#..........#......#.............
...#.......#...#......##.....#####.....#########..#########...########.....
...........................................................................
...........................................................................
...........................................................................
....########.......##..........##........#####......#######......#.........
...#...............#.#.........#.#......#.....#....#......#.....#.#........
...#...............#..#........#..#....#.......#..#.......#.....#.#........
...#...............#...........#...............#...#......#....#...#.......
....#######........#...........#...............#....#####.#....#...#.......
...........#.......#...........#...............#.......#..#...#.###.#......
...........#.......#...........#.......#.......#......#...#...#.....#......
...........#.......#...........#........#.....#.....##....#..#.......#.....
...########....#########...#########.....#####.....##.....#..#.......#.....
...........................................................................
...........................................................................
...........................................................................

[出力例]
8

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

[入力例]

3 9

.........

[出力例]

※AtCoderテストケースより

[入力例]

10 10

..........

#...#.....

..........

....#.....

.#......#.

..........

[出力例]

※AtCoderテストケースより

[入力例]

2 2

[出力例]

[入力例]

3 3

...

[出力例]

[入力例]

8 7

.......

..#....

.##....

..#....

...#..#

.......

[出力例]

[入力例]

8 13

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

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

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

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

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

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

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

[出力例]

[入力例]

15 28

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

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

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

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

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

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

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

[出力例]

[入力例]

27 75

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[出力例]

■参照サイト
AtCoder Regular Contest 112

2023年2月18日

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

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

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

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

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

// 解き直し.
// https://atcoder.jp/contests/abc275/editorial/5140
// 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--)
const int INF = 2020202020;
int dp[3030][3030][2], a[3030];

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    rep(i, N) scanf("%d", &a[i + 1]);
    
    // 2. 初期化.
    rep(i, 3030) rep(j, 3030) rep(k, 2) dp[i][j][k] = INF;
    dp[0][0][1] = 0;
    
    // 3. dp更新.
    repx(i, 1, N + 1){
        // 解説通り.
        rep(j, M + 1){
            // b[i - 1] = 0, b[i] = 0.
            dp[i][j][0] = min(dp[i][j][0], dp[i - 1][j][0]);
            
            // b[i - 1] = 0, b[i] = 1.
            int nj = j + a[i];
            if(nj <= M) dp[i][nj][1] = min(dp[i][nj][1], dp[i - 1][j][0]);
            
            // b[i - 1] = 1, b[i] = 0.
            dp[i][j][0] = min(dp[i][j][0], dp[i - 1][j][1] + 1);
            
            // b[i - 1] = 1, b[i] = 1.
            if(nj <= M) dp[i][nj][1] = min(dp[i][nj][1], dp[i - 1][j][1]);
        }
    }
    
    // 4. 出力.
    repx(i, 1, M + 1){
        int ans = min(dp[N][i][0], dp[N][i][1]);
        printf("%d\n", (ans == INF) ? -1 : ans);
    }
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc275/editorial/5140

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

const int INF = 2020202020;

int dp[3030][3030][2], a[3030];

int main(){

// 1. 入力情報.

int N, M;

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

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

// 2. 初期化.

rep(i, 3030) rep(j, 3030) rep(k, 2) dp[i][j][k] = INF;

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

// 3. dp更新.

repx(i, 1, N + 1){

// 解説通り.

rep(j, M + 1){

// b[i - 1] = 0, b[i] = 0.

dp[i][j][0] = min(dp[i][j][0], dp[i - 1][j][0]);

// b[i - 1] = 0, b[i] = 1.

int nj = j + a[i];

if(nj <= M) dp[i][nj][1] = min(dp[i][nj][1], dp[i - 1][j][0]);

// b[i - 1] = 1, b[i] = 0.

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

// b[i - 1] = 1, b[i] = 1.

if(nj <= M) dp[i][nj][1] = min(dp[i][nj][1], dp[i - 1][j][1]);

}

// 4. 出力.

repx(i, 1, M + 1){

int ans = min(dp[N][i][0], dp[N][i][1]);

printf("%d\n", (ans == INF) ? -1 : ans);

}

return 0;

}

[入力例]
4 5
1 2 3 4

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

[入力例]
1 5
3

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

[入力例]
12 20
2 5 6 5 2 1 7 9 7 2 5 5

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

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

[出力例]
1
1
1

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

[出力例]
2
1
1
1
1

[入力例]
30 12
1 21 20 1 39 8 22 30 16 13 108 11 1 32 1 111 10 15 13 1 100 17 21 15 25 10 18 24 55 1

[出力例]
1
1
2
3
4
5
-1
2
2
2
2
2

[入力例]
50 30
130 12 108 147 161 33 25 198 152 187 195 17 39 201 33 192 79 154 202 8 80 215 7 168 181 150 187 73 169 67 64 88 205 1 128 120 60 105 1 37 220 97 134 1 25 177 31 113 189 1

[出力例]
1
2
3
4
-1
-1
2
2
2
3
4
2
2
3
3
3
2
2
3
3
3
4
5
3
2
2
2
3
3
3

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

[入力例]

4 5

1 2 3 4

[出力例]

※AtCoderテストケースより

[入力例]

1 5

[出力例]

-1

※AtCoderテストケースより

[入力例]

12 20

2 5 6 5 2 1 7 9 7 2 5 5

[出力例]

※AtCoderテストケースより

[入力例]

5 3

1 2 3 2 1

[出力例]

[入力例]

7 5

3 1 4 1 5 9 2

[出力例]

[入力例]

30 12

1 21 20 1 39 8 22 30 16 13 108 11 1 32 1 111 10 15 13 1 100 17 21 15 25 10 18 24 55 1

[出力例]

-1

[入力例]

50 30

130 12 108 147 161 33 25 198 152 187 195 17 39 201 33 192 79 154 202 8 80 215 7 168 181 150 187 73 169 67 64 88 205 1 128 120 60 105 1 37 220 97 134 1 25 177 31 113 189 1

[出力例]

-1

■参照サイト
AtCoder Beginner Contest 275

2023年2月15日

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

C++の練習を兼ねて, AtCoder Grand Contest 014 の問題D (Black and White Tree) を解いてみた.

■感想.
1. 問題D は, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 木の完全マッチングについて, 学習できたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/agc014/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
int memo[101010];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    set<int> G[N];
    rep(i, N - 1){
        int a, b;
        scanf("%d %d", &a, &b);
        --a, --b;
        G[a].insert(b);
        G[b].insert(a);
    }
    
    // 2. 完全マッチング.
    // https://en.wikipedia.org/wiki/Matching_(graph_theory)
    auto isPerfectMatching = [&]() -> bool {
        // 空のキュー.
        queue<int> q;
        
        // 葉を保存.
        rep(i, N) if(G[i].size() == 1) q.push(i);
        
        // キューを処理.
        while(!q.empty()){
            // キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 次へ.
            if(memo[u]) continue;
            
            // 探索.
            int v = -1;
            for(auto &x : G[u]){
                if(!memo[x]){
                    v = x;
                    break;
                }
            }
            
            // 未マッチングの頂点がある場合.
            if(v != -1){
                // マッチングを行う.
                ++memo[u];
                ++memo[v];
                
                // 隣接頂点をチェック.
                for(auto &x : G[v]){
                    // 辺 (x, v) を 削除.
                    G[x].erase(v);
                    
                    // 葉を保存.
                    if(x != u && G[x].size() == 1) q.push(x);
                }
                
                // 辺 (u, ?) を すべて削除.
                G[u].clear();
            }
        }
        
        // 見つからなかった.
        rep(i, N) if(!memo[i]) return false;
        
        // 見つかった.
        return true;
    };
    
    // 3. 出力.
    printf("%s\n", isPerfectMatching() ? "Second" : "First");
    return 0;
    
}

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

int memo[101010];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

set<int> G[N];

rep(i, N - 1){

int a, b;

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

--a, --b;

G[a].insert(b);

G[b].insert(a);

}

// 2. 完全マッチング.

// https://en.wikipedia.org/wiki/Matching_(graph_theory)

auto isPerfectMatching = [&]() -> bool {

// 空のキュー.

queue<int> q;

// 葉を保存.

rep(i, N) if(G[i].size() == 1) q.push(i);

// キューを処理.

while(!q.empty()){

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

int u = q.front();

q.pop();

// 次へ.

if(memo[u]) continue;

// 探索.

int v = -1;

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

if(!memo[x]){

v = x;

break;

}

// 未マッチングの頂点がある場合.

if(v != -1){

// マッチングを行う.

++memo[u];

++memo[v];

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

for(auto &x : G[v]){

// 辺 (x, v) を削除.

G[x].erase(v);

// 葉を保存.

if(x != u && G[x].size() == 1) q.push(x);

}

// 辺 (u, ?) をすべて削除.

G[u].clear();

}

// 見つからなかった.

rep(i, N) if(!memo[i]) return false;

// 見つかった.

return true;

};

// 3. 出力.

printf("%s\n", isPerfectMatching() ? "Second" : "First");

return 0;

}

[入力例]
3
1 2
2 3

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

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

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

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

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

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

[出力例]
Second

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

[出力例]
First

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

[出力例]
Second

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

[出力例]
First

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

[出力例]
Second

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

[入力例]

1 2

2 3

[出力例]

First

※AtCoderテストケースより

[入力例]

1 2

2 3

2 4

[出力例]

First

※AtCoderテストケースより

[入力例]

1 2

2 3

3 4

2 5

5 6

[出力例]

Second

※AtCoderテストケースより

[入力例]

1 2

8 2

1 7

1 5

6 5

5 4

4 3

[出力例]

Second

[入力例]

1 2

2 3

3 4

4 5

[出力例]

First

[入力例]

1 2

3 1

4 1

2 5

2 6

6 7

3 8

9 8

10 4

[出力例]

Second

[入力例]

1 2

2 15

16 2

3 1

4 3

6 3

14 6

5 3

7 5

5 8

8 9

9 12

8 10

10 13

8 11

[出力例]

First

[入力例]

1 17

18 17

1 9

10 1

2 1

8 2

2 3

3 7

3 4

5 4

6 4

11 6

19 7

19 20

21 19

21 22

10 12

10 13

13 14

15 14

16 15

[出力例]

Second

■参照サイト
AtCoder Grand Contest 014

2023年2月11日

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

C++の練習を兼ねて, AtCoder Regular Contest 112 の問題C (DFS Game) を解いてみた.

■感想.
1. 問題C は, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 解説のロジックで計算可能であることが, 不思議な感じがするとともに, 非常に面白く感じた.
3. 深さ優先探索の訓練を積めたので, 非常に良かったと思う.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vvi G(N);
    repx(i, 1, N){
        int p;
        scanf("%d", &p);
        --p;
        G[p].pb(i);
        G[i].pb(p);
    }
    
    // 2. dfs(部分木サイズ).
    // https://ja.wikipedia.org/wiki/深さ優先探索
    auto dfs1 = [](auto&& self, vvi &G, int cur, int bef, int* m, int* s) -> void {
        // 部分木サイズ(往路).
        s[cur]++;
        
        // 終了条件.
        if(m[cur]) return;
        
        // 訪問済みフラグ.
        m[cur] = 1;
        
        // 隣接頂点.
        for(auto &nex : G[cur]){
            if(nex == bef) continue;
            self(self, G, nex, cur, m, s);
        }
        
        // 部分木サイズ(復路).
        if(bef != -1) s[bef] += s[cur];
    };
    int subTree[N], memo[N];
    rep(i, N) subTree[i] = memo[i] = 0;
    dfs1(dfs1, G, 0, -1, memo, subTree);
    // rep(i, N) printf("subTree[%d]=%d\n", i, subTree[i]);
    
    // 3. dfs(ゲーム).
    // https://ja.wikipedia.org/wiki/深さ優先探索
    function<int(vvi&, int, int, int*, int*)> dfs2 = [&](vvi &G, int bef, int cur, int* dp, int* m) {
        // 終了条件.
        if(m[cur]) return dp[cur];
        
        // 訪問済みフラグ.
        m[cur] = 1;
        
        // コイン回収.
        ++dp[cur];
        
        // 葉っぱ(根は除く).
        if(cur != 0 && G[cur].size() == 1) return dp[cur];
        
        // 隣接頂点.
        vi f1, f2, f3;
        for(auto &nex : G[cur]){
            // 次へ.
            if(nex == bef) continue;
            
            // 部分木(頂点 nex) の f.
            int f = dfs2(G, cur, nex, dp, m);
            
            // 保存(パターン③).
            if(subTree[nex] & 1){
                f3.pb(f);
                continue;
            }
            
            // 保存(パターン①, ②).
            if(f < 0) f1.pb(f);
            else      f2.pb(f);
        }
        
        // sort.
        sort(all(f3));
        
        // 集計(パターン①).
        for(auto &f : f1) dp[cur] += f;
        
        // 集計(パターン③).
        int t = 0;
        for(auto &f : f3){
            dp[cur] += t ? -f : +f;
            t ^= 1;
        }
        
        // 集計(パターン②).
        for(auto &f : f2) dp[cur] += t ? -f : +f;
        
        // 返却.
        return dp[cur];
    };
    int dp[N];
    rep(i, N) dp[i] = memo[i] = 0;
    dfs2(G, -1, 0, dp, memo);
    // rep(i, N) printf("dp[%d]=%d\n", i, dp[i]);
    
    // 4. 出力.
    printf("%d\n", (dp[0] + N) / 2);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

// 解き直し.

// https://atcoder.jp/contests/arc112/editorial/724

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

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

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

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

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

#define pb push_back

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

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vvi G(N);

repx(i, 1, N){

int p;

scanf("%d", &p);

--p;

G[p].pb(i);

G[i].pb(p);

}

// 2. dfs(部分木サイズ).

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

auto dfs1 = [](auto&& self, vvi &G, int cur, int bef, int* m, int* s) -> void {

// 部分木サイズ(往路).

s[cur]++;

// 終了条件.

if(m[cur]) return;

// 訪問済みフラグ.

m[cur] = 1;

// 隣接頂点.

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

if(nex == bef) continue;

self(self, G, nex, cur, m, s);

}

// 部分木サイズ(復路).

if(bef != -1) s[bef] += s[cur];

};

int subTree[N], memo[N];

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

dfs1(dfs1, G, 0, -1, memo, subTree);

// rep(i, N) printf("subTree[%d]=%d\n", i, subTree[i]);

// 3. dfs(ゲーム).

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

function<int(vvi&, int, int, int*, int*)> dfs2 = [&](vvi &G, int bef, int cur, int* dp, int* m) {

// 終了条件.

if(m[cur]) return dp[cur];

// 訪問済みフラグ.

m[cur] = 1;

// コイン回収.

++dp[cur];

// 葉っぱ(根は除く).

if(cur != 0 && G[cur].size() == 1) return dp[cur];

// 隣接頂点.

vi f1, f2, f3;

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

// 次へ.

if(nex == bef) continue;

// 部分木(頂点 nex) の f.

int f = dfs2(G, cur, nex, dp, m);

// 保存(パターン③).

if(subTree[nex] & 1){

f3.pb(f);

continue;

}

// 保存(パターン①, ②).

if(f < 0) f1.pb(f);

else f2.pb(f);

}

// sort.

sort(all(f3));

// 集計(パターン①).

for(auto &f : f1) dp[cur] += f;

// 集計(パターン③).

int t = 0;

for(auto &f : f3){

dp[cur] += t ? -f : +f;

t ^= 1;

}

// 集計(パターン②).

for(auto &f : f2) dp[cur] += t ? -f : +f;

// 返却.

return dp[cur];

};

int dp[N];

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

dfs2(G, -1, 0, dp, memo);

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

// 4. 出力.

printf("%d\n", (dp[0] + N) / 2);

return 0;

}

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

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

[入力例]
5
1 2 3 1

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

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

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

[入力例]
15
1 2 3 3 3 2 1 8 8 1 11 11 13 13

[出力例]
8

[入力例]
27
1 2 2 2 5 5 1 8 8 10 10 1 13 14 14 13 13 18 18 18 1 22 22 22 25 25

[出力例]
15

[入力例]
33
3 1 5 2 5 1 1 3 9 9 7 12 12 14 14 8 17 17 17 19 19 1 23 23 8 24 25 28 28 16 16 2

[出力例]
16

[入力例]

1 2 3 4 5 6 7 8 9

[出力例]

※AtCoderのテストケースより

[入力例]

1 2 3 1

[出力例]

※AtCoderのテストケースより

[入力例]

1 1 3 1 3 6 7 6 6

[出力例]

※AtCoderのテストケースより

[入力例]

1 2 3 3 3 2 1 8 8 1 11 11 13 13

[出力例]

[入力例]

1 2 2 2 5 5 1 8 8 10 10 1 13 14 14 13 13 18 18 18 1 22 22 22 25 25

[出力例]

[入力例]

3 1 5 2 5 1 1 3 9 9 7 12 12 14 14 8 17 17 17 19 19 1 23 23 8 24 25 28 28 16 16 2

[出力例]

■参照サイト
AtCoder Regular Contest 112

2023年2月8日

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

C++の練習を兼ねて, AtCoder Beginner Contest 287 の問題C (Path Graph?) ～問題E (Karuta) を解いてみた.

■感想.
1. 問題E は, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 問題C で, 幅優先探索, 問題E で再帰処理の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    vvi G(N);
    rep(i, M){
        int u, v;
        scanf("%d %d", &u, &v);
        --u;
        --v;
        G[u].pb(v);
        G[v].pb(u);
    }
    
    // 2. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, int* c, int l){
        // 空のキュー.
        queue<int> q;
        
        // 連結成分番号を設定.
        c[s] = l;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 取り出した要素を処理.
            for(auto &e : G[u]) if(!c[e] && e != s) c[e] = l, q.push(e);
        }
    };
    int c[N], idx = 0;
    rep(i, N) c[i] = 0;
    rep(i, N) if(!c[i]) bfs(G, i, c, ++idx);
    
    // 3. 次数 1, 2 の 頂点 を 数える.
    int one = 0, two = 0;
    rep(i, N){
        if(G[i].size() == 1) ++one;
        if(G[i].size() == 2) ++two;
    }
    
    // 4. 出力.
    printf("%s\n", (idx == 1 && one == 2 && two == (N - 2)) ? "Yes" : "No");
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

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

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

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

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

#define pb push_back

int main(){

// 1. 入力情報.

int N, M;

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

vvi G(N);

rep(i, M){

int u, v;

scanf("%d %d", &u, &v);

--u;

--v;

G[u].pb(v);

G[v].pb(u);

}

// 2. bfs.

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

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

// 空のキュー.

queue<int> q;

// 連結成分番号を設定.

c[s] = l;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

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

}

};

int c[N], idx = 0;

rep(i, N) c[i] = 0;

rep(i, N) if(!c[i]) bfs(G, i, c, ++idx);

// 3. 次数 1, 2 の頂点を数える.

int one = 0, two = 0;

rep(i, N){

if(G[i].size() == 1) ++one;

if(G[i].size() == 2) ++two;

}

// 4. 出力.

printf("%s\n", (idx == 1 && one == 2 && two == (N - 2)) ? "Yes" : "No");

return 0;

}

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

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

[入力例]
2 0

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

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

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

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

[出力例]
Yes

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

[出力例]
Yes

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

[出力例]
No

[入力例]

4 3

1 3

4 2

3 2

[出力例]

Yes

※AtCoderテストケースより

[入力例]

2 0

[出力例]

※AtCoderテストケースより

[入力例]

5 5

1 2

2 3

3 4

4 5

5 1

[出力例]

※AtCoderテストケースより

[入力例]

5 4

1 2

2 3

3 4

4 5

[出力例]

Yes

[入力例]

7 6

3 2

2 1

1 7

7 6

6 5

5 4

[出力例]

Yes

[入力例]

5 4

1 2

5 3

3 4

4 5

[出力例]

■C++版プログラム(問題D／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[303030], t[303030];
    scanf("%s %s", s, t);
    string S(s), T(t);
    
    // 2. 一致するか？
    int ss = S.size(), ts = T.size(), l = 0, r = 0;
    rep(i, ts){
        if(S[i] == T[i] || S[i] == '?' || T[i] == '?') ++l;
        else                                           break;
    }
    repr(i, ss - 1, 0){
        int j = i - (ss - ts);
        if(j >= 0 && S[i] == T[j] || S[i] == '?' || T[j] == '?') ++r;
        else                                                     break;
    }
    
    // 3. 出力.
    rep(x, ts + 1) printf("%s\n", ((x <= l) && (ts - x <= r)) ? "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[303030], t[303030];

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

string S(s), T(t);

// 2. 一致するか？

int ss = S.size(), ts = T.size(), l = 0, r = 0;

rep(i, ts){

if(S[i] == T[i] || S[i] == '?' || T[i] == '?') ++l;

else break;

}

repr(i, ss - 1, 0){

int j = i - (ss - ts);

if(j >= 0 && S[i] == T[j] || S[i] == '?' || T[j] == '?') ++r;

else break;

}

// 3. 出力.

rep(x, ts + 1) printf("%s\n", ((x <= l) && (ts - x <= r)) ? "Yes" : "No");

return 0;

}

[入力例]
a?c
b?

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

[入力例]
atcoder
?????

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

[入力例]
beginner
contest

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

[入力例]
aaaaa
aaa

[出力例]
Yes
Yes
Yes
Yes

[入力例]
gr?en?pp?e
gapple

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

[入力例]
?trawberry
berry

[出力例]
Yes
Yes
No
No
No
No

[入力例]
onep?usone??two
?ne?two

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

[入力例]

a?c

[出力例]

Yes

※AtCoderテストケースより

[入力例]

atcoder

?????

[出力例]

Yes

※AtCoderテストケースより

[入力例]

beginner

contest

[出力例]

※AtCoderテストケースより

[入力例]

aaaaa

aaa

[出力例]

Yes

[入力例]

gr?en?pp?e

gapple

[出力例]

Yes

[入力例]

?trawberry

berry

[出力例]

Yes

[入力例]

onep?usone??two

?ne?two

[出力例]

Yes

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

// 解き直し.
// https://atcoder.jp/contests/abc287/editorial/5609
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vs = vector<string>;
using vi = vector<int>;
using vvi = vector<vi>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define all(x) x.begin(), x.end()
int memo[505050];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vs v;
    rep(i, N){
        string s;
        cin >> s;
        v.pb(s);
    }
    
    // 2. dfs.
    // https://ja.wikipedia.org/wiki/深さ優先探索
    auto dfs = [&](auto&& self, vi& idxs, int k) -> void {
        // グループ分け.
        vvi g(26);
        for(auto &idx : idxs) g[v[idx][k] - 'a'].pb(idx);
        
        // max LCP 設定.
        rep(i, 26){
            // グループサイズが, 1以下.
            int gs = g[i].size();
            if(gs == 0) continue;
            if(gs == 1){
                memo[g[i][0]] = k;
                continue;
            }
            
            // グループサイズが, 2以上.
            rep(j, gs) if(v[g[i][j]].size() == k + 1) memo[g[i][j]] = k + 1;
        }
        
        // 再帰処理.
        rep(i, 26){
            vi ng;
            for(auto &idx : g[i]) if(memo[idx] == -1) ng.pb(idx);
            if(ng.size()) self(self, ng, k + 1);
        }
    };
    rep(i, 505050) memo[i] = -1;
    vi idxs(N);
    iota(all(idxs), 0);
    dfs(dfs, idxs, 0);
    
    // 3. 出力.
    rep(i, N) printf("%d\n", memo[i]);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc287/editorial/5609

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vs = vector<string>;

using vi = vector<int>;

using vvi = vector<vi>;

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

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

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

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

#define pb push_back

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

int memo[505050];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vs v;

rep(i, N){

string s;

cin >> s;

v.pb(s);

}

// 2. dfs.

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

auto dfs = [&](auto&& self, vi& idxs, int k) -> void {

// グループ分け.

vvi g(26);

for(auto &idx : idxs) g[v[idx][k] - 'a'].pb(idx);

// max LCP 設定.

rep(i, 26){

// グループサイズが, 1以下.

int gs = g[i].size();

if(gs == 0) continue;

if(gs == 1){

memo[g[i][0]] = k;

continue;

}

// グループサイズが, 2以上.

rep(j, gs) if(v[g[i][j]].size() == k + 1) memo[g[i][j]] = k + 1;

}

// 再帰処理.

rep(i, 26){

vi ng;

for(auto &idx : g[i]) if(memo[idx] == -1) ng.pb(idx);

if(ng.size()) self(self, ng, k + 1);

}

};

rep(i, 505050) memo[i] = -1;

vi idxs(N);

iota(all(idxs), 0);

dfs(dfs, idxs, 0);

// 3. 出力.

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

return 0;

}

[入力例]
3
abc
abb
aac

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

[入力例]
11
abracadabra
bracadabra
racadabra
acadabra
cadabra
adabra
dabra
abra
bra
ra
a

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

[入力例]
12
pqr
pq
pqrs
pqrst
pqq
pqrstu
pqrr
pqrss
pqrst
q
qr
qrs

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

[入力例]
30
abccb
bcbcac
bccbcba
bcbaaacc
dcbaaccbc
acabcababc
abcbabaabcc
cbabccbaaacb
baccccbaccbba
cabcbcccaccbbb
aaaaabaccaaabab
ebacbcaaccaaccba
bccbbaaaacbcaacab
bbbaaccbcbbbbcaccc
aabaabccbccbcbcaaba
abcabcabcabcacaabbca
aabbbacbbaabcaaabac
faaaaacacbaaabcbbc
bbbbabcccccbaaccc
abcabcabccaaabca
bbccccaccabcbaa
abcabcaabcbbcc
caacbbabccbca
abcabcabcabc
gacabcacbba
bcccacbccaac
abccbcbcabaac
cbbaacbaccccca
baccabaacababbb
cbaacbacaaabbcbb

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

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

[入力例]

abc

abb

aac

[出力例]

※AtCoderテストケースより

[入力例]

abracadabra

bracadabra

racadabra

acadabra

cadabra

adabra

dabra

abra

bra

[出力例]

※AtCoderテストケースより

[入力例]

pqr

pqrs

pqrst

pqq

pqrstu

pqrr

pqrss

pqrst

qrs

[出力例]

[入力例]

abccb

bcbcac

bccbcba

bcbaaacc

dcbaaccbc

acabcababc

abcbabaabcc

cbabccbaaacb

baccccbaccbba

cabcbcccaccbbb

aaaaabaccaaabab

ebacbcaaccaaccba

bccbbaaaacbcaacab

bbbaaccbcbbbbcaccc

aabaabccbccbcbcaaba

abcabcabcabcacaabbca

aabbbacbbaabcaaabac

faaaaacacbaaabcbbc

bbbbabcccccbaaccc

abcabcabccaaabca

bbccccaccabcbaa

abcabcaabcbbcc

caacbbabccbca

abcabcabcabc

gacabcacbba

bcccacbccaac

abccbcbcabaac

cbbaacbaccccca

baccabaacababbb

cbaacbacaaabbcbb

[出力例]

■参照サイト
ユニークビジョンプログラミングコンテスト2023 新春 (AtCoder Beginner Contest 287)

2023年2月5日2023年2月5日

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

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

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

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

■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--)
const LL MOD = 998244353;
LL dp[2][1010], mPowA[1010], mPowB[1010];

// Fermat's little theorem から, 大きな冪乗の計算を行う.
// @param a: べき乗したい正整数.
// @param b: 指数.
// @return:  べき乗した計算結果(mod版).
LL mPow(LL a, LL b){
    LL t = 1;
    while(b){
        if(b & 1) t = (t * a) % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return t;
}

int main(){
    
    // 1. 入力情報.
    int N, M, K;
    scanf("%d %d %d", &N, &M, &K);
    
    // 2. M の 冪乗(正, 負).
    mPowA[0] = mPowB[0] = 1;
    rep(i, K + 1){
        mPowA[i + 1] = (M * mPowA[i]) % MOD;
        mPowB[i + 1] = (mPow(M, MOD - 2) * mPowB[i]) % MOD;
    }
    
    // 3. dp更新.
    dp[0][0] = 1;
    LL ans = 0;
    rep(i, K){
        // 初期化.
        rep(j, N + 1) dp[1][j] = 0;
        
        // ルーレットの目(M 通り).
        repx(j, 1, M + 1){
            // マス((N + 1)通り)
            // -> マス N は, ゴール到達済と見て, 更新対象外.
            //    したがって, k = 0 ～ N - 1 を, 更新対象と見る.
            rep(k, N){
                // 移動先は？
                int nk = k + j;
                
                // (N + 1)以上ならば, 折り返す.
                if(nk > N) nk = N * 2 - nk;
                
                // 今回分更新.
                dp[1][nk] += dp[0][k];
                dp[1][nk] %= MOD;
            }
        }
        
        // ゴール到達分は？
        ans += (dp[1][N] * mPowA[K - 1 - i]);
        ans %= MOD;
        
        // 前回分更新.
        rep(j, N + 1) dp[0][j] = dp[1][j];
    }
    
    // 4. 確率は？
    ans *= mPowB[K];
    ans %= MOD;
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

const LL MOD = 998244353;

LL dp[2][1010], mPowA[1010], mPowB[1010];

// Fermat's little theorem から, 大きな冪乗の計算を行う.

// @param a: べき乗したい正整数.

// @param b: 指数.

// @return: べき乗した計算結果(mod版).

LL mPow(LL a, LL b){

LL t = 1;

while(b){

if(b & 1) t = (t * a) % MOD;

a = a * a % MOD;

b >>= 1;

}

return t;

}

int main(){

// 1. 入力情報.

int N, M, K;

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

// 2. M の冪乗(正, 負).

mPowA[0] = mPowB[0] = 1;

rep(i, K + 1){

mPowA[i + 1] = (M * mPowA[i]) % MOD;

mPowB[i + 1] = (mPow(M, MOD - 2) * mPowB[i]) % MOD;

}

// 3. dp更新.

dp[0][0] = 1;

LL ans = 0;

rep(i, K){

// 初期化.

rep(j, N + 1) dp[1][j] = 0;

// ルーレットの目(M 通り).

repx(j, 1, M + 1){

// マス((N + 1)通り)

// -> マス N は, ゴール到達済と見て, 更新対象外.

// したがって, k = 0 ～ N - 1 を, 更新対象と見る.

rep(k, N){

// 移動先は？

int nk = k + j;

// (N + 1)以上ならば, 折り返す.

if(nk > N) nk = N * 2 - nk;

// 今回分更新.

dp[1][nk] += dp[0][k];

dp[1][nk] %= MOD;

}

// ゴール到達分は？

ans += (dp[1][N] * mPowA[K - 1 - i]);

ans %= MOD;

// 前回分更新.

rep(j, N + 1) dp[0][j] = dp[1][j];

}

// 4. 確率は？

ans *= mPowB[K];

ans %= MOD;

// 5. 出力.

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

return 0;

}

[入力例]
2 2 1

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

[入力例]
10 5 6

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

[入力例]
100 1 99

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

[入力例]
5 3 2

[出力例]
887328314

[入力例]
11 7 3

[出力例]
937127352

[入力例]
345 10 111

[出力例]
900259854

[入力例]

2 2 1

[出力例]

499122177

※AtCoderテストケースより

[入力例]

10 5 6

[出力例]

184124175

※AtCoderテストケースより

[入力例]

100 1 99

[出力例]

※AtCoderテストケースより

[入力例]

5 3 2

[出力例]

887328314

[入力例]

11 7 3

[出力例]

937127352

[入力例]

345 10 111

[出力例]

900259854

■参照サイト
AtCoder Beginner Contest 275

C++の練習を兼ねて, AtCoder Beginner Contest 291 の 問題C (LRUD Instructions 2) ～ 問題D (Flip Cards) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 156 の 問題C (Tree and LCS) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 156 の 問題A (Non-Adjacent Flip) ～ 問題B (Mex on Blackboard) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 147 の 問題C (Min Diff Sum) ～ 問題D (Sets Scores) を解いてみた.

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

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

C++の練習を兼ねて, AtCoder Grand Contest 014 の 問題D (Black and White Tree) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 112 の 問題C (DFS Game) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 287 の 問題C (Path Graph?) ～ 問題E (Karuta) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 291 の問題C (LRUD Instructions 2) ～問題D (Flip Cards) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 156 の問題C (Tree and LCS) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 156 の問題A (Non-Adjacent Flip) ～問題B (Mex on Blackboard) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 147 の問題C (Min Diff Sum) ～問題D (Sets Scores) を解いてみた.

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

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

C++の練習を兼ねて, AtCoder Grand Contest 014 の問題D (Black and White Tree) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 112 の問題C (DFS Game) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 287 の問題C (Path Graph?) ～問題E (Karuta) を解いてみた.

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