Codeforces Round 1005

スポンサーリンク

A. Brogramming Contest

01 という境界は切る必要があります.10 という境界は切る必要があります.左端が 0 のときに左端を切る必要があります.一回の操作でこれらのうちひとつまでしか切れなくてこれらの個数が答の下界.これは達成可能.

B. Variety is Discouraged

$k$ 個消したときに長さは $k$ 減少,種類数は $k$ 以下しか減少しないので,スコアは消さないときが最大.スコア最大のままなるべく短くするためには,消した分だけ種類数が減る必要があるので,一意な要素の区間のうち最大長のところを求めることになります.

C. Remove the Ends

すべての「操作対象となるプラス」は「操作対象となるマイナス」よりも左にあります.よってある境界から左はプラスのみ,右はマイナスのみが操作対象となります.そのような操作はすべて実現可能です.

D. Eating

クエリを予めソートしておきます.$i$ の討伐に失敗するという条件を言い換えて,失敗するクエリに対して $chmin(ANS[query], N-1-i)$ をするという要領です.結局 $a,b$ を与えて $x\oplus a\leq b$ となる $x$ 全体はどのようなものかを考えればよく,これは $\log(\max(a,b))$ 個の区間として書けます.

E. Mycraft Sand Sort

$1$ 列目,$2$ 列目,と順に見ていくと,「一ヶ所消して間を詰める」操作を繰り返していくことになります.同じ結果になる操作列の個数は,各時点で同じ色の連続する部分の長さの積になります.

削除する代わりに適当な無効値を入れていくことにして,無効値を無視したときの同じ色の区間の長さを取得する問題になります.これはセグメント木二分探索で行えます.

F. We Be Summing

$b$ を固定したときこの和は $i$ について単調性があります.$(b,i)$ であって $i$ が条件を満たすもののうち最小であるようなものを数えることにします.すると,

  • $b_i$ は prefix min を真に減少させる
  • $b_i$ は suffix max を真に増加させる

のうちひとつ以上が成り立つ場合を数えればよいです.

前者は $b_i$(のもとの列での場所) を固定して数えられます.後者は $\max(b_{i+1},\ldots,b_m)$ の位置を固定して数えました.後者から前者との重複を除くこともできます.

必要な計算はセグメント木上の二分探索をたくさん使う感じでできます.

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