Tag: atcoder

AtCoder ABC 023 D「射撃王」

問題概要

• (N) 個の風船があり、風船 (i) は初期高度 (H_i)、1秒ごとに (S_i) 上昇する。
• 競技開始時に1個、その後1秒ごとに1個の風船を割れる（合計 (N) 個のタイミング 0,1,…,N-1 で割る）。
• 風船を割ったときの高度がその風船のペナルティ。最終的なペナルティは、割ったすべての風船のペナルティの最大値。
• 割る順番は自由に選べるとき、最終ペナルティの最小値を求めよ。

解法の着想

「最大値の最小化」は二分探索が有効です。

単調性
もしペナルティを (x) 以下にできるなら、(x+1) 以下にも当然できます。
逆に (x) でできないなら、(x-1) でもできません。
よって「ある値 (…

6.1

この問題は「座標圧縮」と呼ばれる典型的な処理です。
各要素が全体で何番目に小さいか（0始まりの順位）を求める問題で、ソートを使うと (O(N \log N)) で実現できます。

アイデア

1. 値と元の位置をペアにする
   配列 a の各要素に、「値」と「もともとあったインデックス」をセットにしたタプルを作ります。
   例：a = [12, 43, 7, 15, 9] → [(12,0), (43,1), (7,2), (15,3), (9,4)]

2. 値でソートする
   タプルのリストを「値」の昇順に並べ替えます。
   ソート後：[(7,2), (9,4), (12,0), (15,3), (43,1)]
   こうすると、先頭から順に「0番目に小さい値、1番目に小さい値…」と…