Hatena::Grouptopcoder

cou929のTopCoder日記

2009-05-01

SRM439 div2

19:27

Easyをよくわからないミスによって落とし、Mediumが解けなかったため0点。スコアが100点ぐらい落ちました。

Easy - SquareOfDigits

各要素に0-9の整数が格納された2次元配列から、各頂点が同じ数字となっている最大の正方形の面積を返すという問題。

入力のサイズが小さいので、ストレートに実装すればできそうです。が、配列全体ではなく、配列の半分しか走査しないアルゴリズムにしてしまい、システムテストで落ちました。意味不明なミスだ。まじで悔しい。

同じ部屋のシステムテストに落ちた人のコードを見てみると、正方形じゃなくて長方形を探していて、落ちている人が何人かいました。チャレンジのチャンスだったのに、なんで気づかなかったんだろう。悔いが残る。

  int getMax(vector <string> data)
  {
    int i, j, k;
    int ret = 1;

    for (i=0; i<data.size()-1; i++)
      for (j=0; j<data[i].size()-1; j++)
	for (k=j+1; k<data[i].size(); k++)
	  if (data[i][j] == data[i][k])
	    {
	      int l = k-j;
	      if ((l+1)*(l+1) > ret)
		if (i+l < data.size() && j+l < data[i].size() && data[i+l][j] == data[i][j] && data[i+l][j+l] == data[i][j])
		  ret = (l+1)*(l+1);
	    }

    return ret;
  }

Medium - PouringWater

できなかった。この問題のボトルが、2進数と同じ構造を持っているということに気づくことができれば、解けたと思います。そうするとこの問題は、2進数で表現したときに立っているビットの数がKである、N以上の最小の値を探すという問題に変換できます。また、新しく買えるボトルの数に制限がないので、返り値が-1になることはありません。

cafelierさんの日記を参考にさせていただきました。

  int countBit(int N)
  {
    int n = N;
    int counter = 0;

    while (n)
      {
	if (n & 1)
	  counter++;
	n = n >> 1;
      }

    return counter;
  }

  int getMinBottles(int N, int K)
  {
    for (int i=0;;i++)
      {
	if (countBit(N+i) <= K)
	  return i;
      }

    return -1;
  }

SRM349 div2(過去問)

07:18

Easy - DocumentSearch

文字列をサーチする系統の問題。

この手の問題は、ループの境界を間違えやすいです。それぞれのループの開始・終了条件や、イテレータへの加減算には特に注意。逆にチャレンジのチャンスにもなる。

僕は今回、一致するフレーズがあるかどうかを自前で書いたのですが、関数(findとかsubstr)を積極的に使った方が、早いし安全ですね。

  int nonIntersecting(vector <string> doc, string search)
  {
    int i, j, k;
    int ret = 0;
    string s = "";

    for (i=0; i<doc.size(); i++)
      s += doc[i];

    for (i=0; i<s.size(); i++)
      {
	if (s[i] == search[0])
	  {
	    bool found = true;
	    for (k=1; k<search.size(); k++)
	      {
		if (s[i+k] != search[k])
		  {
		    found = false;
		    break;
		  }
	      }

	    if (i+search.size() > s.size())
	      found = false;

	    if (found)
	      {
		ret++;
		i += k-1;
	      }
	  }
      }

    return ret;
  }