結果

問題 No.3345 Reducible Sequence
コンテスト
ユーザー tobisatis
提出日時 2025-11-13 21:57:08
言語 C#
(.NET 8.0.404)
結果
AC  
実行時間 501 ms / 2,000 ms
コード長 4,546 bytes
コンパイル時間 11,196 ms
コンパイル使用メモリ 171,308 KB
実行使用メモリ 197,768 KB
最終ジャッジ日時 2025-11-13 21:57:43
合計ジャッジ時間 17,241 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (145 ミリ秒)。
  main -> /home/judge/data/code/bin/Release/net8.0/main.dll
  main -> /home/judge/data/code/bin/Release/net8.0/publish/

ソースコード

diff # 

#nullable enable

#region
var (_input, _iter) = (Array.Empty<string>(), 0);
T I<T>() where T : IParsable<T>
{
    while (_iter >= _input.Length) (_input, _iter) = (Console.ReadLine()!.Split(' '), 0);
    return T.Parse(_input[_iter++], null);
}
#endregion

static T[] Range<T>(int n, Func<T> F) => Enumerable.Range(0, n).Select(_ => F()).ToArray();

var n = I<int>();
var az = Range(n, I<int>);

var divz = new List<int>[n];
for (var i = 0; i < n; i++)
{
    var a = az[i];
    var al = new List<int>();
    for (var j = 1; j <= 80; j++)
    {
        if (a % j == 0)
        {
            var k = a / j;
            al.Add(j);
            if (k > j) al.Add(k);
        }
    }
    al.Sort();
    divz[i] = al;
}

bool Solve(int x)
{
    var g = new MaximumFlow(n + x + 2);
    var s = 0;
    var t = n + x + 1;
    for (var i = 1; i <= n; i++) g.AddEdge(s, i, 1);
    for (var i = 1; i <= x; i++) g.AddEdge(i + n, t, 1);
    for (var i = 1; i <= n; i++)
    {
        var al = divz[i - 1];
        foreach (var div in al)
        {
            if (div > x) break;
            g.AddEdge(i, div + n, 1);
        }
    }
    var f = g.Flow(s, t);
    return f >= x;
}

var pass = 1;
var fail = n + 1;
while (Math.Abs(pass - fail) > 1)
{
    var mid = (pass + fail) >> 1;
    if (Solve(mid)) pass = mid;
    else fail = mid;
}
Console.WriteLine(pass);

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