2019-07-09

ABC133 C問題：Remainder Minimization 2019

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

問題. Remainder Minimization 2019

非負整数 $L, R$ が与えられる． $\min_{L \le i < j \le R} \left( i \times j \bmod 2019 \right)$ を求めよ．

制約： $0 \le L < R \le 2 \times 10^9$

2019-06-30

ABC132 F問題：Small Products

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

問題. Small Products

正整数からなる長さ $K$ の数列で，隣り合うどの 2 要素の積も $N$ 以下となるものが何通りあるか求めよ．

制約： $1 \le N \le 10^9$ ，　 $2 \le K \le 100$

2019-06-30

ABC132 E問題：Hopscotch Addict

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

問題. Hopscotch Addict

有向グラフ $G = (V, A)$ と，頂点 $S, T \in V$ が与えられる． $S$ から $T$ への移動回数の最小値を求めよ．ただし，任意の頂点 $v$ からの 1 回の移動とは， $v$ から距離がちょうど 3 離れた頂点へ移動することである（弧重みは 1）．また， $S$ から $T$ へ移動することができないときは -1 を出力せよ．

制約： $2 \le N \le 10^5$ ，　 $0 \le M \le \min(10^5, N (N - 1))$ 　（ $N = |V|, M = |A|$ ）

2019-06-30

ABC132 D問題：Blue and Red Balls

競プロ競プロ-AtCoder アルゴリズムアルゴリズム-数え上げ

$K$ 個の青いボールと $N - K$ 個の赤いボールがある．この $N$ 個のボールを一列に並べたものを $b$ としたとき， $b$ から青いボールが無くなるまで次の操作を行う． $b$ の中にある連続する青いボールの部分列を任意に取り除き，取り除いてできた列を $b$ とする． $b$ に対する任意の操作の中で操作回数の最小値を $b$ の最小操作回数と呼ぶ．任意の $1 \le i \le K$ に対して最小操作回数が $i$ となるボールの並べ方が何通りあるかを求めよ．

制約： $1 \le K \le N \le 2,000$

2019-06-25

ARC055 B問題：せんべい

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

問題. せんべい

1 から $N$ までの番号が付けられた $N$ 枚のせんべいが一様ランダムに並べられている．このせんべいを先頭から順番に食べるかどうかを選び最大で $K$ 枚を食べる． $i$ 番目のせんべいを食べるかどうか決めるときに， $i$ 番目のせんべいの番号は分からないが， $i$ 番目のせんべいを含む今まで見てきたすべてのせんべいの番号の大小関係は分かる．番号が $N$ のせんべいを食べた確率が最大となる選び方をしたときの確率を答えよ．

制約： $1 \le K \le N \le 1,000$

2019-06-23

ABC131 F問題：Must Be Rectangular!

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

問題. Must Be Rectangular!

平面上に $n$ 個の点があり， $i$ 番目の点の座標は $(x_i, y_i)$ である． $(a, b), (a, d), (c, b), (c, d)$ 　 $(a \neq c \wedge b \neq d)$ のうち3点が存在するときに残りの1箇所に点を追加するという操作を行う．最大でこの操作を何回行えるかを求めよ．