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#で解いてみた　2章

Posted at

はじめに

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

A問題

A06

一次元の累積和を使った問題．

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

一次元の累積和を使った問題その2．前日比を記録してから累積和を使うのがポイントらしい．

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

2次元の累積和を使った問題．横方向に累積和をとってから縦方向に累積和をとっていく．

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

2次元の累積和を使った問題その2．A07で使った考え方を2次元にも適用していく．

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

累積和のときの考え方の応用，よくできてる．

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

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

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

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

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

たのしくなってきたね～

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?