TCO Marathon Match Round 2

70-80位くらいなので一応 Round 3 にはいけるかな、って感じ? 全力を尽くしたかっていうとそんなことないけど、しかしそれなりに時間使ったわりにはイマイチだった…

問題は適当に大量の点が与えられるから、それをつないで正多角形に近いものをたくさん作ること。「正多角形に近い」ってのの定義は各辺の最大値と最小値の差が少なめ、ってのと、中心からの各点への距離の最大値と最小値の差が少なめ、ってのと、あと凸であること。少なめ、ってのはテストケースくらいにかなり変わる感じ。得点は n 角形一個につき n^2 点。つまり点の多い多角形を作れると嬉しい。

問題はとてもいい問題だったと思う。

やったことは

  • C=(X..3) のループを回す。 X はテストケースのサイズによって 15 から 6 まで
  • 任意の2点に関して、 X 角形が作れるかチェックする
  • 理想的な C 角形を作るにはこのへんの点が欲しい…ってのは計算できるので、その理想的な点に近い点を4分木をたぐってゲット
    • 空間のサイズが 700x700 に固定されてるので、 4分木より単純なメッシュの方が良かったようだ…
  • 点の数が >500 の場合は近い点一個を順に取っていってうまく多角形ができれば OK って感じ。一度使った点はもう使わない
  • 点の数が <500 の場合
    • 近い点を数点 (C==3 の場合だけたくさん取ってくるけどそれ以外の場合は4分木的に近いとこにある最大4点) を取ってきて、組み合わせで大量の多角形候補を作る
    • 多角形候補の群ができるので、その群の中で他の多角形に使われてないものから greedy に取っていく
    • ここを greedy にやるんじゃなくてベストぽい組み合わせをなるべく取るみたいなのは、書いてみたものの遅い上にあんま成績良くならんかったので捨てた
  • 点が >500 の場合も、使える点が 500 以下になった段階で C=(5..3) のループを使って点が少ない時のロジックをまわす

他の人のアプローチを見るに、見込みのないところを見てる時間が長いのがダメなのかなぁと。見込みがありそうなものをさっさと取っていって、だんだん見込みがありそうなものって判定をユルい条件にしつつ何度も回せば良かった気がする。そいう感じだとかなりデカい多角形も取れたみたいだ。あと残り時間調べてギリギリまで探すとかめんどいからやってないのも良くなかったと思う。

なんか捨てたり意味なくなったコード多かったなあ…各頂点同士の距離とか前もって計算する部分を SSE で書いたりとか…

なにかあれば下記メールアドレスへ。
shinichiro.hamaji _at_ gmail.com
shinichiro.h