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

はじめに

「競技プログラミングの鉄則　演習問題集」を進めていく．完成したコードを張り付けていきます．回答はC++かPythonが多かったのでC#で進めた記録を残していきます．

A問題

A01

$N^2$を出力する問題

using System;
class Program
{
    static void Main(string[] args)
    {
        int N = int.Parse(Console.ReadLine());
        Console.WriteLine(N * N);
    }
}

A02

N個の整数の中にXが含まれているかを全探索する問題

using System;
using System.Linq;
class Program
{
    static void Main(string[] args)
    {
        string[] input = Console.ReadLine().Split(' ');
        int N = int.Parse(input[0]);
        int X = int.Parse(input[1]);
        int[] A = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
        bool ans = false;

        for (int i = 0; i < N; i++)
        {
            if (A[i] == X)
            {
                ans = true;
                break;
            }
        }

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

    }
}

A03

整数が書かれた赤と青，それぞれN枚のカードから1枚ずつ選んで和がちょうど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[] P = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
        int[] Q = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();

        bool ans = false;

        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                if (P[i] + Q[j] == K) ans = true;
            }
        }

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

    }
}

A04

10進数の数Nを2進数に変換する問題

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

        for (int i = 9; i >= 0; i--)
        {
            if (((N >> i & 1)) == 1) Console.Write("1");
            else Console.Write("0");
        }

    }
}

A05

3つの整数の和がちょうど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 ans = 0;

        for (int i = 1; i <= N; i++)
        {
            for (int j = 1; j <= N; j++)
            {
                int r = K - i - j;
                if (1 <= r && r <= N) ans++;

            }
        }

        Console.WriteLine(ans);

    }
}

B問題

B01

$A+B$を出力するコード

using System;
class Program
{
    static void Main(string[] args)
    {
        string[] input = Console.ReadLine().Split(' ');
        int A = int.Parse(input[0]);
        int B = int.Parse(input[1]);

        Console.WriteLine(A + B);
    }
}

B02

A以上B以下の整数の中に100の約数が含まれているかを求める

using System;
using System.Linq;
class Program
{
    static void Main(string[] args)
    {
        string[] input = Console.ReadLine().Split(' ');
        int A = int.Parse(input[0]);
        int B = int.Parse(input[1]);
        bool ans = false;

        for (int i = A; i <= B; i++)
        {
            if (100 % i == 0)
            {
                ans = true;
                break;
            }
        }

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

    }
}

B03

3重ループを使うので，計算量を減らす工夫が必要

using System;
using System.Linq;
class Program
{
    static void Main(string[] args)
    {
        int N = int.Parse(Console.ReadLine());
        int[] A = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();

        bool ans = false;

        for (int i = 0; i < N; i++)
        {
            for (int j = i + 1; j < N; j++)
            {
                for (int k = j + 1; k < N; k++)
                {
                    if(A[i]+A[j]+A[k]==1000) ans = true;
                }
            }
        }

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

    }
}

B04

2進数を10進数に変換する問題

using System;
using System.Linq;
class Program
{
    static void Main(string[] args)
    {
        int N = int.Parse(Console.ReadLine());
        int ans = 0;

        for (int i = 0; i < 8; i++)
        {
            ans += (N % 10) * (1 << i);
            N /= 10;
        }

        Console.WriteLine(ans);

    }
}

1章なので特に語ることもないです．