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

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

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

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

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

// 解き直し.
// https://atcoder.jp/contests/abc217/editorial/2584
// 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 = 1010;
LL FAC[LIMIT], INV[LIMIT];
int f[808][808];
LL dp[808][808];

// 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 % MOD;
}

// 組み合わせ(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;
    // k = 0 で, 256423756 (※挙動がおかしい) が 出力されたため, ロジック修正.
    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, M;
    scanf("%d %d", &N, &M);
    rep(i, M){
        int a, b;
        scanf("%d %d", &a, &b);
        f[a][b] = 1;
        f[b][a] = 1;
    }
    
    // 2. 事前計算.
    FAC[0] = 1;
    repx(i, 1, LIMIT) FAC[i] = (LL)i * FAC[i - 1] % MOD;
    rep(i, LIMIT)     INV[i] = mPow(FAC[i], MOD - 2);
    
    // 3. dp更新.
    rep(i, N * 2 + 1) dp[i][0] = 1;
    repx(j, 1, N * 2 + 1){
        rep(i, N * 2 + 1){
            repx(k, 1, j + 1){
                LL a1 = dp[i + 1][k - 1];
                LL a2 = dp[i + k * 2][j - k];
                LL a3 = combination((LL)j, (LL)k);
                LL a4 = f[i + 1][i + k * 2];
                dp[i][j] += a1 * a2 % MOD * a3 % MOD * a4;
                dp[i][j] %= MOD;
            }
        }
    }
    
    // 4. 出力.
    printf("%lld\n", dp[0][N]);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc217/editorial/2584

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

LL FAC[LIMIT], INV[LIMIT];

int f[808][808];

LL dp[808][808];

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

}

// 組み合わせ(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;

// k = 0 で, 256423756 (※挙動がおかしい) が出力されたため, ロジック修正.

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

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

rep(i, M){

int a, b;

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

f[a][b] = 1;

f[b][a] = 1;

}

// 2. 事前計算.

FAC[0] = 1;

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

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

// 3. dp更新.

rep(i, N * 2 + 1) dp[i][0] = 1;

repx(j, 1, N * 2 + 1){

rep(i, N * 2 + 1){

repx(k, 1, j + 1){

LL a1 = dp[i + 1][k - 1];

LL a2 = dp[i + k * 2][j - k];

LL a3 = combination((LL)j, (LL)k);

LL a4 = f[i + 1][i + k * 2];

dp[i][j] += a1 * a2 % MOD * a3 % MOD * a4;

dp[i][j] %= MOD;

}

// 4. 出力.

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

return 0;

}

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

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

[入力例]
2 2
1 2
3 4

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

[入力例]
2 2
1 3
2 4

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

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

[出力例]
30

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

[出力例]
604800

[入力例]
20 35
1 2
3 4
5 6
7 8
9 10
11 12
13 14
15 16
17 18
19 20
21 22
23 24
25 26
27 28
29 30
31 32
33 34
35 36
37 38
39 40
1 10
8 9
2 7
3 6
4 5
11 30
12 29
13 28
14 27
15 26
16 25
17 24
18 23
19 22
20 21

[出力例]
883463798

100

[入力例]

2 3

1 2

1 4

2 3

[出力例]

※AtCoderテストケースより

[入力例]

2 2

1 2

3 4

[出力例]

※AtCoderテストケースより

[入力例]

2 2

1 3

2 4

[出力例]

※AtCoderテストケースより

[入力例]

5 5

1 2

3 6

4 5

7 10

8 9

[出力例]

[入力例]

10 15

1 6

2 3

4 5

7 10

8 9

11 12

13 14

15 16

17 20

18 19

11 14

12 13

15 20

16 19

17 18

[出力例]

604800

[入力例]

20 35

1 2

3 4

5 6

7 8

9 10

11 12

13 14

15 16

17 18

19 20

21 22

23 24

25 26

27 28

29 30

31 32

33 34

35 36

37 38

39 40

1 10

8 9

2 7

3 6

4 5

11 30

12 29

13 28

14 27

15 26

16 25

17 24

18 23

19 22

20 21

[出力例]

883463798

■参照サイト
AtCoder Beginner Contest 217

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

コメントを残す コメントをキャンセル

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

コメントを残すコメントをキャンセル