Learning Algorithms

アルゴリズムの勉強メモ

アルゴリズム

彩色数を求めるアルゴリズム

はじめに 彩色数を求めるアルゴリズムについて書きました。English version is available here. 彩色数とは 彩色数(chromatic number)とは、無向グラフにおいて、辺で繋がれた頂点同士が、互いに異なる色でなければいけないという制約のもとで、すべての頂点…

Hirschberg's Algorithmについて

はじめに $Hirschberg's\ Algorithm$ に関する解説を丁寧に書きました。English version is available here. 問題 まず次の問題をご覧くださいCS Academy概要:各マスに数字が書かれたグリッドが与えられ、そのグリッド上で左上のマスから右下のマスまで最短…

重心分解による分割統治法の一般形について

追記 2018/01/22 ・重心を求めるアルゴリズムを変更して高速化しました。 ・最後に実践的な例題を置きました。 はじめに アリ本に載っているものよりも、(個人的に)わかりやすく整理した重心分解による分割統治法の一般形について書きます(アリ本でばっち…

お寿司をできるだけたくさん食べるアルゴリズム

お寿司をできるだけたくさん食べるアルゴリズム みなさんお寿司は好きですか? 僕は好きです。というわけで、できるだけたくさんの種類のお寿司を食べるためのアルゴリズムについて書きます。さて、早速たくさん食べる方法について考えていきます。まずお寿…

木の重心列挙アルゴリズム

木の重心列挙アルゴリズム English version is available here.木の重心を列挙するアルゴリズムです。重心の性質をよく知っている方にとっては自明な木$dp$を実装するだけだと思います。これで $verify$ しています。計算量は $O(n)$ です。中のアルゴリズム…

木の直径のパスを一つ挙げるライブラリ

木の直径のパスを一つ挙げるライブラリ 木の直径のパスを一つ挙げるやつをライブラリ化しました。これを解いている時に必要になって、自明なのに妙に実装に時間がかかったので作りました。この問題でverify済みです。中のアルゴリズムは非常に簡単で、次の通…

平面上のロシアゲー(構築ゲー)を解くためのそこそこ一般的なテクについて

平面上のロシアゲー(構築ゲー)を解くためのそこそこ一般的なテクについて この記事はCompetitive Programming Advent Calendar 2017の12月13日の記事です。 ロシアゲーとは 「ある条件を満たすものを何でもいいから一つ出力しなさい」という形式の問題のこ…

競プロにおけるオイラー路とその応用について

この記事はCompetitive Programming Advent Calendar 2017の12月8日の記事です。 競プロにおけるオイラー路とその応用について 目次 ・はじめに ・オイラー路とは? ・無向グラフのオイラー路 ・有向グラフのオイラー路 ・無向オイラー路の構築 ・有向オイラ…

Inverse of factorialsをO(N)で列挙する

Inverse of factorialsをO(N)で列挙する はじめに 素数 $p$ を法として、 $n$ 以下の階乗の逆元を $O(n)$ で列挙しちゃおうというアレを知っていますか?(僕は知りませんでした。。。)(コードが読みにくくなる割には)そんなに高速になるわけではないため…