@mitchan5 (hiro Minami)posted at 2022-08-19

dfsを使った数列の全探索方法

Q&A

Closed

解決したいこと

C++でAtCoder Beginner Contest 165 C - Many Requirementsを解いています。
適切な値が出ず困っています。

発生している問題・エラー

下記の問題を解いています。（URLですみません。）

例）

https://atcoder.jp/contests/abc165/tasks/abc165_c

該当するソースコード

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

int N,M,Q,maxx=0,last;
vector<int> a(50),b(50),c(50),d(50);
string B;

void sub(string A){
  if(A.size()==N) {
    int sum=0;
    for(int i=0; i<Q; i++){
      　　if(	(A.at(b.at(i)-1)-A.at(a.at(i)-1))==c.at(i)	) sum += d.at(i);
       　  }
    maxx=max(maxx,sum);
    return ;
　　}
         
   last=A.at(A.size()-1);
   for(int i=last; i<=M; i++){
      B = A;
      B += ('0'+i);
      sub(B);
      }   
}

int main() {
  cin >> N >> M >> Q;
  for(int i=0; i<Q; i++) cin >> a.at(i) >> b.at(i) >> c.at(i) >> d.at(i);
  string A="1";
  sub(A);
  cout << maxx << endl;
}

自分で試したこと

3 4 3
1 3 3 100
1 2 2 10
2 3 2 10
の入力に110が出力されればよいのですが、０になってしまいます。
何度も見直しましたがわかりませんでした。。。
よろしくお願いいたします。

1Answer

@PondVillege posted at 2022-08-19

string Bに関してはちゃんと

B += ('0' + i);

として整数と文字の変換ができているのに対し，整数lastでは，文字A.at()をそのまま使って

last = A.at(A.size() - 1);

としているのが原因です．ここでの値はASCIIコードの値が代入されます．
したがって，ASICCコードの整数文字と整数の変換をするために

last = A.at(A.size() - 1) - '0';

としましょう．これで動きました．

余談です．

コード中に全角スペースが散見される
インデントが揃っていない
代入，比較，四則演算の各演算子の前後にスペースを空ける空けないが統一されていない

など見やすさの改善の余地があります．

また，可変サイズのvectorを使うこともできますので，わざわざ文字列で扱う必要はないです．今回のような事故を招きかねません．vectorで書いてみたので参考にしてください．

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

int N, M, Q, ans = 0;
vector<int> a(50), b(50), c(50), d(50), B;

void sub(vector<int> A) {
    if (A.size() == N) {
        int sum = 0;
        for (int i = 0; i < Q; ++i) {
            if (A[b[i] - 1] - A[a[i] - 1] == c[i]) sum += d[i];
        }
        ans = max(ans, sum);
        return ;
    }
    for (int i = A.back(); i <= M; ++i) {
        B = A;
        B.push_back(i);
        sub(B);
    }
}

int main() {
    cin >> N >> M >> Q;
    for(int i = 0; i < Q; ++i) cin >> a[i] >> b[i] >> c[i] >> d[i];
    vector<int> A(1, 1);
    sub(A);
    cout << ans << endl;
}

1Like

Comments

@mitchan5
Questioner
いつも丁寧に教えていただきありがとうございます！！
改善点や別解の方もとても勉強になります、ありがとうございます！
@PondVillege
AtCoderのTwitterコミュニティでも良い回答が得られると思うので
https://twitter.com/i/communities/1502008313579401218
活用してください
@mitchan5
Questioner
ありがとうございます、確認します！

Are you sure you want to delete the question?