競技プログラミングの鉄則をC#で解いてみた。A07編
目的
Atcoderに掲載されている「競技プログラミングの鉄則」を解いて、他の人と回答を比べながらアルゴリズムとC#に関する知識を学んでいくことを目的とした記事。
問題
考え方
問題文を理解する。
昇順で並んでいる配列から、特定の値が入っている番号を求める。
問題文にも書いてある通りに、二分探索を使う。
解く
まずは全探索でどうすればいいか考えてみる。
ある特定の日に訪れた客の人数はそれぞれの客に対して、ある特定の日が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);
}
}
}
ディスカッション
コメント一覧
まだ、コメントがありません