Hatena::Grouptopcoder

TopCoder煮ブログ

本家ブログはこっち → http://d.hatena.ne.jp/nitoyon/

2008-10-08

HoleCakeCuts (SRM411 DIV1 Medium) その1

| 23:44 | HoleCakeCuts (SRM411 DIV1 Medium) その1 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - HoleCakeCuts (SRM411 DIV1 Medium) その1 - TopCoder煮ブログ

勢いで解こうと悩んだが時間切れ。

しばらく頭を冷やして挑んだら、すごくかっこいい答えができた。たまにはコードをここに書いておこう。

int cutTheCake(int cakeLength, int holeLength, vector <int> horizontalCuts, vector <int> verticalCuts)
{
    int h = 0, v = 0;
    for(int i = 0; i < horizontalCuts.size(); i++){
        if(-holeLength <= horizontalCuts[i] && horizontalCuts[i] <= holeLength){
            h++;
        }
    }
    for(int i = 0; i < verticalCuts.size(); i++){
        if(-holeLength <= verticalCuts[i] && verticalCuts[i] <= holeLength){
            v++;
        }
    }

    int total = (horizontalCuts.size() + 1) * (verticalCuts.size() + 1);
    int inner = max(0, h - 1) * max(0, v - 1);
    total -= inner;

    if(h == 0) total += max(0, v - 1);
    if(v == 0) total += max(0, h - 1);
    return total;
}

ざっと解説。

  1. 穴に交わる数をカウントする
  2. 穴がなかったときに何個になるかを total に入れる
  3. 穴の中にある数を引く
  4. 穴があることで上下に分断される場合を加算する

図を描くと分かりやすい。

DIV2 の C++ トップの人は、塗り分け問題として解いていた。法則を導き出せないときは、そうやって機械的に解いた方が確実だろう。あとで試そう。

その2 に続く