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

C++の練習を兼ねて, AtCoder Regular Contest 136 の問題E (Non-coprime DAG) を解いてみた.

■感想.
1. 問題E は, 方針が見えなかったので, 解説を参考にして, ようやく, AC版に到達出来た.
2. 個人的には, 解説のロジックで, 価値の総和としてあり得る最大値が計算されることが, 摩訶不思議な印象を受け, 非常に, 面白く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc136/editorial/3464
// 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 f[1010101], l[1010101], r[1010101];
LL a[1010101], b[2020202];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%lld", &a[i]);
    
    // 2. f を 計算.
    repx(i, 2, N + 1){
        if(!f[i]) repex(j, i, N + 1, i) if(!f[j]) f[j] = i;
    }
    
    // 3. l, r を 計算.
    repx(x, 2, N + 1){
        // 偶数.
        if(!(x & 1)){
            l[x] = x;
            r[x] = x + 1;
        }
        
        // 奇数.
        if(x & 1){
            l[x] = x - f[x] + 1;
            r[x] = x + f[x];
        }
    }
    
    // 4. いもす法.
    repx(i, 1, N){
        b[l[i + 1]] += a[i];
        b[r[i + 1]] -= a[i];
    }
    repx(i, 1, 2020202) b[i] += b[i - 1];
    
    // 5. 最大値は？
    LL ans = 0;
    repx(i, 1, N + 1) ans = max(ans, b[i]);
    
    // 6. 出力.
    printf("%lld\n", ans + a[0]);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc136/editorial/3464

// 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 f[1010101], l[1010101], r[1010101];

LL a[1010101], b[2020202];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

// 2. f を計算.

repx(i, 2, N + 1){

if(!f[i]) repex(j, i, N + 1, i) if(!f[j]) f[j] = i;

}

// 3. l, r を計算.

repx(x, 2, N + 1){

// 偶数.

if(!(x & 1)){

l[x] = x;

r[x] = x + 1;

}

// 奇数.

if(x & 1){

l[x] = x - f[x] + 1;

r[x] = x + f[x];

}

// 4. いもす法.

repx(i, 1, N){

b[l[i + 1]] += a[i];

b[r[i + 1]] -= a[i];

}

repx(i, 1, 2020202) b[i] += b[i - 1];

// 5. 最大値は？

LL ans = 0;

repx(i, 1, N + 1) ans = max(ans, b[i]);

// 6. 出力.

printf("%lld\n", ans + a[0]);

return 0;

}

[入力例]
6
1 1 1 1 1 1

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

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

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

[入力例]
20
40 39 31 54 27 31 80 3 62 66 15 72 21 38 74 49 15 24 44 3

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

[入力例]
5
3 1 4 1 5

[出力例]
13

[入力例]
10
32 47 55 7 78 25 10 25 64 36

[出力例]
222

[入力例]
50
10896 8989 6913 7732 9901 1249 10000 8888 2983 11045 7840 9597 9781 4801 1762 4530 5819 4577 2222 3266 10833 9555 11111 5555 12391 7850 7623 333 1111 1563 3985 12212 10421 12455 9493 7819 5281 9997 10789 9611 454 5411 2364 3891 596 8919 3333 11085 7507 5555

[出力例]
100000

[入力例]

1 1 1 1 1 1

[出力例]

※AtCoderのテストケースより

[入力例]

1 2 1 3 1 6

[出力例]

※AtCoderのテストケースより

[入力例]

40 39 31 54 27 31 80 3 62 66 15 72 21 38 74 49 15 24 44 3

[出力例]

343

※AtCoderのテストケースより

[入力例]

3 1 4 1 5

[出力例]

[入力例]

32 47 55 7 78 25 10 25 64 36

[出力例]

222

[入力例]

10896 8989 6913 7732 9901 1249 10000 8888 2983 11045 7840 9597 9781 4801 1762 4530 5819 4577 2222 3266 10833 9555 11111 5555 12391 7850 7623 333 1111 1563 3985 12212 10421 12455 9493 7819 5281 9997 10789 9611 454 5411 2364 3891 596 8919 3333 11085 7507 5555

[出力例]

100000

■参照サイト
AtCoder Regular Contest 136

C++の練習を兼ねて, AtCoder Regular Contest 136 の 問題E (Non-coprime DAG) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 136 の問題E (Non-coprime DAG) を解いてみた.

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