Educational Codeforces Round 39

スポンサーリンク

A. Partition

要素ごとに考えると単に $\max(x,-x)$ の和です.

B. Weird Subtraction Process

同じ減算が繰り返されるところをまとめると $\log(n+m)$ ステップになります.

C. String Transformation

まだ出てきていない次の文字を作れるなら作ることを貪欲に繰り返します.

D. Timetable

休んだ総日数に対して活動した最小時間を持つ dp.

E. Largest Beautiful Number

$s$ をはじめて下回るタイミングを決めたときの判定が簡単にできます.

F. Fibonacci String Subsequences

部分列を選びさらにその occurrence を選ぶことの数え上げです.状態 $k$ を occurrence の $k$ 文字分を選んだ状態とすると,各文字について,$0$ から $0$ や $N$ から $N$ へは部分列として選ばないという $2$ 通り.他の $k$ から $k$ には$k$ への部分列に選ばないという $1$ 通り,$k$ から $k+1$ にはマッチしているか否かによって $0$ または $1$ 通りの選択があります.文字列は行列になってそれの積をとっていきます.

G. Almost Increasing Array

$A[i]$ を $A[i]-i$ に置き換えておきます.

削除操作がない場合は広義単調増加列を作る問題で,広義単調増加部分列を選べばそれ以外の要素は適切な replace ができます.

削除操作がある場合は,最初の置き換え分の添え字ずれの影響で,$1$ 減少することを $1$ 回許して広義単調増加部分列を選ぶことになります.

CodeForces
スポンサーリンク
シェアする
maspyをフォローする
maspyのHP
タイトルとURLをコピーしました