abc165_cの解き方を解説深さ優先探索(dfs)での数列作成方法

2020/05/19 23:05

AtCoder Beginner Contest 165のC問題を解く

感謝の正拳突き１万回ならぬ、競プロサイトで 1 日 1AC(正解)するように頑張る。

今日は飲み会のあとに挑戦したら撃沈したAtCoder Beginner Contest 165 の C 問題。

問題文の意味が難解で、プログラミングの本筋より読解能力を試される問題。酔ってる時に読んだら意味がわからなかったけど、今読んだらわかった。

まず数列 A がある

入力例 1 の N = 3, M = 4 の場合を考えると、A のパターンは次の通り。

こんな感じの数列を全探索する。

A[b] - A[a] == c となる d の合計

上の A の数列ができたら、Q の数だけ入力が渡されるので、A[b] - A[a] == c となる行を探して d を足す。回答の A = 1 3 4 の場合だとしたら

1 個目の a:1 b:3 c:3 d:100

A[b]は A の 3 番目の数 = 4 A[a]は A の 1 番目の数 = 1 4 - 1 = 3 となり、c が 3 なので当てはまる。

d を足す

こうやって選択された行の d を集計していくと答えが出る。

アルゴリズム

A の数列を作るのは深さ優先探索(dfs)を使う。慣れないと読みづらいけど、こういう書き方は典型的な dfs の使い方なので、脳内で動かして練習したいところ。

A[b] - A[a] == c となる d の合計は言葉の意味は理解しづらいけど、理解しちゃえば簡単なプログラムになる。

この問題は制約でループの数が必ず少なくなるので、単純に全探索で AC となった。

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

int A = 0, B = 1, C = 2, D = 3;
int n,m,q,a,b,c,d;

int result;

// abcdを保存するリスト
vector<vector<int>> abcds;

// Aの数列を作るリスト
vector<int> vec_a(20);

// A[b] - A[a] = cを満たすA[d]の合計を満たす
void resolve() {
    int tmp = 0;
    for(auto&& abcd : abcds) {
        if(vec_a[abcd[B]] - vec_a[abcd[A]] == abcd[C]) tmp += abcd[D];
    }
    if(result < tmp) result = tmp;
    return;
}

// Aの数列を作る
void dfs(int depth) {
    if(depth == n) {
        // 数列が完成したら、答えを出す
        resolve();
        return;
    }
    for(int i = vec_a[depth]; i <= m; i++) {
        vec_a[depth + 1] = i;
        dfs(depth + 1);
    }
    return;
}
int main(){
    cin >> n >> m >> q;
    abcds.assign(q, vector<int>(4, 0));
    for(int i = 0; i < q; i++) {
        cin >> a >> b >> c >> d;
        abcds[i][A] = a;
        abcds[i][B] = b;
        abcds[i][C] = c;
        abcds[i][D] = d;
    }
    vec_a[0] = 1;
    dfs(0);
    cout << fixed << result;
}

abc165_cの解き方を解説 深さ優先探索(dfs)での数列作成方法