問題概要

数字のみからなる長さ $N$ の文字列 $S$ が与えられる。 $S$ を並び替えて得られる文字列であって、平方数を表すものが何通りあるかを答えよ。

制約

$1 \le N \le 13$

考えたこと

$N!$ 通りの順列を考えたのでは間に合わないので発想の転換が必要になる。

よく考えると、13 桁以内の整数であって平方数であるものは、 $\sqrt{10^{13}} \neq 3.2 \times 10^{6}$ 個程度しかないのだ。

よって、文字列 $S$ を並び替えるのではなく、平方数を列挙して、それらの平方数 $v$ に対して「 $v$ を並び替えることで $S$ に一致するかどうか」を調べていけばよい。

数 $v$ の各桁を並び替えて $S$ に一致するかを調べる

$v$ の各桁を並び替えて $S$ に一致するかを調べるためには、次のようにするのが簡単だと思われる。

$v$ を文字列として sort() して、辞書順最小となるようにする
$S$ を文字列として sort() して、辞書順最小となるようにする
それらが一致するかを確かめる

これを各平方数について実行すればよい。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    string S;
    cin >> N >> S;
    sort(S.begin(), S.end());  // S をあらかじめ sort しておく
    
    long long res = 0;
    for (long long v = 0; v <= 3200000; ++v) {
        long long val = v * v;
        string str = to_string(val);
        
        if (str.size() > S.size()) break;
        
        // S と桁数を合わせておく
        while (str.size() < S.size()) str += "0";
        sort(str.begin(), str.end());
        if (S == str) ++res;
    }
    cout << res << endl;
}