Educational Codeforces Round 65

スポンサーリンク

A. Telephone Number

末尾から 10 番目より左に 8 があるかどうかです.

B. Lost Numbers

$(0,1),(1,2),(2,3),(3,4)$ を聞きます.素数 $5,7,23$ から $5,23,42$ 場所が確定.すると $2$ で割れる回数の情報も手に入り全部確定します.が実装は順列全探索でよいです.

C. News Distribution

同じグループ内で辺を張ったときの連結成分分解をすればよいです.グループを表す点を追加して各メンバーと辺で結ぶと辺の個数がおさえられます.

D. Bicolored RBS

先頭から決めます.各時点での 2 種のネストの総和は塗り分けに依存しません.よって貪欲にその時点での 2 つのネストが均等になるように決めていけば最適になります.

E. Range Deleting

$[1,l)$ 部分がうまくいっているか,$[r+1,x]$ 部分がうまくいってるかというのは $l,r$ それぞれ独立に解けます.これらの必要条件を満たす $l$, $r$ を対象に,$a_l<b_r$ を満たすものを数えるというタイプのクエリ処理になり,FenwickTree で処理できます.

F. Scalar Queries

各 $a_i$ の寄与を計算します.

ソート順が係数になるというのは,$a_i$ 未満の要素それぞれについて,区間がそれを含むなら係数に $1$ が加算されるということです.この式を整理すると,左側・右側にある $a_i$ 未満の要素の場所のインデックスの和があれば計算できることが分かります.

G. Low Budget Inception

設定がややこしくて読解難.愚直解はこれです.中心から距離 $2$ 以上離れている正方形同士は干渉しないことから,干渉するのは距離 $1$ 以下の場合だけだと分かります.

制約から距離 $d=7000$ 以下程度に最初の点があります.両側の点がマッチする状況は距離 $2d$ 程度までを探索すればよいです.これを bitset などで高速化します.

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