TopCoder Open 2011 Round 2 by chokudai
- 3. 多角形分割問題 ? 与えられる点の個数nは、50～5000 ? 点はランダムで与えられ、x,y座標は0～700にランダム ? 分割後に得られるスコアは、k角形がAk個あるとして、 ? Σk*k*Akで表わされる ? 単純に言えば、ｋ角形に属している点はｋ点入る ? 多角形は正多角形に近い形でなければならない。 ? 要求される条件は以下の通り ? 生成される多角形は、凸多角形でなくてはならない。 ? (最短の辺の長さ/最長の辺の長さ)が、(100-SideDiff)%以上 ? SideDiffは、1～20でランダムに与えられる変数である。 ? 中心点からの距離の(最短長/最長長)が、(100-radiiDiff)%以上 ? radiiDiffは，1～20でランダムに与えられる変数である。
- 4. 制約条件の確認 ? 中心点は算術平均 ? 単純に足して割るだけ ? SideDiffとradiiDiff ? sideDiff ? 黒い線の最大誤差 ? radiiDiff ? 青い線の最大誤差 ? 凸性の条件 ? 内角が180度未満
- 5. 戦略 ? 可能な限り大きい多角形から貪欲で作る ? 小さいのを作った後、小さいのを崩して大きいのを作るのは、 無駄な部分が多く、効率が悪い。 ? 厳密にやるなら、乱択アルゴリズム等で出来るが、実行時間 の制約上難しい ? 今回は、多角形を列挙するための十分な時間がないので割愛 ? 小さい多角形のみ焼きなまし ? 小さい多角形は生成が簡単 ? 貪欲でなく、焼きなまし法を用いて最適化を行う ? 列挙は制約上無理なので、最大独立集合はここでも相性は悪い
- 6. 多角形の生成方法 ? ある２点を選び、何角形を作るか決める ? ２点から中心点を決定し、点が存在するべき場所を算出 する。 ? 点が存在するべき場所から、もっとも近い点を選ぶ。 ? その点の集合が、多角形の条件を満たしていればＯＫ ? 実行時間に余裕があるsmall caseでは、もうちょっときち んと探索を行う。
- 7. 多角形の生成方法 ? ２点を選ぶ ? 工夫するポイント ? 長い辺を優先的 に選ぶ ? 長い辺の方が生 成確率が上がる
- 8. 多角形の生成方法 ? 中心点の設定 ? 工夫するポイント ? Small caseで、中心 点をずらしてあげる
- 9. 多角形の生成方法 ? 点の場所予測 ? 工夫するポイント ? Small caseでは、円 を少しずつずらして あげる
- 10. 多角形の生成方法 ? 一番近い点を 取っていく ? 工夫するポイント ? 適当なグリッドに 区切って、探索範 囲を狭める！ ? sideDiffの制約を 満たせなくなった ら即break
- 11. 厳密な探索をしない理由 ? radiiDiffの制約の問題 ? 予測中心点が動いてしまう ? 枝刈り誤爆が発生しやすい ? 計算時間の問題 ? 動的計画法を用いても、速度的に話にならない ? 最良１ケースのみで探索→失敗時戻る 程度が限界？ ? 実際は、前述の説明よりほんの少しきちんと探索 ? 非常に緩やかな枝刈りを用いて、生成確率を向上
- 12. 多角形の生成基準 ? 出来るだけ頂点数の多い多角形を作りたい！ ? 頂点数を増やせば増やすほど、生成確率は落ちる。 ? 各頂点が、何角形まで作成可能かを予測する関数 を作る
- 13. 予測関数の作成 ? 各々の辺に対して、「最大何角形まで作れるか」の予測 を行う！ ? 使う指標は以下の２つ ? 基準とする円が、正方形の中に納まっているか？ ? 多角形の生成可能確率が十分に高いか？
- 14. 予測関数その１：枠内に収まるか？ ? 左図角θを決めると、 円が決定される。 ? 枠に収まる範囲は、 容易に決定できる。 ? 数式は割愛するが、 Asin等を使えばOK ? 若干余裕を持たせ てあげるべき
- 15. 予測関数その２：生成確率は十分高い？ ? sideDiffの制約を 青の円で表示 ? radiiDiffの制約を 赤の円で表示 ? 上記より、斜線部 が条件を満たす 箇所 ? これを長方形近 似する
- 16. 予測関数その２：生成確率は十分高い？ ? 長方形の面積を 求めよう！ ? 赤辺は、 ? 半径*radiiDiff/100 ? 青辺は、 ? 辺長*sideDiff/100 ? よって、この積が 面積の近似値
- 17. 予測関数その２：生成確率は十分高い？ ? 一辺の長さをd、生成目標頂点数をtとする。 ? 前述斜線部の面積の近似値Sは、 ? ? = ?2??? ??? sin ? ? ?10000 ただしsD=sideDiff rd=radiiDiff ? 適当な１点が、面積S内に入っている確率p1は、 ? ?1 = ? 7002 = ?2??? ??? sin ? ? ?7 ?108 ? 頂点数nとして、面積S内に点が１つ以上ある確率p2は、 ? ?2 = 1 ? 1 ? ?1 ? = 1 ? 1 ? ?2??? ??? sin ? ? ?7 ?108 ?
- 18. 予測関数その２：生成確率は十分高い？ ? これが全ての頂点に対して見つかる確率p3は、 ? ?3 = ?2 ??2 = 1 ? 1 ? ?2??? ??? sin ? ? ?7 ?108 ? ??2 ? このP3が、確率p以上になるtの境界が求まれば、生成 確率p以上の多角形のみ探索することが出来る。 ? これは、辺の長さdのみに依存する。 ? tの上限は、妥当なpを設定した時、高々50程度 ? よって、二分探索等で適当に範囲を求めれば十分。
- 19. 参考画像：大きなケース ? 頂点数：4654 ? SideDiff : 20 ? RadiiDiff : 18
- 20. 参考画像：大きなケース ? Score: 65554 ? Score/頂点:14.0855 ? 32角形 1個 31角形 2個 ? 30角形 1個 29角形 3個 ? 28角形 3個 27角形 1個 ? 26角形 8個 25角形 5個 ? 24角形 7個 23角形 5個 ? 22角形 7個 21角形 8個 ? 20角形 5個 19角形 5個 ? 18角形 8個 17角形 14個 ? 16角形 4個 15角形 10個 ? 14角形 8個 13角形 17個 ? 12角形 18個 11角形 15個 ? 10角形 18個 9角形 18個 ? 8角形 30個 7角形 36個 ? 6角形 29個 5角形 43個 ? 4角形 109個 3角形 54個