Educational Codeforces Round 185

A. Maximum Neighborhood

単純な全探索でよいです.

B. Addition on a Segment

$B$ を減らして $A$ にするということにします.初手で最大 $r-l+1$ をとり,残り $n-1$ 回の操作で全消しできればよいです.

残り $n-1$ 回時点で,総和が $n-1$ 以下になっていれば大丈夫です.$B$ の総和と $B$ の $0$ ではない要素数から上界が出てきて,それが達成可能ということになります.

C. Quotient and Remainder

ある種の最大マッチングを求める問題ですが,$r_1<r_2$ のとき,$(q,r_2)$ がマッチ可能ならば $(q,r_1)$ もマッチ可能です.

各 $q$ (順序は任意)について次の貪欲をすればよいです.

  • $q$ とマッチ可能なものがなければ無視して次に進む.
  • $q$ とマッチ可能なものがあれば,そのうち最大の $r$ とマッチして次に進む.

マッチ可能なものがあるのにマッチしない解は,交換でマッチングをとるものに変形できるので,マッチしてしまうことが正当です.マッチするならば冒頭の単調性より最大の $r$ を選ぶ(小さいものを湯煎して残す)のが明らかに最も良いです.

$q$ とマッチ可能な $r$ は,$q(r+1)+r\leq K$ を満たすものです.これは割る数が $r+1$ 以上でなければならないことからわかります.

D. Almost Roman

まず,クエリでは I の個数を最大化,次いで V の個数を最大化,という要領で,それぞれの個数が与えられていると思ってよいです.

X, V, I の基礎点を $10, 5, -1$ と考えます.これは簡単に計算できます.

この状態から,II がひとつできてしまうごとに $2$ 点が加算されてしまいます.これを最小化する問題です.結局,次が解けていればよいことになります:? をいくつか I に置き換える.I に置き換えるものの個数が $0,1,\ldots,n$ 個であるときの II の個数の最小値を求めよ.

? の連続する部分を考えると,II を増やさないようにひとつ飛ばしで,どこかから II が増えてしまうという形になります.それっぽい操作手順があり,II の個数は $+0,+1,+2$ のどれかで増えていきます.この増え方は差分が単調増加(凸)になります.

$+1$ にあたる操作は $1$ 回以下なので,この操作手順が最適であることは,「先頭から見て $+0$ の回数が最大化されている」「後ろから見て $+2$ の回数が最大化されている」ことから分かります.

成分ごとに,$+0,+1,+2$ をこの順で最適な回数ずつ使えるので,複数の成分があっても結局,指定の回数の $+0,+1,+2$ をこの順に行うという形の操作列が最適になります.

E. Binary Strings and Blocks

問題文の大部分が,「0, 1 の両方を含む」という文字列を定義することに使われています.結局単に,どの $[l,r)$ 内にも $0,1$ の両方があるようにせよというだけです.

prefix の決め方を考えて dp をします.状態としては,末尾の文字と異なる文字が最後に出てくる場所とします.つまり $s_i$ まで決めた時点で

  • $r\leq i$ となるすべての条件 $(l,r)$ について上手くいっている
  • $s_j\neq s_{j+1}=s_{j+2}=\cdots=s_i$

となるものの数え上げを $\dp[j]$ とします.

区間を $0$ にするということと,区間和をとれるセグメント木の類を使えば解けます.

$0$ にする操作は prefix にしか来なくて,一度 $0$ になった部分はずっと $0$ のままなので,$O(N)$ 時間にもできるでしょう.

F. Build XOR on a Segment

ベクトル空間の基底を管理するような線形代数を想起してしまいましたが,最小個数が要求されており,よく考えるとあんまりそういう感じではないです.

とはいえ線形代数から,解が存在するならば $k\leq 12$ にとれることは分かります.

そこで,$r$ をインクリメントさせながら次のような dp を処理します.

  • $\dp[x][k]$:$[l,r]$ 内で $x$ をコスト $k$ 以下で作るとき,そのようなことが可能な $l$ の最大値.

遷移は単に $\dp[x][k] \to \dp[x \oplus a][k+1]$ です.なお,同じ $a$ で複数回遷移しても解は正しく求まるので,dp table はかなり任意のループ順で in-place に更新できます.

$O(NA\log A+Q\log A)$ 時間で少し気になる計算量ですが,TL もかなり長いしそもそもかなり高速です.

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