結果

問題 No.3173 じゃんけんの勝ちの回数
ユーザー tobisatis
提出日時 2025-06-06 22:14:04
言語 C#
(.NET 8.0.404)
結果
AC  
実行時間 210 ms / 2,000 ms
コード長 5,904 bytes
コンパイル時間 11,340 ms
コンパイル使用メモリ 171,328 KB
実行使用メモリ 223,016 KB
最終ジャッジ日時 2025-06-06 22:14:24
合計ジャッジ時間 16,705 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 33
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (116 ミリ秒)。
  main -> /home/judge/data/code/bin/Release/net8.0/main.dll
  main -> /home/judge/data/code/bin/Release/net8.0/publish/

ソースコード

diff # 

#nullable enable

using System.Numerics;

void Run()
{
    var t = Int();
    var minz = new int[t];
    var maxz = new int[t];
    int Max(int[] az, int[] bz)
    {
        var res = 0;
        for (var j = 0; j < 3; j++)
        {
            var k = j + 1;
            if (k == 3) k = 0;
            var d = Math.Min(az[j], bz[k]);
            res += d;
            az[j] -= d;
            bz[k] -= d;
        }
        return res;
    }
    int Min(int[] az, int[] bz)
    {
        var f = new MaximumFlow(8);
        var s = 6;
        var t = s + 1;
        for (var i = 0; i < 3; i++)
        {
            f.AddEdge(s, i, az[i]);
            f.AddEdge(i + 3, t, bz[i]);
            f.AddEdge(i, i + 3, int.MaxValue);
        }
        f.AddEdge(0, 5, int.MaxValue);
        f.AddEdge(1, 3, int.MaxValue);
        f.AddEdge(2, 4, int.MaxValue);
        var ans = (long)az.Sum() - f.Flow(s, t);
        return (int)ans;
    }
    for (var i = 0; i < t; i++)
    {
        var az = 3.Repeat(Int);
        var bz = 3.Repeat(Int);
        maxz[i] = Max(az.AsSpan().ToArray(), bz.AsSpan().ToArray());
        minz[i] = Min(az.AsSpan().ToArray(), bz.AsSpan().ToArray());
    }
    for (var i = 0; i < t; i++) Out(minz[i] + " " + maxz[i]);
}

#region
var _io_ = new AtCoderIO(){ Backend = new() };
Run();
_io_.Backend.Flush();

string String() => _io_.Next();
int Int() => int.Parse(String());
void Out(object? x, string? sep = null) => _io_.Out(x, sep);

class AtCoderIO
{
    public required StandardIOBackend Backend { get; init; }

    ReadOnlyMemory<string> _input = Array.Empty<string>();
    int _iter = 0;
    public string Next()
    {
        while (_iter >= _input.Length) (_input, _iter) = (Backend.ReadLine().Split(' '), 0);
        return _input.Span[_iter++];
    }

    public void Out(object? x, string? separator = null)
    {
        if (x == null) return;
        separator ??= Environment.NewLine;
        if (x is System.Collections.IEnumerable a and not string)
        {
            var objects = a.Cast<object>();
            if (separator == Environment.NewLine && !objects.Any()) return;
            x = string.Join(separator, objects);
        }
        Backend.WriteLine(x);
    }
}

class StandardIOBackend
{
    readonly StreamReader _sr = new(Console.OpenStandardInput());
    readonly StreamWriter _sw = new(Console.OpenStandardOutput()) { AutoFlush = false };
    public string ReadLine() => _sr.ReadLine()!;
    public void WriteLine(object? value) => _sw.WriteLine(value);
    public void Flush() => _sw.Flush();
}
#endregion

static class Extensions
{
    public static T[] Repeat<T>(this int time, Func<T> F) => Enumerable.Range(0, time).Select(_ => F()).ToArray();
}

class MaximumFlow
{
    int N { get; init; }
    List<(int next, long capacity, int reverse)> Edges { get; init; }
    List<int>[] G { get; init; }
    int[] Depths { get; set; } = Array.Empty<int>();
    int[] Iter { get; set; } = Array.Empty<int>();

    public MaximumFlow(int n)
    {
        N = n;
        Edges = new List<(int, long, int)>();
        G = new List<int>[n];
        for (var i = 0; i < n; i++) G[i] = new List<int>();
    }

    public void AddEdge(int ab, int ad, long capacity)
    {
        G[ab].Add(Edges.Count);
        Edges.Add((ad, capacity, Edges.Count + 1));
        G[ad].Add(Edges.Count);
        Edges.Add((ab, 0, Edges.Count - 1));
    }

    public long Flow(int s, int t) // s must not be equal to t
    {
        var res = 0L;
        SetDepths(s);
        while (Depths[t] >= 0)
        {
            Iter = new int[N];
            long f;
            while ((f = Flow(s, t, long.MaxValue)) > 0) res += f;
            SetDepths(s);
        }
        return res;
    }

    void SetDepths(int s)
    {
        var (n, depths, g, edges) = (N, new int[N], G, Edges);
        for (var i = 0; i < n; i++) depths[i] = -1;
        depths[s] = 0;
        var q = new Queue<int>();
        q.Enqueue(s);
        while (q.Count > 0)
        {
            var v = q.Dequeue();
            var w = depths[v] + 1;
            foreach (var e in g[v])
            {
                var (next, capacity, _) = edges[e];
                if (capacity == 0 || depths[next] >= 0) continue;
                depths[next] = w;
                q.Enqueue(next);
            }
        }
        Depths = depths;
    }

    long Flow(int v, int t, long f)
    {
        if (v == t) return f;
        var (az, depths, edges) = (G[v], Depths, Edges);
        var (ac, depth) = (az.Count, depths[v]);
        for (ref var i = ref Iter[v]; i < ac; i++)
        {
            var e = az[i];
            var (next, capacity, reverse) = edges[e];
            if (capacity == 0 || depths[next] <= depth) continue;
            var d = Flow(next, t, Math.Min(f, capacity));
            if (d == 0) continue;
            edges[e] = (next, capacity - d, reverse);
            edges[reverse] = (v, edges[reverse].capacity + d, e);
            return d;
        }
        return 0;
    }

    public List<(int edgeIndex, int ab, int ad)> MinCutEdges(int start)
    {
        var reachable = new HashSet<int>{ start };
        var q = new Queue<int>();
        q.Enqueue(start);
        while (q.Count > 0)
        {
            var v = q.Dequeue();
            foreach (var edgeIndex in G[v])
            {
                var edge = Edges[edgeIndex];
                if (edge.capacity == 0) continue;
                var next = edge.next;
                if (reachable.Contains(next)) continue;
                reachable.Add(next);
                q.Enqueue(next);
            }
        }
        var res = new List<(int, int, int)>();
        for (var i = 0; i < Edges.Count; i += 2)
        {
            var ad = Edges[i].next;
            var ab = Edges[i + 1].next;
            if (reachable.Contains(ab) ^ reachable.Contains(ad)) res.Add((i, ab, ad));
        }
        return res;
    }
}
0