0

https://atcoder.jp/contests/abc074/tasks/arc083_a
この問題をDFS(深さ優先探索)で解こうと思い、実装してみたのですが、下記の入力例3で無限ループになってしまい解けません。
なぜでしょうか?

書いたコード:

#include <bits/stdc++.h>
int a, b, c, d, e, f;
std::vector<std::tuple<long double, int, int>> vec;
void dfs(int water, int sugar, int limit) {
    std::cout << "water:" << water <<"," << "sugar:" <<sugar << std::endl;
    if (water+sugar > limit) { //溶液の質量がビーカーより大きい
        return;
    }
    if (sugar > (water/100)*e) { // 砂糖が溶け残る
        return;
    }
    long double density = 100*sugar/(water+sugar); // 密度(濃度を計算)
    vec.push_back(std::make_tuple(density, water, sugar)); // vecに格納
    dfs(water+100*a, sugar, limit);
    dfs(water+100*b, sugar, limit);
    dfs(water, sugar+c, limit);
    dfs(water, sugar+d, limit);
}

int main() {
    std::cin >> a >> b >> c >> d >> e >> f;
    dfs(100*a, 0, f);
    dfs(100*b, 0, f);
    auto e = *std::max_element(vec.begin(), vec.end()); //一番濃度の高いvecを取得。
    std::cout << std::get<1>(e) + std::get<2>(e) << " " << std::get<2>(e) << std::endl;
}

すぬけ君はビーカーに砂糖水を作ろうとしています。 最初ビーカーは空です。すぬけ君は以下の
4種類の操作をそれぞれ何回でも行うことができます。一度も行わない操作があっても構いません。

操作 1: ビーカーに水を 100A[g] 入れる。
操作 2: ビーカーに水を 100B[g] 入れる。
操作 3: ビーカーに砂糖をC[g] 入れる。
操作 4: ビーカーに砂糖を D[g] 入れる。

すぬけ君の実験環境下では、水 100[g] あたり砂糖は E[g] 溶けます。

すぬけ君はできるだけ濃度の高い砂糖水を作りたいと考えています。

ビーカーに入れられる物質の質量 (水の質量と砂糖の質量の合計) が F[g] 以下であり、
ビーカーの中に砂糖を溶け残らせてはいけないとき、 すぬけ君が作る砂糖水の質量と、それに溶けている砂糖の質量を求めてください。
答えが複数ある場合はどれを答えても構いません。

水 a[g] と砂糖 b [g] を混ぜた砂糖水の濃度は 100b/(a+b) [%]です。 また、この問題では、砂糖が全く溶けていない水も濃度0[%] の砂糖水と考えることにします。

制約

1≦A 1≦C 1≦E≦100
100A≦F≦3,000
A,B,C,D,E,Fはすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

A B C D E F

出力 整数を空白区切りで 2つ出力せよ。 1つ目は求める砂糖水の質量、2つ目はそれに溶けている砂糖の質量とせよ。

入力例 1

1 2 10 20 15 200

出力例 1

110 10

入力例2

1 2 1 2 100 1000

出力例 2

200 100

入力例 3

17 19 22 26 55 2802

出力例 3

2634 934
3
  • 3
    無限ループではなくて、計算処理に莫大な時間がかかっています。こちらの環境で実行してみると、E の値が 20(g) の場合は 0.013s, 30(g) では 1.16sとなり、40(g) にすると std::bad_alloc exception が発生します。
    – user39889
    Commented 2019年6月2日 8:10
  • この問題では深さ優先探索は筋が悪いということでしょうか?(計算量についてよくわかっていないので...) Commented 2019年6月2日 8:25
  • 2
    単純な総当たりでは組み合わせの数が膨大になりすぎる、と言うところに出題条件が設定されているようです。なんらかの工夫を入れて枝狩りをしないと実用的な時間では解けないですね。
    – OOPer
    Commented 2019年6月2日 8:30

1 件の回答 1

6

コメントに示したように単純な総当たりではケース数が増えすぎて実用的な時間では解けない設定になっています。

最初に水1700gを入れた場合、

入れられる砂糖の最大量は1700*55/100=935(g)です。

全部多い方の「操作 4: ビーカーに砂糖を D(26)[g] 入れる。」を選んだとしても、

935 ÷ 26 = 35...25

となるので、最低35回「砂糖を入れる」操作が必要になりますが、その部分だけ考えても

  • 「操作 3: ビーカーに砂糖を C(22)[g] 入れる。」
  • 「操作 4: ビーカーに砂糖を D(26)[g] 入れる。」

が自由に選べるので、組み合わせは2^35通りで約343億通りあります。

実際には「操作 3」をたくさん選んだ場合には、もっと「砂糖を入れる」を実行できる可能性があるので、上記の組み合わせは「最低でも」の数です。

coutによるログを見ているとお気づきでしょうが、water, sugarの値で同じ組み合わせが何度も出てきます。

...
water:1700,sugar:934 <-
water:3400,sugar:934
water:3600,sugar:934
water:1700,sugar:956
water:1700,sugar:960
water:1700,sugar:938
water:1700,sugar:890
water:3400,sugar:890
water:3600,sugar:890
water:1700,sugar:912
water:3400,sugar:912
water:3600,sugar:912
water:1700,sugar:934 <-
...

なんでそうなるかと言うと、

  1. 「操作 3: ビーカーに砂糖を C(22)[g] 入れる。」
  2. 「操作 4: ビーカーに砂糖を D(26)[g] 入れる。」

の順序で操作しても、

  1. 「操作 4: ビーカーに砂糖を D(26)[g] 入れる。」
  2. 「操作 3: ビーカーに砂糖を C(22)[g] 入れる。」

の順序で操作しても、状態としては同じなのに、どちらの状態からも続きの探索を行っていくので、実は全く無駄な探索をしていることになります。

「水1700g,砂糖48g」と言う状態からの探索は完了している、なんてことをどこかに記録して、探索済みの状態からは新たな探索は行わないようにすれば、かなりの無駄な探索を省くことができるはずです。

int a, b, c, d, e, f;
std::vector<std::tuple<long double, int, int>> vec;
std::unordered_set<int> set; //### 探索済み状態を記録するためのhash set
void dfs(int water, int sugar, int limit) {
    std::cout << "water:" << water <<"," << "sugar:" <<sugar << std::endl;
    if (water+sugar > limit) { //溶液の質量がビーカーより大きい
        return;
    }
    if (sugar > (water/100)*e) { // 砂糖が溶け残る
        return;
    }

    //### 既に探索済みかどうかを確かめる
    int key = (water << 12)+sugar; //上位ビットがwater, 下位12ビットがsugar
    if( set.count(key) ) {
        //探索済みなら何もしない
        return;
    }
    //探索済みであることをマーキング
    set.insert(key);

    long double density = 100*sugar/(water+sugar); // 密度(濃度を計算)
    vec.push_back(std::make_tuple(density, water, sugar)); // vecに格納
    dfs(water+100*a, sugar, limit);
    dfs(water+100*b, sugar, limit);
    dfs(water, sugar+c, limit);
    dfs(water, sugar+d, limit);
}

この手の出題は「条件をよく考えてなんらかの絞り込みを行わないと、単純な総当たりでは制限時間以内に解けない」ように設定されることが多いようです。

整数論的な考察を行えば、もっとはるかに速く解けそうな気もしますが、上記の修正だけでも「入力例 3」程度の値なら実用的な速度で解き終わると思います。お試しください。

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

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。