ここで重要なのは3つ。
- この問題のクエリ処理では配列Aの要素に対する変更がない。
- Kの制約が5までと少ない。
- Aから効率良く最小値を取り出すには並び替えの必要がある。
Aの配列は制約上109程度まで大きくなるが、実際に評価するのはAを昇順に並び替えた時の先頭6個まで。Kの制約上取り出されうるのは5個、つまりその+1個までがquery毎に調べればいい場所。後に残る配列Aの109-6個は調べる必要がない。
であれば取り出した要素がK個ある配列Bと昇順の配列Aそれぞれの最初の要素が違えば「取り出されていない」ことが分かる。あとBは制約で重複のない昇順のインデックスになっているのでそのまま使える。
公式解説の実装例だとAの元のインデックスを保持したまま並び替えをしBとのインデックス同士の比較に使うという、可能であれば限界まで計算量を省くスタイルが表れている。
そこまでしなくてもボールに書かれた数値を比較する素朴な実装で通るし、コレクションの型に拘る必要もなく配列（int[]）とリスト（List<int>）で事足りる。
コメント