競技プログラミングの鉄則をC#で解いてみた。A14 – Four Boxes

2月 6, 2025

問題

A14 – Four Boxes

考え方

問題文を理解する。

A、B、C、D4つの数列が与えられるので、各数列から1つずつ値を選んで合算した値がkになることがあるかを問われている。

解説

まずは全探索。

using System;
using System.Linq;
using System.Collections.Generic;
class Program
{
    static void Main(string[] args)
    {
        bool result = Solve();
        if (result) Console.WriteLine("Yes");
        else Console.WriteLine("No");
    }

    private static bool Solve()
    {
        int[] nk = Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray();
        int n = nk[0];
        int k = nk[1];
        int[] a = Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray();
        int[] b = Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray();
        int[] c = Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray();
        int[] d = Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray();

        for (int f = 0; f < n; f++)
        {
            for (int s = 0; s < n; s++)
            {
                for(int t = 0; t < n; t++)
                {
                    for(int fourth = 0; fourth < n; fourth++)
                    {
                        long sum = 0;
                        sum += a[f];
                        sum += b[s];
                        sum += c[t];
                        sum += d[fourth];
                        if (sum == k) return true;
                    }
                }
            }
        }

        return false;
    }
}

ただし、各数列の要素数は最大で10の3乗。
これだと、計算量が4重のforループで10の12乗を超えてしまう。
TLE。ここを解決する必要がある。

■パターン１

数列A、B、C、DをAとB、CとDに分けて、それぞれのグループにおいて全ての組み合わせに対して合計を算出する。
片方のグループから求まる値をkから引いた値を求める。
もう一方のグループにその値が含まれているかを求める。

数列A、B、C、Dを (AとB)、(CとD) の2つのグループに分ける。
それぞれのグループで、すべての組み合わせに対してそれぞれ合計を求める。

次に、片方のグループから k を引いた値 を求める。
その値がもう一方のグループの合計リストに含まれているかを調べる。

（文章じゃ伝わりずらいよね。）

using System;
using System.Linq;
using System.Collections.Generic;
class Program
{
    static void Main(string[] args)
    {
        bool result = Solve();
        if (result) Console.WriteLine("Yes");
        else Console.WriteLine("No");
    }

    private static bool Solve()
    {
        int[] nk = Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray();
        int n = nk[0];
        int k = nk[1];
        int[] a = Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray();
        int[] b = Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray();
        int[] c = Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray();
        int[] d = Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray();
        int[] abSum = new int[n * n];
        int[] cdSum = new int[n * n];
        Dictionary<int, bool> map = new Dictionary<int, bool>();

        int index = 0;
        for (int f = 0; f < n; f++)
        {
            for (int s = 0; s < n; s++)
            {
                abSum[index] = a[f] + b[s];
                cdSum[index] = c[f] + d[s];
                index++;
            }
        }

        for (int f = 0; f < cdSum.Length; f++)
        {
            map[cdSum[f]] = true;
        }

        for (int f = 0; f < abSum.Length; f++)
        {
            int target = k - abSum[f];
            if (map.ContainsKey(target))
            {
                if (map[target] == true) return true;
            }
        }

        return false;
    }
}

グループABとグループCDは要素数がnなので、1グループに対して全組み合わせはn*n。計算量は最大でnの2乗。2グループなので2nの2乗。

Dictionary<int, bool>にKeyがk-cdi(1<=i<=n)をtrueにして、これがグループABの組み合わせに含まれるかを確認する。計算量は10の6乗。