SRM268 - Division2 脱出

Hayato Ito

SRM268 に挑戦．Division2 の問題です．

CrossWordPuzzle (code)

250 点問題． 1 文字・1 文字，順にチェックしている人が多かったようですが，正規表現を使用した文字列分割 (いわゆる split(..)) が利用できる言語なら，それを使えば簡単です．今回は正規表現を使用するほどでもないですが，正規表現を使用すれば，ずっと簡単になる問題も TopCoder ではときどき出題されるようです．

CmpdWords (code)

500 点問題．一見，問題がわかりにくいですが，ハッシュテーブルを使用して，合成文字列の重複のカウントをすれば，これも簡単です．

TriArea

1000 点問題．重なり合う 2 等辺三角形が複数与えられます．それらがカバーする面積をもとめる問題です. 3 角形の重なりを判定して全体の面積を求めようととしたのですが， 1 時間以上，格闘したあげく，時間切れでした．

パラメータの条件として

Each element of xCenter and yCenter will be between -100 and 100, inclusive.

とあるので，全 2 次元空間をひたすら調べたほうが簡単でした. 1 x 1 のグリッドをさらに 4 つのエリアにわけて，そのエリアが三角形に含まれているなら

(面積) += 0.25

とすればよいです．

public class TriArea {

  public double area(int[] xCenter,
                     int[] yCenter, int[] height) {
    double res = 0;
    int N = xCenter.length;
    int[] dx = {1, 2, 2, 3};
    int[] dy = {2, 1, 3, 2};
    for (int x = -200; x < 200; x++) {
      for (int y = -100; y < 200; y++) {
        for (int d = 0; d < 4; d++) {
          double nx = x + dx[d] / 4.0;
          double ny = y + dy[d] / 4.0;
          for (int i = 0; i < N; i++) {
            if (ny < yCenter[i]) continue;
            if ( height[i] > Math.abs(xCenter[i] - nx)
                  + (ny - yCenter[i])) {
              res += 0.25;
              break;
            }
          }
        }
      }
    }
    return res;
  }
}

これでも，Order は 400 x 400 x 4 x 25(3 角形の最大数) ですから，これで十分いけましたね．．

結果

System Test の結果です． ( Room Statistics )

Room Statistics

1000 点問題ができなかったのが悔やまれますが,250 点問題と 500 点問題は早めに Submit できたためか，ルーム内では Top のポイントでした． レーティングは 1152 -> 1303 と 1200 を超えたので，Division2 脱出です．

今日の教訓