55454


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

書いたコード:

[code]

    #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;
    }
    
[/code]

> すぬけ君はビーカーに砂糖水を作ろうとしています。 最初ビーカーは空です。すぬけ君は以下の  
>  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はすべて整数である。
>
> ### 入力
>
> 入力は以下の形式で標準入力から与えられる。
[code]

>     A B C D E F
>  
[/code]

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

>     1 2 10 20 15 200
>  
[/code]

>
> 出力例 1
[code]

>     110 10
>  
[/code]

>
> 入力例2
[code]

>     1 2 1 2 100 1000
>  
[/code]

>
> 出力例 2
[code]

>     200 100
>  
[/code]

>
> 入力例 3
[code]

>     17 19 22 26 55 2802
>  
[/code]

>
> 出力例 3
[code]

>     2634 934
>  
[/code]


CC BY-SA 4.0
2019-06-02T06:45:01.487
55450
2019-06-02T09:16:02.877
2019-06-02T07:12:24.540
5246
5246
question
c++ アルゴリズム
C++での深さ優先探索が無限に終わらない


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

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

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

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

[code]

    935 ÷ 26 = 35...25
    
[/code]

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

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

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

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

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

[code]

    ...
    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 <-
    ...
    
[/code]

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

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

の順序で操作しても、

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

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

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

[code]

    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);
    }
    
[/code]

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

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


CC BY-SA 4.0
2019-06-02T09:10:24.493
55454
2019-06-02T09:16:02.877
2019-06-02T09:16:02.877
13972
13972
55450
answer