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

# はじめに
「[競技プログラミングの鉄則　演習問題集](https://atcoder.jp/contests/tessoku-book)」を進めていく．本日は3章を進めていきます．
前回のは[こちら](https://qiita.com/YamayouOmiya/items/256807cb39240d2525d5)

https://qiita.com/YamayouOmiya/items/256807cb39240d2525d5

# A問題
## A11
https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_k

配列の二分探索を行う問題．色々なタイプの二分探索に適応できるように関数化しておく．
```c#
using System;
using System.Linq;

class Program
{
    static bool Check(int x, int mid, int[] a)
    {
        return (x >= a[mid]);
    }
    
    static void Main(string[] args)
    {
        string[] input = Console.ReadLine().Split(' ');
        int n = int.Parse(input[0]);
        int x = int.Parse(input[1]);
        int[] a = new int[n + 10];
        input = Console.ReadLine().Split(' ');
        for (int i = 1; i <= n; i++) a[i] = int.Parse(input[i - 1]);

        int l = 0, r = n + 1;
        while (r - l > 1)
        {
            int mid = (r + l) / 2;
            if (Check(x, mid, a)) l = mid;
            else r = mid;
        }

        Console.WriteLine(l);
    }
}
```
## A12
https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_l

二分探索の問題．出力の際l,rどちらを出力するのかをよく見極める必要がある．
```c#
using System;
using System.Linq;

class Program
{
    static bool Check(long k, long mid, long[] a)
    {
        long sum = 0;
        for (long i = 1; i <= a.Length - 1; i++) sum += mid / a[i];
        return k > sum;
    }
    static void Main(string[] args)
    {
        string[] input = Console.ReadLine().Split(' ');
        long n = long.Parse(input[0]);
        long k = long.Parse(input[1]);
        long[] a = new long[n + 1];
        input = Console.ReadLine().Split(' ');
        for (long i = 1; i <= n; i++) a[i] = long.Parse(input[i - 1]);

        long l = 0, r = (long)Math.Pow(10, 9);
        while (r - l > 1)
        {
            long mid = (r + l) / 2;
            if (Check(k, mid, a)) l = mid;
            else r = mid;
        }
        Console.WriteLine(r);

    }
}
```
## A13
https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_m

しゃくとり法を使って差がK以下の整数のペアを数え上げる問題．
```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 k = int.Parse(input[1]);

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

        int[] r = new int[n + 10];
        long count = 0;
        for (int i = 1; i <= n - 1; i++)
        {
            if (i == 1) r[i] = 1;
            else r[i] = r[i - 1];

            while (r[i] < n && a[r[i] + 1] - a[i] <= k) r[i]++;
            count += r[i] - i;
        }
        Console.WriteLine(count);
    }
}
```

## A14
https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_n

半分全列挙のを使う問題．AとBの各和と，CとDの各和の配列を使った後に2分探索を使う．
```c#
using System;
using System.Linq;

class Program
{
    static bool Check(int mid, int k, int p, int[] q)
    {
        return (p + q[mid] <= k);
    }

    static void Main(string[] args)
    {
        string[] input = Console.ReadLine().Split(' ');
        int n = int.Parse(input[0]);
        int k = int.Parse(input[1]);

        int[] a = new int[n + 10];
        int[] b = new int[n + 10];
        int[] c = new int[n + 10];
        int[] d = new int[n + 10];

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

        int[] p = new int[n * n + 1];
        int[] q = new int[n * n + 1];
        for (int x = 1; x <= n; x++)
        {
            for (int y = 1; y <= n; y++)
            {
                p[(x - 1) * n + y] = a[x] + b[y];
                q[(x - 1) * n + y] = c[x] + d[y];
            }
        }
        Array.Sort(p);
        Array.Sort(q);

        bool ans = false;

        for (int i = 1; i <= n * n; i++)
        {
            int l = 1, r = n * n + 1;
            while (r - l > 1)
            {
                int mid = (l + r) / 2;
                if (Check(mid, k, p[i], q)) l = mid;
                else r = mid;
            }
            if (p[i] + q[l] == k) ans = true;
        }

        if (ans) Console.WriteLine("Yes");
        else Console.WriteLine("No");
    }
}
```


## A15
https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_o

チャレンジ問題．新しいリストを用意してaを代入してソートして同じ要素を削除する．あとは2分探索でa[i]がtの何番目の要素を探せばいい．．．はずなのだが！！！！
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3817552/993362d2-4f52-1215-ce0e-5dddd7911ff1.png)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3817552/417363d6-f27d-8e62-ad6d-4339b9eb5fa9.png)
なぜかこの問題，sampleだけどういうわけかREで何度やってもACにならない！！
原因を探るために先代の解答を見てみると．．．
```c#
int n = int.Parse(Console.ReadLine().Trim());
int[] a = Console.ReadLine().Trim().Split(' ').Select(int.Parse).ToArray();
```
どういうわけかこの問題だけTrim()をつけないとうまくいかないらしい！！なんでだ！！時間返せ！
```c#
using System;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        int n = int.Parse(Console.ReadLine().Trim());
        int[] a = Console.ReadLine().Trim().Split(' ').Select(int.Parse).ToArray();
        int[] b = new int[n];

        List<int> t = a.Distinct().ToList();
        t.Sort();

        for (int i = 0; i < n; i++)
        {
            b[i] = t.BinarySearch(a[i]) + 1;
        }

        Console.WriteLine(string.Join(" ", b));
    }
}
```
# B問題
## B11
https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_cj

sortを一回挟むだけ
```C#
using System;
using System.Linq;

class Program
{
    static bool Check(int x, int mid, int[] a)
    {
        return (x > a[mid]);
    }
    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[] x = new int[q + 10];
        for (int i = 1; i <= q; i++) x[i] = int.Parse(Console.ReadLine());
        Array.Sort(a);
        for (int i = 1; i <= q; i++)
        {
            int l = 0, r = n + 1;
            while (r - l > 1)
            {
                int mid = (r + l) / 2;
                if (Check(x[i], mid, a)) l = mid;
                else r = mid;
            }
            Console.WriteLine(l);
        }
    }
}
```
## B12
https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_ck

$x^3+x=N$となるような$x$を探す問題．誤差は0.001まで許容してくれるので結構甘い．Nは最大でも100000なので$x$はすくなくとも100より小さいと考える．2分探索なので0から100の間をかなり細かく区切っても計算余裕なので適当にrとlの間隔が0.0001になるまで計算させたが，これで絶対計算できる保証はない．当然細かくすればするほど値は正確になる，
```c#
using System;
using System.Linq;

class Program
{
    static bool Check(int n, double mid)
    {
        double fx = mid * mid * mid + mid;
        return (fx <= n);
    }

    static void Main(string[] args)
    {
        int n = int.Parse(Console.ReadLine());

        double l = 0.0, r = 100.0;
        while (r - l > 0.0001)
        {
            double mid = (r + l) / 2.0;
            if (Check(n, mid)) l = mid;
            else r = mid;
        }
        Console.WriteLine(l);

    }
}
```

## B13
https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_cl

累積和をとってからしゃくとり法を使う問題なので基本はA13と同じ．だが，今回の連続する番号の品物を買う方法の中には1個だけを選ぶ方法も入っているのでA13とは少し違う数え上げをしてあげないといけない(r[i] - i + 1)．また，A[1]のみとA[N]のみの場合が抜けがちなので注意
```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 k = int.Parse(input[1]);

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

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

        int[] r = new int[n + 10];
        long count = 0;
        for (int i = 1; i <= n; i++)
        {
            if (i == 1) r[i] = 0;
            else r[i] = r[i - 1];

            while (r[i] < n && sum[r[i] + 1] - sum[i - 1] <= k) r[i]++;
            count += r[i] - i + 1;
        }
        Console.WriteLine(count);
    }
}
```

## B14
https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_cm

N枚のカードを使って和がKとなる組み合わせがあるかどうかを探す問題．まず最初にbit全探索が思いつくが計算量は$O(N^2)$でNは最大30なので制限時間を超えてしまう．前半のカードと後半のカードで組み合わせをすべて洗い出すことで半分全列挙の考え方が利用できる．
```c#
using System;
using System.Linq;

class Program
{
    static bool Check(int mid, int k, int p, int[] q)
    {
        return (p + q[mid] <= k);
    }

    static void Main(string[] args)
    {
        string[] input = Console.ReadLine().Split(' ');
        int n = int.Parse(input[0]);
        int k = int.Parse(input[1]);

        int[] a = new int[n + 10];


        input = Console.ReadLine().Split(' ');
        for (int i = 1; i <= n; i++) a[i] = int.Parse(input[i - 1]);
        int pL = n / 2;
        int qL = n - pL;

        int[] p = new int[1 << pL];
        int[] q = new int[1 << qL];
        for (int x = 0; x < (1 << (pL)); x++)
        {
            int sum = 0;
            for (int y = 0; y < pL; y++)
            {
                if (((x >> y) & 1) == 1) sum += a[y + 1];
            }
            p[x] = sum;
        }

        for (int x = 0; x < (1 << (qL)); x++)
        {
            int sum = 0;
            for (int y = 0; y < qL; y++)
            {
                if (((x >> y) & 1) == 1) sum += a[pL + y + 1];
            }
            q[x] = sum;
        }

        Array.Sort(p);
        Array.Sort(q);

        bool ans = false;

        for (int i = 0; i < (1 << pL); i++)
        {
            int l = 0, r = (1 << qL);
            while (r - l > 1)
            {
                int mid = (l + r) / 2;
                if (Check(mid, k, p[i], q)) l = mid;
                else r = mid;
            }
            if (p[i] + q[l] == k) ans = true;
        }

        if (ans) Console.WriteLine("Yes");
        else Console.WriteLine("No");
    }
}
```