Hatena::Grouptopcoder

cou929のTopCoder日記

2009-05-28

SRM441 div2

16:18

始まる前に少し寝ておこうと思い、仮眠をとったのですが、開始時間を20分くらい寝過ごしてしまいました。でもトラブルがあり開始が遅れたらしく、寝過ごしの影響が少なくなりラッキーでした。

頭が回っていなくて、250点問題は時間がかかってしまいました。500点問題はチャレンジ成功されました。最終的にはスコアが10点くらいアップしました。

Easy - DifferentStrings

文字列A, Bの間の、異なる文字の個数を求める問題。

Aを1文字ずつスライドさせながらBと比較し、異なっている文字数を求め、それぞれの結果の中から最小値を返します。

class DifferentStrings {
public:
  int minimize(string A, string B)
  {
    int ret = 1000000;

    for (int i=0; i<=B.size() - A.size(); i++)
      {
	int len = 0;
	for (int j=0; j<A.size(); j++)
	  {
	    if (A[j] != B[i+j])
	      len++;
	  }
	ret = min(len, ret);
      }

    return ret;
  }
};

Medium - PaperAndPaintEasy

紙を折り畳んでいき、その一部を切り抜く(色を塗る)。その後紙を広げたときに、切り抜かれていない部分の面積を求める。

まず紙を折り畳み、必要なセルに色を塗ります。色を塗ったそれぞれのセルについて、広げたときに何倍の個数になるかを計算していきます。考慮すべき点は、

  • xfoldがwidthの半分を超えているかどうか。
  • x1, x2, xfoldの位置関係に応じて、3通りに場合分け。
    • xfold <= x1 の場合
    • x1 < xfold < x2 の場合
    • xfold <= x2 の場合
  • 値のオーバーフロー。かけ算するときはlong longにキャストする。

加えて、僕が最初に組んだ解法は、色を塗ったセルを1つずつ調べていいました。しかしこの方法では大きな値でTLEしてしまします。チャレンジされたのもこれが原因だったと思います。

class PaperAndPaintEasy {
public:
  long long computeArea(int width, int height, int xfold, int cnt, int x1, int y1, int x2, int y2)
  {
    long long color = 0;

    if (xfold > width/2)
      xfold = width - xfold;

    if (xfold <= x1)
      {
	color += ((long long)x2 - x1) * (cnt + 1);
      }
    else if (x2 <= xfold)
      {
	color += ((long long)x2 - x1) * (cnt + 1) * 2;
      }
    else
      {
	color += ((long long)xfold - x1) * (cnt + 1) * 2;
	color += ((long long)x2 - xfold) * (cnt + 1);
      }

    color *= (y2 - y1);

    return (long long)width * (long long)height - color;
  }
};