結果

問題 No.458 異なる素数の和
コンテスト
ユーザー fairy_lettuce
提出日時 2020-05-27 15:47:37
言語 C#(csc)
(csc 3.9.0)
結果
WA  
実行時間 -
コード長 15,755 bytes
コンパイル時間 963 ms
コンパイル使用メモリ 120,540 KB
実行使用メモリ 27,952 KB
最終ジャッジ日時 2024-10-13 03:41:19
合計ジャッジ時間 6,179 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1
other AC * 5 WA * 23
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

using System;
using System.IO;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder.Contest.A
{
	static class Program
	{
        public static List<int> prime;
        public static SortedDictionary<int, int> dp;

        public static void Main(string[] args)
        {
            var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);

            var cin = new Scanner();

            prime = new List<int>();
            dp = new SortedDictionary<int, int>();
            int n = cin.NextInt();
            for (int i = 2; i < n; i++)
            {
                bool isPrime = true;
                foreach (var item in prime)
                {
                    if (item * item > i) break;
                    if (i % item == 0) { isPrime = false; break; }
                }
                if (isPrime)
                {
                    prime.Add(i);
                }
            }
            dp.Add(0, -1);
            dp.Add(1, -1);
            dp.Add(2, 1);

            Console.WriteLine(a(n));

            Console.Out.Flush();
        }

		public static int a(int n)
        {
            int now = -1;
            if (dp.ContainsKey(n)) return dp[n];
            if (prime.Contains(n)) now = Math.Max(now, 1);
            for (var i = prime.UpperBound(n) - 1; i >= 0; i--)
            {
                if (prime[i] * 2 > n) now = Math.Max(now, a(n - prime[i]) == -1 ? -1 : a(n - prime[i]) + 1);
                else if (prime[i] * 2 == n) now = Math.Max(now, a(n - prime[i]) <= 1 ? -1 : a(n - prime[i]) + 1);
                else break;
            }
            dp.Add(n, now);
            return now;
        }
	}

    static class BinarySearch
    {
        public static int UpperBound<T>(T[] array, T value) => UpperBound(array, 0, array.Length - 1, value, Comparer<T>.Default);

        public static int UpperBound<T>(T[] array, T value, Comparer<T> comparer) => UpperBound(array, 0, array.Length - 1, value, comparer);

        public static int UpperBound<T>(T[] array, int index, int length, T value) => UpperBound(array, index, length, value, Comparer<T>.Default);

        public static int UpperBound<T>(T[] array, int index, int length, T value, Comparer<T> comparer)
        {
            var l = index;
            var r = l + length - 1;
            while (l <= r)
            {
                var mid = l + (r - l) / 2;
                var res = comparer.Compare(array[mid], value);
                if (res <= 0) l = mid + 1;
                else r = mid - 1;
            }
            return l;
        }

        public static int UpperBound<T>(this List<T> list, T item) => list.UpperBound(0, list.Count, item, Comparer<T>.Default);

        public static int UpperBound<T>(this List<T> list, T item, Comparer<T> comparer) => list.UpperBound(0, list.Count, item, comparer);

        public static int UpperBound<T>(this List<T> list, int index, int count, T item, Comparer<T> comparer)
        {
            var l = index;
            var r = l + count - 1;
            while (l <= r)
            {
                var mid = l + (r - l) / 2;
                var res = comparer.Compare(list[mid], item);
                if (res <= 0) l = mid + 1;
                else r = mid - 1;
            }
            return l;
        }

        public static int LowerBound<T>(T[] array, T value) => LowerBound(array, 0, array.Length - 1, value, Comparer<T>.Default);

        public static int LowerBound<T>(T[] array, T value, Comparer<T> comparer) => LowerBound(array, 0, array.Length - 1, value, comparer);

        public static int LowerBound<T>(T[] array, int index, int length, T value) => LowerBound(array, index, length, value, Comparer<T>.Default);

        public static int LowerBound<T>(T[] array, int index, int length, T value, Comparer<T> comparer)
        {
            var l = index;
            var r = l + length - 1;
            while (l <= r)
            {
                var mid = l + (r - l) / 2;
                var res = comparer.Compare(array[mid], value);
                if (res == -1) l = mid + 1;
                else r = mid - 1;
            }
            return l;
        }

        public static int LowerBound<T>(this List<T> list, T item) => list.LowerBound(0, list.Count, item, Comparer<T>.Default);

        public static int LowerBound<T>(this List<T> list, T item, Comparer<T> comparer) => list.LowerBound(0, list.Count, item, comparer);

        public static int LowerBound<T>(this List<T> list, int index, int count, T item, Comparer<T> comparer)
        {
            var l = index;
            var r = l + count - 1;
            while (l <= r)
            {
                var mid = l + (r - l) / 2;
                var res = comparer.Compare(list[mid], item);
                if (res == -1) l = mid + 1;
                else r = mid - 1;
            }
            return l;
        }
    }

    public class Pair<T, U> : IComparable, IEquatable<Pair<T, U>> where T : IComparable<T>, IEquatable<T> where U : IComparable<U>, IEquatable<U>
    {
        public T First { get; set; }
        public U Second { get; set; }

        public Pair(T first, U second)
        {
            First = first;
            Second = second;
        }

        public int CompareTo(object obj)
        {
            Pair<T, U> castedObj = (Pair<T, U>)obj;
            int x = First.CompareTo(castedObj.First);
            if (x != 0) return x;
            else return Second.CompareTo(castedObj.Second);
        }

        public static bool operator ==(Pair<T, U> x, Pair<T, U> y) => x.CompareTo(y) == 0;

        public static bool operator !=(Pair<T, U> x, Pair<T, U> y) => x.CompareTo(y) != 0;

        public static bool operator <(Pair<T, U> x, Pair<T, U> y) => x.CompareTo(y) == 1;

        public static bool operator >(Pair<T, U> x, Pair<T, U> y) => x.CompareTo(y) == -1;

        public static bool operator <=(Pair<T, U> x, Pair<T, U> y) => x.CompareTo(y) > 0;

        public static bool operator >=(Pair<T, U> x, Pair<T, U> y) => x.CompareTo(y) < 0;

        public bool Equals(Pair<T, U> x) => First.Equals(x.First) && Second.Equals(x.Second);

        public override bool Equals(object obj)
        {
            return obj is Pair<T, U> pair &&
                   EqualityComparer<T>.Default.Equals(First, pair.First) &&
                   EqualityComparer<U>.Default.Equals(Second, pair.Second);
        }

        public override int GetHashCode()
        {
            unchecked
            {
                var hashCode = 405212230;
                hashCode = hashCode * -1521134295 + EqualityComparer<T>.Default.GetHashCode(First);
                hashCode = hashCode * -1521134295 + EqualityComparer<U>.Default.GetHashCode(Second);
                return hashCode;
            }
        }
    }

    /// <summary>
    /// Self-Balancing Binary Search Tree
    /// (using Randamized BST)
    /// </summary>
    public class SB_BinarySearchTree<T> where T : IComparable
    {
        public class Node
        {
            public T Value;
            public Node LChild;
            public Node RChild;
            public int Count;     //size of the sub tree

            public Node(T v)
            {
                Value = v;
                Count = 1;
            }
        }

        static Random _rnd = new Random();

        public static int Count(Node t)
        {
            return t == null ? 0 : t.Count;
        }

        static Node Update(Node t)
        {
            t.Count = Count(t.LChild) + Count(t.RChild) + 1;
            return t;
        }

        public static Node Merge(Node l, Node r)
        {
            if (l == null || r == null) return l == null ? r : l;

            if ((double)Count(l) / (double)(Count(l) + Count(r)) > _rnd.NextDouble())
            {
                l.RChild = Merge(l.RChild, r);
                return Update(l);
            }
            else
            {
                r.LChild = Merge(l, r.LChild);
                return Update(r);
            }
        }

        /// <summary>
        /// split as [0, k), [k, n)
        /// </summary>
        public static Tuple<Node, Node> Split(Node t, int k)
        {
            if (t == null) return new Tuple<Node, Node>(null, null);
            if (k <= Count(t.LChild))
            {
                var s = Split(t.LChild, k);
                t.LChild = s.Item2;
                return new Tuple<Node, Node>(s.Item1, Update(t));
            }
            else
            {
                var s = Split(t.RChild, k - Count(t.LChild) - 1);
                t.RChild = s.Item1;
                return new Tuple<Node, Node>(Update(t), s.Item2);
            }
        }

        public static Node Remove(Node t, T v)
        {
            if (Find(t, v) == null) return t;
            return RemoveAt(t, LowerBound(t, v));
        }

        public static Node RemoveAt(Node t, int k)
        {
            var s = Split(t, k);
            var s2 = Split(s.Item2, 1);
            return Merge(s.Item1, s2.Item2);
        }

        public static bool Contains(Node t, T v)
        {
            return Find(t, v) != null;
        }

        public static Node Find(Node t, T v)
        {
            while (t != null)
            {
                var cmp = t.Value.CompareTo(v);
                if (cmp > 0) t = t.LChild;
                else if (cmp < 0) t = t.RChild;
                else break;
            }
            return t;
        }

        public static Node FindByIndex(Node t, int idx)
        {
            if (t == null) return null;

            var currentIdx = Count(t) - Count(t.RChild) - 1;
            while (t != null)
            {
                if (currentIdx == idx) return t;
                if (currentIdx > idx)
                {
                    t = t.LChild;
                    currentIdx -= (Count(t == null ? null : t.RChild) + 1);
                }
                else
                {
                    t = t.RChild;
                    currentIdx += (Count(t == null ? null : t.LChild) + 1);
                }
            }

            return null;
        }

        public static int UpperBound(Node t, T v)
        {
            var torg = t;
            if (t == null) return -1;

            var ret = Int32.MaxValue;
            var idx = Count(t) - Count(t.RChild) - 1;
            while (t != null)
            {
                var cmp = t.Value.CompareTo(v);

                if (cmp > 0)
                {
                    ret = Math.Min(ret, idx);
                    t = t.LChild;
                    idx -= (Count(t == null ? null : t.RChild) + 1);
                }
                else if (cmp <= 0)
                {
                    t = t.RChild;
                    idx += (Count(t == null ? null : t.LChild) + 1);
                }
            }
            return ret == Int32.MaxValue ? Count(torg) : ret;
        }

        public static int LowerBound(Node t, T v)
        {
            var torg = t;
            if (t == null) return -1;

            var idx = Count(t) - Count(t.RChild) - 1;
            var ret = Int32.MaxValue;
            while (t != null)
            {
                var cmp = t.Value.CompareTo(v);
                if (cmp >= 0)
                {
                    if (cmp == 0) ret = Math.Min(ret, idx);
                    t = t.LChild;
                    if (t == null) ret = Math.Min(ret, idx);
                    idx -= t == null ? 0 : (Count(t.RChild) + 1);
                }
                else if (cmp < 0)
                {
                    t = t.RChild;
                    idx += (Count(t == null ? null : t.LChild) + 1);
                    if (t == null) return idx;
                }
            }
            return ret == Int32.MaxValue ? Count(torg) : ret;
        }

        public static Node Insert(Node t, T v)
        {
            var ub = LowerBound(t, v);
            return InsertByIdx(t, ub, v);
        }

        static Node InsertByIdx(Node t, int k, T v)
        {
            var s = Split(t, k);
            return Merge(Merge(s.Item1, new Node(v)), s.Item2);
        }

        public static IEnumerable<T> Enumerate(Node t)
        {
            var ret = new List<T>();
            Enumerate(t, ret);
            return ret;
        }

        static void Enumerate(Node t, List<T> ret)
        {
            if (t == null) return;
            Enumerate(t.LChild, ret);
            ret.Add(t.Value);
            Enumerate(t.RChild, ret);
        }
    }

/// <summary>
/// C-like set
/// </summary>
public class Set<T> where T : IComparable
    {
        protected SB_BinarySearchTree<T>.Node _root;

        public T this[int idx] { get { return ElementAt(idx); } }

        public int Count()
        {
            return SB_BinarySearchTree<T>.Count(_root);
        }

        public virtual void Insert(T v)
        {
            if (_root == null) _root = new SB_BinarySearchTree<T>.Node(v);
            else
            {
                if (SB_BinarySearchTree<T>.Find(_root, v) != null) return;
                _root = SB_BinarySearchTree<T>.Insert(_root, v);
            }
        }

        public void Clear()
        {
            _root = null;
        }

        public void Remove(T v)
        {
            _root = SB_BinarySearchTree<T>.Remove(_root, v);
        }

        public bool Contains(T v)
        {
            return SB_BinarySearchTree<T>.Contains(_root, v);
        }

        public T ElementAt(int k)
        {
            var node = SB_BinarySearchTree<T>.FindByIndex(_root, k);
            if (node == null) throw new IndexOutOfRangeException();
            return node.Value;
        }

        public int Count(T v)
        {
            return SB_BinarySearchTree<T>.UpperBound(_root, v) - SB_BinarySearchTree<T>.LowerBound(_root, v);
        }

        public int LowerBound(T v)
        {
            return SB_BinarySearchTree<T>.LowerBound(_root, v);
        }

        public int UpperBound(T v)
        {
            return SB_BinarySearchTree<T>.UpperBound(_root, v);
        }

        public Tuple<int, int> EqualRange(T v)
        {
            if (!Contains(v)) return new Tuple<int, int>(-1, -1);
            return new Tuple<int, int>(SB_BinarySearchTree<T>.LowerBound(_root, v), SB_BinarySearchTree<T>.UpperBound(_root, v) - 1);
        }

        public List<T> ToList()
        {
            return new List<T>(SB_BinarySearchTree<T>.Enumerate(_root));
        }
    }

    class Scanner
	{
		string[] s;
		int i;

		char[] cs = new char[] { ' ' };

		public Scanner()
		{
			s = new string[0];
			i = 0;
		}

		public string Next()
		{
			if (i < s.Length) return s[i++];
			string st = Console.ReadLine();
			while (st == "") st = Console.ReadLine();
			s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
			if (s.Length == 0) return Next();
			i = 0;
			return s[i++];
		}

		public int NextInt()
		{
			return int.Parse(Next());
		}

		public int[] ArrayInt(int N, int add = 0)
		{
			int[] Array = new int[N];
			for (int i = 0; i < N; i++)
			{
				Array[i] = NextInt() + add;
			}
			return Array;
		}

		public long NextLong()
		{
			return long.Parse(Next());
		}

		public long[] ArrayLong(int N, long add = 0)
		{
			long[] Array = new long[N];
			for (int i = 0; i < N; i++)
			{
				Array[i] = NextLong() + add;
			}
			return Array;
		}

		public double NextDouble()
		{
			return double.Parse(Next());
		}

		public double[] ArrayDouble(int N, double add = 0)
		{
			double[] Array = new double[N];
			for (int i = 0; i < N; i++)
			{
				Array[i] = NextDouble() + add;
			}
			return Array;
		}
	}
}
0