2月13日　日誌

JOI 2023/2024 二次予選 過去問B

未だに理解できていないため、bard 君に解説してもらいました。

問題

模範解答

コードの構成:

1. 必要なライブラリのインポート: bisect ライブラリのみインポートされています。
2. 入力: 商品数 (N)、種類数 (M)、クエリ数 (Q) を読み込みます。
3. 商品情報の読み込み: 商品の定価 (P) と種類 (A) をそれぞれリストに格納します。
4. 種類ごとのインデックスと集計: 種類ごとに商品インデックスと累積和を格納するリスト idx と sum を用意します。
5. クエリ処理:
   • クエリ情報 (T_k, L_k, R_k) を取得
   • バイナリサーチを使って、種類 T_k の範囲内のインデックス l と r を特定
   • 区間 [L_k, R_k] 内の種類 T_k の累積和 (sum[T][r] - sum[T][l]) を計算
   • 部分和の影響を除くため、累積和の半分を引いて購入金額を計算
   • 答えを出力

詳細解説:

• インデックスと集計: 種類ごとにインデックスと累積和を格納することで、特定の種類の商品情報へのアクセスと累積和計算を効率化しています。
• バイナリサーチ: 商品インデックスリストに対してバイナリサーチを行うことで、特定の種類 T_k の範囲内の商品インデックスを効率的に特定できます。
• 部分和の調整: 購入金額計算において、累積和の半分を引くことで、重複要素の影響を排除しています。

解説を見ても分からぬ。
己の解釈で理解していこう！