ABC165に参加してみました - インフラエンジニアの備忘録とか色々

初めに

今回はABC165に参加しました。A・BはACして、Cは解いている途中でタイムアップしました。
Twitterを見た限りだとDよりCが難しかったようで、「Cを飛ばせば良かったなぁ」と思いました。
(まぁ、CよりDの方が簡単だからと言って私が解けるかは別な話ですがw、、、)
では早速、解いている途中で終わってしまったC問題について書いて行こうと思います。

https://atcoder.jp/contests/abc165

※ブログ内で問題の制約事項をすべて記載はしないので、制約事項は↑のURLより参照願います。

C - Many Requirements

正整数 $N , M , Q$ と、4 つの整数の組 $( a_i , b_i , c_i , d_i ) Q$ 組が与えられます。 $N , M , Q$ はそれぞれ以下を表しています。

　 $N　→　入力される数列の長さ$
　 $M　→　数列A_nに含まれる数の最大値$
　 $Q　→　入力される「4つの整数の組」の数$

そして、 $A_{b_i} - A_{a_i} = c_i$ を満たすような $i$ についての $d_i$ の総和を計算し、
与えれらた $Q$ 組の整数の組を利用して得られる数列 $A$ の得点の最大値を求める問題です。

初めの回答

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

ll N,M,Q;
ll sum = 0,ans = 0;
vector<ll> a(50);
vector<ll> b(50);
vector<ll> c(50);
vector<ll> d(50);
vector<ll> A(10);

//深さ優先探索を行っている関数です。
void dfs(ll NN){

    //樹形図の一番下の頂点の位置です。
    if(NN == 0){

        sum = 0;

        for(ll i = 0;i < Q;++i){
            //条件を満たすか確認します。条件を満たしている場合はsumにdiを加算します。
            if(A[b[i]-1]-A[a[i]-1] == c[i]){
                sum = sum + d[i];
            }
        }

        //最大値ansに格納されている値よりsumの値が大きかった場合、最大値ansをsumの値で更新します。
        if(ans < sum) ans = sum;

    }
    else{

        for(ll i = 0;i < M;++i){
            // 樹形図の各頂点の数値を格納しています。
            A[NN-1] = i + 1;
            // 樹形図の下の頂点に向かう操作をしています。
            dfs(NN-1);
        }

    }

}

int main(){

cin >> N >> M >> Q;

for(ll i = 0;i < Q;++i)    cin >> a[i] >> b[i] >> c[i] >> d[i];

dfs(N);

cout << ans << endl;

return 0;

}

再帰関数を利用しDFS(深さ優先探索)を行って数列 $A$ の全列挙を行います。以下はDFSのイメージになりますが、樹形図の一番の下の頂点にぶつかるまで探索(赤矢印)したら、一歩戻って(青矢印)また一番下の頂点まで探索を行う操作を繰り返し行う探索方法になります。

f:id:hgm_blog:20200506230510p:plain — イメージ

mathtrain.jp

全列挙したそれぞれの数列に対して $A_{b_i} - A_{a_i} = C_i$ の条件に合うか確認し、数列 $A$ の得点を計算を求め、得点の最大値が格納されている変数ansの更新を行い、DFS完了後に最終的な変数ansの値を出力しています。

提出結果としては、実行時間が掛かり過ぎてしまいAC出来ませんでした。
(最大で10¹⁰の計算をする場合があるから、まぁTLEになっちゃいますよねぇ。。。)

そして、探索の中で枝刈りが行る場所は無いか考えている最中にタイムアップになりました。
(そもそも問題文の理解に時間が掛かり過ぎて、あまり実装に時間を掛けられませんでしたorz)

解説を見てからの回答

下記のコードは最初に書いたコードから少し変わっていますが、
解説を見た上で変更したのは樹形図の下の頂点に向かう操作の条件のみです。

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

ll N,M,Q;
ll sum = 0,ans = 0;
vector<ll> a(50);
vector<ll> b(50);
vector<ll> c(50);
vector<ll> d(50);
vector<ll> A(11,1);

void dfs(ll NN){

    if(N == NN){

        sum = 0;

        for(ll i = 0;i < Q;++i){
            if(A[b[i]-1]-A[a[i]-1] == c[i]){
                sum = sum + d[i];
            }

        }

        if(ans < sum) ans = sum;

    }
    else{

        for(ll i = 1;i <= M;++i){

            A[NN] = i;
            // 一つ前の頂点の数字以上であった場合のみ樹形図の下に向かう操作をします。
            if(A[NN-1] <= A[NN])    dfs(NN+1);
            
        }

    }

}

int main(){

cin >> N >> M >> Q;

for(ll i = 0;i < Q;++i)    cin >> a[i] >> b[i] >> c[i] >> d[i];

dfs(1); 

cout << ans << endl;

return 0;

}

数列 $A$ の条件( $1≤A_1≤A_2≤⋯≤A_N≤M$ )より、広義単調増加しているため、 $A_n$ は、 $A_{n-1}$ 以上の数字しか取りません。