2023年3月24日，筑波大学で博士（工学）を取得しました． 社会人早期修了というシステムによって，会社で書いた論文を業績として使うことで1年で博士号を取ることができました． 少し珍しいパターンでの博士号取得だと思いますので，自分の備忘録も兼ねて体…
去年に続いて2022年の振り返りをします． 2022年の内に書く予定だったのに書ききれませんでした． 特に有益な情報はなさそうです． 仕事（研究） 社会人博士課程 競プロ その他 今年の目標の振り返りと来年の目標 面白かった本，面白かった映画 本 映画 仕事…
数学とかアルゴリズムの話をよく書いているこのブログだが，今回はそれらには全く関係ない，ビールに関するポエムを書く． 皆さんはアンテナアメリカを知っているか？ アンテナアメリカは株式会社ナガノトレーディングが運営している，アメリカのクラフトビ…
もう年末ということで，2021年に自分に起きたことを振り返ってみようという日記です． 今まで数学的な内容の記事ばかり書いていましたが，たまにはこういうのも良いということでひとつ． 大して有益な情報はありません． 競プロ アルゴリズムコンテスト ヒュ…
皆さん，パラドックスは好きですか？僕は大好きです．高校生の時の愛読書の一つがウイリアム・パウンドストーンの「パラドックス大全」だったくらいです．パラドックスが提示する思考の迷路をうろうろして途方に暮れるのはとっても楽しいですね． 最近，ネッ…
輸送問題と呼ばれる問題があります． この問題は，普通は線形計画法やフローのアルゴリズムを使って解かれます． この記事では，この輸送問題を近似的に行列計算で解くアルゴリズム（エントロピー正則化 + Sinkhorn-Knopp アルゴリズム）を紹介します． 輸送…
ネットワークフロー好き好きマンとして，フローを布教したくなったので記事を書きました． ただし，フローの解説資料は既に素晴らしいものがたくさんあるので，今回は今まであまり焦点が当てられてこなかった部分を推して話をしたいと思います． テーマは，…
この間の opt (@opt_coder) さん作の yukicoder の問題 No.1172 Add Recursive Sequence - yukicoder において，imos 法を漸化式で表される数列の加算に一般化することが問われました． この一般化はパッと見何をしているか分かりにくいのですが，線形代数の…
前回の記事では，競プロ界隈における「燃やす埋める問題」と離散最適化のトピックである「劣モジュラ関数のグラフ表現可能性」の関係性について述べ，与えられた列モジュラ関数が最小カットを通して最小化できるための条件について説明しました． 今回の記事…
競プロ界隈でいわゆる「燃やす埋める問題」と呼ばれる問題群があります．（このネーミングが適切かどうかには賛否両論あるようですが，広く用いられているようなので本記事中では用います） それほど出題頻度は高くないようですが，知らないと解くのが難しい…
最近ネットワークフローにハマっている（？）ので，勉強したことを書きます． 一応競プロに役に立つ可能性がなくはないです． あと，簡単のために詳細な数学的議論を省略しているところがあります． TL;DR 最小費用流問題は一般化すると双対関係が綺麗に書け…
最近，最短路アルゴリズムについて新しく知ったことがあるのでメモ． 内容にそんなに自信はないので間違っているかも． グラフ 上の二点間の最短路問題と言えば 辺の長さが全て非負→Dijkstra法 負の長さの辺がある→Bellman-Ford法 というような使い分けを行…
