「ネタ」の記事一覧(2 / 12ページ目)

イベントソートとmultisetの代替策

AtCoderで苦戦中

イベントソートとはクエリをそれに関連する時刻や位置の順にソートして順番に処理する方法です。この方法を採用することで計算量を落とすことができる場合があります。 E – Roadwork E – Ro・・・

ABC 367 で大惨敗したので反省文(D問題まで)

AtCoderで苦戦中

一番簡単な A問題でまさかの WA(不正解:Wrong Answer)。ABC 367 で大惨敗したので反省文を書きます。D問題までです。 A – Shout Everyday A – Shout・・・

両端キューとスライド最小値(最大値) 蟻本読書会

蟻本読書会

両端キュー 両端キューまたはデックは、計算機科学における抽象データ型の1つで、先頭または末尾で要素を追加・削除できるキューです。 C – pushpush C – pushpush 長さ N の数・・・

最大長方形問題 蟻本読書会

蟻本読書会

ヒストグラム中の最大の長方形の面積は? 緑色の部分から最大の長方形を探す問題です。 これは最大長方形問題を解く 面積が最大の長方形を見つけるアルゴリズムでもやったように、スタックを利用してO(N)で解を求める方法がありま・・・

強連結成分分解をして充足可能性問題を解く

蟻本読書会

充足可能性問題とは? 充足可能性問題(satisfiability problem, SAT)は、一つの命題論理式が与えられたとき、それに含まれる変数の値を偽 (False) あるいは真 (True) にうまく定めること・・・

強連結成分分解 蟻本読書会

蟻本読書会

強連結成分分解とは? 強連結成分(SCC, Strongly Connected Component)とは、有向グラフにおいて互いに行き来が可能な頂点の集合のことです。強連結成分分解とは、強連結成分を1つの頂点にまとめる・・・

Nim と Grundy数 蟻本読書会

蟻本読書会

Nim は、2人でおこなうレクリエーション数学ゲーム(組合せゲーム)の一つです。歴史的には、最初に必勝法が数学的に解決したゲームです。双方が最善をつくす場合、どちらが勝つかは最初の個数の組で決まります。 以下のようなゲー・・・

ゲームの必勝法を考える 石取りゲーム 蟻本読書会

蟻本読書会

今回は石取りゲームの必勝法を考えます。 K – Stones K – Stones N 個の正整数からなる集合 A = { a_1, a_2, …, a_N } があります。 最初に、K 個の石か・・・

包除原理 蟻本読書会

蟻本読書会

包除原理とは数え上げ組合せ論における基本的な結果のひとつです。 2つの有限集合 A と B の和集合に属する元の数を計算するには、まずそれぞれに属する元の数 |A| と |B| を足しあわせた後、それらの共通部分に属する・・・

mod の逆元 累乗、階乗 蟻本読書会

蟻本読書会

整数 A を M で割った余りと、整数 B を M で割った余りが等しい場合、「M を法として A と B は合同である」といい A ≡ B(mod M)と表されます。 mod の逆元 M と互いに素である整数 A に対・・・