2025-12-08

強 NP 完全性とは？

この記事では、数値を含む判定問題に関係する 強 NP 完全性（強 NP 困難性）、弱 NP 完全性（弱 NP 困難性）、擬多項式時間アルゴリズム、弱多項式時間アルゴリズム、強多項式時間アルゴリズム について、次の論文の内容に沿って紹介する。

[1] M. R. Garey and D. S. Johnson. "Strong" NP-Completeness Results: Motivation, Examples, and Implications. J. ACM 25 (1978) pp. 499–508.
DOI:10.1145/322077.322090

2025-07-07

ICPC国内予選2025 G問題：面の数

競プロ-ICPC アルゴリズム-計算幾何

問題. 面の数

3次元ユークリッド空間中に 2 つの平面 $H_1: z = 1$ と $H_2: z = 2$ がある。
実数列 $d = (d_1, \ldots, d_n)$ と $d' = (d'_1, \ldots, d'_m)$ が与えられる。平面 $H_1, H_2$ に頂点の内角が原点から見て反時計周り順にそれぞれ $d, d'$ となるように凸多角形を構成して、それら2 つの凸多角形を含む $n + m$ 個の頂点からなる凸多面体の面の数としてあり得るものを全列挙せよ。

制約： $3 \le n, m \le 50$ 、 $10^{-9} \le d_i, d_i' < 180$

2025-04-11

ICPCアジア地区予選2016 K問題：Black and White Boxes

競プロ-ICPC アルゴリズム-ゲーム

大昔（2016年11月22日）に書いた記事が読めなくなっていたので移植しました。

1. 概要

これは Competitive Programming （その2） Advent Calendar 2016 - Adventar の22日目の記事です．

今年のACM-ICPC 2016アジア地区つくば大会のK問題で組合せゲーム理論に関する問題が出題されました．この問題を通して組合せゲーム理論の紹介をします ~~(考察が中途半端になってしまいました)~~．
2017年1月5日に追記・修正しました．

解説等は公開されています．

問題： Problem K : Black and White Boxes
判定データ： http://icpc.iisf.or.jp/past-icpc/regional2016/judge-data/K/
講評： http://icpc.iisf.or.jp/past-icpc/comments/2016.pdf#page=5
講評スライド： http://icpc.iisf.or.jp/past-icpc/comments/2016-slides.pdf#page=56
オンラインジャッジ : http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1377

natsugiriさんの分かりやすい解説があります．
ACM-ICPC 2016 Asia Tsukuba Regional, K 解法 - でも今日はSRMあるから

組合せゲーム理論の参考書として次の本を参考にしました．

組合せゲーム理論入門－勝利の方程式－

作者:M.H.Albert,R.J.Nowakowski,D.Wolfe
共立出版

Amazon

2024-05-03

The 47th World Championship ICPC I問題：Waterworld

競プロ-ICPC アルゴリズム-計算幾何

問題. Waterworld

下図のように表面が分割された球が与えられる。水平方向には高さが等しくなるように $n$ 分割されており、垂直方向には $m$ 等分されている。 $j$ ステップ目のときの領域 $A_i$ の表面積に占める水の量の割合をパーセント表記したものを $a_{i, j}$ とする。
球全体の表面積に占める水の量の割合をパーセント表記で答えよ。

制約： $2 \le n, m \le 1,000$ 、 $0 \le a_{i, j} \le 100$

2024-04-25

The 46th World Championship ICPC P問題：Turning Red

競プロ-ICPC

問題. Turning Red

$n$ 個のライトと $m$ 個のボタンがある。ライトは赤、緑、青の三色のいずれかで点灯する。ライトの色を変えることができるボタンを1回押すと、赤は緑に、緑は青に、青は赤に色を変える。
各ボタンに対して、そのボタンを押すと同時に色が変わるライトのリストが与えられる。ただし、各ライトに対して、そのライトの色を変えることができるボタンの数は高々 2 個である。また、あるライトの色を変えるボタンが与えられない場合もある。

初めに各ライトの色が与えられる。すべてのライトの色が赤色になるようなボタンの押し方で、押したボタンの回数の総和の最小値を答えよ。ただし、そのような押し方が無い場合は "impossible" と答えよ。

制約： $0 \le n \le 2 \cdot 10^5$ 、 $0 \le m \le 2 \cdot n$