Codeforces Round 1110 (Div. 1 + Div. 2) 参加記

2026/07/16

私です。

Codeforces Round 1110 (Div. 1 + Div. 2) に参加しました。A, B の2問を解けました。

初めての Div. 1 + Div. 2 だったのですが、なんか問題が難しい気がします。

解けた2問とも説明しづらく、私が苦手なタイプの問題だったのですが、ちゃんと仕留めることができたので、少しは成長しているのかな…

条件を満たさない場合を考えます。

この2つの条件の少なくとも一方を満たすとき、その文字列は条件を満たしません。

したがって、

の和が答えになります。

また、 $N < 2K$ のときは $-1$ となります。

まず、

B_i = A_i - K

とします。

すると、1個の要素を単独で消す場合は $B_i$ をスコアに加え、2個の要素 $x, y$ をまとめて消す場合は $\max(x, y)$ をスコアに加える、と考えることができます。

まず、すべての要素を1個ずつ消した場合のスコアを

S = \sum_{i=1}^{n} B_i

とします。

ここで、2つの要素 $x, y \; (x \le y)$ をまとめて消すことを考えます。

別々に消した場合は $x+y$ 、まとめて消した場合は $y$ なので、2個取りをすることで小さい方の $x$ をスコアから消すことができます。

つまり、2個取りとは「2つの要素のうち小さい方を捨てる操作」と考えられます。

2個取りは最大で $\left\lfloor \frac{n}{2} \right\rfloor$ 回行えるため、最大で $\left\lfloor \frac{n}{2} \right\rfloor$ 個の要素をスコアから消すことができます。

当然、正の値を消すと損なので、負の値のうち小さいものから消したいです。

ここで、消したい要素を X、残したい要素を O と考えます。消したい要素は高々 $\left\lfloor \frac{n}{2} \right\rfloor$ 個なので、必ず X の個数は O の個数以下になります。

また、小さい順に X を選んでいるため、X はどの O 以下でもあります。

元の配列上で X と O が隣接している場所を2個取りすれば、必ず X の方をスコアから消すことができます。これを繰り返すことで、選んだすべての X を消すことができます。

したがって、元の位置関係を気にせず、「どの要素を消すか」だけを考えてよいことになります。

よって、 $B$ を昇順にソートし、小さい方から最大で $\left\lfloor \frac{n}{2} \right\rfloor$ 個の負数を $S$ から取り除きます。

最終的な $S$ が答えです。

C問題以降は全くわからなかったです…。C だけでも Upsolved したいなぁ。

次こそは、緑？黄緑？に行きたいです。

それでは、また。