#370390 (C#(csc)) No.421 しろくろチョコレート

提出ソース

結果

問題	No.421 しろくろチョコレート
ユーザー	ひばち
提出日時	2019-08-17 23:58:22
言語	C#(csc) (csc 3.9.0)
結果	AC
実行時間	45 ms / 2,000 ms
コード長	9,366 bytes
コンパイル時間	1,952 ms
コンパイル使用メモリ	117,228 KB
実行使用メモリ	25,724 KB
最終ジャッジ日時	2023-10-24 14:58:50
合計ジャッジ時間	5,834 ms
ジャッジサーバーID （参考情報）	judge13 / judge15

このコードへのチャレンジ（β）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	34 ms 25,716 KB
testcase_01	AC	37 ms 25,716 KB
testcase_02	AC	35 ms 25,716 KB
testcase_03	AC	34 ms 25,716 KB
testcase_04	AC	36 ms 25,716 KB
testcase_05	AC	35 ms 25,716 KB
testcase_06	AC	35 ms 25,716 KB
testcase_07	AC	38 ms 25,716 KB
testcase_08	AC	35 ms 25,716 KB
testcase_09	AC	35 ms 25,716 KB
testcase_10	AC	34 ms 25,716 KB
testcase_11	AC	35 ms 25,716 KB
testcase_12	AC	34 ms 25,724 KB
testcase_13	AC	33 ms 25,724 KB
testcase_14	AC	34 ms 25,724 KB
testcase_15	AC	33 ms 25,724 KB
testcase_16	AC	37 ms 25,716 KB
testcase_17	AC	38 ms 20,356 KB
testcase_18	AC	39 ms 20,364 KB
testcase_19	AC	33 ms 19,712 KB
testcase_20	AC	36 ms 20,200 KB
testcase_21	AC	37 ms 20,264 KB
testcase_22	AC	36 ms 20,020 KB
testcase_23	AC	33 ms 19,712 KB
testcase_24	AC	33 ms 19,712 KB
testcase_25	AC	33 ms 19,712 KB
testcase_26	AC	34 ms 19,712 KB
testcase_27	AC	33 ms 21,760 KB
testcase_28	AC	35 ms 25,716 KB
testcase_29	AC	34 ms 25,716 KB
testcase_30	AC	37 ms 25,716 KB
testcase_31	AC	45 ms 25,716 KB
testcase_32	AC	37 ms 25,716 KB
testcase_33	AC	37 ms 25,716 KB
testcase_34	AC	33 ms 25,716 KB
testcase_35	AC	34 ms 25,716 KB
testcase_36	AC	35 ms 25,716 KB
testcase_37	AC	39 ms 25,716 KB
testcase_38	AC	42 ms 25,716 KB
testcase_39	AC	35 ms 25,716 KB
testcase_40	AC	36 ms 25,716 KB
testcase_41	AC	34 ms 25,716 KB
testcase_42	AC	34 ms 25,716 KB
testcase_43	AC	35 ms 25,716 KB
testcase_44	AC	38 ms 25,716 KB
testcase_45	AC	35 ms 25,716 KB
testcase_46	AC	35 ms 25,716 KB
testcase_47	AC	36 ms 25,716 KB
testcase_48	AC	42 ms 25,716 KB
testcase_49	AC	35 ms 25,716 KB
testcase_50	AC	34 ms 25,716 KB
testcase_51	AC	39 ms 25,716 KB
testcase_52	AC	36 ms 25,716 KB
testcase_53	AC	34 ms 25,716 KB
testcase_54	AC	34 ms 25,716 KB
testcase_55	AC	33 ms 25,716 KB
testcase_56	AC	35 ms 25,716 KB
testcase_57	AC	34 ms 25,716 KB
testcase_58	AC	37 ms 25,716 KB
testcase_59	AC	35 ms 25,716 KB
testcase_60	AC	44 ms 25,716 KB
testcase_61	AC	41 ms 25,716 KB
testcase_62	AC	33 ms 25,716 KB
testcase_63	AC	34 ms 25,716 KB
testcase_64	AC	33 ms 25,700 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

raw source code

using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using static System.Console;
using static System.Convert;
using static System.Math;
//using static System.Globalization.CultureInfo;
using System.Text;
class Program
{
    private static void chmin<T>(ref T num, T val) where T : IComparable<T>
        => num = num.CompareTo(val) == 1 ? val : num;
    private static void chmax<T>(ref T num, T val) where T : IComparable<T>
        => num = num.CompareTo(val) == -1 ? val : num;
    static void Main(string[] args)
    {
        var pr = new Program();
        var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
        Console.SetOut(sw);
        pr.Solve();
        Console.Out.Flush();
    }
    void Solve()
    {       
        int n, m;
        Input.Make(out n, out m);
        var grid = Input.grid(n);
        var gh = new[] { 0, 0, 1, -1 };
        var gw = new[] { 1, -1, 0, 0 };
        var f = new MaxFlow(n * m + 2);
        var ctw = 0;
        var ctb = 0;
        for (var i = 0; i < n; i++)
            for (var j = 0; j < m; j++)
                if (grid[i][j] != '.')
                {
                    if ((i + j) % 2 == 0) ctw++;
                    else { ctb++; continue; }
                    for(var k = 0; k < 4; k++)
                    {
                        var h = gh[k] + i;
                        var w = gw[k] + j;
                        if (!Inside(h, w, n, m)||grid[h][w]=='.') continue;
                        f.AddDirectedEdge(i * m + j, h * m + w, 1);
                    }
                }
        for(var i=0;i<n;i++)
            for(var j=0;j<m;j++)
                if (grid[i][j] != '.')
                {
                    if ((i + j) % 2 == 0)
                        f.AddDirectedEdge(n * m, i * m + j, 1);
                    else f.AddDirectedEdge(i * m + j, n * m + 1, 1);
                }
        var c = f.Execute(n * m, n * m + 1);
        ctw -= c;
        ctb -= c;
        WriteLine(100 * c + 10 * Min(ctw, ctb) + Abs(ctw - ctb));
    }

    public static bool Inside(int h, int w, int[] hw)
        => Inside(h, w, hw[0], hw[1]);
    public static bool Inside(int h, int w, int hh, int ww)
        => 0 <= h && h < hh && 0 <= w && w < ww;
}

public class Input
{
    public static string read => ReadLine().Trim();
    public static int[] ar => read.Split(' ').Select(int.Parse).ToArray();
    public static int num => ToInt32(read);
    public static long[] arL => read.Split(' ').Select(long.Parse).ToArray();
    public static long numL => ToInt64(read);
    public static T[] create<T>(int n, Func<int, T> f)
        => Enumerable.Repeat(0, n).Select(f).ToArray();
    public static char[][] grid(int h)
        => create(h, _ => read.ToCharArray());
    public static int[] ar1D(int n)
        => create(n, _ => num);
    public static long[] arL1D(int n)
        => create(n, _ => numL);
    public static string[] strs(int n)
        => create(n, _ => read);
    public static int[][] ar2D(int n)
        => create(n, _ => ar);
    public static long[][] arL2D(int n)
        => create(n, _ => arL);
    public static List<T>[] edge<T>(int n)
        => create(n, _ => new List<T>());
    public static T GetValue<T>(string g)
    {
        var t = typeof(T);
        if (t == typeof(int))
            return (T)(object)int.Parse(g);
        if (t == typeof(long))
            return (T)(object)long.Parse(g);
        if (t == typeof(string))
            return (T)(object)g;
        if (t == typeof(char))
            return (T)(object)char.Parse(g);
        if (t == typeof(double))
            return (T)(object)double.Parse(g);
        if (t == typeof(bool))
            return (T)(object)bool.Parse(g);
        return default(T);
    }
    public static void Make<T1, T2>(out T1 v1, out T2 v2)
    {
        v1 = Next<T1>();
        v2 = Next<T2>();
    }
    public static void Make<T1, T2, T3>(out T1 v1, out T2 v2, out T3 v3)
    {
        Make(out v1, out v2);
        v3 = Next<T3>();
    }
    public static void Make<T1, T2, T3, T4>(out T1 v1, out T2 v2, out T3 v3, out T4 v4)
    {
        Make(out v1, out v2, out v3);
        v4 = Next<T4>();
    }
    public static void Make<T1, T2, T3, T4, T5>(out T1 v1, out T2 v2, out T3 v3, out T4 v4, out T5 v5)
    {
        Make(out v1, out v2, out v3, out v4);
        v5 = Next<T5>();
    }
    public static void Make<T1, T2, T3, T4, T5, T6>(out T1 v1, out T2 v2, out T3 v3, out T4 v4, out T5 v5, out T6 v6)
    {
        Make(out v1, out v2, out v3, out v4, out v5);
        v6 = Next<T6>();
    }
    private static Queue<string> sc;
    public static T Next<T>(){ sc = sc ?? new Queue<string>(); if (sc.Count == 0) foreach (var item in read.Split(' ')) sc.Enqueue(item);return GetValue<T>(sc.Dequeue()); }
    public static void Next<T>(ref T val) => val = Next<T>(); 
    public const long Inf = (long)1e18;
    public const double eps = 1e-6;
    public const string Alfa = "abcdefghijklmnopqrstuvwxyz";
    public const int MOD = 1000000007;
}

public class Pair<T1, T2> : IComparable<Pair<T1, T2>>
{
    public T1 v1 { get; set; }
    public T2 v2 { get; set; }
    public Pair() { v1 = Input.Next<T1>(); v2 = Input.Next<T2>(); }
    public Pair(T1 v1, T2 v2)
    { this.v1 = v1; this.v2 = v2; }

    public int CompareTo(Pair<T1, T2> p)
    {
        var c = Comparer<T1>.Default.Compare(v1, p.v1);
        if (c == 0)
            c = Comparer<T2>.Default.Compare(v2, p.v2);
        return c;
    }
    public override string ToString()
        => $"{v1.ToString()} {v2.ToString()}";
    public override bool Equals(object obj)
        => this == (Pair<T1, T2>)obj;
    public override int GetHashCode()
        => v1.GetHashCode() ^ v2.GetHashCode();
    public static bool operator ==(Pair<T1, T2> p1, Pair<T1, T2> p2)
        => p1.CompareTo(p2) == 0;
    public static bool operator !=(Pair<T1, T2> p1, Pair<T1, T2> p2)
        => p1.CompareTo(p2) != 0;
    public static bool operator >(Pair<T1, T2> p1, Pair<T1, T2> p2)
        => p1.CompareTo(p2) == 1;
    public static bool operator >=(Pair<T1, T2> p1, Pair<T1, T2> p2)
        => p1.CompareTo(p2) != -1;
    public static bool operator <(Pair<T1, T2> p1, Pair<T1, T2> p2)
        => p1.CompareTo(p2) == -1;
    public static bool operator <=(Pair<T1, T2> p1, Pair<T1, T2> p2)
        => p1.CompareTo(p2) != 1;
}

public class Pair<T1, T2, T3> : Pair<T1, T2>, IComparable<Pair<T1, T2, T3>>
{
    public T3 v3 { get; set; }
    public Pair() : base() { v3 = Input.Next<T3>(); }
    public Pair(T1 v1, T2 v2, T3 v3) : base(v1, v2)
    { this.v3 = v3; }

    public int CompareTo(Pair<T1, T2, T3> p)
    {
        var c = base.CompareTo(p);
        if (c == 0)
            c = Comparer<T3>.Default.Compare(v3, p.v3);
        return c;
    }
    public override string ToString()
        => $"{base.ToString()} {v3.ToString()}";
}


public class MaxFlow
{
    readonly List<Edge>[] G;
    readonly int[] lv, iter;

    public MaxFlow(int V)
    {
        G = new List<Edge>[V];
        lv = new int[V];
        iter = new int[V];
        for (int i = 0; i < G.Length; i++)
            G[i] = new List<Edge>();
    }

    public void AddDirectedEdge(int from, int to, int cap)
        => addEdge(from, to, cap, 0);

    public void AddUndirectedEdge(int from, int to, int cap)
        => addEdge(from, to, cap, cap);

    void addEdge(int f, int t, int c1, int c2)
    {
        var a = new Edge(t, c1);
        var b = new Edge(f, c2);
        Edge.Link(a, b);
        G[f].Add(a);
        G[t].Add(b);
    }

    public int Execute(int src, int sink, int f = -1)
    {
        int flow = 0;
        if (f < 0) f = int.MaxValue;
        while (f > 0)
        {
            bfs(src);
            if (lv[sink] == 0) return flow;
            Array.Clear(iter, 0, iter.Length);
            int df;
            while ((df = dfs(src, sink, f)) > 0) { flow += df; f -= df; }
        }
        return flow;
    }

    void bfs(int s)
    {
        Array.Clear(lv, 0, lv.Length);
        var q = new Queue<int>();
        lv[s] = 1;
        q.Enqueue(s);
        while (q.Count > 0)
        {
            var v = q.Dequeue();
            foreach (var e in G[v])
                if (e.Cap > 0 && lv[e.To] == 0)
                {
                    lv[e.To] = lv[v] + 1;
                    q.Enqueue(e.To);
                }
        }

    }
    int dfs(int v, int t, int f)
    {
        if (v == t) return f;
        int ret = 0;
        for (; iter[v] < G[v].Count; iter[v]++)
        {
            var e = G[v][iter[v]];
            if (e.Cap <= 0 || lv[v] >= lv[e.To]) continue;
            int df = dfs(e.To, t, Math.Min(f, e.Cap));
            if (df <= 0) continue;
            e.Cap -= df;
            e.Rev.Cap += df;
            ret += df; f -= df;
            if (f == 0) break;
        }
        return ret;

    }
    class Edge
    {
        public static void Link(Edge e1, Edge e2)
        {
            e1.Rev = e2; e2.Rev = e1;
        }
        public int To { get; private set; }
        public Edge Rev { get; private set; }
        public int Cap { get; set; }
        public Edge(int t, int c)
        {
            To = t;
            Cap = c;
        }
        public override string ToString()
        {
            return string.Format("to: {0}, cap: {1}", To, Cap);
        }
    }
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード