Member SRM 465 DIV2 Easy

TopCoder

NumberNeighbours



ある２つの数について、各桁の数の順列が一致する（leading zeroは無視）とき

Neibouring Numberであるという。

例えば、40020と204はそれぞれの順列00042と042で一致するのでNeighbouring Numberである。

いくつかの数がvectorで与えられるので、Neighbouring Numberの組は何個あるか答える。

方針



とりあえずforを２回回して全ての組み合わせを試す。

for(i)for(j)の中でnumbers[i]、numbers[j]を文字列に変換してごにょごにょ…

numbers[i]、numbers[j]を文字列に変換したs1とs2にnext_permutation()を使って
順列生成しながらatoi()で一致判定。。。とか考えたけどO(s1.size()!*s2.size()!)でTLE必至。


う〜ん。。。


上の方針で進めてた過程で、next_permutation()を使うなら
最小の順列（40020なら00024）を生成する必要があって、sort()を使ってみた。


…あれ？


これを比較すればよくね？ｗ
s1="40020", s2="204"なら

sort(s1.begin(), s1.end());
sort(s2.begin(), s2.end());
// これでs1="00024", s2="024"
if (atoi(s1.c_str()) == atoi(s2.c_str())) ++result;

でおｋ！

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
using namespace std;
static const double EPS = 1e-5;
typedef long long ll;

class NumberNeighbours {
public:
    int numPairs(vector <int> numbers) {
        int result = 0;
        for (int i = 0; i < numbers.size(); ++i) {
            for (int j = i+1; j < numbers.size(); ++j) {
                stringstream ss1, ss2;
                ss1 << numbers[i], ss2 << numbers[j];
                string s1, s2;
                ss1 >> s1, ss2 >> s2;
                sort(s1.begin(), s1.end());
                sort(s2.begin(), s2.end());
                if (atoi(s1.c_str()) == atoi(s2.c_str())) ++result;
            }
        }
        return result;
    }
};

stringstream使うのにid:ororogの日記参照してたら20分くらいかかったん