0

以下のコードで Atcoder abc165_c (https://atcoder.jp/contests/abc165/tasks/abc165_c)の入力例を試したのですが、すべてで 0 が返ってきます。どなたか理由を教えていただけたら嬉しいです。
方向性としては、func 内でDFS的にAが求まるたびに得点を求め、その最大値を更新しています。

Atcoder abc165_c
問題概要
 Q 個のクアドラプレット(4 要素タプル)が与えられる.i 番目のクアドラプレットは (ai,bi,ci,di) である.
 また,整数 N,M が与えられる.以下の条件を満たす数列 {Ai} を考える.

|A|=N
1≤A1≤A2≤⋯≤AN≤M
この数列 A の「得点」を,

Abi−Aai=ci を満たすようなクアドラプレットについての di の総和
とする.
 可能な数列の内,得点が最大のものの得点を求めよ.
制約
2≤N≤10
1≤M≤10
1≤Q≤50
ai,bi,ci は意味を成す値
1≤di≤105

コード

#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define rep3(i, s, n) for (int i = (s); i > (int)(n); i--)
#define all(v) v.begin(), v.end()
#define pb push_back
#define sz(x) ((int)(x).size())
typedef long long ll;
using namespace std;
using Graph = vector<vector<int>>;
template<class T>bool chmax(T & a, const T & b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T & a, const T & b) { if (b < a) { a = b; return 1; } return 0; }

int N, M, Q;
int a[50], b[50], c[50], d[50];
int Max = 0;

void func(string A) {
    if (sz(A) == N) {
        int score = 0;
        rep(i, Q) {
            if (A[b[i] - 1] - A[a[i] - 1] == c[i]) score += d[i];
        }
        chmax(Max, score);
        return;
    }
    int last = 1;
    if (sz(A) >= 1) last = A[sz(A) - 1];
    rep2(i, last, M + 1) {
        string nA = A;
        nA += ('0' + i);
        func(nA);
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> N >> M >> Q;
    rep(i, Q) cin >> a[i] >> b[i] >> c[i] >> d[i];
    string A = "";

    func(A);

    cout << Max << "\n";

    return 0;
}
2
  • 2
    void func(string A) としている部分ですが、正整数列であると定義されている A がなぜか string 型になっています。そのため、nA += ('0' + i); の結果(nAの値)が 49 とか 50 になっています。なので、これを較正するために if (sz(A) >= 1) last = A[sz(A) - 1];if (sz(A) >= 1) last = A[sz(A) - 1] - '0'; とする必要があります。
    – user39889
    2021年1月9日 10:10
  • 回答ありがとうございます 無事解決しました
    – user43471
    2021年1月9日 10:28

0

この質問に回答するには、ログインする必要があります。