Hatena::Grouptopcoder

cou929のTopCoder日記

2009-06-14

SRM442 div2

11:06

250、500点問題ともに比較的簡単でした。よってチャレンジも、僕の部屋では一回もありませんでした。よって当たり前のところをより早く正確にやる必要のある回だったと思います。

Easy - SimpleWordGame

プレイヤーの持つワードの集合と辞書が与えられる。プレイヤーのワードのうち、辞書にあるものの長さの総和を求めよ。ただし、プレイヤーのワードの重複は1回とカウントし、またワードの長さはワードの文字数の自乗とする。

プレイヤーのワードの重複を取り除き、辞書にあるか調べ、長さを計算していきます。そのままやるだけの問題でした。

class SimpleWordGame {
public:
  int points(vector <string> player, vector <string> dictionary)
  {
    set <string> s;
    int ret = 0;

    for (int i=0; i<player.size(); i++)
      s.insert(player[i]);

    for (set <string>::iterator i=s.begin(); i!=s.end(); i++)
      {
	if (find(dictionary.begin(), dictionary.end(), *i) != dictionary.end())
	  {
	    string t = *i;
	    ret += t.size() * t.size();
	  }
      }

    return ret;
  }
};

Medium - Underprimes

整数AからBの範囲にある、underprimeの数を求める。整数Xが、任意個の素数の積で表現でき、かつその素数の数が素数個であった場合、Xはunderprimeであると定義する。

まず昇順の素数の集合を用意する。AからBの範囲の整数Xを一つずつ走査する。Xについて、素数集合を小さい方からループさせながら割っていく。もし最後まで素数のみで割り切れた場合、個数が素数かどうかチェックする。

prime factorizationの計算を、だいたいlog(n)と考えて、計算量がワーストケースで100000 * log(100000)だからなんとかなるかなと実装しました。

class Underprimes {
public:
  bool isPrime(int n)
  {
    if (n < 2)
      return false;

    if (n != 2 && n % 2 == 0)
      return false;

    int s = sqrt(n);

    for (int i=3; i<=s; i++)
      if (n % i == 0)
	return false;

    return true;
  }

  int howMany(int A, int B)
  {
    vector <int> primes;
    int ret = 0;

    for (int i=2; i<=50000; i++)
      if (isPrime(i))
	primes.push_back(i);

    for (int i=A; i<=B; i++)
      {
	int count = 0;
	int t = i;
	while (t != 1)
	  {
	    bool flg = false;
	    for (int j=0; j<primes.size(); j++)
	      if (t % primes[j] == 0)
		{
		  t /= primes[j];
		  count++;
		  flg = true;
		  break;
		}

	    if (!flg)
	      {
		count = 0;
		break;
	      }
	  }

	if (isPrime(count))
	  ret++;
      }

    return ret;
  }
};

Hard - EqualTowers

異なる高さのブロックがいくつか与えられる。ブロックを積み上げて2つのタワーを作りたい。2つのタワーの高さが同じ場合、最大の高さはどれだけになるか。ただし全てのブロックを使い切らなくても良い。また同じ高さのタワーを作れない場合は-1を返す。

brute- forceに解いた場合。最大で3^50個のケースを探索しないといけないため、時間に間に合いません。DPなどを使う必要がありそうですが、慣れてないので時間内に実装できる自信がありませんでした。よって、前者のbrute-forceな方法で、暫定解より悪い場合や、解が上界を超えている場合などに枝狩りして、なんとか計算量をへらせないかなあととりあえず実装してみました。

案の定、この実装では最悪のケースでTLEです。とりあえずDPは早々に慣れておきたいです。

class EqualTowers {
  int ret;
  int opt;
  vector <int> b;
  vector <int> dif;

  int s(int A, int B, int n)
  {
    if (n == b.size())
      {
	if (A != 0 && B != 0 && A == B)
	  ret = max(ret, A);
	return 0;
      }

    if (max(A, B) > opt)
      return 0;

    if (dif[n] != 0 && min(A, B) + dif[n] < max(A, B))
      return 0;

    if (max(A, B) + dif[n]/2 < ret)
      return 0;

    s(A, B, n+1);
    s(A+b[n], B, n+1);
    s(A, B+b[n], n+1);

    return 0;
  }

  int height(vector <int> bricks)
  {
    int sum = 0;
    ret = 0;
    b = bricks;

    dif.push_back(0);

    for (int i=bricks.size()-1; i>0; i--)
      {
	sum += bricks[i];
	dif.push_back(sum);
      }

    reverse(dif.begin(), dif.end());

    sum += bricks[0];
    opt = sum / 2;

    s(0, 0, 0);

    if (ret == 0)
      ret = -1;
    
    return ret;
  }
};