充足可能性問題とは? 充足可能性問題(satisfiability problem, SAT)は、一つの命題論理式が与えられたとき、それに含まれる変数の値を偽 (False) あるいは真 (True) にうまく定めること・・・
充足可能性問題とは? 充足可能性問題(satisfiability problem, SAT)は、一つの命題論理式が与えられたとき、それに含まれる変数の値を偽 (False) あるいは真 (True) にうまく定めること・・・
強連結成分分解とは? 強連結成分(SCC, Strongly Connected Component)とは、有向グラフにおいて互いに行き来が可能な頂点の集合のことです。強連結成分分解とは、強連結成分を1つの頂点にまとめる・・・
Nim は、2人でおこなうレクリエーション数学ゲーム(組合せゲーム)の一つです。歴史的には、最初に必勝法が数学的に解決したゲームです。双方が最善をつくす場合、どちらが勝つかは最初の個数の組で決まります。 以下のようなゲー・・・
今回は石取りゲームの必勝法を考えます。 K – Stones K – Stones N 個の正整数からなる集合 A = { a_1, a_2, …, a_N } があります。 最初に、K 個の石か・・・
包除原理とは数え上げ組合せ論における基本的な結果のひとつです。 2つの有限集合 A と B の和集合に属する元の数を計算するには、まずそれぞれに属する元の数 |A| と |B| を足しあわせた後、それらの共通部分に属する・・・
整数 A を M で割った余りと、整数 B を M で割った余りが等しい場合、「M を法として A と B は合同である」といい A ≡ B(mod M)と表されます。 mod の逆元 M と互いに素である整数 A に対・・・
行列を用いて連立一次方程式を解く方法は 掃き出し法で連立一次方程式を解く 逆行列と行列式を求める でやりました。 掃き出し法(ガウス・ジョルダン Gauss-Jordan 法) 連立方程式を 行列 と 列ベクトル で表し・・・
ひとりで勝手にはじめた蟻本読書会 平面走査 計算幾何 蟻本読書会 の続きです。 凸包とグラハムスキャン Beauty Contest (POJ No.2187) 二次元平面に N 箇所の牧場があります。i 番目の牧場は(・・・
ひとりで勝手にはじめた蟻本読書会 ギリギリを考える計算幾何 蟻本読書会 の続きです。 Coneology (POJ No.2932) Coneology (POJ No.2932) 2次元平面上にN個の円があります。i番・・・
ひとりで勝手にはじめた蟻本読書会 平面・空間を扱う計算幾何 蟻本読書会 の続きです。 選択肢が無限にある最適化問題の場合、ギリギリを考えることで候補を有限個に絞るという方法があります。 White Bird (AOJ 2・・・