ABC466 B - Representative Balls

考え方

色ごとに、その色のボールの最大値を探す問題。
指示通りに $1$ 色ずつ調べることもできるが、ここではもっとスマートなやり方を考える。

各色に対し、「今のところの最大値」を保管しておく変数を用意する。
色が $1$ から $M$ までなので、これを 0-indexed に変換し、vector でデータを持てばよい。
そして、それぞれをどんなボールの大きさよりも小さい値で初期化しておく。
ここでは、後述する便利さを考えて、すべて -1 で初期化しておく。

そして、ボールを $1$ つずつ見ていく。
まずは色を確認する。
その後、該当する色の「今のところの最大値」データを更新する。
暫定最大値が a に保管されていて、b がそれより大きければ書き換えたい場合、以下でよい。
今回は a にあたる部分に vector の要素を書くことになる。

a = max(a,b);

これを全ボールについてループで処理する。
すると、$1$ 個でもボールがあった色は、vector 内に、その色のボールの大きさの最大値が入っている。
-1 がどのボールの大きさよりも小さい値であるため、制約上最小のボールでも更新が行われている。
また、その色のボールが $1$ つもなかった場合、初期化した -1 がそのまま入っている。
このような場合は、問題で -1 と答えるよう指示されている。

つまり、この vector を全てそのまま出力すれば、問題に対する答えとなっている。
$2$ 種類の意味の値が混在しているのにまとめて処理できるのが、-1 で初期化した便利さである。

入力例1での動作

入力を受け取る。
色は入力時に $1$ ずつ減らし、0-indexed に直す。

n: 4
m: 5
c: {0, 1, 0, 3}
s: {3, 10, 7, 9}

答え用の配列 result を、長さ $5$ の -1 で初期化する。

result: {-1, -1, -1, -1, -1}

$1$ 個目のボールを見る。
色は 0、大きさは 3 なので、result[0] を最大値更新する。

result: {3, -1, -1, -1, -1}

$2$ 個目のボールを見る。
色は 1、大きさは 10 なので、result[1] を最大値更新する。

result: {3, 10, -1, -1, -1}

$3$ 個目のボールを見る。
色は 0、大きさは 7 なので、result[0] を最大値更新する。

result: {7, 10, -1, -1, -1}

$4$ 個目のボールを見る。
色は 3、大きさは 9 なので、result[3] を最大値更新する。

result: {7, 10, -1, 9, -1}

最後に、result の要素を前から順に出力すればよい。

注意点

特になし。

別解

特になし。