競技プログラミングの鉄則をC#で解いてみた。A07編

2月 3, 2025

目的

Atcoderに掲載されている「競技プログラミングの鉄則」を解いて、他の人と回答を比べながらアルゴリズムとC#に関する知識を学んでいくことを目的とした記事。

問題

A07 – Event Attendance

考え方

問題文を理解する。

昇順で並んでいる配列から、特定の値が入っている番号を求める。
問題文にも書いてある通りに、二分探索を使う。

解く

まずは全探索でどうすればいいか考えてみる。

ある特定の日に訪れた客の人数はそれぞれの客に対して、ある特定の日がLからRの区間に含まれているかを判定して、含まれている人数を数えあげれば良い。

それを全部の区間でやるとD(最大で10の5乗)日に対してN人(最大で10の5乗)調べる必要があり、計算量としては10の10乗になってしまう。これはTLE。

では、どうすれば計算量を減らせるかを考える。

D日に対してそれぞれ調べる必要があるからこれは削れなそう。
ある特定の日に客が何人訪れたかは改善の余地がありそう。
ということで、後者をいじってみよう。

表をイメージして、ペッちゃんこにして、Lで加算、Rで減算すれば良さそう。

僕が書いたたコード

using System;
using System.Linq;
class Program
{
    static void Main(string[] args)
    {
        int d = int.Parse(Console.ReadLine());
        int n = int.Parse(Console.ReadLine());
        int[] l = new int[d + 1];
        int[] r = new int[d + 1];

        for (int i = 0; i < n; i++)
        {
            int[] lr = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
            l[lr[0] - 1]++;
            r[lr[1]]++;
        }

        int sum = 0;
        for (int i = 0; i < d; i++)
        {
            sum += l[i];
            sum -= r[i];
            Console.WriteLine(sum);
        }
    }
}

Atcoder

Posted by admin