ABC 170 D - Not Divisible
問題
長さ $n$ の数列 $A$ が与えられる。任意の $j \neq i$ に対して $A _i$ が $A _ j$ で割り切れないような $i$ の個数を求めよ。($n \leq 2 \times 10 ^ 5$, $A _ i \leq 10 ^ 6$)
Read moreABC 167 F - Bracket Sequencing
問題
(
と )
からなる $n$ 個の文字列 $S _ i$ を適当な順番に連結して、余りなくすべての括弧が閉じられている状態にできるか判定せよ。($n\leq 10 ^ 6, \ \sum _ {i} | S _ i | \leq 10 ^ 6$)
ABC 167 D - Teleporter
問題
$i=1,\ldots,n$ のそれぞれについて行き先 $A _ i$ が決まっているとき、$1$ を $k$ 回移動したときの行き先を求めよ。($n \leq 2 \times 10 ^ 5, \ k \leq 10 ^ {18}, 1 \leq A _ i \leq n$)
Read moreABC 167 E - Colorful Blocks
問題
一列に並んだ $n$ 個のブロックを、同じ色で塗られた隣り合うブロックの組が $k$ 組以下になるように $ m $ 色で塗る塗り方は何通りあるか。($n,m \leq 2 \times 10 ^ 5, \ k \leq n - 1$)
Read moreABC 166 F - Three Variables Game
問題
長さ $3$ の配列とこのうちの $2$ つからなるペアが $n$ 個与えられる。それぞれのペアに対して片方を選んで $+1$ し、もう一方を $-1$ するという操作を、$3$ つの数字のいずれも負にならないようにしながら $n$ 回終えられることが可能か判定し、可能ならその手順を示せ。
Read moreABC 165 E - Rotation Matching
問題
$n$ 人の参加者と $ m $ 個の対戦場があり、各対戦場に $2$ つずつ、$1$ から $n$ の番号のうちの $2 m $ 個を割り当てる。参加者は自分の番号のある対戦場で対戦し、その後自分の番号に $1$ 足す。このとき $n+1$ は $1$ とする。この操作を $n$ 回繰り返すとき 、同じ組合せの対戦が起きないような対戦場への番号の割り当てを求めよ。($2 m + 1 \leq n \leq 2 \times 10 ^ 5 $)
Read moreABC 131 F - Must Be Rectangular!
問題
座標平面上に与えられた $n$ 個の点 $(X _ i , Y_ i )$ について、長方形の $3$ 頂点をなすような $3$ 点があれば残りの $1$ 点を追加する、という操作が最大で何回行えるか求めよ。($n\leq 10 ^ 5,\ 1\leq X _ i, Y _ i \leq 10 ^ 5$)
Read more