#1156831 (C#) No.861 ケーキカット

• 問題: No.861 ケーキカット
• ユーザー: kakel-san
• 提出日時: 2026-04-08 22:40:07
• 言語: C# (.NET 10.0.201)
• 結果: AC
• 実行時間: 175 ms / 1,000 ms
• コード長: 3,655 bytes
• コンパイル時間: 8,265 ms
• コンパイル使用メモリ: 172,036 KB
• 実行使用メモリ: 219,368 KB
• 最終ジャッジ日時: 2026-04-08 22:40:21
• 合計ジャッジ時間: 13,753 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge3_0

ファイルパターン	結果
sample	AC * 3
other	AC * 21

コンパイルメッセージ

  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (91 ミリ秒)。
  main -> /home/judge/data/code/bin/Release/net10.0/main.dll
  main -> /home/judge/data/code/bin/Release/net10.0/publish/

ソースコード

using System;
using static System.Console;
using System.Linq;
using System.Collections.Generic;
using System.Security.Cryptography;

class Program
{
    static int NN => int.Parse(ReadLine());
    static int[] NList => ReadLine().Split().Select(int.Parse).ToArray();
    static int[][] NArr(long n) => Enumerable.Repeat(0, (int)n).Select(_ => NList).ToArray();
    public static void Main()
    {
        Solve();
    }
    static void Solve()
    {
        var c = NArr(5);
        WriteLine(Cake(c));
    }
    static long Cake(int[][] c)
    {
        var ox = new int[] { 0, 0, 0, 0, 1, 2, 3, 4, 4, 4, 4, 4, 3, 2, 1 };
        var oy = new int[] { 1, 2, 3, 4, 4, 4, 4, 4, 3, 2, 1, 0, 0, 0, 0 };
        var ix = new int[] { 1, 1, 1, 2, 2, 2, 3, 3, 3 };
        var iy = new int[] { 1, 2, 3, 1, 2, 3, 1, 2, 3 };
        var ans = INF;
        var bitmax = 512;
        {
            for (var b = 0; b < bitmax; ++b)
            {
                var div = new bool[5, 5];
                for (var i = 0; i < 9; ++i)
                {
                    if (((b >> i) & 1) != 0) div[ix[i], iy[i]] = true;
                }
                ans = Math.Min(ans, Divide(c, div));
            }
        }
        for (var of = 0; of < ox.Length; ++of)
        {
            for (var ot = of; ot < ox.Length; ++ot)
            {
                var div = new bool[5, 5];
                for (var i = of; i <= ot; ++i) div[ox[i], oy[i]] = true;
                for (var b = 0; b < bitmax; ++b)
                {
                    for (var i = 0; i < 9; ++i)
                    {
                        div[ix[i], iy[i]] = ((b >> i) & 1) != 0;
                    }
                    ans = Math.Min(ans, Divide(c, div));
                }
            }
        }
        return ans;
    }
    static long INF = long.MaxValue;
    static long Divide(int[][] c, bool[,] div)
    {
        var uf = new UnionFindTree(25);
        for (var i = 0; i < 5; ++i) for (var j = 0; j < 4; ++j) if (div[i, j] == div[i, j + 1]) uf.Unite(i * 5 + j, i * 5 + j + 1);
        for (var i = 0; i < 4; ++i) for (var j = 0; j < 5; ++j) if (div[i, j] == div[i + 1, j]) uf.Unite(i * 5 + j, i * 5 + j + 5);
        var sum = new long[25];
        var one = -1;
        var two = -1;
        for (var i = 0; i < 25; ++i)
        {
            var r = uf.GetRoot(i);
            if (one != r && two != r)
            {
                if (one < 0) one = r;
                else if (two < 0) two = r;
                else return INF;
            }
            sum[r] += c[i / 5][i % 5];
        }
        if (two < 0) return sum[one];
        else return Math.Abs(sum[one] - sum[two]);
    }
    class UnionFindTree
    {
        int[] roots;
        public UnionFindTree(int size)
        {
            roots = new int[size];
            for (var i = 0; i < size; ++i) roots[i] = -1;
        }
        public int GetRoot(int a)
        {
            if (roots[a] < 0) return a;
            return roots[a] = GetRoot(roots[a]);
        }
        public bool IsSameTree(int a, int b)
        {
            return GetRoot(a) == GetRoot(b);
        }
        public bool Unite(int a, int b)
        {
            var x = GetRoot(a);
            var y = GetRoot(b);
            if (x == y) return false;
            if (-roots[x] < -roots[y]) { var tmp = x; x = y; y = tmp; }
            roots[x] += roots[y];
            roots[y] = x;
            return true;
        }
        public int GetSize(int a)
        {
            return -roots[GetRoot(a)];
        }
    }
}