2019-06-21

ABC130 F問題：Minimum Bounding Box

問題. Minimum Bounding Box

平面上に $n$ 個の点がある．時刻 0 のときの $i$ 番目の点の座標を $(x_i, y_i)$ とする．各点は時刻 0 から秒速 1 で決まった方向に同時に動き出す．ただし，動く方向は軸並行に左右上下のいずれか一方向のみである（または動かない）．ある時刻での各点の $x$ 座標と $y$ 座標の最小値と最大値をそれぞれ $x_{\min}, x_{\max}, y_{\min}, y_{\max}$ としたとき，そのときの値を $(x_{\max} - x_{\min}) \times (y_{\max} - y_{\min})$ とする．この値としてとりうる最小値を求めよ．

制約： $1 \le N \le 10^5$ ，　 $-10^8 \le x_i, y_i \le 10^8$

2019-06-21

ABC130 E問題：Common Subsequence

競プロ競プロ-AtCoder アルゴリズムアルゴリズム-動的計画法

問題. Common Subsequence

長さ $N$ の整数列 $S$ と長さ $M$ の整数列 $T$ が与えられる． $S$ と $T$ の等しい部分列が何通りあるか求めよ．

制約： $1 \le N, M \le 2 \times 10^3$ ，　 $S$ と $T$ の各要素は 1 以上 $10^5$ 以下

2019-06-20

ARC129 F問題：Takahashi's Basics in Education and Learning

競プロ競プロ-AtCoder アルゴリズムアルゴリズム-整数論アルゴリズム-冪乗法

問題. Takahashi's Basics in Education and Learning

初項 $A$ と公差 $B$ からなる長さ $L$ の等差数列 $s_0, s_1, \ldots, s_{L - 1}$ がある．この等差数列を一列に並べたものをひとつの整数として見たときの $M$ による剰余を答えよ．

制約： $1 \le L, A, B < 10^{18}$ ，　 $2 \le M \le 10^9$ ，　等差数列の要素はすべて $10^{18}$ 未満

2019-06-19

ABC129 E問題：Sum Equals Xor

競プロ競プロ-AtCoder アルゴリズムアルゴリズム-数え上げアルゴリズム-動的計画法

問題. Sum Equals Xor

正整数 $L$ が二進表記で与えられる．次の条件を満たす非負整数の対 $(a, b)$ がいくつあるか求めよ．
　・ $a + b \le L$
　・ $a \oplus b = a + b$

制約： $1 \le L \le 2^{100,001}$ （ $L$ の先頭文字は必ず 1 ）

2019-06-12

点と超平面の間の距離

数学数学-幾何

$n$ 次元ユークリッド空間上の点と超平面の間の距離を求める．

点 $x' \in \mathbb{R}^n$ と超平面 $H = \{x \in \mathbb{R}^n \mid a^{\mathrm{T}} x + b = 0 \}$ との間のハウスドルフ距離は，
　　 $d_H(x', H) = \frac{\left| a^{\mathrm{T}} x' + b \right|}{ \| a \| }$
である．

2019-06-10

MDwiki

環境環境-ツール

MDwiki とは Timo Dörr さんによって作成された CMS/Wiki です．
注意：MDwiki は Archived されています

2019-06-02

M-SOLUTIONS プロコンオープン D問題：Maximum Sum of Minimum

競プロ競プロ-AtCoder アルゴリズムアルゴリズム-グラフ

問題. Maximum Sum of Minimum

$N$ 頂点からなる木 $T$ と，正の整数 $c_1, c_2, \ldots, c_N$ が与えられる．全単射 $f \colon V(T) \to \{c_1, c_2, \ldots, c_N\}$ のスコアを各辺 $u v \in E(T)$ に対して $\min\{ f(u), f(v)\}$ の総和とする．スコアを最大とする全単射を求めよ．

制約： $1 \le N \le 10,000$ ，　 $1 \le c_i \le 10^5$