LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@YamayouOmiya(Yama you)

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

Posted at

はじめに

「競技プログラミングの鉄則　演習問題集」を進めていく．本日は3章を進めていきます．
前回のはこちら

A問題

A11

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

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

二分探索の問題．出力の際l,rどちらを出力するのかをよく見極める必要がある．

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

しゃくとり法を使って差がK以下の整数のペアを数え上げる問題．

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

半分全列挙のを使う問題．AとBの各和と，CとDの各和の配列を使った後に2分探索を使う．

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

チャレンジ問題．新しいリストを用意してaを代入してソートして同じ要素を削除する．あとは2分探索でa[i]がtの何番目の要素を探せばいい．．．はずなのだが！！！！
image.png
image.png
なぜかこの問題，sampleだけどういうわけかREで何度やってもACにならない！！
原因を探るために先代の解答を見てみると．．．

int n = int.Parse(Console.ReadLine().Trim());
int[] a = Console.ReadLine().Trim().Split(' ').Select(int.Parse).ToArray();

どういうわけかこの問題だけTrim()をつけないとうまくいかないらしい！！なんでだ！！時間返せ！

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

sortを一回挟むだけ

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

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

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

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

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

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

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");
    }
}
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?