http://www.hackerrank.comでオンライン プログラミング コンテストに参加しています。私が取り組んでいる問題の 1 つは、回文でもある文字列のアナグラムの数を見つけることです。問題は解決しましたが、アップロードしようとすると、多くのテスト ケースで失敗します。実際のテスト ケースは私には隠されているため、なぜ失敗するのかはわかりませんが、スケーラビリティの問題である可能性があると思います。今、誰かに既製の解決策を教えてもらいたくありません。なぜなら、それは公平ではないからです。ただ、人々が私のアプローチについてどう思うか興味があります。
Web サイトの問題の説明は次のとおりです。
与えられた単語に回文であるアナグラムがあるかどうかを調べる方法を知った王は、別の課題に直面します。彼は、特定の単語の回文であるアナグラムが複数存在する可能性があることを認識しています。回文である与えられた単語に対して可能なアナグラムの数を彼が見つけるのを手伝ってくれますか?
王の言葉は多い。与えられた単語ごとに、王は回文である文字列のアナグラムの数を見つける必要があります。アナグラムの数は多くなる可能性があるため、キングはアナグラムの数 % (10 9 + 7) を必要とします。
入力形式 :
入力文字列を含む単一行出力形式:
であるアナグラム文字列の数を含む 1 行。palindrome % (109 + 7)制約 :
1<=length of string <= 105- 文字列の各文字は小文字のアルファベットです。
- 各テストケースには、回文である少なくとも 1 つのアナグラムがあります。
サンプル入力 01 :
aaabbbbサンプル出力 01 :
3説明 :
回文である与えられた文字列の 3 つの順列は、 abbabba 、 bbaaabb 、および bababab として与えることができます。サンプル入力 02 :
cdcdcdcdeeeefサンプル出力 02 :
90
問題の説明で指定されているように、入力文字列は 10^5 まで大きくなる可能性があるため、数の飽和の問題が発生するため、大きな文字列のすべての回文は不可能です。また、モジュロ (10^9 + 7) ベースの答えを出すだけでよいので、底 (10^9 + 7) で数値の対数を取り、すべての計算で底 (10^9) で分数部分の逆対数を取ることを考えました。とにかくモジュロになるので、答えの+ 7）。
私のアルゴリズムは次のとおりです。
- 各文字の頻度を格納します (回文の定義により、文字列の後半は最初の文字列と同じであるため、文字列の半分だけを調べる必要があります)
- 複数の文字が奇数回出現する場合、回文は不可能
- それ以外の場合は、各文字の頻度について、回文数を段階的に計算します (動的プログラミング)
DP の場合、副問題は次のとおりです: previous_count = 1
追加キャラごとに
added number of palindromes = previous_count * (number_of_char_already_seen + 1)/(number of char same as current char)
これが私のコードです：
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <fstream>
using namespace std;
#define MAX_SIZE 100001
void factorial2 (unsigned int num, unsigned int *fact) {
fact[num]++;
return;
}
double mylog(double x) {
double normalizer = 1000000007.0;
return log10(x)/log10(normalizer);
}
int main() {
string in;
cin >> in;
if (in.size() == 1) {
cout << 1 << endl;
return 0;
}
map<char, int> freq;
for(int i=0; i<in.size(); ++i) {
if (freq.find(in.at(i)) == freq.end()) {
freq[in.at(i)] = 1;
} else {
freq[in.at(i)]++;
}
}
map<char, int> ::iterator itr = freq.begin();
unsigned long long int count = 1;
bool first = true;
unsigned long long int normalizer = 1000000007;
unsigned long long int size = 0;
unsigned int fact[MAX_SIZE] = {0};
vector<unsigned int> numerator;
while (itr != freq.end()) {
if (first == true) {
first = false;
} else {
for (size_t i=1; i<=itr->second/2; ++i) {
factorial2(i, fact);
numerator.push_back(size+i);
}
}
size += itr->second/2;
++itr;
}
//This loop is to cancel out common factors in numerator and denominator
for (int i=MAX_SIZE-1; i>1; --i) {
while (fact[i] != 0) {
bool not_div = true;
vector<unsigned int> newNumerator;
for (size_t j=0; j<numerator.size(); ++j) {
if (fact[i] && numerator[j]%i == 0) {
if (numerator[j]/i > 1)
newNumerator.push_back(numerator[j]/i);
fact[i]--; //Do as many cancellations as possible
not_div = false;
} else {
newNumerator.push_back(numerator[j]);
}
}
numerator = newNumerator;
if (not_div) {
break;
}
}
}
double countD = 0.0;
for (size_t i=0; i<numerator.size(); ++i) {
countD += mylog(double(numerator[i]));
}
for (size_t i=2; i <MAX_SIZE; ++i) {
if (fact[i]) {
countD -= mylog((pow(double(i), double(fact[i]))));
fact[i] = 0;
}
}
//Get the fraction part of countD
countD = countD - floor(countD);
countD = pow(double(normalizer), countD);
if (floor(countD + 0.5) > floor(countD)) {
countD = ceil(countD);
} else {
countD = floor(countD);
}
count = countD;
cout << count;
return 0;
}
今、私はこの問題に多くの時間を費やしてきましたが、私のアプローチに何か問題があるのでしょうか、それともここで何かが欠けているのでしょうか。何か案は？