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

C++の練習を兼ねて, AtCoder Regular Contest 027 の問題D (ぴょんぴょんトレーニング) を解いてみた.

■感想.
1. 問題Dは, 方針が絞り込めたので, AC版に到達出来た.
※ 但し, 実行時間は, 7623[ms] だったので, 実行時間制限の 8[sec] に, ギリギリ収まる実装となっている.
2. 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d", &h[i + 1]);
    int D;
    scanf("%d", &D);
    
    // 2. クエリ回答.
    rep(i, D){
        // 2-1. クエリ入力情報.
        int s, t;
        scanf("%d %d", &s, &t);
        
        // 2-2. dp更新.
        LL dp[N + 1];
        rep(j, N + 1) dp[j] = 0;
        dp[s] = 1;
        repx(j, s, t){
            // 現在地点.
            LL cur = dp[j];
            
            // 区間[j + 1, j + h[j] + 1) へ ジャンプ.
            rep(k, h[j]){
                int n = j + k + 1;
                if(n <= N) dp[n] += cur, dp[n] %= MOD;
                else       break;
            }
        }
        
        // 2-3. 出力.
        printf("%lld\n", dp[t]);
    }
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

int h[303030];

const LL MOD = 1e9 + 7;

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

int D;

scanf("%d", &D);

// 2. クエリ回答.

rep(i, D){

// 2-1. クエリ入力情報.

int s, t;

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

// 2-2. dp更新.

LL dp[N + 1];

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

dp[s] = 1;

repx(j, s, t){

// 現在地点.

LL cur = dp[j];

// 区間[j + 1, j + h[j] + 1) へジャンプ.

rep(k, h[j]){

int n = j + k + 1;

if(n <= N) dp[n] += cur, dp[n] %= MOD;

else break;

}

// 2-3. 出力.

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

}

return 0;

}

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

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

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

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

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

[出力例]
2
4
14
216
16
657
13

[入力例]
100
5 2 5 1 8 10 8 2 9 1 1 5 7 9 7 7 6 1 6 2 2 1 10 6 2 2 4 2 8 6 1 4 1 4 6 8 5 1 9 4 8 1 6 5 1 2 7 10 9 1 10 9 7 9 4 7 2 2 4 3 9 8 4 1 7 1 4 1 5 1 7 7 10 7 2 1 7 5 4 3 9 5 6 7 8 5 8 5 7 10 3 4 1 2 5 9 8 10 3 2
15
57 78
36 88
81 100
28 41
46 51
41 53
18 40
74 93
62 80
90 98
3 21
7 36
70 94
99 100
84 98

[出力例]
92250
461505895
127192
1122
12
684
108651
136102
20899
68
27120
12050088
2109316
1
4064

[入力例]

1 2 3 2 2 1 1

2 6

5 7

1 7

[出力例]

※AtCoderテストケースより

[入力例]

3 1 4 1 5 9 2 6 5 3 5

3 7

2 9

1 10

1 11

[出力例]

175

※AtCoderテストケースより

[入力例]

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

3 5

4 7

1 6

2 11

3 8

1 12

5 10

[出力例]

216

657

[入力例]

100

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

57 78

36 88

81 100

28 41

46 51

41 53

18 40

74 93

62 80

90 98

3 21

7 36

70 94

99 100

84 98

[出力例]

92250

461505895

127192

1122

684

108651

136102

20899

27120

12050088

2109316

4064

■参照サイト
AtCoder Regular Contest 027

C++の練習を兼ねて, AtCoder Regular Contest 027 の 問題D (ぴょんぴょんトレーニング) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 027 の問題D (ぴょんぴょんトレーニング) を解いてみた.

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