arc021_4
考えたこと
ほぼ最小な全域木を作れっていう奇妙な問題
点が5000あるので辺は10^7くらいある
ちょっと厳しいか。距離の計算に200掛かるし。
入力がランダムであることが保証されてるのが肝か
まず点をおよそ半分に分ける
一軸に注目して正負で分ければ良い
辺は1/4になるのでクラスカル法のコストは半分になる
分けたものをつなぐコストが、最良の辺を見つけようとすると高いけど、これは適当につないで大丈夫、最良の場合と比べて高々2しか悪くない
実際には次元の呪いでほとんどすべての点の距離が1付近
半分で間に合うようになるのかはよくわからない
間に合わないならもっと細かく割る必要がある
サンプルの最小スコアから判断して、16個に割って適当につないでも大丈夫
公式解説
200次元なので200個に割ってる
それをやって最適解の1.01倍に収まることの証明はしないのか…
Related Pages
- →盲点×triz×トップダウンとボトムアップ×盲点カード候補×まだ絵のない盲点カード×失敗確率が高いが平均的に良い×バラツキが多い方がよいとき×円であるという思い込み×量が減らなくても割合は減る×直交しない2軸×湖にコップ一杯の水を入れる×インタラクションの属性×対立しているものを分割する×上が単一という思い込み×バーベル×解が一つとは限らない×大きな石だけが水面から顔を出す×トートバッグ×二人が違うことを言う絵のシリーズ×二人が違うことを言う絵のシリーズを盲点カードに追加するかどうか？×無味乾燥×(6.3.1.1)_誰が顧客かわからなければ、何が品質かもわからない×用途が明確になってからふるいわけ×ネットワーク構造×ツリーとリゾーム×知識のツリーではなく知識のリゾーム×「xである」と「xでない」が両立する×家族的類似性×妥協の方法は複数ある×良いものを移動させる×要素ではなく集合×集合ではなく軸×対立は一つだけではない×描きやすい絵のバイアス×最速のコースは最速ではない×片方向ではなく両方向×観測範囲の問題×誤った二分法×無味乾燥ページ×効果の有無×「なぜ」は曖昧×大小関係が存在しない×次元の呪い×イコールでないものを同一視し、差の拡大によって同一視できなくなる×円柱は円にも四角にも見えるが、円でも四角でもない×自分を自分の一部に使う×知識の少ない人からでも学ぶことができる×無の場所×同じものに属する違うもの×対称性×黄金比×陰陽太極図×弁証法×2015×螺旋階段×逆に進むがゴールは同じ×一つでも二つでもある×降りるために登らなければならない×別の世界で解決する×「同じ」と「違う」は両立する→
- →次元の呪い×高次元空間において正規分布はほぼ超球面上の一様分布×悲観的な勘違い×利用と探索のトレードオフ×c3:_computer_created_cats×ベルヌーイ分布×トンプソンサンプリング×強化学習×トンプソンサンプリング採用の流れ×良いの定義→
- →chokudai×貪欲法の証明パターン×選択肢が少ない方から貪欲×マトロイド×クラスカル法×区間スケジューリング×交換しても悪化しない×アルゴリズムとデータ構造×区間はマトロイドではない×abc076b×現在が良いほど未来も良い×poj3617×poj3069×ダイクストラ法×agc009a×arc111×abc187×arc110c×一回り小さい同じ形の問題×agc049b×abc103d×abc023d×和の比率の最大化×単位時間ジョブスケジューリング問題×乱択＋貪欲×abc171_f×離散凸性→
- →オイラー路×グリッド上の幅優先探索×ハンガリアン法×二部グラフの最大マッチング×二重辺連結成分分解×二重頂点連結成分分解×全点対間最短路×単一始点最短路×強連結成分分解×彩色数×最大クリーク×最大流×最大独立集合×最小全域有向木×最小全域木×最小流量制限付き最大流×最小費用流×橋/関節点×bit×binary-trie×convex-hull-trick-add-monotone×li-chao-tree×link-cut木_部分木クエリ×link-cut木×ウェーブレット行列×スパーステーブル×スライド区間の昇順k個の和×セグメント木×トライ木×マージ可能ヒープ×列の平方分割×平衡二分探索木×永続配列×素集合データ構造×unionfind×ローリングハッシュ×接尾辞配列×最長共通接頭辞×最長回文×回文×複数文字列検索×hl分解×全方位木dp×最小共通祖先×木の直径×木の重心分解×根付き木に変換×mod-pow×オイラーのφ関数×オイラーのφ関数テーブル×ベル数×ラグランジュ補間×二項係数×二項係数テーブル×任意mod畳み込み×分割数×分割数テーブル×商列挙×形式的冪級数×形式的べき級数×拡張ユークリッドの互除法×拡張ユークリッド互除法×第2種スターリング数×約数列挙×素因数分解×素数テーブル×素数判定×組合せ×行列演算×進数変換×階乗×離散対数問題×高速フーリエ変換×divide-and-conquer-optimization×monotone-minima×スライド最小値×一次元累積和×二次元累積和×個数制限付きナップサック×最大長方形×最適二分探索木×最長増加部分列×ダブリング×包除原理×燃やす埋める問題×燃やす埋める×牛ゲー×mo’s_algorithm×offline-dynamic-connectivity×座標圧縮×アルゴリズム→
- →アルゴリズム×蟻本×区間スケジューリング×二分探索木×unionfind×最短路問題×最小全域木×ユークリッドの互除法×ニ分探索×しゃくとり法×半分全列挙×座標圧縮×セグメント木×binary_lndexed_tree×バケット法×平方分割×ビットdp×bitdp×行列累乗×繰り返し二乗法×最大流×最小カット×二部マッチング×一般マッチング×マッチング×辺カバー×安定集合×点カバー×最小費用流×凸包×grundy数×強連結成分分解×2-sat×lca×ダブリング×接尾辞配列×sparse_table×rmq×atcoder→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]