ABC 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 moreABC 095 D - Static Sushi
問題
円周上に配置された $n$ 個の点それぞれに価値 $V _ i$ が定まっている。円周上を自由に移動していくつかの点を回収するとき、「価値の総和$-$移動距離」の最大値を求めよ。（$n\leq10 ^ 5$）
Read moreABC 159 E - Dividing Chocolate
問題
$h$ 行 $w$ 列の $0,1$ からなる行列を、どのブロックの和も $k$ 以下になるように縦横に分割するとき、分割回数の最小値を求めよ。（$h\leq10, w\leq 1000$）
Read moreABC 164 E - Two Currencies
問題
$n$ 個の頂点からなる無向グラフがあり、各辺にはコスト $A _ {ij}$ と所要時間 $B _ {ij}$ が定まっていて、通過するにはコストを支払う必要がある。また、各頂点では時間 $D _ i$ をかけて $C _ i$ のコストをためることができる。頂点 $0$ でコスト $s$ を持った状態から、他の各頂点への最小所要時間を求めよ。（$n\leq 50, A _ {ij} \leq 50$）
Read moreABC 157 E - Simple String Queries
問題
長さ $n$ の文字列 $S$ に対して以下のいずれかのクエリを $q$ 個処理せよ。（$n\leq 5 \times 10 ^ 5, q\leq 2 \times 10 ^ 4$）
- $S$ の $i$ 文字目を $c$ に変える。
- $S$ の $l$ 文字目から $r$ 文字目に含まれる文字の種類数を答える。
