読者です 読者をやめる 読者になる 読者になる

うにゅーん、って感じだ

SRM, CF, AtCoder黄. SRM highest:1746. C#を書きます.

Saiko~ No Contesuto #02

普通に面白くてウケるw、って感じ。


A : 出力に自明に奇数が出ないことに気づかなくて1WA、かなしい

B : 全ての目を同じ数字、{ N }の約数にすればよい。
約数列挙が{ O(\sqrt{N}) }、それらの約数と各マス目の値をソートし、マス目の累積和を持っておくと、その後の処理が{ O(d(N) + M) }({ d(N) }{ N }の約数の個数)で行える。計算量は、約数の個数のオーダーは自明に{ \sqrt{N} }以下な気がするので{ O(max(\sqrt{N} \log N, M)) }かなぁ。

using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Text;
using System.Numerics;

namespace Solver
{
    class Program
    {
        const int M = 1000000007;
        const double eps = 1e-9;
        static void Main()
        {
            var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            var sc = new Scan();
            long n;
            int m;
            sc.Multi(out n, out m);
            var a = sc.LongArr;
            Array.Sort(a);
            var sum = new long[m + 1];
            for (int i = 0; i < m; i++)
                sum[i + 1] = sum[i] + a[i];

            var list = new List<long>();
            for (long i = 1; i * i <= n; i++)
            {
                if (n % i == 0)
                {
                    list.Add(i);
                    if (i * i < n)
                        list.Add(n / i);
                }
            }
            list.Sort();
            long min = long.MaxValue;
            int j = 0;
            foreach (var item in list)
            {
                for (; ; j++)
                {
                    if (a[j] >= item)
                    {
                        min = Math.Min(min, sum[m] - sum[j] * 2 + item * (j * 2 - m));
                        break;
                    }
                    else if (j == m - 1)
                    {
                        min = Math.Min(min, item * m - sum[m]);
                        break;
                    }
                }
            }
            sw.WriteLine(min);
            sw.Flush();
        }
    }
    class Scan
    {
        // 略
    }
}

C : 初期状態で頂点1からの距離の異なる点にいる車同士は同時に同じ道を通らない(頂点1からの距離が{ d }な点と{ d + 1 }な点を結ぶ辺は、初期状態で頂点1からの距離が{ x }である点にいた車は時刻{ x - d}にしか通れないため)ので、各点の頂点1からの距離やら、頂点1からの距離が同じである点の集合やらを持っておいて、あとは使ってよい辺に容量1の有向辺を張り、各集合に対して最大流をしてやって答えを出すことができる。計算量に関してはdinicの計算量がよくわからんのでよくわからん。

using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Text;
using System.Numerics;

namespace Solver
{
    class Program
    {
        const int M = 1000000007;
        const double eps = 1e-9;
        static void Main()
        {
            var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            var sc = new Scan();
            int n, m;
            sc.Multi(out n, out m);
            var a = sc.IntArr;
            var e = new int[m][];
            var edge = new List<int>[n];
            var dist = new int[n];
            var d = new List<int>[n];
            for (int i = 0; i < n; i++)
            {
                edge[i] = new List<int>();
                d[i] = new List<int>();
                dist[i] = M;
            }
            dist[0] = 0;
            for (int i = 0; i < m; i++)
            {
                e[i] = sc.IntArr;
                --e[i][0];
                --e[i][1];
                edge[e[i][0]].Add(e[i][1]);
                edge[e[i][1]].Add(e[i][0]);
            }
            var q = new Queue<int>();
            q.Enqueue(0);
            while (q.Count > 0)
            {
                var p = q.Dequeue();
                foreach (var item in edge[p])
                {
                    if (dist[item] > dist[p] + 1)
                    {
                        dist[item] = dist[p] + 1;
                        d[dist[item]].Add(item);
                        q.Enqueue(item);
                    }
                }
            }
            for (int i = 1; i < n; ++i)
            {
                if (d[i].Count == 0)
                    continue;

                var mf = new MaxFlow(n + 1);
                foreach (var item in e)
                {
                    if (dist[item[0]] <= i && dist[item[1]] <= i)
                    {
                        if (dist[item[0]] + 1 == dist[item[1]])
                            mf.add_edge(item[1], item[0], 1, true);
                        else if (dist[item[1]] + 1 == dist[item[0]])
                            mf.add_edge(item[0], item[1], 1, true);
                    }
                }
                int sum = 0;
                foreach (var j in d[i])
                {
                    sum += a[j - 1];
                    mf.add_edge(n, j, a[j - 1], true);
                }
                if (mf.run(n, 0) < sum)
                {
                    sw.WriteLine("PANIC");
                    sw.Flush();
                    return;
                }
            }
            sw.WriteLine("NO PANIC");
            sw.Flush();
        }
    }
    class Scan
    {
        // 略
    }
    class MaxFlow
    {
        class edge { public int to, cap, rev; }
        int V;
        List<edge>[] G;
        int[] itr, level;

        public MaxFlow(int V) // V : ten no kazu
        {
            this.V = V;
            G = new List<edge>[V];
            for (int i = 0; i < V; ++i)
                G[i] = new List<edge>();
        }

        public void add_edge(int from, int to, int cap, bool IsDirection)
        {
            G[from].Add(new edge { to = to, cap = cap, rev = G[to].Count });
            if (IsDirection)
                G[to].Add(new edge { to = from, cap = 0, rev = G[from].Count - 1 });
            else
                G[to].Add(new edge { to = from, cap = cap, rev = G[from].Count - 1 });
        }

        void bfs(int s)
        {
            level = new int[V];
            for (int i = 0; i < V; ++i)
                level[i] = -1;

            Queue<int> q = new Queue<int>();
            level[s] = 0;
            q.Enqueue(s);
            while (q.Count > 0)
            {
                int v = q.Dequeue();
                foreach (edge e in G[v])
                {
                    if (e.cap > 0 && level[e.to] < 0)
                    {
                        level[e.to] = level[v] + 1;
                        q.Enqueue(e.to);
                    }
                }
            }
        }

        int dfs(int v, int t, int f)
        {
            if (v == t) return f;
            for (int i = itr[v]; i < (int)G[v].Count; ++i)
            {
                edge e = G[v][i];
                if (e.cap > 0 && level[v] < level[e.to])
                {
                    int d = dfs(e.to, t, Math.Min(f, e.cap));
                    if (d > 0)
                    {
                        e.cap -= d;
                        G[e.to][e.rev].cap += d;
                        return d;
                    }
                }
            }
            return 0;
        }

        public int run(int s, int t)
        {
            int ret = 0, f;
            bfs(s);
            while (level[t] >= 0)
            {
                itr = new int[V];
                while ((f = dfs(s, t, Int32.MaxValue)) > 0)
                    ret += f;

                bfs(s);
            }
            return ret;
        }
    }
}