結果

問題 No.515 典型LCP
コンテスト
ユーザー 👑 kakel-san
提出日時 2026-11-14 18:09:25
言語 C#
(.NET 10.0.403 + ACL)
コンパイル:
dotnet_c
実行:
/usr/bin/dotnet_wrap
結果
RE  
実行時間 -
コード長 3,182 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 6,839 ms
コンパイル使用メモリ 167,592 KB
実行使用メモリ 144,904 KB
最終ジャッジ日時 2026-11-14 18:09:49
合計ジャッジ時間 23,425 ms
ジャッジサーバーID
(参考情報)
judge4_0 / judge5_0
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 1 RE * 18
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (191 ミリ秒)。
  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 int[] NList => ReadLine().Split().Select(int.Parse).ToArray();
    static int[][] NArr(long n) => Enumerable.Repeat(0, (int)n).Select(_ => NList).ToArray();
    public static void Main()
    {
        Solve();
    }
    static void Solve()
    {
        var n = NN;
        var text = new List<char>();
        var idlist = new int[n];
        for (var i = 0; i < n; ++i)
        {
            var s = ReadLine();
            idlist[i] = text.Count;
            text.AddRange(s);
            text.Add('#');
        }
        var iddic = new Dictionary<int, int>();
        for (var i = 0; i < n; ++i) iddic[idlist[i]] = i;
        var ts = string.Concat(text);
        var c = NList;
        var (m, x, d) = (c[0], (long)c[1], c[2]);
        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;
            ans += st.Calc(refid[ik], refid[jk]);
        }
        WriteLine(string.Join("\n", 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