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

1月 30, 2025

目的

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

問題

Atcoderページ

考え方

まずは問題文を理解する。
質問がQ個渡されて、それぞれに答えればOK。
各質問内容は開催されたイベントの特定期間にどれくらい来場者数があったかを聞かれる。

最初はシンプルに全探索する方法を考えてみる。
質問ごとに来場者数を開始日から終了日まで足して、その値を出力するればOK。

using System;
using System.Linq;
class Program
{
    static void Main(string[] args)
    {
        int[] nq = Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray();
        int n = nq[0];
        int q = nq[1];
        int[] a = Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray();

        for (int i = 0; i < q; i++)
        {
            int[] lr = Console.ReadLine().Split(' ').Select(j => int.Parse(j)).ToArray();
            int sum = 0;

            for(int k = lr[0]; k <= lr[1]; k++)
            {
                sum += a[k - 1]; // 0-indexなので1日目の来場者数は1-1=0にアクセスする必要がある。
            }
            Console.WriteLine(sum);
        }
    }

}

ただし、
・Nが最大で10の5乗
・Qが最大で10の5乗
なので、Lが1、Rが100000の時TLEになる。

うーん、困った。これを解消するために来勝者数を計算する処理(計算量がn)をどうにかする必要がある。

僕が書いたたコード

来場者数を累積和で配列にあらかじめ持っておく。

using System;
using System.Linq;
class Program
{
    static void Main(string[] args)
    {
        int[] nq = Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray();
        int n = nq[0];
        int q = nq[1];
        int[] a = Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray();

        for (int i = 1; i < n; i++)
        {
            a[i] += a[i - 1];
        }

        for (int i = 0; i < q; i++)
        {
            int[] lr = Console.ReadLine().Split(' ').Select(j => int.Parse(j)).ToArray();
            if (lr[0] == 1)
            {
                Console.WriteLine(a[lr[1] - 1]);
            }
            else
            {
                Console.WriteLine(a[lr[1] - 1] - a[lr[0] - 2]);
            }
        }
    }
}

出力部分のif文を三項条件演算子で置き換えてもOK。

using System;
using System.Linq;
class Program
{
    static void Main(string[] args)
    {
        int[] nq = Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray();
        int n = nq[0];
        int q = nq[1];
        int[] a = Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray();

        for (int i = 1; i < n; i++)
        {
            a[i] += a[i - 1];
        }

        for (int i = 0; i < q; i++)
        {
            int[] lr = Console.ReadLine().Split(' ').Select(j => int.Parse(j)).ToArray();
            int result = (a[lr[1] - 1]) - (lr[0] == 1 ? 0 : a[lr[0] - 2]);
            Console.WriteLine(result);
        }
    }
}

条件分岐をしたくない場合は累積和を求める段階で0日目を作って、合計来場者数を0人にしておけばOK。

using System;
using System.Linq;
class Program
{
    static void Main(string[] args)
    {
        int[] nq = Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray();
        int n = nq[0];
        int q = nq[1];
        int[] a = Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray();
        int[] sum = new int[n + 1]; //来場者数の累積和
        sum[0] = 0;

        for (int i = 1; i <= n; i++)
        {
            //sum[i]はi日目までの累積来場者数
            //a[i]は0-indexなので、i+1日目の来場者数。
            //a配列は0-indexなので-1
            sum[i] = sum[i - 1] + a[i - 1];
        }

        for (int i = 0; i < q; i++)
        {
            int[] lr = Console.ReadLine().Split(' ').Select(j => int.Parse(j)).ToArray();
            Console.WriteLine(sum[lr[1]] - sum[lr[0] - 1]);
        }
    }
}

Atcoder

Posted by admin