Codeforces Round #600 (Div. 2) (Virtual) 解説感想

所感:

A-Eで5完, Bでペナを出しまくったこと以外は好成績だった。

A. Single Push

数列A, Bが与えられ、連続区間に同じ数を1回だけ加算してAをBにできるか。

とりあえずB - Aして正の数の連続区間が1つ以下しか存在しなければOK.

B. Silly Mistake

最近割と見る気がする、setのデータ構造をそのまま使えばいい問題。

ただし一人につき一日一回しか出入りできないので、その日に入った人を保存するsetも用意しておくとよし。

C. Sweets Eating

こちらも典型。まず、小さい飴から使うのがいいのがわかる。さらに、後の日付に食べるのは小さいもののほうがいいということもわかる。これを数列にすると

M = 3とすると、

k = 3 なら A1 + A2 + A3, k = 4なら A1 * 2 + A2 + A3 + A4,

k = 6なら(A1 + A2 + A3) * 2 + A4 + A5 + A6

つまり、最大として取ってる要素の後ろM番目が*2, さらにM番目が*3...となっていく。

これはM間隔の累積和として計算できるのでそのまま素直に書けばOK.

サンプル1が一発で合ったのでそのまま投げたらAC.

D. Harmonious Graph

面白い問題。問題を言い換えると、連結成分の最小値と最大値を区間としてみると交差してるところは繋げてください、という問題になる。

これを言い換えると、A < B < Cで A, Bが異なる集合に属するかつ A, Cが同じ集合に属するということになる。

実装を楽するために、各集合内での最大値を管理して、i と i + 1を比較するように見ていきi内の集合の最大値がi + 1より大きいならマージ、ということをすればよかった。

最大値の更新はiを含む集合内の最大値とi+1を含む集合内の最大値の大きい方を取ればOK.

E. Antenna Coverage

制約が緩いのでO(N * M)が間に合う。

あるアンテナの位置xを始点として、範囲をどんどん拡大していき、sを超えたらコストを増やしていくという方針で更新するDPがよさそう。

ここでサンプルを試すと、合ってるサンプルと答えが1異なるサンプルがあってビックリ。添え字ガチャしても合わない。

少し冷静に考えてみると、今回の問題は[1, M]を満たし、かつ区間は端が隣り合っているなら重なっていなくてもOK, という条件がある。

しかし、上記の方法だと, 伸ばしたアンテナの長さをLとすると[x - L, x + L]の範囲のカバーになってしまう。これだと重なるまで伸ばしてしまうので最小コストとは言えない。

したがって、構築を半開区間に置き換えてみる。

まず全てのindexを1ずらして[0, M)を満たすように伸ばすことを考える。半開区間であれば上記の方法のカバーは[x - L, x + L + 1)という具合になる。

半開区間なので範囲が被ることがないというのが保証されている。これが思いつけばOK. 添え字ガチャしてる時間がもったいなかった。

F. Cheap Robot

解説を見てもわからないので今回は飛ばします……

kaikey’s diary