Educational Codeforces Round 11

スポンサーリンク

A. Co-prime Array

互いに素でないところの間に $1$ を挿入すればよいです.

B. Seating On Bus

書かれている通りにシミュレーション.

C. Hard Process

二分探索.特定の区間の判定問題は累積和前計算で $O(1)$ 時間です.

D. Number of Parallelograms

$abcd$ が平行四辺形になるのは $a+c=b+d$ のときです.入力が一般の位置なので退化ケース等は出てきません.

E. Different Subsets For All Tuples

subsequence の側を固定して,それを含むような $a$ の個数を重みとして総和をとります.$a$ の個数は subsequence の列にしか依存しないことが,含むかどうかの判定問題の貪欲解法を考えると分かります.

F. Bear and Bowling 4

適当な累積和テーブルを用意するとすべての $(l,r)$ に対して [l,r) のコスト $cost(l,r)$ が $O(1)$ 時間で計算できる形になります.CHT を使えば $r$ を固定したときの計算をまとめることができます.

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