メリークリスマス！ この記事は 物工/計数 Advent Calendar 2021 - Adventar の第25日目（最終日）の記事です。 前提知識 途中までは特に何の知識もなく読めます。後半は、ラグランジュの未定乗数法、および数理計画法の「相補性条件」の知識*1を前提としま…

この記事は物工・計数 Advent Calendar 2021 の第9日目の記事です。掲載が遅れてしまい、大変申し訳ございません。 本体は以下のpdfです。 drive.google.com この記事は 物工・計数 Advent Calendar 20211の第9 日目の記事です。掲載が遅れてしまい、大変申…

最近、オンラインの数学コンテストサイトであるOnlineMathContest(OMC)にハマっているのですが、始めたてのころ「幾何」がけっこう鬼門に感じました。 これは、大学入試や大学以降のカリキュラムで初等幾何をガッツリ扱う機会がそんなになく(個人差有)、解き…

前回の記事 の続きです。 前回は、最小全域木を求めるアルゴリズムとその「凸っぽさ」を定義し、離散版の凸関数を定義する必要性を述べた。ここからはいよいよその定義に入る。 3.「離散版」凸関数の定義（M凸関数） まず、ユークリッド空間で定義された関数…

☆この記事は、室田一雄・塩浦昭義『離散凸解析と最適化アルゴリズム』の1章及び8～13章をを参考にしていますが、証明の流れや定理の置き方などがかなり大幅に変わっています。誤りがあったらご報告いただけますと幸いです。 はじめに 重み付きグラフの全域木…

最近OMC ( onlinemathcontest.com ) にハマっている。超雑に言うと数学版AtCoderみたいな感じの数学コンテストサイトである。 OMCをやる上で一番の課題は幾何である。ベクトルや三角関数はまだしも、初等幾何は大学に入って以降はおろか大学入試ですらまとも…

貪欲法の証明は難しいことが多い。（学科のレポート課題で死んだトラウマ） こういうときは問題を解いた後丁寧に証明を書くことで、理解が深まるらしい。そこで、AtCoderで貪欲法の問題を解いたらたまに証明をなるべく丁寧に書いて載せてみようと思う。 今回…

表題のような諺があるらしい。 無い 1月の前半を鬱々とした気分*1で無駄にしてしまった*2ので、残り350日の目標を考えてみる。 50個用意してみます 凡例 難易度、重要度を【難易度/重要度】のフォーマットで書く。 定量的にできるものは極力する。 生活 目薬…