Hatena::Grouptopcoder

cou929のTopCoder日記

2009-07-08

SRM444 div2

22:51

250点問題は問題なし。500点問題ができませんでした。500が解けてる人はそれほど多くなかったので、250のスコアの僅差で順位が大きく変わるという状況でした。一応レイティングは50ほどあがりましたが、納得のいく結果ではなかったです。

Easy - FourBlocksEasy

少し時間がかかってしまったんですが、特に難しいところはない問題でした。

2 x N の大きさの長方形の升目がある。その上にパネルを配置していく。パネルの大きさは1 x 1 のものと、2 x 2のものの2種類。また1 x 1のパネルの得点は1点、2 x 2は16点である。あらかじめ1 x 1のパネルが配置された升目が与えられるので、最も点数が高くなるようなパネルの敷き詰め方を求め、その得点を返す。

升目を左から順にみていって、2x2がおけそうなら置く、そう出なければ1x1を敷き詰める。という単純な戦略で十分だと思います。

class FourBlocksEasy {
public:
  int maxScore(vector <string> grid)
  {
    int ret = 0;

    for (int i=0; i<grid[0].size(); i++)
      {
	if (grid[0][i] == '.')
	  {
	    if (grid[1][i] == '.' && (i+1 < grid[0].size() && grid[0][i+1] == '.' && grid[1][i+1] == '.'))
	      {
		grid[0][i] = '4';
		grid[1][i] = '4';
		grid[0][i+1] = '4';
		grid[1][i+1] = '4';
	      }
	    else
	      {
		grid[0][i] = '1';
		if (grid[1][i] == '.')
		  grid[1][i] = '1';
	      }
	  }
	else
	  {
	    if (grid[1][i] == '.')
	      grid[1][i] = '1';
	  }
      }

    for (int i=0; i<grid[0].size(); i++)
      ret += (grid[0][i] - '0') + (grid[1][i] - '0');

    return ret;
  }
};

Medium - NumericalPerfectionLevel

整数Nのスコアを求める。スコアの計算方法は、N = a * b * c * d となる2以上の整数a, b, c, dのうち、最小の数+1です。またNが4つの因数に分割できない場合は、スコアは0です。

Nが高々10E13なので、ブルートフォースでは間に合いません。他の人のコードを見ていたところ、みんな次の解法で解いていました。

まずNをスコアが0になるような小さな数でひたすら割っていき、その回数を数えます。この数をkとします。次にkをどんどん4で割っていき、その回数を数えます。この数が解です。

たとえば、テストケース3の167961は2*2*2*2*2*2*2*2*3*3*3*3*3*3*3*3と表せます。これはさらに(2*2*3*3 = 36)が4つという4グループに分けられます。よってスコアは2です。一度一番細かいところまで分解し、もう一度組み直すというイメージです。

以下のコードはコンテスト後に書いたものです。今プラクティスルームで試してみたのですが、たまにTLEになってしまいます。ほぼ同様の書き方でシステムテストに通っている人がいたのですが、原因がよくわかりません。みんなが殺到していて、サーバが重くなっているせいでしょうか。

class NumericalPerfectionLevel {
public:
  int getLevel(long long N)
  {
    int ret = 0;
    int factor = 0;

    for (int i=2; i*i<=N; i++)
      {
	while (N % i == 0)
	  {
	    N /= i;
	    cout << i << endl;
	    factor++;
	  }
      }

    if (N != 1)
      factor++;

    while (factor / 4 > 0)
      {
	ret++;
	factor /= 4;
      }

    return ret;
  }
};

Hard - RotatingTriangles

オープンすらしていません。