audition

解説

解法

各オーディションごとに「必要ポイントを満たせるか」を判定する。
行動には 4 種類あるが、重要な観察として次が成り立つ：

• オールアピールを 3 回以上行う必要はない。
  オールを $T$ 回行った場合、$T=3q+r\ (0 \le r < 3)$ と分解できる。
  このとき
  • オール $r$ 回
  • ダンス/ビジュアル/ボーカルをそれぞれ $q$ 回ずつ
    に置き換えると、加算ポイントはそれぞれ増え、総行動回数は $T$ のままである。
    よって「オールアピールを $0,1,2$ 回行う場合」だけを調べれば十分。

手順

1. 各オーディション $(A_i,B_i,C_i)$ について、オールを $d=0,1,2$ 回行う場合を試す（ただし $d \le K$ の範囲）。
2. その場合に残る必要値を $$A_i' = \max(0, A_i - d\lfloor X/3 \rfloor), \quad B_i' = \max(0, B_i - d\lfloor Y/3 \rfloor), \quad C_i' = \max(0, C_i - d\lfloor Z/3 \rfloor)$$ とする。
3. 残りを単項目アピールで満たす最小回数は $$\text{need}_X = \begin{cases} 0 & \text{if } A_i' \le 0 \\ \left\lceil \dfrac{A_i'}{X} \right\rceil & \text{if } X>0 \\ \infty & \text{if } X=0 \text{ and } A_i'>0 \end{cases}$$ （$Y,Z$ も同様）。
   切り上げは整数演算で (a + b - 1) // b と計算する。
4. 総行動回数 $d + \text{need}_X + \text{need}_Y + \text{need}_Z \le K$ なら、そのオーディションは合格可能。

以上を全オーディションについて判定し、合格できる数を数える。

正当性

• オールは $0,1,2$ 回しか調べなくてよい → 3 回以上は上位互換に置き換えられるため。
• 各項目は独立して考えられる。残りを埋めるのに最小限の単項目アピール回数を使えば最適。
• よって「$d=0,1,2$ を全探索 + 残りを貪欲に埋める」戦略で常に最適解を得られる。

計算量

• 各オーディションについて $d=0,1,2$ の最大 3 通りを試す。
• 1 通りごとの計算は定数時間。
• よって全体計算量は $O(N)$。
  制約 $N \le 2 \times 10^5$ に対して十分高速。

コーナーケースと注意点

• 切り捨て/切り上げの誤差
  • 浮動小数点を使うと誤差で ceil がずれる可能性がある。必ず整数演算 (a + b - 1) // b で計算する。
  • Pythonの場合切り捨ては // を用いる (floor を用いない)。
• ゼロケース
  • A_i=0 ならその項目は行動不要。
  • X=0 かつ A_i=0 なら問題なし。
  • X=0 かつ A_i>0 なら不合格確定。

実装例は以下のようになります。