AtCoder ABC233 C問題

Question

前提・実現したいこと

AtCoderのABC233のC問題について
模範解答とほぼ同じコードを書いているのに自分のコードだけエラーを吐きます。
模範解答と自分のコードのどこが違うのかを知りたいです。
問題ページ

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

終了コード139
おそらくスタックオーバーフローが起きてます

該当のソースコード

自分のコード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll result = 0;
ll n, x;
vector<vector<ll>> v;
void dfs(ll index, ll product) {
    if (index == n) {
        if (product == x) {
            result++;
            return;
        }
    }

    for (ll a : v[index]) {
        if (product * a < x) {
            dfs(index + 1, product * a);
        }
    }
}

signed main() {
    cin >> n >> x;
    v.resize(n);
    ll l;
    for (ll i = 0; i < n; i++) {
        cin >> l;
        v[i].resize(l);
        for (ll j = 0; j < l; j++) {
            cin >> v[i][j];
        }
    }

    dfs(0, 1);
    cout << result << endl;
}

模範解答

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll ans = 0;
ll n,x;
vector<vector<ll>>a;
void dfs(ll pos,ll seki){
    if(pos==n){
        if(seki == x)ans++;
        return;
    }
    for(ll c:a[pos]){
        if(seki>x/c)continue;
        dfs(pos+1,seki*c);
    }
}

signed main(){
    cin>>n>>x;
    a.resize(n);
    for(ll i=0;i<=n-1;i++){
        ll L;cin>>L;
        a[i].resize(L);
        for(ll j=0;j<=L-1;j++)cin>>a[i][j];
    }
    dfs(0,1);
    cout<<ans<<endl;
    return 0;
}

試したこと

自分のコードがエラーを吐くので少しずつ模範解答に寄せましたがエラーが消えません

Answer 1

void dfs(ll index, ll product) {
    if (index == n) {
        if (product == x) {
            result++;
            return; //(1)
        }
    }

    for (ll a : v[index]) {
        if (product * a < x) { //(2)
            dfs(index + 1, product * a);
        }
    }
}

(1) return;の位置を間違えています。このコードだとindex == nを満たしてもproduct == xを満たさない場合にはreturnされず、続くfor文が実行されてしまうため、REとなります。index == nを満たす場合はproduct == xの真偽に関わらずreturnされる必要があります。

(2) 条件式を間違えています。product * a < xだとproduct * a == xの場合を含まないため、resultが加算されません。

Comments

[a9uaDrops]

回答ありがとうございます
REの訂正だけでなく、他の場所のミスも指摘してくださり助かりました

[luuguas]

(2)について、今回はテストケースのガバ(?)によりこれでACできるようですが、制約から考えると product * a を計算するときにオーバーフローする可能性があります。そのため、product * a <= x の a を右辺に持ってきて、product <= x / a とするのが適切です。

[a9uaDrops]

確かにproduct <= x / aの方が良いですね。
今後は途中の計算オーバーフローもケアしたコードを心がけます。
初心者なので大変勉強になりました。