#738970 (C#) No.994 ばらばらコイン

提出ソース

結果

問題	No.994 ばらばらコイン
ユーザー	chikara-miki
提出日時	2022-02-12 21:36:24
言語	C# (.NET 8.0.203)
結果	AC
実行時間	103 ms / 2,000 ms
コード長	35,172 bytes
コンパイル時間	12,453 ms
コンパイル使用メモリ	145,580 KB
実行使用メモリ	163,208 KB
最終ジャッジ日時	2023-09-11 09:58:12
合計ジャッジ時間	14,620 ms
ジャッジサーバーID （参考情報）	judge13 / judge15

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	50 ms 28,628 KB
testcase_01	AC	48 ms 28,412 KB
testcase_02	AC	102 ms 51,956 KB
testcase_03	AC	102 ms 52,176 KB
testcase_04	AC	103 ms 51,996 KB
testcase_05	AC	76 ms 40,064 KB
testcase_06	AC	102 ms 52,064 KB
testcase_07	AC	103 ms 54,232 KB
testcase_08	AC	86 ms 44,644 KB
testcase_09	AC	100 ms 50,820 KB
testcase_10	AC	87 ms 46,800 KB
testcase_11	AC	92 ms 46,888 KB
testcase_12	AC	95 ms 48,496 KB
testcase_13	AC	49 ms 28,284 KB
testcase_14	AC	50 ms 28,808 KB
testcase_15	AC	49 ms 28,660 KB
testcase_16	AC	50 ms 28,696 KB
testcase_17	AC	50 ms 30,856 KB
testcase_18	AC	50 ms 30,636 KB
testcase_19	AC	50 ms 28,336 KB
testcase_20	AC	50 ms 28,752 KB
testcase_21	AC	50 ms 28,728 KB
testcase_22	AC	50 ms 163,208 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

  Determining projects to restore...
  Restored /home/judge/data/code/main.csproj (in 152 ms).
.NET 向け Microsoft (R) Build Engine バージョン 17.0.0-preview-21470-01+cb055d28f
Copyright (C) Microsoft Corporation.All rights reserved.

  プレビュー版の .NET を使用しています。https://aka.ms/dotnet-core-preview をご覧ください
  main -> /home/judge/data/code/bin/Release/net6.0/main.dll
  main -> /home/judge/data/code/bin/Release/net6.0/publish/

ソースコード

raw source code

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Text.RegularExpressions;
using System.Xml.Xsl;
using System.Reflection;
using System.Diagnostics;
using System.Collections;

namespace Atcoder
{
    public class Program
    {
        static void Main(string[] args)
        {
            var NK = GetIntArray();
            var N = NK[0];
            var K = NK[1];

            var AB = GetIntArrayHW(N - 1, 2);
            if(N < K)
            {
                Console.WriteLine(-1);
            }
            else
            {
                Console.WriteLine(K - 1);
            }
        }
       
        

        public class CID
        {
            //OrderBy             シーケンスの要素をキーに従って昇順に並べ替えます。
            //OrderByDescending   シーケンスの要素をキーに従って降順に並べ替えます。
            //ThenBy              キーに従って昇順のシーケンス内の要素の後続の並べ替えを実行します。
            //ThenByDescending    キーに従って降順に並べ替え、シーケンス内の要素の後続の並べ替えを実行します。


            public CID(int l, int r)
            {
                L = l;
                R = r;
            }
            
            public int L { get; set; }
            public int R { get; set; }

        }

        #region よく使う定数
        public static long INF = 1000000007;
        public static string FILLVALUE = "000000";
        //上→右→下→左
        public static int[] dx = new int[] { 0, 1, 0, -1 };
        public static int[] dy = new int[] { -1, 0, 1, 0 };
        #endregion

        #region 良く使う関数

        /// <summary>
        /// 文字で埋める
        /// </summary>
        /// <param name="val">値</param>
        /// <returns></returns>
        static string Fill(long val)
        {
            return $"{val:FILLVALUE}";
        }

        /// <summary>
        /// ファイル出力
        /// </summary>
        /// <param name="path">出力先</param>
        /// <param name="append">false：上書き　true：追加</param>
        /// <param name="text">内容</param>
        static void OutputFile(bool append, string text)
        {
            var path = "C:\\Users\\cmiki\\Desktop\\output.txt";
            using (StreamWriter writer = new StreamWriter(path, append))
            {
                writer.WriteLine(text);
            }
        }

        /// <summary>
        /// ファイルから取得
        /// </summary>
        /// <param name="path">ファイルパス</param>
        /// <returns></returns>
        static List<List<int>> InputFile(string path)
        {
            var ret = new List<List<int>>();
            StreamReader sr = new StreamReader(path);
            string line = null;
            while ((line = sr.ReadLine()) != null)
            {
                ret.Add(line.Split(' ').Select(i => int.Parse(i)).ToList());
            }
            if (sr != null)
            {
                sr.Close();
            }
            return ret;
        }

        /// <summary>
        /// 値から全パターン出力(何回使ってもOK)
        /// </summary>
        /// <param name="val">今の値</param>
        /// <param name="item">ベースのリスト</param>
        /// <param name="ans">戻すリスト</param>
        /// <param name="len">何桁までやるか</param>
        /// <returns></returns>
        static List<string> AllPattern(string val, List<char> items, List<string> ans, long N)
        {
            if (val.Length == N)
            {
                ans.Add(val);
                return ans;
            }
            foreach (var item in items)
            {
                AllPattern(val + item, items, ans, N);
            }
            return ans;
        }

        /// <summary>
        /// 値から全パターン出力(1回のみ)
        /// </summary>
        /// <param name="val">今の値</param>
        /// <param name="item">ベースのリスト</param>
        /// <param name="ans">戻すリスト</param>
        /// <param name="len">何桁までやるか</param>
        /// <param name="con">使ったかのフラグ</param>
        /// <returns></returns>
        static SortedSet<string> NoCoverPattern(string val, List<string> items, SortedSet<string> ans, int len, List<bool> con)
        {
            // 桁数に応じて変える
            if (val.Length == len)
            {
                ans.Add(val);
                return ans;
            }
            for (int i = 0; i < items.Count; i++)
            {
                if (con[i])
                {
                    con[i] = false;
                    NoCoverPattern(val + items[i], items, ans, len, con);
                    con[i] = true;
                }
            }
            return ans;
        }

        #endregion

        #region 値取得

        #region string
        static string GetString()
        {
            return Console.ReadLine();
        }
        static string[] GetStringArray()
        {
            return Console.ReadLine().Split(' ').ToArray();
        }
        static List<string> GetStringList()
        {
            return Console.ReadLine().Split(' ').ToList();
        }
        static List<string> GetStringRepeat(string val, int cnt)
        {
            return Enumerable.Repeat(val, cnt).ToList();
        }
        static string[,] GetStringArrayHW(int H, int W)
        {
            var ret = new string[H, W];

            for (int i = 0; i < H; i++)
            {
                var tmp = GetStringArray();
                for (int j = 0; j < W; j++)
                {
                    ret[i, j] = tmp[j];
                }
            }
            return ret;
        }
        #endregion

        #region int
        static int GetInt()
        {
            return int.Parse(Console.ReadLine());
        }
        static int[] GetIntArray()
        {
            return Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray();
        }
        static List<int> GetIntList()
        {
            return Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToList();
        }
        static List<int> GetIntRepeat(int val, int cnt)
        {
            return Enumerable.Repeat(val, cnt).ToList();
        }
        static List<List<int>> GetIntListList(int N)
        {
            var ret = new List<List<int>>();
            for (int i = 0; i < N; i++)
            {
                var tmp = GetIntList();
                ret.Add(tmp);
            }
            return ret;
        }
        static int[,] GetIntArrayHW(int H, int W)
        {
            var ret = new int[H, W];

            for (int i = 0; i < H; i++)
            {
                var tmp = GetIntArray();
                for (int j = 0; j < W; j++)
                {
                    ret[i, j] = tmp[j];
                }
            }
            return ret;
        }
        #endregion

        #region BigIntger
        static BigInteger GetBigInt()
        {
            return BigInteger.Parse(Console.ReadLine());
        }
        static BigInteger[] GetBigIntArray()
        {
            return Console.ReadLine().Split(' ').Select(i => BigInteger.Parse(i)).ToArray();
        }
        #endregion

        #region long
        static long GetLong()
        {
            return long.Parse(Console.ReadLine());
        }
        static long[] GetLongArray()
        {
            return Console.ReadLine().Split(' ').Select(i => long.Parse(i)).ToArray();
        }
        static List<long> GetLongList()
        {
            return Console.ReadLine().Split(' ').Select(i => long.Parse(i)).ToList();
        }
        static List<long> GetLongRepeat(long val, int cnt)
        {
            return Enumerable.Repeat(val, cnt).ToList();
        }
        static List<List<long>> GetLongListList(long N)
        {
            var ret = new List<List<long>>();
            for (long i = 0; i < N; i++)
            {
                var tmp = GetLongList();
                ret.Add(tmp);
            }
            return ret;
        }
        static long[,] GetLongArrayHW(long H, long W)
        {
            var ret = new long[H, W];

            for (long i = 0; i < H; i++)
            {
                var tmp = GetLongArray();
                for (int j = 0; j < W; j++)
                {
                    ret[i, j] = tmp[j];
                }
            }
            return ret;
        }
        #endregion

        #region double
        static double GetDouble()
        {
            return double.Parse(Console.ReadLine());
        }
        static double[] GetDoubleArray()
        {
            return Console.ReadLine().Split(' ').Select(i => double.Parse(i)).ToArray();
        }
        static List<double> GetDoubleList()
        {
            return Console.ReadLine().Split(' ').Select(i => double.Parse(i)).ToList();
        }
        static List<double> GetDoubleRepeat(double val, int cnt)
        {
            return Enumerable.Repeat(val, cnt).ToList();
        }
        #endregion

        #region decimal
        static decimal GetDecimal()
        {
            return decimal.Parse(Console.ReadLine());
        }
        static decimal[] GetDecimalArray()
        {
            return Console.ReadLine().Split(' ').Select(i => decimal.Parse(i)).ToArray();
        }
        static List<decimal> GetDecimalList()
        {
            return Console.ReadLine().Split(' ').Select(i => decimal.Parse(i)).ToList();
        }
        static List<decimal> GetDecimalRepeat(decimal val, int cnt)
        {
            return Enumerable.Repeat(val, cnt).ToList();
        }
        #endregion

        #region bool
        static List<bool> GetBoolRepeat(bool val, int cnt)
        {
            return Enumerable.Repeat(val, cnt).ToList();
        }
        static List<List<bool>> GetBoolRepeatHW(bool val, int H, int W)
        {
            var ret = new List<List<bool>>();
            for (int i = 0; i < H; i++)
            {
                var tmp = Enumerable.Repeat(val, W).ToList();
                ret.Add(tmp);
            }
            return ret;
        }

        #endregion

        #endregion

        #region 公式等

        /// <summary>
        /// 左辺と右辺のルートを外して整数で比較
        /// </summary>
        /// <param name="a">左辺１</param>
        /// <param name="b">左辺２</param>
        /// <param name="c">右辺</param>
        /// <returns>右辺が大きい：true</returns>
        public static bool RemoveRoot(long a,long b,long c)
        {
            /*
            √a +√b < √c (1)
            (√a +√b)^2 < c (2)
            2√ab < c − a − b (3)
            c − a − b > 0 ∧ 4ab < (c − a − b)^2
            */
            var d = c - a - b;
            return 0 < d && 4 * a * b < d * d;
        }

        /// <summary>
        /// 串刺し問題は区間スケジューリング法
        /// 右側で並び替えの右とって左を見る。
        /// </summary>
        public static void Skewers()
        {
            //この形
            var ND = GetIntArray();
            var N = ND[0];
            var D = ND[1];

            var LR = new List<CID>();

            for (int i = 0; i < N; i++)
            {
                var tmp = GetIntArray();
                var t = new CID(tmp[0], tmp[1]);
                LR.Add(t);
            }
            LR = LR.OrderBy(x => x.R).ThenBy(x => x.L).ToList();
            var cnt = 1;
            var min = LR[0].R;

            for (int i = 1; i < N; i++)
            {
                if (LR[i].L <= min + D - 1)
                {
                    continue;
                }
                min = LR[i].R;
                cnt++;
            }
            Console.WriteLine(cnt);
        }

        /// <summary>
        /// 逆元
        /// </summary>
        /// <param name="a"></param>
        /// <returns></returns>
        public static long Inverse(long a)
        {
            return modpow(a, INF - 2);
        }

        /// <summary>
        /// 本当の繰返二乗法
        /// </summary>
        /// <param name="a">選択肢が何通り有るか</param>
        /// <param name="n">何個有るか</param>
        /// <param name="mod"></param>
        /// <returns></returns>
        public static long modpow(long a, long n)
        {
            a %= INF;
            long res = 1;
            while (n > 0)
            {
                if ((n & 1) == 1)
                    res = (res * a) % INF;
                a = (a * a) % INF;
                n >>= 1;
            }
            return res;
        }

        /// <summary>
        /// 指定進数から10進数に戻す
        /// </summary>
        /// <param name="val">元の値</param>
        /// <param name="Num">変換元の進数(10進数以下)</param>
        /// <returns></returns>
        static long ChangDecimalnumber(long val, long Num)
        {
            long ans = 0;
            var cnt = 0;
            while (val != 0)
            {
                ans += ((val % 10) * (long)Math.Pow(Num, cnt));
                val /= 10;
                cnt++;
            }
            return ans;
        }

        /// <summary>
        /// 10進数から指定進数に変換
        /// </summary>
        /// <param name="val">元の値</param>
        /// <param name="Num">変換先の進数(10進数以下)</param>
        /// <returns></returns>
        static BigInteger ChangBaseNumber(BigInteger val, long Num)
        {
            if (val == 0)
                return 0;
            var li = new List<BigInteger>();
            while (0 != val)
            {
                li.Add(val % Num);
                val /= Num;
            }
            li.Reverse();
            return BigInteger.Parse(string.Join("", li));
        }

        /// <summary>
        /// エラトステネスの篩
        /// </summary>
        /// <param name="val">範囲の最大値</param>
        /// <returns>true：素数　false：素数ではない</returns>
        static List<bool> EratosthenesSieve(int val)
        {
            var dp = GetBoolRepeat(true, val + 1);
            dp[0] = dp[1] = false;
            var sq = (int)Math.Sqrt(val);

            for (int i = 2; i <= sq; i++)
            {
                if (dp[i])
                {
                    int n = i + i;
                    while (n <= val)
                    {
                        dp[n] = false;
                        n += i;
                    }
                }
            }
            return dp;
        }

        /// <summary>
        /// 各桁の和
        /// </summary>
        /// <param name="sum">合計</param>
        /// <param name="val">値</param>
        /// <returns></returns>
        static long DigitSum(long sum, long val)
        {
            sum += val % 10;
            val /= 10;
            if (val == 0)
                return sum;
            else
                return DigitSum(sum, val);
        }

        /// <summary>
        /// 自然数の和
        /// </summary>
        /// <param name="num">最大数</param>
        /// <returns>合計</returns>
        static long Sumofnatural(long num)
        {
            return num * (num + 1) / 2;
        }

        /// <summary>
        /// 文字入れ替え
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="t1"></param>
        /// <param name="t2"></param>
        /// Swap(ref s[i2][p1 - N], ref s[i2][p2 - N]);の形式で呼出
        static void Swap<T>(ref T t1, ref T t2)
        {
            T t3 = t1;
            t1 = t2;
            t2 = t3;
        }

        /// <summary>
        /// 回文チェック
        /// </summary>
        /// <param name="Target">文字列</param>
        /// <param name="len">文字数</param>
        /// <returns>true：回文　false：回文ではない</returns>
        static bool PalindromeCheck(string Target)
        {
            var len = Target.Length;
            for (int i = 0; i < len / 2; i++)
            {
                if (Target[i] != Target[len - 1 - i])
                {
                    return (false);
                }
            }
            return true;
        }

        /// <summary>
        /// アナグラムチェック　文字列の文字の構成が同じか(文字を入れ替えた時に同一になるか)
        /// </summary>
        /// <param name="word1"></param>
        /// <param name="word2"></param>
        /// <returns>true：アナグラム　false：アナグラムではない</returns>
        static bool AnagramCheck(string word1, string word2)
        {
            char[] val1 = word1.ToCharArray();
            char[] val2 = word2.ToCharArray();
            Array.Sort(val1);
            Array.Sort(val2);
            word1 = new string(val1);
            word2 = new string(val2);

            return word1 == word2;
            //return word1.OrderBy(x => x).SequenceEqual(word2.OrderBy(x => x));
        }

        /// <summary>
        /// 最小公倍数
        /// </summary>
        /// <param name="a"></param>
        /// <param name="b"></param>
        /// <returns>最小公倍数</returns>
        public static long Lcm(long a, long b)
        {
            return a * b / Gcd(a, b);
        }

        /// <summary>
        /// 最大公約数
        /// </summary>
        /// <param name="a"></param>
        /// <param name="b"></param>
        /// <returns>最大公約数</returns>
        public static long Gcd(long a, long b)
        {
            if (a < b)
                // 引数を入替えて自分を呼び出す
                return Gcd(b, a);
            while (b != 0)
            {
                var remainder = a % b;
                a = b;
                b = remainder;
            }
            return a;
        }

        /// <summary>
        /// 余弦定理 三角形の2辺とその接点の角度から残りの辺の長さを出す。
        /// </summary>
        /// <param name="A">辺の長さ</param>
        /// <param name="B">辺の長さ</param>
        /// <param name="k">角度</param>
        /// <returns>辺の長さ</returns>
        public static double CosineTheorem(double A, double B, double k)
        {
            return Math.Sqrt(A * A + B * B - 2 * A * B * Math.Cos(Math.PI * k / 180));
        }

        /// <summary>
        /// 正弦定理　外接円の半径と辺に対する角度から辺の長さを出す。※三角形
        /// </summary>
        /// <param name="R">円の半径</param>
        /// <param name="k">角度</param>
        /// <returns>辺の長さ</returns>
        public static double SineTheorem(double R, double k)
        {
            return 2 * R * Math.Sin(k);
        }

        /// <summary>
        /// ユークリッド距離
        /// </summary>
        /// <param name="x1">現在のx座標</param>
        /// <param name="y1">現在のy座標</param>
        /// <param name="x2">移動後のx座標</param>
        /// <param name="y2">移動後のy座標</param>
        /// <returns></returns>
        public static double EuclideanDistance(double x1, double y1, double x2, double y2)
        {
            return Math.Sqrt(Math.Pow(x1 - x2, 2) + Math.Pow(y1 - y2, 2));
        }

        /// <summary>
        /// 繰返二乗法っぽいやつ
        /// </summary>
        /// <param name="val">値</param>
        /// <param name="div">割値</param>
        /// <param name="minus">引値</param>
        /// <returns></returns>
        public static long RepeatedSquares(long val, long div, long minus)
        {
            if (val == 1)
                return val;
            if (val % div == 0)
            {
                RepeatedSquares(val / div, div, minus);
            }
            else
            {
                RepeatedSquares(val - minus, div, minus);
            }
            return val;
        }

        /// <summary>
        /// 二分探索
        /// </summary>
        /// <param name="items">検索リスト</param>
        /// <param name="target">検索対象</param>
        /// <returns>自分以下_最大indexを返す</returns>
        public static int BinarySearchNear(List<int> items, int target)
        {
            var min = 0;
            var max = items.Count;
            if (items[max - 1] < target)
                return max - 1;
            if (target < items[0])
                return - 1;
            while (min + 1 < max)
            {
                var mid = (min + max) / 2;
                if (items[mid] <= target)
                    min = mid;
                else
                    max = mid;
            }
            return min;
        }

        /// <summary>
        /// 二分探索
        /// </summary>
        /// <param name="items"></param>
        /// <param name="target"></param>
        /// <returns>自分以上_最小indexを返す</returns>
        public static int LowerBound(List<long> items, long target)
        {
            var min = -1;
            var max = items.Count;
            if (items[max - 1] < target)
                return max;
            if (target < items[0])
                return 0;
            while (min + 1 < max)
            {
                var mid = (min + max) / 2;
                if (target <= items[mid])
                    max = mid;
                else
                    min = mid;
            }
            return max;
        }

        /// <summary>
        /// ３点の座標に囲まれた三角形の面積
        /// </summary>
        /// <param name="x1"></param>
        /// <param name="y1"></param>
        /// <param name="x2"></param>
        /// <param name="y2"></param>
        /// <param name="x3"></param>
        /// <param name="y3"></param>
        /// <returns></returns>
        public static bool TriangleArea(double x1, double y1, double x2, double y2, double x3, double y3)
        {
            //var result = 0d;
            var ln1 = LineLen(x1, y1, x2, y2);
            var ln2 = LineLen(x2, y2, x3, y3);
            var ln3 = LineLen(x3, y3, x1, y1);

            var tmp = new List<double>();
            tmp.Add(ln1);
            tmp.Add(ln2);
            tmp.Add(ln3);

            tmp.Sort();
            if (tmp[0] + tmp[1] <= tmp[2])
                return false;
            else
                return true;

            //ヘロンの公式
            //s=(a+b+c)/2
            //S=√s(s-a)(s-b)(s-c)

            //var s1 = (ln1 + ln2 + ln3) / 2d;

            //var s2 = s1 * (s1 - ln1) * (s1 - ln2) * (s1 - ln3);

            //result = Math.Sqrt(s2);
            //return result;
        }

        /// <summary>
        /// ２点間の距離を返す
        /// </summary>
        /// <param name="x1"></param>
        /// <param name="y1"></param>
        /// <param name="x2"></param>
        /// <param name="y2"></param>
        /// <returns></returns>
        public static double LineLen(double x1, double y1, double x2, double y2)
        {
            return Math.Sqrt(Math.Pow(Math.Abs(x1 - x2), 2.0f) + Math.Pow(Math.Abs(y1 - y2), 2.0f));
        }

        /// <summary>
        /// 組合せの数(順序違いは数えない)
        /// </summary>
        /// <param name="n">何個中</param>
        /// <param name="r">何個選ぶか</param>
        /// <returns></returns>
        public static Mint nCr(long n, long r)
        {
            var ret = new Mint(1);
            for (long i = n - r + 1; i <= n; i++)
                ret *= i;
            for (int i = 2; i <= r; i++)
                ret /= i;
            return ret;
        }

        /// <summary>
        /// 組合せの数(順序違いも数える)
        /// </summary>
        /// <param name="n">何個中</param>
        /// <param name="r">何個選ぶか</param>
        /// <returns></returns>
        public static Mint nPr(long n, long r)
        {
            var ret = new Mint(1);
            for (long i = n - r + 1; i <= n; i++)
                ret *= i;
            return ret;
        }
        #endregion

        #region クラス
        #region　ユニオンファインド
        public class UnionFind
        {
            // 親要素のインデックスを保持する
            // 親要素が存在しない(自身がルートである)とき、マイナスでグループの要素数を持つ
            public int[] Parents { get; set; }
            public UnionFind(int n)
            {
                this.Parents = new int[n];
                for (int i = 0; i < n; i++)
                {
                    // 初期状態ではそれぞれが別のグループ(ルートは自分自身)
                    // ルートなのでマイナスで要素数(1個)を保持する
                    this.Parents[i] = -1;
                }
            }

            // 要素xのルート要素はどれか
            public int Find(int x)
            {
                // 親がマイナスの場合は自分自身がルート
                if (this.Parents[x] < 0) return x;
                // ルートが見つかるまで再帰的に探す
                // 見つかったルートにつなぎかえる
                this.Parents[x] = Find(this.Parents[x]);
                return this.Parents[x];
            }

            // 要素xの属するグループの要素数を取得する
            public int Size(int x)
            {
                // ルート要素を取得して、サイズを取得して返す
                return -this.Parents[this.Find(x)];
            }

            // 要素x, yが同じグループかどうか判定する
            public bool Same(int x, int y)
            {
                return this.Find(x) == this.Find(y);
            }

            // 要素x, yが属するグループを同じグループにまとめる
            public bool Union(int x, int y)
            {
                // x, y のルート
                x = this.Find(x);
                y = this.Find(y);
                // すでに同じグループの場合処理しない
                if (x == y) return false;

                // 要素数が少ないグループを多いほうに書き換えたい
                if (this.Size(x) < this.Size(y))
                {
                    var tmp = x;
                    x = y;
                    y = tmp;
                }
                // まとめる先のグループの要素数を更新
                this.Parents[x] += this.Parents[y];
                // まとめられるグループのルートの親を書き換え
                this.Parents[y] = x;
                return true;
            }
        }
        #endregion

        #region プライオリティキュー
        public class PriorityQueue<T> : IEnumerable<T>
        {
            private readonly List<T> _data = new List<T>();
            private readonly IComparer<T> _comparer;
            private readonly bool _isDescending;

            public PriorityQueue(IComparer<T> comparer, bool isDescending = true)
            {
                _comparer = comparer;
                _isDescending = isDescending;
            }

            public PriorityQueue(Comparison<T> comparison, bool isDescending = true)
                : this(Comparer<T>.Create(comparison), isDescending)
            {
            }

            public PriorityQueue(bool isDescending = true)
                : this(Comparer<T>.Default, isDescending)
            {
            }

            public void Enqueue(T item)
            {
                _data.Add(item);
                var childIndex = _data.Count - 1;
                while (childIndex > 0)
                {
                    var parentIndex = (childIndex - 1) / 2;
                    if (Compare(_data[childIndex], _data[parentIndex]) >= 0)
                        break;
                    Swap(childIndex, parentIndex);
                    childIndex = parentIndex;
                }
            }

            public T Dequeue()
            {
                var lastIndex = _data.Count - 1;
                var firstItem = _data[0];
                _data[0] = _data[lastIndex];
                _data.RemoveAt(lastIndex--);
                var parentIndex = 0;
                while (true)
                {
                    var childIndex = parentIndex * 2 + 1;
                    if (childIndex > lastIndex)
                        break;
                    var rightChild = childIndex + 1;
                    if (rightChild <= lastIndex && Compare(_data[rightChild], _data[childIndex]) < 0)
                        childIndex = rightChild;
                    if (Compare(_data[parentIndex], _data[childIndex]) <= 0)
                        break;
                    Swap(parentIndex, childIndex);
                    parentIndex = childIndex;
                }
                return firstItem;
            }

            public T Peek()
            {
                return _data[0];
            }

            private void Swap(int a, int b)
            {
                var tmp = _data[a];
                _data[a] = _data[b];
                _data[b] = tmp;
            }

            private int Compare(T a, T b)
            {
                return _isDescending ? _comparer.Compare(b, a) : _comparer.Compare(a, b);
            }

            public int Count => _data.Count;

            public IEnumerator<T> GetEnumerator()
            {
                return _data.GetEnumerator();
            }

            IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
        }

        public class PriorityQueue<TKey, TValue> : IEnumerable<TValue>
        {
            private readonly List<KeyValuePair<TKey, TValue>> _data = new List<KeyValuePair<TKey, TValue>>();
            private readonly bool _isDescending;
            private readonly Func<TValue, TKey> _keySelector;
            private readonly IComparer<TKey> _keyComparer;

            public PriorityQueue(Func<TValue, TKey> keySelector, bool isDescending = true)
                : this(keySelector, Comparer<TKey>.Default, isDescending)
            {
            }

            public PriorityQueue(Func<TValue, TKey> keySelector, IComparer<TKey> keyComparer, bool isDescending = true)
            {
                _keySelector = keySelector;
                _keyComparer = keyComparer;
                _isDescending = isDescending;
            }

            public void Enqueue(TValue item)
            {
                _data.Add(new KeyValuePair<TKey, TValue>(_keySelector(item), item));
                var childIndex = _data.Count - 1;
                while (childIndex > 0)
                {
                    var parentIndex = (childIndex - 1) / 2;
                    if (Compare(_data[childIndex].Key, _data[parentIndex].Key) >= 0)
                        break;
                    Swap(childIndex, parentIndex);
                    childIndex = parentIndex;
                }
            }

            public TValue Dequeue()
            {
                var lastIndex = _data.Count - 1;
                var firstItem = _data[0];
                _data[0] = _data[lastIndex];
                _data.RemoveAt(lastIndex--);
                var parentIndex = 0;
                while (true)
                {
                    var childIndex = parentIndex * 2 + 1;
                    if (childIndex > lastIndex)
                        break;
                    var rightChild = childIndex + 1;
                    if (rightChild <= lastIndex && Compare(_data[rightChild].Key, _data[childIndex].Key) < 0)
                        childIndex = rightChild;
                    if (Compare(_data[parentIndex].Key, _data[childIndex].Key) <= 0)
                        break;
                    Swap(parentIndex, childIndex);
                    parentIndex = childIndex;
                }
                return firstItem.Value;
            }

            public TValue Peek()
            {
                return _data[0].Value;
            }

            private void Swap(int a, int b)
            {
                var tmp = _data[a];
                _data[a] = _data[b];
                _data[b] = tmp;
            }

            private int Compare(TKey a, TKey b)
            {
                return _isDescending ? _keyComparer.Compare(b, a) : _keyComparer.Compare(a, b);
            }

            public int Count => _data.Count;

            public IEnumerator<TValue> GetEnumerator()
            {
                return _data.Select(r => r.Value).GetEnumerator();
            }

            IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
        }
        #endregion

        #region 特殊系
        /// <summary>
        /// mod p の世界
        /// </summary>
        public class Mint
        {
            public long x;
            public Mint(long x = 0)
            {
                this.x = ((x % INF + INF) % INF);
            }
            public static Mint operator -(Mint m, Mint n)
            {
                return new Mint((m.x + INF - n.x) % INF);
            }
            public static Mint operator -(Mint m, long n)
            {
                return new Mint((m.x + INF - (n % INF)) % INF);
            }
            public static Mint operator -(long m, Mint n)
            {
                return new Mint(((m % INF) + INF - n.x) % INF);
            }
            public static Mint operator +(Mint m, Mint n)
            {
                return new Mint((m.x + n.x) % INF);
            }
            public static Mint operator +(Mint m, long n)
            {
                return new Mint((m.x + (n % INF)) % INF);
            }
            public static Mint operator +(long m, Mint n)
            {
                return new Mint(((m % INF) + n.x) % INF);
            }
            public static Mint operator *(Mint m, Mint n)
            {
                return new Mint((m.x * n.x) % INF);
            }
            public static Mint operator *(Mint m, long n)
            {
                return new Mint((m.x * (n % INF)) % INF);
            }
            public static Mint operator *(long m, Mint n)
            {
                return new Mint(((m % INF) * n.x) % INF);
            }
            public static Mint operator /(Mint m, Mint n)
            {
                return new Mint((m.x * Inverse(n.x)) % INF);
            }
            public static Mint operator /(Mint m, long n)
            {
                return new Mint((m.x * Inverse((n % INF))) % INF);
            }
            public static Mint operator /(long m, Mint n)
            {
                return new Mint(((m % INF) * Inverse(n.x)) % INF);
            }
        }
        #endregion
        #endregion
    }
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード