#618325 (C#(csc)) No.1397 Analog Graffiti

提出ソース

結果

問題	No.1397 Analog Graffiti
ユーザー	りあん
提出日時	2021-02-14 22:49:17
言語	C#(csc) (csc 3.9.0)
結果	AC
実行時間	4,186 ms / 10,000 ms
コード長	14,517 bytes
コンパイル時間	2,740 ms
コンパイル使用メモリ	117,120 KB
実行使用メモリ	30,720 KB
最終ジャッジ日時	2024-07-22 10:44:03
合計ジャッジ時間	36,330 ms
ジャッジサーバーID （参考情報）	judge1 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	30 ms 18,560 KB
testcase_01	AC	30 ms 18,432 KB
testcase_02	AC	4,181 ms 30,720 KB
testcase_03	AC	30 ms 18,560 KB
testcase_04	AC	30 ms 18,560 KB
testcase_05	AC	4,186 ms 30,592 KB
testcase_06	AC	27 ms 18,048 KB
testcase_07	AC	27 ms 18,304 KB
testcase_08	AC	28 ms 18,432 KB
testcase_09	AC	30 ms 18,176 KB
testcase_10	AC	30 ms 18,688 KB
testcase_11	AC	4,092 ms 30,336 KB
testcase_12	AC	832 ms 25,728 KB
testcase_13	AC	4,005 ms 30,208 KB
testcase_14	AC	4,011 ms 30,592 KB
testcase_15	AC	85 ms 22,472 KB
testcase_16	AC	770 ms 25,984 KB
testcase_17	AC	3,744 ms 28,800 KB
testcase_18	AC	3,862 ms 30,208 KB
testcase_19	AC	36 ms 22,272 KB
testcase_20	AC	37 ms 22,400 KB
testcase_21	AC	70 ms 22,272 KB
testcase_22	AC	1,455 ms 25,472 KB
testcase_23	AC	79 ms 22,596 KB
testcase_24	AC	32 ms 19,200 KB
testcase_25	AC	231 ms 22,784 KB
testcase_26	AC	30 ms 18,944 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 System.Threading;
using System.Text;
using System.Text.RegularExpressions;
using System.Diagnostics;
using static util;
using P = pair<int, int>;

class Program {
    static void Main(string[] args) {
        var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
        var solver = new Solver(sw);
        // var t = new Thread(solver.solve, 1 << 28); // 256 MB
        // t.Start();
        // t.Join();
        solver.solve();
        sw.Flush();
    }
}

class Solver {
    StreamWriter sw;
    Scan sc;
    void Prt(string a) => sw.WriteLine(a);
    void Prt<T>(IEnumerable<T> a) => Prt(string.Join(" ", a));
    void Prt(params object[] a) => Prt(string.Join(" ", a));
    public Solver(StreamWriter sw) {
        this.sw = sw;
        this.sc = new Scan();
    }

    public void solve() {
        int w, h, n;
        sc.Multi(out w, out h, out n);
        var dp = new long[1 << h][][];
        for (int i = 0; i < (1 << h); i++)
        {
            dp[i] = new long[5][];
            for (int j = 0; j < 5; j++)
            {
                dp[i][j] = new long[n + 1];
            }
        }
        memo = new P[1 << h][][];
        for (int i = 0; i < (1 << h); i++)
        {
            memo[i] = new P[1 << h][];
            for (int j = 0; j < (1 << h); j++)
            {
                memo[i][j] = new P[5];
            }
        }
        long ans = 0;
        cnt = new int[1 << h];
        for (int i = 1; i < (1 << h); i++)
        {
            int c = 0;
            for (int j = 0; j < h; j++)
            {
                if (((i >> j) & 1) == 1 && (j == 0 || ((i >> (j - 1)) & 1) == 0)) {
                    ++c;
                }
            }
            cnt[i] = c;
            if (c * 4 <= n) {
                if (c == 1) {
                    ++dp[i][0][c * 4];
                }
                else if (c == 2) {
                    ++dp[i][1][c * 4];
                }
                else {
                    ++dp[i][4][c * 4];
                }
            }
            ans += dp[i][0][n] * w;
        }
        for (int t = w - 1; t > 0 ; t--)
        {
            var nex = new long[1 << h][][];
            for (int i = 0; i < (1 << h); i++)
            {
                nex[i] = new long[5][];
                for (int j = 0; j < 5; j++)
                {
                    nex[i][j] = new long[n + 1];
                }
            }
            for (int i = 1; i < (1 << h); i++)
            {
                for (int j = 0; j < 5; j++)
                {
                    for (int k = 0; k < n + 1; k++)
                    {
                        if (dp[i][j][k] == 0) continue;
                        // Assert(k % 2 == 0);
                        for (int l = 1; l < (1 << h); l++)
                        {
                            var nx = next(h, i, l, j);
                            // DBG(nx);
                            if (nx.v1 == -1) continue;
                            if (k + nx.v2 <= n) {
                                nex[l][nx.v1][k + nx.v2] = (nex[l][nx.v1][k + nx.v2] + dp[i][j][k]) % M;
                            }
                        }
                    }
                }
            }
            dp = nex;
            for (int i = 1; i < (1 << h); i++) {
                ans = (ans + dp[i][0][n] * t) % M;
            }
        }
        Prt(ans);
    }
    int[] cnt;
    P[][][] memo;

    int calc_c(int h, int b1, int b2) {
        int res = 0;
        {
            int c = 0;
            c += (b1 >> 0) & 1;
            c += (b2 >> 0) & 1;
            if (c % 2 == 1) ++res;
        }
        {
            int c = 0;
            c += (b1 >> (h - 1)) & 1;
            c += (b2 >> (h - 1)) & 1;
            if (c % 2 == 1) ++res;
        }
        for (int i = 0; i < h - 1; i++)
        {
            int c = 0;
            c += (b1 >> i) & 1;
            c += (b1 >> (i + 1)) & 1;
            c += (b2 >> i) & 1;
            c += (b2 >> (i + 1)) & 1;
            if (c % 2 == 1) ++res;
        }
        return res;
    }
    int calc_diff(int h, int b1, int b2) {
        return -calc_c(h, b1, 0) + calc_c(h, b1, b2) + calc_c(h, b2, 0);
    }

    bool check1(int h, int b1, int b2) {
        for (int i = 0; i < h - 1; i++)
        {
            bool b11 = ((b1 >> i) & 1) == 1;
            bool b12 = ((b1 >> (i + 1)) & 1) == 1;
            bool b21 = ((b2 >> i) & 1) == 1;
            bool b22 = ((b2 >> (i + 1)) & 1) == 1;
            if (b11 && b22 && !b12 && !b21) {
                return false;
            }
            if (!b11 && !b22 && b12 && b21) {
                return false;
            }
        }
        return true;
    }
    int next_con(int h, int b1, int b2, int con) {
        var uf = new UnionFind(h * 2);
        var b = new bool[2][];
        b[0] = new bool[h];
        b[1] = new bool[h];
        var l1 = new List<int>();
        for (int j = 0; j < h; j++)
        {
            if (((b1 >> j) & 1) == 1 && (j == 0 || ((b1 >> (j - 1)) & 1) == 0)) {
                l1.Add(j);
            }
        }

        for (int i = 0; i < h; i++)
        {
            b[0][i] = ((b1 >> i) & 1) == 1;
            b[1][i] = ((b2 >> i) & 1) == 1;
        }
        for (int i = 0; i < h; i++)
        {
            if (b[0][i] && b[1][i]) {
                uf.unite(i, h + i);
            }
            for (int j = 0; j < 2; j++)
            {
                if (i + 1 < h && b[j][i] && b[j][i + 1]) {
                    uf.unite(j * h + i, j * h + i + 1);
                }
            }
        }
        if (cnt[b1] == 2 && con == 0) {
            if (!uf.unite(l1[0], l1[1])) {
                return -1;
            }
        }
        if (cnt[b1] == 3) {
            if (con == 0) {
                if (!uf.unite(l1[0], l1[1])) {
                    return -1;
                }
                if (!uf.unite(l1[0], l1[2])) {
                    return -1;
                }
            }
            else if (con == 1) {
                if (!uf.unite(l1[0], l1[1])) {
                    return -1;
                }
            }
            else if (con == 2) {
                if (!uf.unite(l1[0], l1[2])) {
                    return -1;
                }
            }
            else if (con == 3) {
                if (!uf.unite(l1[1], l1[2])) {
                    return -1;
                }
            }
        }
        foreach (var item in l1)
        {
            bool cc = false;
            for (int i = 0; i < h; i++)
            {
                cc |= uf.same(item, h + i);
            }
            if (!cc) {
                return -1;
            }
        }
        var l2 = new List<int>();
        for (int j = 0; j < h; j++)
        {
            if (((b2 >> j) & 1) == 1 && (j == 0 || ((b2 >> (j - 1)) & 1) == 0)) {
                l2.Add(j);
            }
        }
        if (cnt[b2] == 1) {
            return 0;
        }
        else if (cnt[b2] == 2) {
            if (uf.same(h + l2[0], h + l2[1])) {
                return 0;
            }
            else {
                return 1;
            }
        }
        else {
            if (uf.same(h + l2[0], h + l2[1]) && uf.same(h + l2[0], h + l2[2])) {
                return 0;
            }
            else if (uf.same(h + l2[0], h + l2[1])) {
                return 1;
            }
            else if (uf.same(h + l2[0], h + l2[2])) {
                return 2;
            }
            else if (uf.same(h + l2[1], h + l2[2])) {
                return 3;
            }
            else {
                return 4;
            }
        }
    }
    P next(int h, int b1, int b2, int con) {
        if (memo[b1][b2][con] != null) {
            return memo[b1][b2][con];
        }
        if (!check1(h, b1, b2)) {
            return new P(-1, -1);
        }
        int nex_con = next_con(h, b1, b2, con);
        if (nex_con == -1) {
            return new P(-1, -1);
        }
        int diff = calc_diff(h, b1, b2);
        return new P(nex_con, diff);
    }

}

class pair<T, U> : IComparable<pair<T, U>> {
    public T v1;
    public U v2;
    public pair() : this(default(T), default(U)) {}
    public pair(T v1, U v2) { this.v1 = v1; this.v2 = v2; }
    public int CompareTo(pair<T, U> a) {
        int c = Comparer<T>.Default.Compare(v1, a.v1);
        return c != 0 ? c : Comparer<U>.Default.Compare(v2, a.v2);
    }
    public override string ToString() => $"{v1} {v2}";
    public void Deconstruct(out T a, out U b) { a = v1; b = v2; }
}
static class util {
    // public static readonly int M = 1000000007;
    public static readonly int M = 998244353;
    public static readonly long LM = 1L << 60;
    public static readonly double eps = 1e-11;
    public static void DBG(string a) => Console.Error.WriteLine(a);
    public static void DBG<T>(IEnumerable<T> a) => DBG(string.Join(" ", a));
    public static void DBG(params object[] a) => DBG(string.Join(" ", a));
    public static void Assert(params bool[] conds) {
        if (conds.Any(x => !x)) throw new Exception();
    }
    public static pair<T, U> make_pair<T, U>(T v1, U v2) => new pair<T, U>(v1, v2);
    public static int CompareList<T>(IList<T> a, IList<T> b) where T : IComparable<T> {
        for (int i = 0; i < a.Count && i < b.Count; i++)
            if (a[i].CompareTo(b[i]) != 0) return a[i].CompareTo(b[i]);
        return a.Count.CompareTo(b.Count);
    }
    public static bool inside(int i, int j, int h, int w) => i >= 0 && i < h && j >= 0 && j < w;
    public static readonly int[] dd = { 0, 1, 0, -1 };
    // static readonly string dstring = "RDLU";
    public static IEnumerable<P> adjacents(int i, int j) {
        for (int k = 0; k < 4; k++) yield return new P(i + dd[k], j + dd[k ^ 1]);
    }
    public static IEnumerable<P> adjacents(int i, int j, int h, int w) {
        for (int k = 0; k < 4; k++) if (inside(i + dd[k], j + dd[k ^ 1], h, w))
            yield return new P(i + dd[k], j + dd[k ^ 1]);
    }
    public static IEnumerable<P> adjacents(this P p) => adjacents(p.v1, p.v2);
    public static IEnumerable<P> adjacents(this P p, int h, int w) => adjacents(p.v1, p.v2, h, w);
    public static IEnumerable<int> all_subset(this int p) {
        for (int i = 0; ; i = i - p & p) {
            yield return i;
            if (i == p) break;
        }
    }
    public static Dictionary<T, int> compress<T>(this IEnumerable<T> a)
        => a.Distinct().OrderBy(v => v).Select((v, i) => new { v, i }).ToDictionary(p => p.v, p => p.i);
    public static Dictionary<T, int> compress<T>(params IEnumerable<T>[] a)
        => compress(a.SelectMany(x => x));
    public static T[] inv<T>(this Dictionary<T, int> dic) {
        var res = new T[dic.Count];
        foreach (var item in dic) res[item.Value] = item.Key;
        return res;
    }
    public static void swap<T>(ref T a, ref T b) where T : struct { var t = a; a = b; b = t; }
    public static void swap<T>(this IList<T> a, int i, int j) where T : struct {
        var t = a[i]; a[i] = a[j]; a[j] = t;
    }
    public static T[] copy<T>(this IList<T> a) {
        var ret = new T[a.Count];
        for (int i = 0; i < a.Count; i++) ret[i] = a[i];
        return ret;
    }
}

class Scan {
    StreamReader sr;
    public Scan() { sr = new StreamReader(Console.OpenStandardInput()); }
    public Scan(string path) { sr = new StreamReader(path); }
    public int Int => int.Parse(Str);
    public long Long => long.Parse(Str);
    public double Double => double.Parse(Str);
    public string Str => ReadLine.Trim();
    public string ReadLine => sr.ReadLine();
    public pair<T, U> Pair<T, U>() {
        T a; U b;
        Multi(out a, out b);
        return new pair<T, U>(a, b);
    }
    public P P => Pair<int, int>();
    public int[] IntArr => StrArr.Select(int.Parse).ToArray();
    public long[] LongArr => StrArr.Select(long.Parse).ToArray();
    public double[] DoubleArr => StrArr.Select(double.Parse).ToArray();
    public string[] StrArr => Str.Split(new[]{' '}, StringSplitOptions.RemoveEmptyEntries);
    bool eq<T, U>() => typeof(T).Equals(typeof(U));
    T ct<T, U>(U a) => (T)Convert.ChangeType(a, typeof(T));
    T cv<T>(string s) => eq<T, int>()    ? ct<T, int>(int.Parse(s))
                       : eq<T, long>()   ? ct<T, long>(long.Parse(s))
                       : eq<T, double>() ? ct<T, double>(double.Parse(s))
                       : eq<T, char>()   ? ct<T, char>(s[0])
                                         : ct<T, string>(s);
    public void Multi<T>(out T a) => a = cv<T>(Str);
    public void Multi<T, U>(out T a, out U b) {
        var ar = StrArr; a = cv<T>(ar[0]); b = cv<U>(ar[1]);
    }
    public void Multi<T, U, V>(out T a, out U b, out V c) {
        var ar = StrArr; a = cv<T>(ar[0]); b = cv<U>(ar[1]); c = cv<V>(ar[2]);
    }
    public void Multi<T, U, V, W>(out T a, out U b, out V c, out W d) {
        var ar = StrArr; a = cv<T>(ar[0]); b = cv<U>(ar[1]); c = cv<V>(ar[2]); d = cv<W>(ar[3]);
    }
    public void Multi<T, U, V, W, X>(out T a, out U b, out V c, out W d, out X e) {
        var ar = StrArr;
        a = cv<T>(ar[0]); b = cv<U>(ar[1]); c = cv<V>(ar[2]); d = cv<W>(ar[3]); e = cv<X>(ar[4]);
    }
    public void Multi<T, U, V, W, X, Y>(out T a, out U b, out V c, out W d, out X e, out Y f) {
        var ar = StrArr;
        a = cv<T>(ar[0]); b = cv<U>(ar[1]); c = cv<V>(ar[2]);
        d = cv<W>(ar[3]); e = cv<X>(ar[4]); f = cv<Y>(ar[5]);
    }
}
class UnionFind {
    int num;
    int[] par, sz, rank;
    public UnionFind(int n) {
        num = n;
        par = new int[n];
        sz = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; ++i) {
            par[i] = i;
            sz[i] = 1;
            rank[i] = 0;
        }
    }
    int find(int x) => par[x] == x ? x : (par[x] = find(par[x]));
    public bool same(int x, int y) => find(x) == find(y);
    public int unionsize(int x) => sz[find(x)];
    public int unioncount => num;
    public bool unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return false;
        --num;
        if (rank[x] < rank[y]) {
            par[x] = y;
            sz[y] += sz[x];
        }
        else {
            par[y] = x;
            sz[x] += sz[y];
            if (rank[x] == rank[y]) ++rank[x];
        }
        return true;
    }
    public bool ispar(int x) => x == find(x);
    public int getpar(int x) => find(x);
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード