結果

問題 No.2672 Subset Xor Sum
ユーザー tktk_snsn
提出日時 2024-04-07 00:22:07
言語 C#
(.NET 8.0.404)
結果
AC  
実行時間 148 ms / 2,000 ms
コード長 5,843 bytes
コンパイル時間 8,764 ms
コンパイル使用メモリ 166,648 KB
実行使用メモリ 188,220 KB
最終ジャッジ日時 2024-10-01 04:15:20
合計ジャッジ時間 14,499 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 66
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (94 ms)。
MSBuild のバージョン 17.9.6+a4ecab324 (.NET)
  main -> /home/judge/data/code/bin/Release/net8.0/main.dll
  main -> /home/judge/data/code/bin/Release/net8.0/publish/

ソースコード

diff # 

using System;
using System.Text;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Numerics;
using Compro.IO;
using static Compro.Common.ComproUtils;

namespace Compro
{
    public class Program
    {
        public static void Main(string[] args)
        {
            var solver = new AtCoder.Solver();
            solver.Solve();
        }
    }
}


namespace AtCoder
{
    public class Solver
    {
        private readonly StreamScanner scanner;
        

        public Solver()
        {
            scanner = new StreamScanner(Console.OpenStandardInput());
        }

        public void Solve()
        {
            var n = scanner.NextInt();
            var a = scanner.ScanIntArray(n);
            Console.WriteLine(check(n, a) ? "Yes": "No");
        }

        private bool check(int n, int[] A)
        {
            var xor = A.Aggregate(0, (cur, nxt) => cur ^ nxt);
            if (xor != 0)
            {
                return false;
            }

            if (n > 5555 || A.Contains(0))
            {
                return true;
            }

            int m = (1 << 13);
            var dp = Enumerable.Repeat(INF, m).ToArray();
            dp[A[0]] = 1;
            foreach (var a in A[1..])
            {
                var ndp = Enumerable.Repeat(INF, m).ToArray();
                for (int i = 0; i < m; ++i)
                {
                    ndp[i] = Math.Min(ndp[i], dp[i]);
                    ndp[i ^ a] = Math.Min(ndp[i ^ a], dp[i] + 1);
                }
                dp = ndp;
            }
            return dp[0] != n;
        }
    }
}



namespace Compro.Common
{
    public static class ComproUtils
    {
        public static readonly long LINF = long.MaxValue / 2;
        public static readonly int INF = int.MaxValue / 2;

        public static readonly int[] dr = new[] { 0, 1, 0, -1 };
        public static readonly int[] dc = new[] { 1, 0, -1, 0 };
        public const string ds = "RBLF";

        public static long gcd(long x, long y) => y == 0 ? x : gcd(y, x % y);
        public static long lcm(long x, long y) => x * (y / gcd(x, y));


        /// <summary>
        /// nの約数を列挙する
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public static IEnumerable<long> GenDivisor(long n)
        {
            for (long i = 1L; i * i <= n; ++i)
            {
                if (n % i == 0)
                {
                    yield return i;
                    if (i * i != n) yield return n / i;
                } 
            }
        }


        /// <summary>
        /// aを素因数分解する Dict<long primeNumber, int count>
        /// </summary>
        /// <param name="a"></param>
        /// <returns></returns>
        public static Dictionary<long, int> PrimeFactorization(long a)
        {
            var dict = new Dictionary<long, int>();

            if (a == 0)
                return dict;

            int cnt = 0;
            while (a % 2 == 0)
            {
                a /= 2;
                cnt++;
            }
            if (cnt > 0)
            {
                dict.Add(2, cnt);
            }


            for(long p = 3; p * p <= a; p += 2)
            {
                cnt = 0; 
                while (a % p == 0)
                {
                    cnt++;
                    a /= p;
                }
                dict.Add(p, cnt);
            }

            if (a > 1)
            {
                dict.Add(a, 1);
            }

            return dict;
        }
    }
}




namespace Compro.IO
{
    using System.IO;
    using System.Text;
    using System.Globalization;
    using System;

    public class StreamScanner
    {
        private readonly Stream stream;
        private readonly byte[] buffer = new byte[1024];
        private int size, ptr;
        private bool isEOF = false;

        public StreamScanner(Stream stream)
        {
            this.stream = stream;
            ptr = 0;
            size = 0;
        }

        private byte read()
        {
            if (isEOF) return 0;
            if (ptr >= size)
            {
                ptr = 0;
                size = stream.Read(buffer, 0, 1024);
                if (size <= 0)
                {
                    isEOF = true;
                    return 0;
                }
            }
            return buffer[ptr++];
        }

        public char Char()
        {
            byte b = 0;
            do { b = read(); } while ((b < 33 || 126 < b) && !isEOF);
            return (char)b;
        }

        public string Scan()
        {
            var sb = new StringBuilder();
            for (var b = Char(); b >= 33 && b <= 126; b = (char)read())
                sb.Append(b);
            return sb.ToString();
        }

        public int NextInt() { return isEOF ? Int32.MinValue : Int32.Parse(Scan(), CultureInfo.InvariantCulture); }
        public long NextLong() { return isEOF ? Int64.MinValue : Int64.Parse(Scan(), CultureInfo.InvariantCulture); }
        public double NextDouble() { return isEOF ? Double.MinValue : Double.Parse(Scan(), CultureInfo.InvariantCulture); }

        public int[] ScanIntArray(int size)
        {
            var res = new int[size];
            for (int i = 0; i < size; ++i) 
                res[i] = NextInt();
            return res;
        }

        public long[] ScanLongArray(int size)
        {
            var res = new long[size];
            for (int i = 0; i < size; ++i)
                res[i] = NextLong();
            return res;
        }

        public double[] ScanDoubleArray(int size)
        {
            var res = new double[size];
            for (int i = 0; i < size; ++i)
                res[i] = NextDouble();
            return res;
        }
    }
}
0