問題 長さ $n$ の数列 $A$ が与えられる。任意の $j \neq i$ に対して $A _i$ が $A _ j$ で割り切れないような $i$ の個数を求めよ。（$n \leq 2 \times 10 ^ 5$, $A _ i \leq 10 ^ 6$）

問題 長さ $n$ の数列 $A$ と自然数 $s$ が与えられる。$\{ 1, \ldots , n \}$ の部分集合 $T$ について、$f(T)$ を $T$ の部分集合 $\{i _ 1, \ldots , i _ k\}$ で $A _ {i _ 1} + \cdots + A _ {i _ k} = s$ をみたすものの個数とするとき、すべての $T$ …

問題 $n$ 個の区間 $[A _ i, B _ i]$ が与えられる。各 $X _ i$ が $A _ i \leq X _i \leq B _ i$ を動くとき、$X _ 1, \ldots , X _ n$ の中央値として取りうる値は何個あるか。（$n \leq 2 \times 10 ^ 5$）

問題 自然数 $n$ を、相異なる数で素数の冪乗になっているようなものの積で表すとき、最大で何個の積で表すことができるか。（$n \leq 10 ^ {12}$）

問題 $a \times b$ の小数点以下を切り捨てたものを求めよ。（$a$ は $10 ^ {15}$ 以下の整数で、$b$ は小数第 $2$ 位まで与えられる。）

問題 $n$ 未満の自然数からなる集合の空でない部分集合で、$X _ i X _ j + Y _ i Y _ j = 0 \ (i \neq j)$ なる $i,j$ を同時に含まないものの個数を求めよ。（$n \leq 2 \times 10 ^ 5$）

概要 与えられた条件をみたす数列を全列挙したいとき、ジェネレーターを使うと簡単に書けて便利。

問題 ( と ) からなる $n$ 個の文字列 $S _ i$ を適当な順番に連結して、余りなくすべての括弧が閉じられている状態にできるか判定せよ。（$n\leq 10 ^ 6, \ \sum _ {i} | S _ i | \leq 10 ^ 6$）

問題 $i=1,\ldots,n$ のそれぞれについて行き先 $A _ i$ が決まっているとき、$1$ を $k$ 回移動したときの行き先を求めよ。（$n \leq 2 \times 10 ^ 5, \ k \leq 10 ^ {18}, 1 \leq A _ i \leq n$）

問題 一列に並んだ $n$ 個のブロックを、同じ色で塗られた隣り合うブロックの組が $k$ 組以下になるように $ m $ 色で塗る塗り方は何通りあるか。（$n,m \leq 2 \times 10 ^ 5, \ k \leq n - 1$）

問題 長さ $3$ の配列とこのうちの $2$ つからなるペアが $n$ 個与えられる。それぞれのペアに対して片方を選んで $+1$ し、もう一方を $-1$ するという操作を、$3$ つの数字のいずれも負にならないようにしながら $n$ 回終えられることが可能か判定し、可能…

問題 長さ $n$ の自然数列 $A$ に対して、$A _ i + A _ j = j - i$ となる $(i,j)$ の個数を求めよ。（$n \leq 2 \times 10 ^ 5$）

問題 $n$ 頂点の木の各頂点に整数が書かれているとき、頂点 $0$ から各頂点へのパス上の整数からなる数列それぞれについて、最長増加部分列の長さを求めよ。

問題 $n$ 人の参加者と $ m $ 個の対戦場があり、各対戦場に $2$ つずつ、$1$ から $n$ の番号のうちの $2 m $ 個を割り当てる。参加者は自分の番号のある対戦場で対戦し、その後自分の番号に $1$ 足す。このとき $n+1$ は $1$ とする。この操作を $n$ 回繰…

問題 座標平面上に与えられた $n$ 個の点 $(X _ i , Y_ i )$ について、長方形の $3$ 頂点をなすような $3$ 点があれば残りの $1$ 点を追加する、という操作が最大で何回行えるか求めよ。（$n\leq 10 ^ 5,\ 1\leq X _ i, Y _ i \leq 10 ^ 5$）

問題 円周上に配置された $n$ 個の点それぞれに価値 $V _ i$ が定まっている。円周上を自由に移動していくつかの点を回収するとき、「価値の総和$-$移動距離」の最大値を求めよ。（$n\leq10 ^ 5$）

問題 $h$ 行 $w$ 列の $0,1$ からなる行列を、どのブロックの和も $k$ 以下になるように縦横に分割するとき、分割回数の最小値を求めよ。（$h\leq10, w\leq 1000$）

問題 $n$ 個の頂点からなる無向グラフがあり、各辺にはコスト $A _ {ij}$ と所要時間 $B _ {ij}$ が定まっていて、通過するにはコストを支払う必要がある。また、各頂点では時間 $D _ i$ をかけて $C _ i$ のコストをためることができる。頂点 $0$ でコスト …

Educational DP Contest / DP まとめコンテストの問題を解いていく。

問題 $0$ ~ $9$ または $?$ からなる文字列 $S$ の $?$ を数字に置き換えてできる整数のうち $13$ で割って $5$ あまる数の個数を求めよ。

問題 長さ $n$ の文字列 $S$ に対して以下のいずれかのクエリを $q$ 個処理せよ。（$n\leq 5 \times 10 ^ 5, q\leq 2 \times 10 ^ 4$） $S$ の $i$ 文字目を $c$ に変える。 $S$ の $l$ 文字目から $r$ 文字目に含まれる文字の種類数を答える。

問題 長さ $n$ の配列 $A$ から $2$ つ選んでできるペアの積のうち $k$ 番目に小さいものを求めよ。（$n \leq 2\times 10 ^ 5$）

問題 $1, 10, \ldots, 10 ^ {1000000}$ 円札で $n$ 円払うとき、渡す枚数とお釣りで使う枚数の和の最小値を求めよ。（$n \leq 10 ^ {1000000}$）

問題 与えられた平面上の $n$ 個の点について、最小包含円の半径を求めよ。（$n\leq50$）

問題 数直線上に配置された $n$ 体の敵の座標 $X _ i$ と体力 $H _ i$ が与えられていて、長さ $2d$ の範囲にいる敵の体力を一斉に $a$ 削る攻撃ができる。何回の攻撃ですべての敵を倒せるか求めよ。（$n\leq 2\times 10 ^5$）

問題 長さ $n$ の配列 $A$ の長さ $k$ の部分列について、最大値と最小値の差をすべての部分列について足したものを求めよ。（$k\leq n\leq 10 ^ 5$）

問題 $1$ 以上 $k$ 以下の整数からなるすべての長さ $n$ の配列 $A$ の最大公約数の和を求めよ。($n,k\leq 10 ^ 5$)

問題 縦棒が $w$ 本、$h$ 段で $0$ 番が $k - 1$ 番に到達するようなあみだくじの個数を求めよ。（$h\leq100$, $w\leq8$）

問題 与えられた長さ $n$ の配列 $A$ に対して、順番を適当に決めたとき、$i$ の行き先を $s_i$ として $\displaystyle\sum_{i=0}^{n-1}A_i|i-s_i|$ の最大値を求めよ。($n\leq2000$)

ブログを始めました！