2019-07-21

ABC134 E問題：Sequence Decomposing

問題. Sequence Decomposing

長さ $N$ の非負整数列 $a = (a_1, a_2, \ldots, a_N)$ が与えれられる．各要素を色で塗ることを考える．ただし，同じ色で塗られたどの 2 要素 $a_i$ と $a_j \, (i < j)$ に対しても $a_i < a_j$ が成り立つように塗る．このような塗り方の中で使用した色の種類の最小値を答えよ．

制約： $1 \le N \le 10^5$ ，　 $0 \le a_i \le 10^9$

2019-07-20

ICPC国内予選2019 C問題：天秤

競プロ競プロ-ICPC アルゴリズムアルゴリズム-全探索

問題. 天秤

$n$ 個の薬品と $m$ 個の分銅の重さが与えられる． $i$ 番目の薬品の重さは $a_i$ で， $j$ 番目の分銅の重さは $w_j$ である．すべての薬品に対して天秤が釣り合うような分銅の置き方が存在するか判定せよ．ただし，釣り合わないときは任意の重さの分銅を 1 つだけ追加することができる．追加して釣り合うことができる分銅が複数ある場合は重さが最小のものを答えよ．

制約： $1 \le n \le 100$ ，　 $1 \le m \le 10$ ，　 $1 \le a_i \le 10^9$ ，　 $1 \le w_i \le 10^8$

2019-07-20

メモ：コマンド

環境環境-ツール

よく使うコマンドの雑多なメモ．

2019-07-15

ARC016 C問題：ソーシャルゲーム

競プロ競プロ-AtCoder アルゴリズムアルゴリズム-確率アルゴリズム-動的計画法アルゴリズム-ビット操作

$N$ 種類のカードと $M$ 種類のくじがある． $i$ 番目のくじを引くのにかかる費用は $c_i$ で，くじを引いたときに得られるカードの集合を $D_i \subseteq \{1, 2, \ldots, N\}$ とする．また， $i$ 番目のくじを引いて $j \in D_i$ 番目のカードが当たる確率を $p_{i, j}$ とする．
最適な戦略でくじを引いて全種類のカードをコンプリートするまでにかかる費用の期待値を答えよ．

制約： $1 \le N \le 10$ ，　 $1 \le M \le 4$ ，　 $1 \le c_i \le 3,000$

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 を出力せよ．