Hatena::Grouptopcoder

nodchipのTopCoder日記 このページをアンテナに追加 RSSフィード

 | 

2013-06-30

幾何コンテスト2013 17:00 幾何コンテスト2013 - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - 幾何コンテスト2013 - nodchipのTopCoder日記 幾何コンテスト2013 - nodchipのTopCoder日記 のブックマークコメント

A : 役人

  • これは焼きなますに違いない!(<-おいちょっと待ってこら落ち着け!)
  • 焼きなましライブラリペタペタ
  • エネルギー関数ガリガリ
  • でけた
  • Submit
  • RE
  • なぬぅーっ!!!
  • 手元ではちゃんと動いているのに・・・orz
  • とりあえず色々コメントアウトして"0"だけ出力させるようにしてみる
  • TLE
  • ・・・
  • ( ゚д゚)
  • ・・・
  • 落ち着こう・・・
  • とりあえず落ち着こう・・・
  • 順位表には4分以内に解けた人もいるのだからきっと簡単な解法があるはず
  • ソートして貪欲とかどうだろう
  • x座標でソートして端から3つずつ取っていくとか
  • AC 100
  • そんな簡単でよかったのか・・・
typedef complex<double> P;

namespace std {
  bool operator < (const P& a, const P& b) {
    return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);
  }
}

int main() {
  std::ios::sync_with_stdio(false);

  vector<pair<P, int> > points;
  REP(i, 300) {
    int x, y;
    cin >> x >> y;
    points.push_back(MP(P(x, y), i + 1));
  }
  sort(ALL(points));

  cout << 100 << endl;
  REP(i, 100) {
    int a = points[i * 3 + 0].second;
    int b = points[i * 3 + 1].second;
    int c = points[i * 3 + 2].second;
    cout << a << " " << b << " " << c << endl;
  }
}

B : 玉座の間

  • 満点とか無理ゲー臭しかしないので部分点を狙いに行く
  • N<=20なら左右に振り分けて、y軸に移動させるものとy軸対称にマッチングさせるものを全探索すれば良いだけ
  • ビット演算ガリガリ
  • Spagetti Sourceのハンガリアンマッチングをコピペして型をdoubleに変更
  • サンプル通るかな・・・
  • ・・・
  • ローカル環境でTLE・・・orz
  • ハンガリアンの中で無限ループしているっぽい
  • 多分doubleの誤差で何処かの判定が狂ってる
  • 短時間で直すのは無理っぽい
  • どうしよう
  • とりあえずハンガリアンの代わりに最小費用流で解こうか・・・
  • TLE 100
  • やっぱり最小費用流遅いか・・・
  • じゃあlong longで固定小数にしてしまおうか
  • 1e15倍すれば値自体は範囲内に収まるし、誤差も多分大丈夫
  • TLE 150
typedef complex<double> P;

int main() {
	std::ios::sync_with_stdio(false);

  vector<P> left, right;
  int N;
  cin >> N;
  REP(n, N) {
    int x, y;
    cin >> x >> y;
    if (x < 0) {
      left.push_back(P(-x, y));
    } else if (x > 0) {
      right.push_back(P(x, y));
    }
  }

  double answer = INT_MAX;
  for (int leftBits = 0; leftBits < (1 << left.size()); ++leftBits) {
    vector<P> leftFiltered;
    double leftAnswer = 0.0;
    REP(i, left.size()) {
      if (leftBits & (1 << i)) {
        leftFiltered.push_back(left[i]);
      } else {
        leftAnswer += left[i].real();
      }
    }
    int numberOfPoints = countPop(leftBits);

    for (int rightBits = 0; rightBits < (1 << right.size()); ++rightBits) {
      if (numberOfPoints != countPop(rightBits)) {
        continue;
      }

      vector<P> rightFiltered;
      double rightAnswer = 0.0;
      REP(i, right.size()) {
        if (rightBits & (1 << i)) {
          rightFiltered.push_back(right[i]);
        } else {
          rightAnswer += right[i].real();
        }
      }

      matrix m(numberOfPoints, array(numberOfPoints));
      REP(leftIndex, numberOfPoints) {
        REP(rightIndex, numberOfPoints) {
          m[leftIndex][rightIndex] = -abs(leftFiltered[leftIndex] - rightFiltered[rightIndex]) * 1e15;
        }
      }

      double answerMatching = -hungarian(m) * 1e-15;
      double tempAnswer = leftAnswer + rightAnswer + answerMatching;
      MIN_UPDATE(answer, tempAnswer);
    }
  }

  printf("%.20f\n", answer);
}

C : 泥棒

  • N<=1000くらいなら凸包取って内包判定するだけじゃね?
  • TLE 150
  • 更に高速化するためには凸包の天井部分と床部分を別個に持って、それぞれについて端または途中に挿入、上限下限判定とかすれば良い気がする
  • ・・・
  • けど残り時間じゃ実装できないよね・・・
  • orz
int main() {
	std::ios::sync_with_stdio(false);

  int N;
  cin >> N;
  vector<P> polygon;
  REP(n, N) {
    string S;
    double x, y;
    cin >> S >> x >> y;

    if (S == "TARGET") {
      if (contains(polygon, P(x, y)) == OUT) {
        cout << "SAFE" << endl;
      } else {
        cout << "DANGER" << endl;
      }

    } else {
      polygon.push_back(P(x, y));
      polygon = convex_hull(polygon);
    }
  }
}

D : 魔女

  • どこかで見たような問題・・・
  • MaximumだったかICPCだったかJAGだったか・・・
  • いずれにしてもよくからない

System Test

順位ユーザ名役人玉座の間泥棒魔女得点 / Total
19nodchip100 (11) 124:25150 (1) 150:01150 110:28-400 (12) 150:01

なんとか1ページ目に載ることができました。幾何は好きです。はい。

トラックバック - http://topcoder.g.hatena.ne.jp/nodchip/20130630
 |