ゲーム理論の基礎と応用：ニムゲームからスプラグ-グリニー定理まで
ニムゲームの基本構造
ニムゲームは組合せゲーム（Combinatorial Game）の代表例であり、両者交互に行動し、最終的に移動できない者が敗れるというルールを持つ。各ターンで、プレイヤーは任意の山から1個以上の石を取り除くことができる。
重要な性質として、ある状態 (a₁, a₂, ..., aₙ) がP-ポジション（後手必勝）であるための条件は、すべての山の石の数のビット単位 ...
9月22日 07:43 投稿
Codeforces 近況コンテストにおける高度なアルゴリズム技法と実装パターン
区間交差関係に基づく最小全域木構築
与えられた区間集合において、交差する区間同士を結ぶ辺の重みを権重の差とし、生成されるグラフの最小全域木を求める問題。辺を全列挙すると計算量が爆発するため、幾何学的性質と貪欲戦略を組み合わせる。権重が小さい区間から順にアクティブな集合に追加し、各区間の挿入・削除タイミング（スライン法）において、権重でソートされ ...
6月24日 18:37 投稿