【競技プログラミング】AtCoder Beginner Contest 371_D問題

問題

既存投稿一覧ページへのリンク

一覧ページ

解法手順1

1. 入力データの読み込み (io_func関数)

• 入力として以下のデータを読み取る:
  • 村の数 N。
  • 村の座標 X (長さ N のリスト)。
  • 各村に住む村人の人数 P (長さ N のリスト)。
  • クエリの数 Q。
  • 各クエリで指定される範囲 [L_i, R_i] (長さ Q のリスト)。
• この関数は、標準入力からすべてのデータを読み取り、適切な形式で返す。

---

2. 累積和の計算 (solve関数)

• 村人の人数リスト P を使って累積和を計算する。
  • 累積和は、あるインデックスまでの村人の合計人数を効率的に求めるために使用される。
  • 累積和リスト cumulative_sum を作成し、以下の式で更新します:

    cumulative_sum[i + 1] = cumulative_sum[i] + P[i]
    

  • この累積和により、任意の区間 [left_idx, right_idx) における村人総数を次式で計算できる:

    cumulative_sum[right_idx] - cumulative_sum[left_idx]
    

---

3. クエリ処理

• 各クエリ [L_i, R_i] に対して以下を行う:
  • 範囲 [L_i, R_i] に含まれる村を効率的に探索するため、座標リスト X を二分探索する。
    • 左端 (L_i) に対応するインデックス left_idx を取得:

      left_idx = bisect.bisect_left(X, L_i)
      

      • bisect_left は、座標 X の中で値が L_i 以上となる最初の位置を返す。
    • 右端 (R_i) に対応するインデックス right_idx を取得:

      right_idx = bisect.bisect_right(X, R_i)
      

      • bisect_right は、座標 X の中で値が R_i より大きくなる最初の位置を返す。
  • 累積和を利用して、範囲 [left_idx, right_idx) に含まれる村人総数を計算

    villagers_num = cumulative_sum[right_idx] - cumulative_sum[left_idx]
    

  • 計算結果を出力。

---

4. 出力

• 各クエリに対する結果 (指定された範囲内に住む村人総数) を標準出力に表示する。

---

ACコード1

ac.py

import bisect
import logging

def setup_logger(debug_mode):
    logger = logging.getLogger(__name__)
    if not logger.handlers:
        logger.setLevel(logging.DEBUG if debug_mode else logging.INFO)
        formatter = logging.Formatter('%(asctime)s - %(name)s - %(levelname)s - %(message)s')

        file_handler = logging.FileHandler('program_trace.log', encoding="utf8")
        file_handler.setFormatter(formatter)
        logger.addHandler(file_handler)

    logger.debug(f"ロガーのセットアップが完了しました。デバッグモード: {debug_mode}")
    return logger

logger = setup_logger(debug_mode=False)

def io_func():
    N = int(input())
    X = list(map(int, input().split()))
    P = list(map(int, input().split()))

    Q = int(input())
    queries = []
    for _ in range(Q):
        L_i, R_i = map(int, input().split())
        queries.append((L_i, R_i))

    logger.debug(f"入力完了: 村の数 N={N}, 村の座標 X={X}, 村人の人数 P={P}, クエリ数 Q={Q}, クエリ内容={queries}")
    return N, X, P, Q, queries

def solve(N, X, P, Q, queries):
    # 累積和を計算する
    cumulative_sum = [0] * (N + 1)
    for i in range(N):
        cumulative_sum[i + 1] = cumulative_sum[i] + P[i]
        logger.debug(f"累積和更新: cumulative_sum[{i+1}]={cumulative_sum[i+1]}")

    # クエリごとに村人の人数を計算する
    for idx, (L_i, R_i) in enumerate(queries):
        left_idx = bisect.bisect_left(X, L_i)
        right_idx = bisect.bisect_right(X, R_i)
        villagers_num = cumulative_sum[right_idx] - cumulative_sum[left_idx]

        logger.debug(f"クエリ{idx+1}: 範囲[{L_i}, {R_i}]に対してleft_idx={left_idx}, right_idx={right_idx}, 村人総数={villagers_num}")
        print(villagers_num)

def main():
    N, X, P, Q, queries = io_func()
    solve(N, X, P, Q, queries)

if __name__ == "__main__":
    main()