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…

ch6 二分探索法

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…

対象読者

• STEM系で、学士〜博士過程の学生

必要なもの

新卒に限って言えば

• 学歴
• コーディング力
• 業務経験

ではどれぐらいのレベルが要求されるかというが気になるだろうが、定量化するのは難しいのでこれまでみたことがあるキャリアの例をいくつか示す。なるべく再現性と納得性のあるケースを集めている

• 東大理三 → Google intern → Google
• 東大情報理工学研究科 → Google intern → Google
• 東大情報理工学研究科 → ベンチャーインターン → LINE
• 東大情報理工学部 → Ph.D at california southern university → Meta
• 早稲田CS → ベンチャー・メガベンチャーインターン → Woven by T…