几何コンテスト2013
- 2. Problem ?A 役?人 原案 : ?@not_?522 テスト : ?@not_?522, ?@pepsin_?amylase 解説 : ?@pepsin_?amylase 2013年 6月 30日 幾何コンテスト ?2013
- 3. 問題概要 ?? xy平?面上に300頂点が与えられる ?? 任意の3点は同?一直線上にない ?? 共有点を持たないように出来るだけ多くの 三?角形を作れ 2013年 6月 30日 幾何コンテスト ?2013
- 4. 問題概要 ?? xy平?面上に300頂点が与えられる ?? 任意の3点は同?一直線上にない ?? 共有点を持たないように出来るだけ多くの 三?角形を作れ ?? この制約が重要な役割を果たします 2013年 6月 30日 幾何コンテスト ?2013
- 5. 解法1 ?? x 座標でソートし?小さい順に三?角形を作る ?? x 座標が同じ点は2個以下なのでうまくいき ます 2013年 6月 30日 幾何コンテスト ?2013
- 6. 解法1 ?動作の様?子 2013年 6月 30日 幾何コンテスト ?2013
- 7. 解法1 ?動作の様?子 2013年 6月 30日 幾何コンテスト ?2013
- 8. 解法1 ?動作の様?子 2013年 6月 30日 幾何コンテスト ?2013
- 9. 解法2 ?? 頂点の凸包を取り、そこから辺を?一つ選ぶ ?? 凸包を取ると頂点が辺の?片側に寄る ?? 辺のどちらかの頂点を原点にとり、各頂点 の偏?角を考える ?? 偏?角が?一番?小さい頂点とはじめに選んだ辺 で三?角形を作る ?? これを100回繰り返す 2013年 6月 30日 幾何コンテスト ?2013
- 10. 解法2 ?動作の様?子 2013年 6月 30日 幾何コンテスト ?2013
- 11. 解法2 ?動作の様?子 この点からの偏?角を考える 2013年 6月 30日 幾何コンテスト ?2013
- 12. 解法2 ?動作の様?子 3頂点が同?一直線上にないので、 最?小偏?角の頂点はただひとつに決まる これが最?小偏?角の頂点 2013年 6月 30日 幾何コンテスト ?2013
- 13. 解法2 ?動作の様?子 2013年 6月 30日 幾何コンテスト ?2013
- 14. 回答状況 満点の?人数：88?人 最初に正の得点を得た提出 ?? evima（1分21秒, 1点） 最初に満点を得た提出 ?? semiexp（3分41秒） 2013年 6月 30日 幾何コンテスト ?2013
- 15. Problem ?B ?玉座の間 原案 : ?@not_?522 テスト : ?@not_?522, ?@pepsin_?amylase 解説 : ?@pepsin_?amylase 2013年 6月 30日 幾何コンテスト ?2013
- 16. 問題概要 ?? xy平?面上にn頂点が与えられる ?? y軸に関して線対称になるように点を動かし たい ?? 移動先は重複していてもよい ?? 移動距離離の総和を最?小化せよ 2013年 6月 30日 幾何コンテスト ?2013
- 17. 部分点 ?? (1) 50点 :n = 1 ?? (2) 50点 :n ≦ 10 ?? (3) 50点 :n ≦ 20 ?? (4) 50点 :n ≦ 100 2013年 6月 30日 幾何コンテスト ?2013
- 18. 解法1（50点） ?? 1頂点の場合はy軸に移動させるしかない ?? x座標の絶対値が答え 2013年 6月 30日 幾何コンテスト ?2013
- 19. 解法2（100点） ?? 対応させるペアの組み合わせをすべて試す ?? n! / 2(n/2) ≦ 113400通り 2013年 6月 30日 幾何コンテスト ?2013
- 20. 2頂点の組を対称にする ?? 各ペアを対称にするのに必要な移動距離離 ?? = ペアの?片?方をy軸反転させたあとで2点 を?一致させるのに必要な移動距離離 ?? = ペアの?片?方をy軸反転させたあとの2点間 の距離離 ?? もしくはそれぞれをy軸にのせるのに必要な 距離離の和 2013年 6月 30日 幾何コンテスト ?2013
- 21. 2頂点の組を対称にする ?赤実線 ?= 対称にするのに必要な距離離 ?青実線 = y軸に乗せるのに必要な距離離 2013年 6月 30日 幾何コンテスト ?2013
- 22. 解法3（150点） ?? すでに線対称になっている頂点集合を状態 としたbitDP ?? 2通りの遷移があるのに注意 ?? 2頂点をペアとして対称にする ?? 1頂点をy軸上に移動させる 2013年 6月 30日 幾何コンテスト ?2013
- 23. 解法4（200点） ?? この図をよく?見見ると…… 2013年 6月 30日 幾何コンテスト ?2013
- 24. 解法4（200点） ?? y軸に載せないほうが得する ? x 座標の符 号が異異なる a ?? ということがわかる ?? d < c, a < b から従う c d 2013年 6月 30日 幾何コンテスト ?2013 b
- 25. 解法4（200点） ?? x座標の符号が異異なるペアについてのみ、そ のペアを対称にするのに必要な距離離をコス トとする辺を張ったグラフを作る ?? これは?二部グラフになる ?? ?足りない側に ?y ?= ?0 ?の頂点を付け?足して 左右の頂点を同数にしておく ?? このようにして作ったグラフ上での最?小費 ?用完全マッチングとなる ?? ?二部グラフなので最?小費?用流流を流流す 2013年 6月 30日 幾何コンテスト ?2013
- 26. 回答状況 満点の?人数：26?人 最初に正の得点を得た提出 ?? kyuridenamida（3分6秒, 50点） 最初に満点を得た提出 ?? Navi（21分55秒） 2013年 6月 30日 幾何コンテスト ?2013
- 38. C（３） 凸包 ?点の集合を覆う最小の凸多角形 O(N log N)のアルゴリズムがある Andrew's monotone chainなど http://www.prefield.com/algorithm/geometry/convex_hull.html ?凸包作るのはO(NMlogN) 間に合う
- 43. C（４） 動的凸包 ?点の挿入をO(log N)でやる ならし計算量でOK ?計算幾何学では有名な問題 2 ?点の削除があってもO((log N) )らしい Overmars, M. H., van Leeuwen, J. (1981)
- 49. C 解答状況 正答数：３ ファーストアクセプト （３）uwi (0:32:14) （４）Navi (1:22:15)
- 60. D（４） 経路は３パターンしかない ?まっすぐゴールまで進む 呪いに触れずにすむならこれが最短 ?呪いの上側を通る ?呪いの下側を通る 以降では魔女を原点とし、スタート地点が y軸上にあるとする
- 61. D（４） まっすぐゴールまで進む 呪いと接触しないかの判定が必要 →２次方程式を解くだけ 円の方程式：x2+y2=(Wr + t Wv)2 位置：(Sx + t dx, t dy) これが0 < t < |S-G|/Vに解を持つか判定する
- 66. D（４） 呪いの周囲を通る⑤ 全体の長さを求める 一見、対数螺旋の長さを求める必要がありそう →実は要らない 対数螺旋に触れた点、離れた点がわかればWv が一定なのでかかった時間はすぐに求められる
- 67. D 解答状況 正答数：０ ファーストアクセプト （１）uwi (1:24:39) （２）sune2 (2:46:25)