結果

問題 No.563 超高速一人かるた large
ユーザー RisenRisen
提出日時 2017-08-27 15:49:01
言語 C#(csc)
(csc 3.9.0)
結果
TLE  
実行時間 -
コード長 7,485 bytes
コンパイル時間 2,660 ms
コンパイル使用メモリ 116,692 KB
実行使用メモリ 48,552 KB
最終ジャッジ日時 2024-11-06 06:44:54
合計ジャッジ時間 9,649 ms
ジャッジサーバーID
(参考情報)
judge5 / judge1
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 48 ms
28,152 KB
testcase_01 AC 48 ms
28,260 KB
testcase_02 AC 44 ms
25,608 KB
testcase_03 AC 426 ms
33,928 KB
testcase_04 AC 2,668 ms
38,920 KB
testcase_05 TLE -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff #

using System;
using System.Collections.Generic;
using System.Numerics;
using System.Linq;
using static Common;

public static class Common
{
    public const int Mod = 1000000007;

    // nPk
    private static Dictionary<Tuple<int, int>, BigInteger> perms = new Dictionary<Tuple<int, int>, BigInteger>();
    public static BigInteger CalcPermutation(int n, int k)
    {
        var key = Tuple.Create(n, k);
        if (perms.ContainsKey(key))
        {
            return perms[key];
        }

        var v = Enumerable.Range(n - k + 1, k).Aggregate(BigInteger.One, (p, next) => p * next);
        perms[key] = v;
        return v;
    }

    // nCk
    private static Dictionary<Tuple<int, int>, BigInteger> combs = new Dictionary<Tuple<int, int>, BigInteger>();
    public static BigInteger CalcCombination(int n, int k)
    {
        var key = Tuple.Create(n, k);
        if (combs.ContainsKey(key))
        {
            return combs[key];
        }

        var v = CalcPermutation(n, k);
        for (int i = 2; i <= k; i++)
        {
            v /= i;
        }
        combs[key] = v;
        return v;
    }
}

public class PatriciaNode
{
    public string Fullstr { private set; get; }
    public string Str;
    public PatriciaNode Parent;
    public List<PatriciaNode> Children = new List<PatriciaNode>();
    public int DescendantCount { private set; get; }

    public PatriciaNode()
    {
    }

    public PatriciaNode(string str)
    {
        Fullstr = str;
    }

    public void SetFullStr(string parentName = "")
    {
        Fullstr = parentName + Str;
        foreach (var child in Children)
        {
            child.SetFullStr(Fullstr);
        }
    }

    public int SetDescendantCount()
    {
        int count = 0;
        foreach (var child in Children)
        {
            count += child.SetDescendantCount();
        }
        DescendantCount = count;
        return Math.Max(1, DescendantCount);
    }

    public long GetExpectedLength(int removeCount, int otherCount)
    {
        // 削除する必要のある子孫の数, 決まり字までの文字列長
        var parents = new List<Tuple<int, int>>();

        for (var node = Parent; node != null; node = node.Parent)
        {
            var len = node.Parent == null ? 1 : node.Parent.Fullstr.Length + 1;
            parents.Add(Tuple.Create(node.DescendantCount - 1, len));
        }

        var allPattern = CalcPermutation(otherCount, removeCount);
        var removes = parents.Select(p => p.Item1).ToArray();
        var patterns = removes.Select(r =>
        {
            if (r > removeCount)
            {
                return 0;
            }
            // 削除対象の組み合わせ * 残りの組み合わせ * 並べ方
            var remComb = CalcCombination(r, r);
            var otherComb = CalcCombination(otherCount - r, removeCount - r);
            return remComb * otherComb * CalcPermutation(removeCount, removeCount);
        }).ToList();
        patterns.Add(0);

        long expects = 0;
        for (int i = 0; i < parents.Count; i++)
        {
            // 重複するので,上位のパターンを除く
            expects += (long)(((patterns[i] - patterns[i + 1]) * parents[i].Item2) % Mod);
        }

        var remainPattern = allPattern - patterns.First();
        expects += (long)((remainPattern * (Parent.Fullstr.Length + 1)) % Mod);
        expects %= Mod;
        return expects;
    }

    public override string ToString()
    {
        return $" {Fullstr}: DescendantCount:{DescendantCount}";
    }
}

public class PatriciaTree
{
    public PatriciaNode Root;

    public PatriciaTree()
    {
        Root = new PatriciaNode();
        Root.Str = "";
    }

    public void Add(string str)
    {
        var node = new PatriciaNode(str);
        if (Root == null)
        {
            node.Str = str;
            Root = node;
            return;
        }

        var parent = Root;
        for (var s = str; ;)
        {
            // 部分的にしか合致しないので,共通部を親にして子になる
            if (!s.StartsWith(parent.Str))
            {
                int sameCount;
                for (sameCount = 0; true; sameCount++)
                {
                    if (s[sameCount] != parent.Str[sameCount])
                    {
                        break;
                    }
                }
                var overlap = s.Substring(0, sameCount);
                var newParent = new PatriciaNode
                {
                    Str = overlap,
                    Parent = parent.Parent
                };
                newParent.Parent.Children.Remove(parent);
                newParent.Parent.Children.Add(newParent);
                newParent.Children.Add(parent);
                newParent.Children.Add(node);
                parent.Parent = newParent;
                parent.Str = parent.Str.Substring(sameCount);

                node.Parent = newParent;
                node.Str = s.Substring(sameCount);
                return;
            }

            s = s.Substring(parent.Str.Length);
            bool found = false;
            foreach (var child in parent.Children)
            {
                if (s[0] == child.Str[0])
                {
                    parent = child;
                    found = true;
                    break;
                }
            }

            // 新しいChildになる
            if (!found)
            {
                node.Str = s;
                node.Parent = parent;
                parent.Children.Add(node);
                return;
            }
        }
    }

    public List<PatriciaNode> GetEdges()
    {
        var edges = new List<PatriciaNode>();
        var nodes = new List<PatriciaNode> { Root };
        while (nodes.Count > 0)
        {
            var children = new List<PatriciaNode>();
            foreach (var node in nodes)
            {
                if (node.Children.Count == 0)
                {
                    edges.Add(node);
                }
                else
                {
                    children.AddRange(node.Children);
                }
            }
            nodes = children;
        }
        return edges;
    }

    public void UpdateTree()
    {
        Root.SetFullStr();
        Root.SetDescendantCount();
    }

    public override string ToString()
    {
        var s = "";
        var nodes = new List<PatriciaNode> { Root };
        while (nodes.Count > 0)
        {
            var next = new List<PatriciaNode>();
            foreach (var node in nodes)
            {
                s += node + "\n";
                next.AddRange(node.Children);
            }
            nodes = next;
        }
        return s;
    }
}

class Solution
{
    static void Main()
    {
        var n = int.Parse(Console.ReadLine());
        var tree = new PatriciaTree();
        for (int i = 0; i < n; i++)
        {
            var s = Console.ReadLine() + " ";
            tree.Add(s);
        }
        tree.UpdateTree();

        var edges = tree.GetEdges();
        long expected = 0;
        for (int remove = 0; remove < n; remove++)
        {
            foreach (var e in edges)
            {
                expected += e.GetExpectedLength(remove, n - 1);
                expected %= Mod;
            }
            Console.WriteLine(expected);
            expected *= (n - remove - 1);
            expected %= Mod;
        }
    }
}
0