Educational Codeforces Round 8

スポンサーリンク

A. Tennis Tournament

参加人数は $n$ で試合数は $n-1$ です.

B. New Skateboard

長さ $2$ 以上のものについては,末尾 $2$ 文字を決めたら判定できるので,末尾 $2$ 文字ごとに数えます.

C. Bear and String Distance

貪欲に,総和が $K$ 以下となる範囲で可能な限り大きい距離を使っていきます.

D. Magic Numbers

桁 dp です.

$1+2+\cdots+k\leq n$ となる最大の $k$ を求めます.線形探索でも $O(\sqrt{N})$ 時間.

E. Zbazi in Zeydabad

斜め線ごとに考えます.あるいは $i$ 行目の座標を $i$ ずらして 右・下・右という折線の数え上げに帰着し,縦線ごとに考えます.

線を固定した場合の数え上げは次のようになります:

$(i,j)$ であって $i<j$ かつ $A_i\geq j-i$ かつ $B_j\geq j-i$ となるものを数えよ.

さらに $j$ を止めて考えると,$a\leq i < b$ かつ $c\leq i+A_i < d$ となる $i$ を数えることになり,これは長方形における点の個数の数えあげです.$O(nm\log m)$ 時間で解けます.

F. Bear and Fair Set

$\bmod 5$ に応じた個数の条件に加えて,区間に分割されていてそれぞれの区間でいくつというのが決まっています.

フローで解けます.始点から $\bmod 5$ に応じた $5$ 頂点に $n/5$ ずつ振り分けたあと,各値を通り,対応する区間を表す頂点を通り終点に流します.

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