プログラマ専用SNS ミクプラ

こんにちは。
今回、ＰＯＪというサイトの問題を解いていて、どうしても解法が分からずいろいろ調べていたところ、ビット演算子、bitsetを用いた解法を見つけ、どうにかして理解したく、ここにて質問させていただきます。

問題：http://poj.org/problem?id=2718

問題の概要：０～９までの最大の長さ１０、最小の長さ２の数列があって、それを順番は自由でよいので、二つに分割し、それの最小値の絶対値を求める問題です。
２進数を用いた解法を使っていたコードです。

コード:

#ifndef ONLINE_JUDGE
#pragma warning(disable : 4996)
#endif
#include <iostream>
#include <string>
#include <algorithm>
#include <bitset>
using namespace std;
 
///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    int n;
    cin >> n;
    cin.ignore();
    while (n--)
    {
        string all;
        getline(cin, all);
        all.erase(remove(all.begin(), all.end(), ' '), all.end());
        int length = all.size();
        int cut = length / 2;
        int permute = 1 << length;
        int result = 0x3F3F3F3F;
        do
        {
            bitset<10> used = static_cast<bitset<10>>(permute);
            string s1, s2;
            for (int i = 0; i < length; ++i)
            {
                if (used[i])
                {
                    s1 += all[i];
                }
                else
                {
                    s2 += all[i];
                }
            }
            if (s1.size() != cut)
            {
                continue;
            }
            if (s1[0] == '0' && s1.size() > 1)
            {
                continue;
            }
            // s1 s2 已经被切割出来了
            // 穷举它们
            do
            {
                int n1 = atoi(s1.c_str());
                do
                {
                    if (s2[0] == '0' && s2.size() > 1)
                    {
                        continue;
                    }
                    int n2 = atoi(s2.c_str());
                    int dif = abs(n1 - n2);
                    //cout << s1 << ' ' << s2 << " dif " << dif << " result: " << result << endl;
                    if (dif < result)
                    {
                        result = dif;
                    }
                } while (next_permutation(s2.begin(), s2.end()));
            } while (next_permutation(s1.begin(), s1.end()));
        } while (--permute);
 
        cout << result << endl;
    }
#ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stdout);
    system("out.txt");
#endif
    return 0;
}

（http://www.hankcs.com/program/poj-2718- ... swers.html さんより引用）
このなかで、どうしてもわからない所は

コード:

int length = all.size();
        int cut = length / 2;
        int permute = 1 << length;
        int result = 0x3F3F3F3F;
        do
        {
            bitset<10> used = static_cast<bitset<10>>(permute);
            string s1, s2;
            for (int i = 0; i < length; ++i)
            {
                if (used[i])
                {
                    s1 += all[i];
                }
                else
                {
                    s2 += all[i];
                }
            }

です。ビット演算子の部分は理解できたのですが、 bitset<10> used = static_cast<bitset<10>>(permute);のところで二進数に変換し、usedに格納しているところまではどうにかわかりました。しかし、次のfor分で、uesdが０，１のどちらかで、ｓ１、ｓ２どっちに入れるか決めているところで、どうしてこのような解法が出てきたのかわかりません。
どなたか教えていただけないでしょうか？

きょうさんが書きました:問題：http://poj.org/problem?id=2718

問題の概要：０～９までの最大の長さ１０、最小の長さ２の数列があって、それを順番は自由でよいので、二つに分割し、それの最小値の絶対値を求める問題です。

原文を見ました。
「数字の集合が与えられるので、それらを被らないように適当に組み合わせて2個のリーディングゼロを持たない整数を作り、その差の絶対値の最小値を求める」という問題ですね。

きょうさんが書きました:しかし、次のfor分で、uesdが０，１のどちらかで、ｓ１、ｓ２どっちに入れるか決めているところで、どうしてこのような解法が出てきたのかわかりません。

std::bitsetの[]演算子を用いると指定した場所のビットが得られるので、
「次のfor分文で、uesdusedが０，１のどちらかで、ｓ１、ｓ２どっちに入れるか決めている」という解釈なら正しいはずです。
ここでは使う数字の組み合わせを決めて、次の場所で具体的な数値を生成しているようですね。

「どうしてこのような解法が出てきたのか」というのは、「作者の気持ちを答えよ」ということでしょうか？

分け方を総当たりでループする処理を
>どうして
そう書いたのか？って言われても，何でその実装方法を取ったのかなんて
そんなの本人にしかわからんような気がしますけど……

みけCATさん、ありがとうございます。
解釈としては、合っているわけですね。

＞「次のfor分文で、uesdusedが０，１のどちらかで、ｓ１、ｓ２どっちに入れるか決めている」という解釈なら正しいはずです。
ここでは使う数字の組み合わせを決めて、次の場所で具体的な数値を生成しているようですね。

この場合は、すべての場合を網羅することはできるのでしょうか？

また、作者はどのようなお気持ちで、二進数を使った解法にしたのか、非常に興味がありました。bitsetを使ったことは一度もないので、調べながら、お聞きしながらマスターしていきたいと思います。

usaoさん、ご回答ありがとうございます。

たしかに　どうして　という言い方はおかしかったです。解法は一パターンだけではないですし、書く人によって変わってきますし・・・
今回お聞きしたかったのは、二進数を用いた全列挙の方法についてです。
bitset、ビット演算子などの重要分野も入ってきており、どうにかして理解したいです。ネットでも調べましたが、usedの０，１のどちらかでｓ１，ｓ２のどちらかに入れるのを決めることで、全列挙になっているのかどうかを知りたく、質問させていただきました。

適当に，個数が少ない場合とかで考えてみてはどうでしょうか．

例えば，数字が３個のとき…

最初は
permute = 1 << 3; (line25)
になるので，２進数で 1000 です．
この状態で line33～のfor文の処理を行うと，used[0]，used[1], used[2]　は全て0ですから
全ての数字がs1側に含まれて，s2側が空っぽになります．
　↓　line72 で permuteが１減る
permuteは２進数で 111 です．
今度は３つの数字全てがs2側になりそうですね．
　↓　line72 で permuteが１減る
permuteは 110
　↓
…

やってることは全てのパターンの列挙だということがわかるかと．

ありがとうございます。
なるほど、確かにシュミレーションをすると、理解できますね。
今後は小さい数から、シュミレーションを行っていきます！

きょうさんが書きました:ビット演算子の部分は理解できたのですが、 bitset<10> used = static_cast<bitset<10>>(permute);のところで二進数に変換し、usedに格納しているところまではどうにかわかりました。

なぜ、bitset<10> used = permute; と書かないのか、作者の気持ちが理解できません。

私なら、bitset なんか使わず、次のようなプログラムにします。

コード:

#include <iostream>  // cin, cout
#include <string>    // string, getline
#include <algorithm> // copy, next_permutation
#include <sstream>   // istringstream
#include <cstdlib>   // atoi, abs
using namespace std;

int main()
{
    int i, n;
    char s1[11] = "", s2[11] = "";
    string line;
    getline(cin, line);
    istringstream iss(line);
    iss >> i;
    while (i--) {
        getline(cin, line);
        istringstream is(line);
        for (n = 0; n < 10 && is >> s1[n]; n++);
        int m = n / 2, min = 99999;
        do {
            if (s1[0] == '0' || s1[m] == '0') continue;
            copy(s1, s1 + m, s2);
            int diff = abs(atoi(s2) - atoi(s1 + m));
            if (diff < min) min = diff;
            //cout << s2 << " - " << s1+m << " = " << diff << endl;
        } while (next_permutation(s1, s1 + n));
        cout << min << endl;
    }
}

プログラマ専用SNS ミクプラ

２進数を使って、最小値を求めたいです。

２進数を使って、最小値を求めたいです。

Re: ２進数を使って、最小値を求めたいです。

Re: ２進数を使って、最小値を求めたいです。

Re: ２進数を使って、最小値を求めたいです。

Re: ２進数を使って、最小値を求めたいです。

Re: ２進数を使って、最小値を求めたいです。

Re: ２進数を使って、最小値を求めたいです。

Re: ２進数を使って、最小値を求めたいです。