【C#】AtCoder Beginner Contest 127 に参加した

AtCoder Beginner Contest 127に参加した。

atcoder.jp

結果

Cが解けなかった。おそらくコード自体は問題ないと思うが、TLEになってしまった。

解説

まだ

振り返り

A・Bは問題なし。C問題は何をすればいいかはわかるのだが、高速化ができなかった。今回、Nで与えられた値が各L・Rの値に入っているかを判定するコードを書いた。そのため、n^2の計算量(Nの繰り返しの中でMの繰り返しを実施)になってしまった。色々と計算量を減らそうとしたみたが、n^2が解消できずTLEで終了した。

他の人の回答をみたが、途中で思いついたのだが時間がなくて断念した方法が正しかったっぽい。そうなると悔しい。下記がACで通ったコード。要は、与えられたLRを使って、該当する範囲を狭めていく方法。

class Program
{
    static void Main(string[] args)
    {
        string[] s = Console.ReadLine().Split('
        int[] n = s.Select(x => int.Parse(x)).T
        int RR = n[0];
        int LL = 1;
        int L, R = 1;
        for (int i = 0; i < n[1]; i++)
        {
            s = Console.ReadLine().Split(' ');
            L = int.Parse(s[0]);
            R = int.Parse(s[1]);
            if (LL > R || RR < L)
            {
                Console.WriteLine(0);
                return;
            }
            if (LL < L)
            {
                LL = L;
            }
            if (R < RR)
            {
                RR = R;
            }
        }
        Console.WriteLine(RR - LL + 1);
    }
}

コード

github.com