2021-09-06から1日間の記事一覧
何の話かというと atcoder.jpこの問題をネタに L1 ノルムの最小化の話をします。 L2 ノルムの最小化 平面上の点の集合 に対して、各点との「ユークリッド距離の2乗の話」 を最小にする点 は、 の条件から、与えられた点の集合の重心に一致することがわかりま…
何の話かというと atcoder.jp上記の問題をネタに、Union-find の解説と、Union-find の特徴を利用した別解を紹介します。 Union-find Union-find の基本的な実装はこちらになります。 group_parent = defaultdict(lambda:None) def create_group(x): global …