Educational Codeforces Round 58

スポンサーリンク

A. Minimum Integer

$d$ または $R$ より大きい最小の $d$ の倍数.

B. Accordion

最後に残した文字が [, : (左側), |, : (右側), ] のどれであるかで dp ができます.

C. Division and Union

ある場所の左側・右側で二分できるような境界があるかを調べればよいです.

D. GCD Counting

素数 $p$ の倍数だけ残したときの直径をすべての $p$ で求めます.

E. Polycarp’s New Job

$x\leq y$, $h\leq w$ としてよく,この向きに入るかだけ試せばよいです.なのでこれまでの $(x,y)$ の max を求めておくだけです.

F. Trucks and Cities

$m$ 個のクエリごとに二分探索で最適化できます.これをやると計算量 $O(m\log(\text{ans})\cdot N)$ となります.二分探索+全探索の状況なので,クエリをランダム順に調べることで $O(m + \log m\log(\text{ans})\cdot N)$ になります.

G. (Zero XOR Subset)-less

累積 xor をいくつか選ぶ,ただし全体 xor は選ばなければいけない.線形独立にたくさん選べ.ということです.なので全体 xor が $0$ ならば不可能,そうでなければ累積 xor の張るベクトル空間の次元です.

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