atcoder nomura プログラミングコンテスト 2020 c問題 Folia が解けない

Question

atcoder NOMURAプログラミングコンテスト2020 のc問題でいくつかのケースについてWAとなってしまいます。

解説や他の人のコードをながめたりしましたが、自力で解決できなかったのでお力を貸していただけるとうれしいです。

問題文についてはこちらを参照してもらえればと思います。
https://atcoder.jp/contests/nomura2020/tasks/nomura2020_c

自分のコード

#include<iostream>
#include<algorithm>
#include<string>
#include<map>
#include<cmath>
#include<iomanip>
#include<math.h>
#define rep(i, n) for(int i=0; i<n; i++)
using namespace std;
typedef long long ll;

int main(){
    ll N; cin >> N;
    ll a[N+1];
    ll node = 0;
    rep(i, N+1){
        cin >> a[i];
    }
    ll c[N+2];
    c[0] = 1;
    
    for(ll i=0; i<N+1; i++){
        c[i+1] = 2*(c[i]-a[i]);
        if(c[i+1] < 0){
            cout << -1 << endl;
            return 0;
        }
    }

    node += a[N];
    ll now = a[N];
    
    for(ll i=N-1; i>-1; i--){
        now += a[i];
        if(now+a[i] < c[i]){
            node += now;
        }else{
            node += c[i];
        }
    }
    cout << node << endl;
}

変更を加えたが結局うまくいかなかったコード

ACしている人のコードを参考にして以下のコードなら、上のコードでWAだったものがACできることはわかりました。
しかし、加えた記述の目的がわからないのと、下のコードでも全てのケースがACとはなりませんでした。
その辺についても説明をしてもらえるとうれしいです。
下のコードは、上のコードに変更を加えた部分を ////// で囲っています。

#include<iostream>
#include<algorithm>
#include<string>
#include<map>
#include<cmath>
#include<iomanip>
#include<math.h>
#define rep(i, n) for(int i=0; i<n; i++)
using namespace std;
typedef long long ll;
//////////////////////////////
#define INF 1000000000000000LL
//////////////////////////////

int main(){
    ll N; cin >> N;
    ll a[N+1];
    ll node = 0;
    rep(i, N+1){
        cin >> a[i];
    }
    ll c[N+2];
    c[0] = 1;
    
    for(int i=0; i<N+1; i++){
        ////////////////////////////////
        c[i+1] = min(2*(c[i]-a[i]),INF);
        ////////////////////////////////
        if(c[i+1] < 0){
            cout << -1 << endl;
            return 0;
        }
    }

    node += a[N];
    ll now = a[N];
    
    for(int i=N-1; i>-1; i--){
        now += a[i];
        if(now+a[i] < c[i]){
            node += now;
        }else{
            node += c[i];
        }
    }
    cout << node << endl;
}

よろしくおねがいします。

Answer 1

c[i+1] = min(2*(c[i]-a[i]),INF);

ここについてはオーバーフロー回避のため
WAが出ることについては、何をしようとしてるのかわからないので何とも言えませんが

        now += a[i];
        if(now+a[i] < c[i]){
            node += now;
        }else{
            node += c[i];
        }

ここでやりたいことができてるのかの確認が必要でしょう

Comments

[goro_gnm]

回答ありがとうございます。

> ここについてはオーバーフロー回避のため
なるほど、c[i] は 2^{100000} 程度の大きさになってしまう可能性があるが、a[i] の上限よりも大きい値には意味がないからオーバーフロー回避として適当な値でスレッショルドしても問題がないということなんですね。理解しました、ありがとうございます。

> ここでやりたいことができてるのかの確認が必要でしょう
ケアレスミスでおかしなコードになってしまっていました。
```c++
now += a[i];
if(now < c[i])　node += now;
else　node += c[i];
```
に変更して提出したところ、ACでした。