Educational Codeforces Round 12

スポンサーリンク

A. Buses Between Cities

読解難.B から A へのバスをすべて試して数えます.

B. Shopping

そのままシミュレーション.

C. Simple Strings

手前から貪欲.直前と一致したら何かに変更しますが, この際直後の文字とも異なるものに変えます.

D. Simple Subset

$2$ 以上の偶数はひとつ以下.$2$ 以上の奇数はひとつ以下.これらを選び,$1$ を追加するかどうかを決めれば列挙できます.

E. Beautiful Subarrays

累積 xor をとれば,$A[i] \oplus A[j]>=K$ を満たす $(i,j)$ を数える問題になります.$a,b$ を固定したとき $a \oplus x \geq b$ となる $x$ 全体は $O(\log A)$ 個の区間になるので区間内の要素の数え上げに帰着できます.

F. Four Divisors

$p^3$ および $pq$ ($p<q$).それぞれ $p$ を固定して数えます.後者については $N/p$ 以下の素数の個数が必要です → https://judge.yosupo.jp/problem/counting_primes

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