#1195010 (C#) No.5025 Forest Fire

• 問題: No.5025 Forest Fire
• ユーザー: tobisatis
• 提出日時: 2026-10-24 15:50:24
• 言語: C# (.NET 10.0.402 + ACL)
• 結果: AC
• 実行時間: 1,897 ms / 2,000 ms
• コード長: 3,453 bytes
• コンパイル時間: 13,847 ms
• コンパイル使用メモリ: 173,180 KB
• 実行使用メモリ: 52,096 KB
• スコア: 154,039,809
• 最終ジャッジ日時: 2026-10-24 15:53:14
• 合計ジャッジ時間: 170,166 ms
• ジャッジサーバーID （参考情報）: judge5_0 / <nil>

ファイルパターン	結果
other	AC * 50

コンパイルメッセージ

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

ソースコード

#nullable enable

var stopwatch = new System.Diagnostics.Stopwatch();
stopwatch.Start();
var random = new Random(1);

StreamReader _sr = new(Console.OpenStandardInput());
StreamWriter _sw = new(Console.OpenStandardOutput()) { AutoFlush = false };

const int N = 50;
// const int K = 100;
_sr.ReadLine();
var g = new int[N][];
for (var i = 0; i < N; i++)
{
    var str = _sr.ReadLine()!;
    var row = new int[N];
    for (var j = 0; j < N; j++) row[j] = str[j] - '0';
    g[i] = row;
}

var ans = new List<(int, int)>();
void Run()
{
    var h = new int[N][];
    for (var i = 0; i < N; i++)
    {
        var rg = g[i];
        var rh = new int[N];
        for (var j = 0; j < N; j++) if (rg[j] >= 6) rh[j] = 1;
        h[i] = rh;
    }
    var score = int.MaxValue;
    while (stopwatch.ElapsedMilliseconds < 1900)
    {
        var iz = new int[N];
        var jz = new int[N];
        for (var lp = 0; lp < 2; lp++)
        {
            var x = iz[0] = random.Next(N);
            for (var i = 1; i < N; i++)
            {
                x = x + random.Next(2) - 1;
                x = Math.Max(Math.Min(x, N - 1), 0);
                iz[i] = x;
            }
            (iz, jz) = (jz, iz);
        }
        for (var i = 0; i < N; i++) h[i][jz[i]] ^= 2;
        for (var j = 0; j < N; j++) h[iz[j]][j] ^= 2;
        var uf = new UnionFind(N * N);
        for (var i = 0; i < N; i++)
        {
            var rh = h[i];
            var t = i * N;
            for (var j = 0; j < N - 1; j++)
            {
                if (rh[j] != 1 || rh[j + 1] != 1) continue;
                uf.Union(t + j, t + j + 1);
            }
        }
        for (var i = 0; i < N - 1; i++)
        {
            var rh0 = h[i];
            var rh1 = h[i + 1];
            var t0 = i * N;
            var t1 = t0 + N;
            for (var j = 0; j < N; j++)
            {
                if (rh0[j] != 1 || rh1[j] != 1) continue;
                uf.Union(t0 + j, t1 + j);
            }
        }
        var s = 0;
        for (var i = 0; i < N; i++)
        {
            var rh = h[i];
            var t = i * N;
            for (var j = 0; j < N; j++)
            {
                if (rh[j] != 1 || uf.Find(t + j) != t + j) continue;
                var c = uf.Size(t + j);
                s += c * c;
            }
        }
        if (s < score)
        {
            score = s;
            ans = [];
            for (var i = 0; i < N; i++) ans.Add((i, jz[i]));
            for (var j = 0; j < N; j++) ans.Add((iz[j], j));
        }
        for (var i = 0; i < N; i++) h[i][jz[i]] ^= 2;
        for (var j = 0; j < N; j++) h[iz[j]][j] ^= 2;
    }
}

Run();
ans = [.. ans.Where(e => g[e.Item1][e.Item2] != 0).Distinct()];
_sw.WriteLine(ans.Count);
foreach (var (ai, aj) in ans) _sw.WriteLine(ai + " " + aj);
_sw.Flush();

class UnionFind
{
    int[] Verticals { get; set; }
    public UnionFind(int verticals)
    {
        Verticals = new int[verticals];
        Verticals.AsSpan().Fill(-1);
    }

    public int Union(int x, int y)
    {
        (x, y) = (Find(x), Find(y));
        if (x == y) return x;
        var (sx, sy) = (Size(x), Size(y));
        if (sx < sy) (x, y, sy) = (y, x, sx);
        Verticals[x] -= sy;
        return Verticals[y] = x;
    }

    public int Find(int x)
    {
        var p = Verticals[x];
        if (p < 0) return x;
        return Verticals[x] = Find(p);
    }

    public int Size(int x) => -Verticals[Find(x)];
}