結果

問題 No.517 壊れたアクセサリー
コンテスト
ユーザー 鳩でもわかるC#
提出日時 2025-05-09 18:07:25
言語 C#
(.NET 8.0.404)
結果
AC  
実行時間 80 ms / 2,000 ms
コード長 5,421 bytes
コンパイル時間 9,964 ms
コンパイル使用メモリ 174,204 KB
実行使用メモリ 190,988 KB
最終ジャッジ日時 2025-05-09 18:07:46
合計ジャッジ時間 12,581 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 15
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (113 ミリ秒)。
  main -> /home/judge/data/code/bin/Release/net8.0/main.dll
  main -> /home/judge/data/code/bin/Release/net8.0/publish/

ソースコード

diff # 

using HatoLibrary;
using System.Diagnostics;
class Program
{
    static string ReadLine() => Console.ReadLine().Trim();
    static int ReadInt() => int.Parse(ReadLine());
    static void ReadInt2(out int a, out int b) { int[] vs = ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); a = vs[0]; b = vs[1]; }
    static void ReadInt3(out int a, out int b, out int c) { int[] vs = ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); a = vs[0]; b = vs[1]; c = vs[2]; }
    static int[] ReadIntArray() => ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

    static void Main()
    {
        SourceExpander.Expander.Expand();

        List<string> strings = new List<string>();
        Dictionary<char, bool> dic = new Dictionary<char, bool>();
        {
            char[] cs = CharEx.Uppercases;
            foreach (char c in cs)
            {
                dic.Add(c, false);
            }
        }


        int N = ReadInt();
        for (int i = 0; i < N; i++)
        {
            string s = ReadLine();
            strings.Add(s);

            char[] cs = s.ToArray();
            foreach (char c in cs)
                dic[c] = true;
        }
        int M = ReadInt();
        for (int i = 0; i < M; i++)
        {
            string s = ReadLine();
            strings.Add(s);

            char[] cs = s.ToArray();
            foreach (char c in cs)
                dic[c] = true;
        }

        var rets = dic.OrderBy(_ => _.Key).ToArray();
        int useCount = 0;
        Dictionary<int, char> intToChar = new Dictionary<int, char>();
        Dictionary<char, int> charToInt = new Dictionary<char, int>();
        for (int i = 0; i < 26; i++)
        {
            if (rets[i].Value == true)
            {
                intToChar.Add(useCount, rets[i].Key);
                charToInt.Add(rets[i].Key, useCount);
                useCount++;
            }
        }

        Graph g = new Graph(useCount);

        foreach (string s in strings)
        {
            for (int i = 0; i < s.Length - 1; i++)
            {
                int from = charToInt[s[i]];
                int next = charToInt[s[i + 1]];
                g.AddEdge(from, next);
            }
        }

        var ret = g.TopologicalSortIsUnique();
        if (ret.Sorted.Count > 0 && ret.IsUnique)
        {
            string ans = "";
            foreach (int v in ret.Sorted)
                ans += intToChar[v];
            Console.WriteLine(ans);
        }
        else
            Console.WriteLine(-1);
    }
}

#region Expanded by https://github.com/kzrnm/SourceExpander
namespace HatoLibrary { public static class CharEx { public static bool IsUpper(char c) { int ci = (int)c; int ca = (int)'A'; int cz = (int)'Z'; if (ca <= ci && ci <= cz) return true; else return false; }  public static bool IsLower(char c) { int ci = (int)c; int ca = (int)'a'; int cz = (int)'z'; if (ca <= ci && ci <= cz) return true; else return false; }  public static char[] Uppercases { get { return "ABCDEFGHIJKLMNOPQRSTUVWXYZ".ToArray(); } }  public static char[] Lowercases { get { return "abcdefghijklmnopqrstuvwxyz".ToArray(); } } } }
namespace HatoLibrary { public class Graph { int N = 0; List<int>[] Edges; public Graph(int n) { N = n; Edges = new List<int>[N]; for (int i = 0; i < N; i++) Edges[i] = new List<int>(); }  public void AddEdge(int from, int next) { Edges[from].Add(next); }  int[] GetInCounts() { int[] counts = new int[N]; for (int a = 0; a < N; a++) { foreach (int b in Edges[a]) counts[b]++; }  return counts; }  public List<int> TopologicalSort() { int[] counts = GetInCounts(); Queue<int> q = new Queue<int>(); for (int i = 0; i < N; i++) { if (counts[i] == 0) q.Enqueue(i); }  List<int> sorted = new List<int>(); while (q.Count > 0) { int cur = q.Dequeue(); sorted.Add(cur); foreach (int next in Edges[cur]) { counts[next]--; if (counts[next] == 0) q.Enqueue(next); } }  if (sorted.Count == N) return sorted; else return new List<int>(); }  public (List<int> Sorted, bool IsUnique) TopologicalSortIsUnique() { List<int> sorted = TopologicalSort(); if (sorted.Count != N) return (Sorted: new List<int>(), IsUnique: false); bool isUnique = true; for (int i = 0; i < N - 1; i++) { int a = sorted[i]; int b = sorted[i + 1]; if (Edges[a].IndexOf(b) == -1) { isUnique = false; break; } }  return (Sorted: sorted, IsUnique: isUnique); }  public List<(int Goal, long PathCount)> GetPathCounts(List<int>[] lists, long mod) { int[] inCounts = GetInCounts(); long[] pathCounts = new long[N]; for (int i = 0; i < N; i++) { if (inCounts[i] == 0) pathCounts[i] = 1; }  List<int> sorted = TopologicalSort(); if (sorted.Count != N) return new List<(int Goal, long PathCount)>(); for (int i = 0; i < N; i++) { int start = sorted[i]; List<int> goals = lists[start]; foreach (int g in goals) { pathCounts[g] += pathCounts[start]; pathCounts[g] %= mod; } }  var rets = new List<(int Goal, long PathCount)>(); for (int i = 0; i < N; i++) { if (lists[i].Count == 0) { (int Goal, long PathCount) ret; ret.Goal = i; ret.PathCount = pathCounts[i]; rets.Add(ret); } }  return rets; } } }
namespace SourceExpander{public class Expander{[Conditional("EXP")]public static void Expand(string inputFilePath=null,string outputFilePath=null,bool ignoreAnyError=true){}public static string ExpandString(string inputFilePath=null,bool ignoreAnyError=true){return "";}}}
#endregion Expanded by https://github.com/kzrnm/SourceExpander
0