[Atcoder]ABC099C問題 ー 配列を初期化する１行を書き換えた際、ACとRE結果の違いが生じる理由がわかりません。

Question

前提・実現したいこと

Atcoder における質問です。
現在、動的計画法を勉強しており、ABC099C Strange Bank　という問題を解いています。
その提出結果に関する質問です。
コードを提出した際に、同じような処理をしていると思われる１行を書き換えたときに、結果が、AC(Accepted)、RE(Runtime Error)と別れる原因がわからず困っています。どなたかご教示願えると嬉しいです。よろしくお願いします。

発生している問題・エラーメッセージ

下記のソースコードはメモ化再帰を使って解いているものですが、main関数内において、

dp.assign(N+1, -1); //⇦ACとなる　

としている部分を

rep(i, N+1) dp[i] = -1; //⇦提出するとREとなる

と書き換えるとRE(Runtime Error)が返されてしまいます。

また、※のついている2箇所（dpの宣言部分と、dpの初期化部分）を同時に変更した場合はACとなりました。

以上のような結果の違いはなぜ起きるのでしょうか。

該当のソースコード

#include <bits/stdc++.h>
#define  rep(i,n) for(int i=0;i<n;++i)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
using namespace std;
const int INF = 1LL << 30;

const int MAX = 110000;
int N;
vector<int> dp(N+1); //※dp(MAX)とし、
//メモ化再帰
int rec(int n){
    if(n==0) return 0;
    if(dp[n] != -1) return dp[n];
    int res = INF;
    for(int i = 1; i <= n; i *= 6) chmin(res, rec(n-i)+1);
    for(int i = 1; i <= n; i *= 9) chmin(res, rec(n-i)+1);
    return dp[n] = res;
}
int main(){
    cin >> N;
    //メモとして使う配列dpの初期化
    dp.assign(N+1, -1); //⇦ACとなる
    //rep(i, N+1) dp[i] = -1; //⇦提出するとREとなる
    //rep(i, MAX) dp[i] = -1; //※この行で書き換えるとAC
    cout << rec(N) << endl;
    return 0;
}

試したこと

REの主な原因であるゼロ除算は、割り算を行っていないので考えなくても良いので、配列の範囲外アクセスが原因かと考えて、メモとして使っているdpの配列について、色々な書き方を試しました。その結果わかったことと、知りたいことが上記の「発生している問題・エラーメッセージ」の内容です。

補足情報（FW/ツールのバージョンなど）

提出時の選択言語は　C++(GCC9.2.1)　です。

Answer 1

assignにはresizeの作用もあってrep(i, N+1) dp[i] = -1;にはないからでしょう。
Nがグローバル変数ならNは初期値0で、vector<int> dp(N+1)の初期サイズは１です。
assignされてはじめてサイズはN+1になるわけで、resizeもせずにいきなりdp[1]と触った時点で範囲外アクセスということです。

Comments

[hageg]

なるほどです。dpの初期サイズについては、目が向いていませんでした...。
assignにはresizeの作用もあるのですか！
納得しました。ありがとうございます！！