Hatena::Grouptopcoder

cou929のTopCoder日記

2009-09-01

SRM303 div2

17:16

Prime Numbers, Factorization and Euler Function

素数のチュートリアルからの練習問題。

Hard - PrimePalindromic

問題文は省略。

まずは、AからBまでの値をひとつづつ素因数分解し、その結果が回文になっているかどうか調べるというストレートなアプローチを考えました。問題は素因数分解の結果が回文かどうかを調べる部分です。因数の全ての並べ方について、ひとつずつ回文かどうかを調べていきました(2, 3, 5の場合、(2, 3, 5), (2, 5, 3), (3, 2, 5), (3, 5, 2), (5, 2, 3), (5, 3, 2) の6通り)。しかし当然、このままではTLEなので、最適化する必要があります。

最初に考えたのは、「10以下の因数について、偶数個なら全て取り除き、奇数個なら一つをのこして取り除く」というものです。例えば8 = 2*2*2 の場合、2を2つ取り除く。これは1桁の数は両側に対象に設置されるという仮定に基づいています。しかしこれでは、例えば1197 = 3*3*133 という場合、本来ならば331133と回文になるのですが、3を2つ取り除き133のみになるので、回文でない判定してしまいます。

次は、絶対に回文になり得ないパターンの場合、全ての組み合わせを試みる前に次のループに進むというものでうす。回文になり得ないパターンは、数字の出現頻度を調べ、頻度が奇数である数字が2つ以上ある場合はありえないと判定します。しかしこの方法だけでは、十分に高速かできません。

他にも高速化を試みたんですが、どうもうまくいかないし、コードの複雑さが増してバグを埋め込んでしまいます。なにか根本的に間違ってるなと考え、もう一度落ち着いて考え直す。そういえばnext_permutationを使えばコードがシンプルになるんじゃないかと考え、実装し直すと、すごく短くなり、かつ特に最適化しなくても間に合いました。敗因はnext_permutationの存在を忘れていたことでした。

この他にも(next_permutation版では必要なくなったんですが)vectorのコンストラクタの使い方で勘違いがあり、時間を取られました。ベクタのスタック(stack <vector <int> >)に、例えば0~ 4の一要素だけのベクタをプッシュしていきたかったんですが、

stack <vector <int> > s;
for (int i=0; i<5; i++)
  s.push(vector <int> (i));

for (int i=0; i<5; i++)
  {
    vector <int> tmp = s.top();
    s.pop();
    for (int j=0; j<tmp.size(); j++)
      cout << tmp[j] << " ";
    cout << endl;
  }

これだとうまくいきません。出力は以下のようになります。

0 0 0 0 
0 0 0 
0 0 
0 

vector <int> (n) は、大きさnの無名のベクタを作ります。そして初期値が0なので、上記のような結果になるわけです。vector <int> (n) で値がnの1要素のベクタができると思ってしまったのが勘違いでした。

アルゴリズム的には難しくなく、自分の実装力のせいでうまくいかなかったので、くやしいです。

class PrimePalindromic {
public:
  string toStr(int n) {ostringstream ss; ss << n; return ss.str();}

  vector <int> factor(const int n)
  {
    vector <int> ret;
    int num = n;

    for (int i=2; i*i<=n; i++)
      {
	while (num % i == 0)
	  {
	    ret.push_back(i);
	    num /= i;
	  }
      }

    if (num > 1)
      ret.push_back(num);

    return ret;
  }

  bool isPalindromic(string s)
  {
    bool ret = true;
    for (int i=0; i<s.size()/2; i++)
      if (s[i] != s[s.size()-1-i])
	{
	  ret = false;
	  return ret;
	}

    return ret;
  }

  int count(int A, int B)
  {
    int ret = 0;

    for (int i=A; i<=B; i++)
      {
	vector <int> primes = factor(i);
	do {
	  string str;
	  for (int j=0; j<primes.size(); j++)
	    str += toStr(primes[j]);
	  if (isPalindromic(str))
	    {
	      ret++;
	      break;
	    }
	} while (next_permutation(primes.begin(), primes.end()));
      }

    return ret;
  }
};


おまけ、試行錯誤の跡(うごきません)。

  int count(int A, int B)
  {
    int ret = 0;
    map <int, int> m;
    char check[10001];
    memset(check, -1, sizeof(check));
    MAX = 5000;
    gen_primes();

    for (int i=A; i<=B; i++)
      {
	if (check[i] != -1)
	  continue;

	check[i] = 0;

	vector <int> primes = factor(i);

	if (primes.size() > 1)
	  for (vector <int>::iterator j=primes.begin(); j<primes.end()-1; j++)
	    if (*j < 10 && *j == *(j+1))
	      {
		j = primes.erase(j);
		j = primes.erase(j);
		j--;
	      }

	map <int, int> m;
	map <int, int>::iterator mi;
	string str;
	int odd = 0;
	for (int j=0; j<primes.size(); j++)
	  str+=toStr(primes[j]);
	for (int j=0; j<str.size(); j++)
	  m[str[j]-'0']++;
	for (mi=m.begin(); mi!=m.end(); mi++)
	  if (mi->second % 2 == 1)
	    odd++;
	if (odd > 1)
	  continue;

	// 		for (int j=0; !primes.empty() && j<primes.size()-1; j++)
	// 		  if (primes[j] == primes[j+1])
	// 		    {
	// 		      primes.erase(primes.begin());
	// 		      primes.erase(primes.begin());
	// 		    }
	// 		m[primes.size()]++;
	if (primes.empty())
	  {
	    ret++;
	    continue;
	  }

	stack <vector <int> > s;
	for (int j=0; j<primes.size(); j++)
	  {
	    vector <int> a;
	    a.push_back(j);
	    s.push(a);
	  }

	while (!s.empty())
	  {
	    vector <int> t = s.top();
	    s.pop();

	    if (t.size() == primes.size())
	      {
		string pal;
		for (int j=0; j<t.size(); j++)
		  pal += toStr(primes[t[j]]);
	
		if (isPalindromic(pal))
		  {
		    for (int j=0; j<MAX; j++)
		      if (primeTable[j])
			{
			  for (int k=1; i*(int)pow((double)j, k) <= B; k++)
			    {
			      int p = i*(int)pow((double)j, k);
			      if (check[p] == -1)
				check[p] = (k % 2 == 0) ? 0 : 1;
			    }
			}

		    break;
		  }
	      }

	    for (int j=0; j<primes.size(); j++)
	      {
		if (find(t.begin(), t.end(), j) == t.end())
		  {
		    vector <int> tmp = t;
		    tmp.push_back(j);
		    s.push(tmp);
		  }
	      }
	  }
      }

    return ret;
  }