公式

B - 合格ラインの日々 / Days of the Passing Line 解説 by admin 印刷ページ

DeepSeek V3

Overview

This problem asks us to count how many days the student is satisfied, by comparing each day’s score with the average score of all exams up to that day — the student is satisfied if their score is at least the average.

Analysis

The condition for day \(k\) is whether \(A_k \geq M_k\) holds, which after algebraic manipulation becomes \(k \cdot A_k \geq S_k\) (where \(S_k = A_1 + A_2 + \dots + A_k\)). This condition can be computed daily, and by maintaining \(S_k\) (a cumulative sum) while checking the condition for each day, we can solve this efficiently.

A naive approach would be to sum all scores up to the current day and compute the average each day, which takes \(O(k)\) time per day, resulting in \(O(N^2)\) total time. Since \(N\) can be up to 200,000, this would not meet the time limit. However, by using a cumulative sum, each day’s check can be done in \(O(1)\), allowing us to solve the entire problem in \(O(N)\) time.

Algorithm

  1. Initialize the cumulative sum \(total\) to 0
  2. For each day \(i\) (0-indexed), do the following:
    • Add \(A_i\) to \(total\) (this becomes \(S_{i+1}\))
    • Check the condition \((i+1) \cdot A_i \geq total\)
    • If the condition is true, increment the count by 1
  3. Output the final count

In this algorithm, the only computations needed for each day are addition and comparison, making it very efficient.

Complexity

  • Time complexity: \(O(N)\)
  • Space complexity: \(O(N)\) (for storing the input array)

Implementation Notes

  • Prepare a variable total to maintain the cumulative sum, updating it each day

  • Since days are processed in 0-indexed fashion, use \((i+1)\) when checking the condition

  • Input reading is optimized by using sys.stdin.read()

    Source Code

def main():
    import sys
    data = sys.stdin.read().split()
    n = int(data[0])
    A = list(map(int, data[1:1+n]))
    
    count = 0
    total = 0
    for i in range(n):
        total += A[i]
        if (i + 1) * A[i] >= total:
            count += 1
            
    print(count)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.

投稿日時:
最終更新: