nkhrlab~

140字超の記事

アルゴリズム

ドミノを用いたパズルの自動生成

概要 ドミノはトランプと同じくそれひとつでいろいろなゲームを楽しむことができる玩具のひとつである.本記事では,ドミノを用いたパズルの自動生成の手法とサンプルコードを紹介する. 準備 1セットのドミノは28枚の牌からなる*1.それぞれの牌は2つの領域…

勝敗グラフと有向閉路の存在性

勝敗グラフ 本記事における勝敗グラフを次のように定義する.勝敗グラフは有向グラフの一種である. 頂点集合,辺集合を持つ有向グラフを考える. に対しを次のように定義する. が次に示す条件を満たすとき,かつその場合に限り,は勝敗グラフである. 本記…

AtCoder に登録したら解くべき精選過去問 10 問を PostgreSQL で解いてみた

はじめに この記事は,次のQiita記事に「過去問精選 10 問!」として示されている10問の問題をPostgreSQLを用いて解いたものである. qiita.comまた,AtCoderではこれらの問題をまとめた初心者向け問題集として「AtCoder Beginners Selection」を用意してい…

無向グラフに関する頂点数・染色数制約下での辺数の最大化

この記事で扱う問い 無向グラフの染色数をと表すとき,グラフに対する頂点数についての制約および染色数についての制約を同時に満たす無向グラフのうちで,辺数が最大であるものはいかなるグラフであろうか.ただし, 特殊なに対する答え まず,特殊なについ…