TCO2017R1
- 2. 問題概要 ? https://community.topcoder.com/longcontest/?module=ViewProblemStatem ent&rd=16903&pm=14565 ? 点がN個あり、辺の対応する頂 点?長さがM個与えられる。 ? 点を700x700の平面座標に配置 ? 各辺に対して、要求された長さ の何%か計算する ? 最小の% / 最大の%がスコア ? 最大スコアは1
- 3. これから使う用語集 ? 後の数式でつかいます。 ? ?? = ? ????????? (Time Rate) ? ?? = 0 … 1 (Random Number)
- 4. ランダムに点を置く ? 700 x 700の範囲に適当に 置く ? 整数じゃなくてdoubleで 管理 ? ?? = ?? ? 700, ?? ? 700
- 5. 点を動かす！ ? 比率が最大or最小の辺を 見つけて、その辺と平行 に点を動かす ? 動かし方は次ページ ? Field size内に収める ? 770 x 770 (min(E) = 1) ? 900 x 900 (else)
- 6. TargetPointの決め方 ? 適当に重み付けする。よく選ばれている頂点を動きづらくする。 ? ? ? ?′ : ? ? ?′ = ? ? 1.5? 1??? : ? ? 1.5? 1??? ? ? ? = Σ?=0 ??????? ? ?, ? ? 0.97 ??????? ?1 ? ? ?, ? = ?ターン目にその頂点を動かした？ ? 1: 0 Target Point Target Point A B A’
- 7. 点の動かし方 ? ? = ? + ?′ ? ? ? 1.5 ? 1 ? ?? ? ?? ? ? = ? + ?′ ? ? ? 1.5 ? 1 ? ?? ? ?? Target Point Target Point ?? = 0 ?? = 1 3 ?? = 2 3 A B A’ Move Range
- 8. （補足）大体の位置を合わせるには？ ? こんな感じのパターンでハマる ? エッジの左右の関係が正しくないとハマる ? 回避方法 ? 突き抜けるくらい激しく動かす！ ? 移動距離が大きくないとハマりっぱなしに ? 一番割合が悪い辺以外を無視する ? 今回だと、Aからの引力のみの影響を与える感じ ? 割合より距離を重視する（今回は不採用） ? 以上の理由で、激しく動かすのが良い A B C D A B C D 正しい配置 ハマった配置 1 1 1 1 0.8 0.8 2.0
- 9. （補足）点の動かし方の考え方 ? 大体の位置が正しくなっていれば、あとはちょっとずつ動かすだけ で、最適な配置にすることが出来る ? 序盤は大体の位置を合わせることを考える ? 出来るだけ激しく動かすことで、大体の位置を合わせる ? そのため、「スコアが上がらない移動は排除」みたいなことはしない ? 後に解説するハマりパターンが回避しづらい ? 10歩進んで8歩戻っても2歩進んでる、くらいの考え方 ? 後半は、前半で正しくした「大体の位置」を変えないように、細か く動かす ? 一気に動かすと、前後関係とかが変わって変なことになる。
- 10. （補足）ハマり回避→再ハマり の回避 ? 激しく動かすと、正しい場所から悪い場所へ自分で動かしてし まうことがある ? 正→誤にかかる移動割合は誤→正にかかる移動割合より小さい ? 正しい状態に近い方が、Target Pointへの距離の差が小さくなりがち ? それを利用すると、「ハマり回避は発生するが、再ハマりは発生しな い」という移動割合が大体の場合に存在する ? よって、「前半」「後半」で分けて考えていたが、少しずつ移 動距離を小さくする（前半から後半に近づける）ようにすれば、 正しい配置に近づけることが出来る ? この変化は時間で管理すれば良い
- 11. （補足）Field Sizeについて ? 元となる配置は700x700だが、誤差が含まれるため、最善配置 は700x700に収まるとは限らない ? そのため、大きく取るべきである ? だが、大きく取り過ぎると、整数座標に移す時に大きな誤差が 発生 ? 長さ1の辺が存在すると、最大割合が1以上に固定されてしまい顕著 ? 例えば1500x1500で最適解が作れたとして、整数座標に置換すると、 min=7/15,max=1となり、min/max=7/15程度のスコアしか得られない。 ? そのため、最短辺にもよるが、900x900程度にするのが良い ? 最短辺の長さが1のときは735*735あたりが良い ? 外側に膨れる点が増えるのを回避する意味もある
- 12. （補足）悪い辺の見つけ方 ? 基本的には、頂点が動くたびに、その周りの辺を全て優先度付 きキューに入れれば良い。 ? これだと実行速度が少し遅い ? 各頂点に対し、「最も大きい辺」「最も小さい辺」だけを優先 度付きキューに入れると少し改善される。 ? この時、「頂点が移動済みでスキップする時も、キューに追加しなお す」という操作をしないと、厳密性は失われる ? 厳密性が失われたままでも、考慮漏れの辺が発生する部分で、 結果的に強いランダム性が生まれるお陰で、あまり悪い結果に ならないため、そのままの実装にすると良い。
- 13. （補足）悪い辺の見つけ方２ ? あまりにも候補から遠い辺まで優先度付きキューに入れると遅 くなる。 ? 今までの最高値を用いて、1.02倍や0.98倍以内のものだけ保持 すれば良い。 ? 前述の理由で漏れが発生するアルゴリズムなので、キューが空になっ た時用の対策はきちんとする。
- 14. 点をswap ? 頻繁に選ばれる辺があれ ば、その頂点同士をswap する。 ? 単純な移動で発見しづらい ハマりパターンを回避する ? 「頻繁に選ばれる」の機 運は、10000 ?? 回
- 15. スコアが更新されなくなったら？ ? 5Nターン連続で最大スコ アが更新されなくなった らランダムに動かす ? 1/5の確率で最高スコアの 状態に戻す ? 移動距離は、x,y方向とも に min 400, 3500 ? Tr √N ? ??
- 16. 点の整数座標への配置 ? 適当に回転、縮小したもの を整数座標に当てはめる ? （実際は点を回すが、都合上、 周りの枠の方をまわしてま す） ? 縮小率は0.7~1倍 ? X,Yともに+3から-3まで調 べ、スコアが 最も高くなる ものを貪欲に選ぶ ? 仮min、仮maxを、±0.001く らいで最初に与えておくと良 い
- 17. 配置順序 ? Prim配置 ? 適当な１点を始点にする ? 始点を含むグループから最も距離の近い頂点を配置しグループに追加 ? 全ての点が入るまで繰り返し。非連結の場合は適当に追加 ? メリット：Nパターンの初期値がある。 ? Kruscal配置 ? 全ての頂点の、最も短い辺をキーにソート ? 最初の頂点から順番に整数座標に配置 ? メリット：高速化すると前計算がしやすい分実行が早い ? 両方つかいました。どっちが強いかは微妙過ぎて不明
- 18. 配置方法 ? これまで配置した点のみを比較する ? minR, maxRを用意し、minR/maxRが最終スコアになるように する ? 初期値は適当にこんな感じ ? minR = 配置前のminR – 0.01*Rn ? maxR= 配置前のmaxR +0.01*Rn ? この後、minR/maxRができるだけ大きくなるように、貪欲に 頂点を配置 ? 同じ値になる場合は、元の場所から近いところに配置
- 19. 多点スタート ? 適当なヒューリスティックアルゴリズムなので、時間を無限に 書けても良い解が出るとは限らない ? 初期値を変えてたくさん実行しよう！ ? 実行時間と精度を天秤にかけて適当に調整。 ? 今回は２回の実行にしました。