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

# はじめに
「[競技プログラミングの鉄則　演習問題集](https://atcoder.jp/contests/tessoku-book)」を進めていく．完成したコードを張り付けていきます．回答はC++かPythonが多かったのでC#で進めた記録を残していきます．
前回のは[こちら](https://qiita.com/YamayouOmiya/items/646a86e1e4ceabc5fadf)

https://qiita.com/YamayouOmiya/items/646a86e1e4ceabc5fadf

# A問題
## A06

https://atcoder.jp/contests/tessoku-book/tasks/math_and_algorithm_ai

一次元の累積和を使った問題．
```C#
using System;
using System.Linq;
class Program
{
    static void Main(string[] args)
    {
        string[] input = Console.ReadLine().Split(' ');
        int n = int.Parse(input[0]);
        int q = int.Parse(input[1]);
        
        int[] a = new int[n+1];
        input = Console.ReadLine().Split(' ');
        for (int i = 1; i <= n; i++) a[i] = int.Parse(input[i-1]);

        int[] sum = new int[n+1];
        sum[0] = 0;
        for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + a[i];

        for (int i = 0; i < q; i++)
        {
            input = Console.ReadLine().Split(' ');
            int l = int.Parse(input[0]);
            int r = int.Parse(input[1]);

            Console.WriteLine(sum[r] - sum[l-1]);
        }
    }
}

```

## A07

https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_g

一次元の累積和を使った問題その2．前日比を記録してから累積和を使うのがポイントらしい．
```C#
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[n + 1];
        int[] r = new int[n + 1];

        int[] b = new int[d + 2];
        int[] sum = new int[d + 2];
        sum[0] = 0;

        for (int i = 1; i <= n; i++)
        {
            string[] input = Console.ReadLine().Split(' ');
            l[i] = int.Parse(input[0]);
            r[i] = int.Parse(input[1]);
        }

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

        for (int i = 1; i <= d; i++)
        {
            sum[i] = sum[i - 1] + b[i];
            Console.WriteLine(sum[i]);
        }
    }
}
```

## A08

https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_h

2次元の累積和を使った問題．横方向に累積和をとってから縦方向に累積和をとっていく．
```C#
using System;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        string[] input = Console.ReadLine().Split(' ');
        int h = int.Parse(input[0]);
        int w = int.Parse(input[1]);
        int[,] x = new int[h + 10, w + 10];

        for (int i = 1; i <= h; i++)
        {
            input = Console.ReadLine().Split(' ');
            for (int j = 1; j <= w; j++)
            {
                x[i, j] = int.Parse(input[j-1]);
            }
        }

        int q = int.Parse(Console.ReadLine());
        int[] a = new int[q + 10];
        int[] b = new int[q + 10];
        int[] c = new int[q + 10];
        int[] d = new int[q + 10];


        for (int i = 1; i <= q; i++)
        {
            input = Console.ReadLine().Split(' ');
            a[i] = int.Parse(input[0]);
            b[i] = int.Parse(input[1]);
            c[i] = int.Parse(input[2]);
            d[i] = int.Parse(input[3]);
        }

        int[,] z = new int[h + 10, w + 10];

        for (int i = 1; i <= h; i++)
        {
            for (int j = 1; j <= w; j++)
            {
                z[i, j] = z[i, j - 1] + x[i, j];
            }
        }

        for (int i = 1; i <= w; i++)
        {
            for (int j = 1; j <= h; j++)
            {
                z[j, i] = z[j - 1, i] + z[j, i];
            }
        }

        for (int i = 1; i <= q; i++)
        {
            Console.WriteLine(z[c[i],d[i]]+z[a[i]-1,b[i]-1]-z[a[i]-1,d[i]]-z[c[i],b[i]-1]);
        }
    }
}
```

## A09

https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_i

2次元の累積和を使った問題その2．A07で使った考え方を2次元にも適用していく．
```C#
using System;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        int n = int.Parse(Console.ReadLine());
        int[] a = new int[n + 10];
        int[] b = new int[n + 10];
        int[] c = new int[n + 10];
        int[] d = new int[n + 10];
        string[] input;

        for (int i = 1; i <= n; i++)
        {
            input = Console.ReadLine().Split(' ');
            a[i] = int.Parse(input[0]);
            b[i] = int.Parse(input[1]);
            c[i] = int.Parse(input[2]);
            d[i] = int.Parse(input[3]);
        }

        int[,] x = new int[1510, 1510];
        int[,] z = new int[1510, 1510];

        for (int i = 1; i <= n; i++)
        {
            x[a[i], b[i]]++;
            x[a[i], d[i]]--;
            x[c[i], b[i]]--;
            x[c[i], d[i]]++;
        }

        for (int i = 0; i <= 1500; i++) z[i, 0] = x[i, 0];

        for (int i = 0; i <= 1500; i++)
        {
            for (int j = 1; j <= 1500; j++)
            {
                z[i, j] = z[i, j - 1] + x[i, j];
            }
        }

        for (int i = 0; i <= 1500; i++)
        {
            for (int j = 1; j <= 1500; j++)
            {
                z[j, i] = z[j - 1, i] + z[j, i];
            }
        }

        int count = 0;

        for (int i = 0; i <= 1500; i++)
        {
            for (int j = 0; j <= 1500; j++)
            {
                if (z[i, j] > 0) count++;
            }
        }
        Console.WriteLine(count);
    }
}

```

## A10

https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_j

累積和のときの考え方の応用，よくできてる．
```C#
using System;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        int n = int.Parse(Console.ReadLine());
        int[] a = new int[n + 10];
        string[] input = Console.ReadLine().Split(' ');
        for (int i = 1; i <= n; i++) a[i] = int.Parse(input[i - 1]);

        int d = int.Parse(Console.ReadLine());
        int[] l = new int[d + 10];
        int[] r = new int[d + 10];

        for (int i = 1; i <= d; i++)
        {
            input = Console.ReadLine().Split(' ');
            l[i] = int.Parse(input[0]);
            r[i] = int.Parse(input[1]);
        }

        int[] p = new int[n + 10];
        int[] q = new int[n + 10];

        p[1] = a[1];
        q[n] = a[n];

        for (int i = 2; i <= n; i++) p[i] = Math.Max(p[i - 1], a[i]);
        for (int i = n - 1; i >= 1; i--) q[i] = Math.Max(q[i + 1], a[i]);

        for (int i = 1; i <= d; i++)
        {
            Console.WriteLine(Math.Max(p[l[i] - 1], q[r[i] + 1]));
        }
    }
}
```
# B問題
## B06
https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_ce

```C#
using System;
using System.Linq;
class Program
{
    static void Main(string[] args)
    {
        int n = int.Parse(Console.ReadLine());

        int[] a = new int[n + 1];
        string[] input = Console.ReadLine().Split(' ');
        for (int i = 1; i <= n; i++) a[i] = int.Parse(input[i - 1]);

        int q = int.Parse(Console.ReadLine());

        int[] sum = new int[n + 1];
        sum[0] = 0;
        for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + a[i];

        for (int i = 0; i < q; i++)
        {
            input = Console.ReadLine().Split(' ');
            int l = int.Parse(input[0]);
            int r = int.Parse(input[1]);
            int win = sum[r] - sum[l - 1];
            int lose = r - l + 1 - win;

            if (win > lose) Console.WriteLine("win");
            else if (win < lose) Console.WriteLine("lose");
            else Console.WriteLine("draw");

        }
    }
}

```

## B07
https://atcoder.jp/contests/tessoku-book/tasks/math_and_algorithm_al

```C#
using System;
using System.ComponentModel.DataAnnotations;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {

        int t = int.Parse(Console.ReadLine());
        int n = int.Parse(Console.ReadLine());
        int[] l = new int[n + 10];
        int[] r = new int[n + 10];

        int[] b = new int[t + 10];
        int[] sum = new int[t + 10];

        for (int i = 1; i <= n; i++)
        {
            string[] input = Console.ReadLine().Split(' ');
            l[i] = int.Parse(input[0]);
            r[i] = int.Parse(input[1]);
        }

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

        sum[0] = b[0];
        Console.WriteLine(sum[0]);

        for (int i = 1; i <= t - 1; i++)
        {
            sum[i] = Math.Max(0, sum[i - 1] + b[i]);
            Console.WriteLine(sum[i]);
        }
    }
}
```

## B08
https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_cg

```C#
using System;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        int n = int.Parse(Console.ReadLine());
        int[] x = new int[n + 10];
        int[] y = new int[n + 10];

        string[] input;

        for (int i = 1; i <= n; i++)
        {
            input = Console.ReadLine().Split();
            x[i] = int.Parse(input[0]);
            y[i] = int.Parse(input[1]);
        }

        int[,] p = new int[1510, 1510];
        for (int i = 1; i <= n; i++) p[x[i], y[i]]++;

        int q = int.Parse(Console.ReadLine());
        int[] a = new int[q + 10];
        int[] b = new int[q + 10];
        int[] c = new int[q + 10];
        int[] d = new int[q + 10];


        for (int i = 1; i <= q; i++)
        {
            input = Console.ReadLine().Split(' ');
            a[i] = int.Parse(input[0]);
            b[i] = int.Parse(input[1]);
            c[i] = int.Parse(input[2]);
            d[i] = int.Parse(input[3]);
        }

        int[,] z = new int[1510, 1510];

        for (int i = 1; i <= 1500; i++)
        {
            for (int j = 1; j <= 1500; j++)
            {
                z[i, j] = z[i, j - 1] + p[i, j];
            }
        }

        for (int i = 1; i <= 1500; i++)
        {
            for (int j = 1; j <= 1500; j++)
            {
                z[j, i] = z[j - 1, i] + z[j, i];
            }
        }

        for (int i = 1; i <= q; i++)
        {
            Console.WriteLine(z[c[i], d[i]] + z[a[i] - 1, b[i] - 1] - z[a[i] - 1, d[i]] - z[c[i], b[i] - 1]);
        }
    }
}
```

## B09
https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_ch

```C#
using System;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        int n = int.Parse(Console.ReadLine());
        int[] a = new int[n + 10];
        int[] b = new int[n + 10];
        int[] c = new int[n + 10];
        int[] d = new int[n + 10];
        string[] input;

        for (int i = 1; i <= n; i++)
        {
            input = Console.ReadLine().Split(' ');
            a[i] = int.Parse(input[0]);
            b[i] = int.Parse(input[1]);
            c[i] = int.Parse(input[2]);
            d[i] = int.Parse(input[3]);
        }

        int[,] x = new int[1510, 1510];
        int[,] z = new int[1510, 1510];

        for (int i = 1; i <= n; i++)
        {
            x[a[i], b[i]]++;
            x[a[i], d[i]]--;
            x[c[i], b[i]]--;
            x[c[i], d[i]]++;
        }

        for (int i = 0; i <= 1500; i++) z[i, 0] = x[i, 0];

        for (int i = 0; i <= 1500; i++)
        {
            for (int j = 1; j <= 1500; j++)
            {
                z[i, j] = z[i, j - 1] + x[i, j];
            }
        }

        for (int i = 0; i <= 1500; i++)
        {
            for (int j = 1; j <= 1500; j++)
            {
                z[j, i] = z[j - 1, i] + z[j, i];
            }
        }

        int count = 0;

        for (int i = 0; i <= 1500; i++)
        {
            for (int j = 0; j <= 1500; j++)
            {
                if (z[i, j] > 0) count++;
            }
        }
        Console.WriteLine(count);
    }
}

```

たのしくなってきたね～