結果

問題 No.515 典型LCP
コンテスト
ユーザー 👑 kakel-san
提出日時 2026-11-14 18:32:22
言語 C#
(.NET 10.0.403 + ACL)
コンパイル:
dotnet_c
実行:
/usr/bin/dotnet_wrap
結果
TLE  
実行時間 -
コード長 3,693 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 6,795 ms
コンパイル使用メモリ 166,792 KB
実行使用メモリ 152,624 KB
最終ジャッジ日時 2026-11-14 18:32:40
合計ジャッジ時間 16,583 ms
ジャッジサーバーID
(参考情報)
judge5_0 / judge1_0
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 5 TLE * 3 -- * 11
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (198 ミリ秒)。
  main -> /home/judge/data/code/bin/Release/net10.0/main.dll
  main -> /home/judge/data/code/bin/Release/net10.0/publish/

ソースコード

diff #
raw source code

using System;
using static System.Console;
using System.Linq;
using System.Collections.Generic;

class Program
{
    static int NN => int.Parse(ReadLine());
    static long[] NList => ReadLine().Split().Select(long.Parse).ToArray();
    static string[] SList(long n) => Enumerable.Repeat(0, (int)n).Select(_ => ReadLine()).ToArray();
    public static void Main()
    {
        Solve();
    }
    static void Solve()
    {
        var n = NN;
        var s = SList(n);
        var c = NList;
        WriteLine(Text(n, s, c[0], c[1], c[2]));
    }
    static long Text(int n, string[] s, long m, long x, long d)
    {
        var text = new List<char>();
        var idlist = new int[n];
        var sdic = new Dictionary<string, int>();
        var iddic = new Dictionary<int, int>();
        for (var i = 0; i < n; ++i)
        {
            if (sdic.ContainsKey(s[i]))
            {
                idlist[i] = idlist[sdic[s[i]]];
            }
            else
            {
                sdic[s[i]] = i;
                idlist[i] = text.Count;
                iddic[idlist[i]] = i;
                text.AddRange(s[i]);
                text.Add('#');
            }
        }
        var ts = string.Concat(text);
        var mul = (long)n * (n - 1);
        var sa = AtCoder.StringLib.SuffixArray(ts);
        // refid[i] = idlist[i] がsaの何番目にあるか
        var refid = new int[n];
        for (var i = 0; i < sa.Length; ++i) if (iddic.ContainsKey(sa[i])) refid[iddic[sa[i]]] = i;
        var lcp = AtCoder.StringLib.LcpArray(ts, sa);
        var st = new SparseTable<int>(lcp, Math.Min);
        var ans = 0L;
        for (var k = 1; k <= m; ++k)
        {
            var ik = x / (n - 1);
            var jk = x % (n - 1);
            if (ik > jk) (ik, jk) = (jk, ik);
            else ++jk;
            x = (x + d) % mul;
            var iid = refid[sdic[s[ik]]];
            var jid = refid[sdic[s[jk]]];
            if (iid == jid) ans += s[ik].Length;
            else
            {
                ans += st.Calc(Math.Min(iid, jid), Math.Max(iid, jid));
            }
        }
        return ans;
    }
    /// <summary>
    /// 静的な配列に対する区間クエリを高速に処理する
    /// 最小値など、f(a, a) = a を満たすクエリに対して使用可能
    /// </summary>
    /// <typeparam name="T">データの型</typeparam>
    class SparseTable<T>
    {
        int[] lenIdx;
        T[][] table;
        Func<T, T, T> F;
        public SparseTable(T[] init, Func<T, T, T> f)
        {
            F = f;
            var len = 1;
            var tmp = 1;
            while (tmp < init.Length)
            {
                ++len;
                tmp <<= 1;
            }
            table = new T[len][];
            table[0] = (T[]) init.Clone();
            tmp = 1;
            for (var i = 1; i < len; ++i)
            {
                table[i] = new T[init.Length];
                for (var j = 0; j < init.Length; ++j)
                {
                    if (j + tmp < init.Length) table[i][j] = f(table[i - 1][j], table[i - 1][j + tmp]);
                    else table[i][j] = table[i - 1][j];
                }
                tmp <<= 1;
            }
            lenIdx = new int[init.Length];
            for (var i = 1; i < init.Length; ++i) lenIdx[i] = lenIdx[i / 2] + 1;
        }
        public T Calc(int left, int right)
        {
            var idx = lenIdx[right - left] - 1;
            var roffset = 1 << idx;
            return F(table[idx][left], table[idx][right - roffset]);
        }
    }
}
0