$\newcommand{\set}[1]{\{#1\}}$ $\newcommand{\inset}[2]{\{#1 \mid #2\}}$ $\newcommand{\name}[1]{\emph{#1}}$ $\newcommand{\size}[2][]{\left| #2^{#1} \right|}$ $\newcommand{\sig}[1]{\mathcal{#1}}$

近似アルゴリズムのお話し: Baker's technique

今年もデータ構造とアルゴリズムアドベントカレンダーの季節になってきました.これはカレンダー12日目の記事ですね.個人的な話ですが,去年度にようやく長い長い学生生活を終えたので,今年は隣の分野くらいのことをちゃんと勉強してみたいなぁと思い,い…

オレンジグラフの別解(TLEしました.)

昔昔にオレンジグラフという問題が出ていましたね. atcoder.jp これはどういう問題かというと,グラフが与えられるので,極大な部分二部グラフ(これ以上二部性を保証しながら辺追加ができない部分二部グラフ)の列挙が想定解法なのですが,計算時間が $O(m…

辞書順幅優先探索Lex BFS(Chordal Graph 5回)

この記事はデータ構造とアルゴリズムアドベントカレンダー 2018の19日目の記事です. qiita.com とりあえず懺悔します.遅れて申し訳ありません. データ構造とアルゴリズムアドベントカレンダーで列挙とかの話をしようかなぁとか思ったのですが,書くのが大…

木の同型性判定のお話

この記事は文字列アドベントカレンダー5日目の記事です. qiita.com はじめに 文字列Advent Calendarと言いつつ,木について書いていこうかなと思います. まあ,文字列ガチ勢から見れば,根付き木は実質文字列なので,このCalendarで書いてもみんな喜んでく…

Chordal Graph: Maximum Cardinality Search

今回はグラフの性質のお話ではなくPEOを求めるためのアルゴリズムのお話をします. MCSとLex BFSというアルゴリズムのお話をします. chordal graphの性質についてはこの2つのアルゴリズムを説明した後にもまだまだ書きます. 今回は長くなるので,2回に分け…

Chordal Graph: Perfect elimination ordering

3回目のChordal Graph回です. 知識的にストックがあるのと,始めたばかりでやる気があるので,更新ペースがめちゃくちゃ早いです. 今回はPerfect elimination orderingについて説明します. Perfect elimination ordering (PEO) もchordal graphの重要で面…

Chordal Graph: Simplicial vertex

なんか意外に反響があった(アクセスログを見ていたらみんなが見ていてくれた)のでやる気を出したのと,少し今回の内容が簡単だったのもあって が〜っと書いてしまいました.2回目のChordal Graph回です. 今回は次回にやる予定のPerfect elimination order…

Chordal Graph: Minimal vertex separators

chocobaby-aporo.hatenablog.com Chordal Graph回の第一回目です.今回はMinimal vertex separatorsを紹介します. Minimal vertex separators まず,$G = (V, E)$中の頂点集合$S \subseteq V$が,vertex separator (separator)とは 次のような2頂点$u, v$が…

Chordal Graph

最近Chordal Graphがマイブームです. このシリーズの記事でわからないところやこれ間違っているぞっというのがあったら Twitterで教えてくれると僕が喜びます. Twitter ID: kazu0x17 Chordal Graphとは Chordal Graphとは任意の長さ4以上のサイクルに対し…

CodeFestival2016本戦の問題

この前Code Festival2016に行ってきました.問題はこんな感じでした. A問題 Where's sunuke まあ,A問題なのでやるだけ問題です. #include<iostream> using namespace std; int main(){ int h, w; std::cin >> h >> w; string s; for (int i = 0; i < h; i++) { for </iostream>…

ビームスタックサーチ

この前,ビームサーチを書いてみたので,今度はビームスタックサーチを書いてみました.この辺のサイトを参考に勉強しました. chokudaiサーチのメモ このサイトに載っているchokudaiさんのスライドが(ビームサーチをわかっている人なら)結構わかりやすい…

Code Festival 2016に参加しました

今年もCode Festivalを開催していただけて(しかも,本戦まで行けて)本当に楽しかったです.問題セットも良問ぞろいでした.下の方に今回解いた問題セットがあるのですが,どのコンテストでも1問以上はこの問題考えた人頭いいなと思う問題があってすごかっ…

初めての機械学習

なんやかんやあって初めて機械学習のアルゴリズムを実装しました.機械学習アルゴリズムの実装といっても大したことなくて,PRLMという教科書の最初にある多項式フィッティングというものを実装してみました.点が$N$点与えられるので誤差関数$E(\vec{w})$を…

ビームサーチ

研究室の後輩がマラソンに出るというので一緒に参加してみようかと思いました.ただ,まだ運営がvisualizerを用意してくれないので,とりあえず練習のため,ビームサーチを実装してみました.ビームサーチは名前は聞いたことがあるけどよくわからないアルゴ…

マークダウンでtexマクロを定義したい

最近マークダウンの書き方を少し覚えて,メモをとるのにマークダウンを使い始めました.基本ペンで文字を書くのを面倒臭がるのですが,PCでメモを取るのは苦じゃないので,マークダウンを使ってメモを取ることにしました. でも,メモとるのに結構数学の記法…