何の話かと言うと atcoder.jp上記の問題について、AVL 木（ソート済みのリストに対して、ソートを保った挿入・削除を で実行できるデータ構造）を用いた別解を紹介します。 再帰処理による解法 まずは直感的にわかりやすい再帰的な解法を考えます。与えられ…

何の話かというと atcoder.jp上記の問題の別解です。公式解説 では、身長と体重を 2 次元にプロットして、身長と体重を対称に扱う解法が示されています。あえてこれらを非対称に扱うことも可能です。 身長だけの場合 仮に、身長についてだけ考えればよいとす…

何の話かというと atcoder.jp上記の問題は、公式解説にもあるように、具体例を試しながら隠された規則性を発見する必要があります。どのような試行錯誤で、正解に至れるのか、一例を紹介します。 まずはしらみつぶし まずは、しらみつぶしで、文字列が変化す…

何の話かというと atcoder.jp上記の問題をネタに「キューを用いた全件探索」の話をします。 キューを用いた全件探索 enakai00.hatenablog.com上記の記事では、キューを用いて木構造データを探索するという話をしています。木構造データに限らず、複数の選択…

何の話かというと atcoder.jp上記の問題をネタに、「極端に小さな制約条件に注目する」という話をします。まぁ、下記のネタと似たような話です。enakai00.hatenablog.com の場合 ポイントは、 という条件です。一般には、もっとたくさんの順列が選べるはずな…

何の話かというと 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 …