結果
| 問題 | No.515 典型LCP |
| コンテスト | |
| ユーザー |
👑 |
| 提出日時 | 2026-11-14 18:12:20 |
| 言語 | C# (.NET 10.0.403 + ACL) |
| 結果 |
WA
不安定
|
| 実行時間 | - |
| コード長 | 3,224 bytes |
| 記録 | |
| コンパイル時間 | 5,301 ms |
| コンパイル使用メモリ | 165,812 KB |
| 実行使用メモリ | 144,384 KB |
| 最終ジャッジ日時 | 2026-11-14 18:12:34 |
| 合計ジャッジ時間 | 14,086 ms |
|
ジャッジサーバーID (参考情報) |
judge3_0 / judge2_0 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 7 WA * 9 RE * 3 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (180 ミリ秒)。 main -> /home/judge/data/code/bin/Release/net10.0/main.dll main -> /home/judge/data/code/bin/Release/net10.0/publish/
ソースコード
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(Math.Min(refid[ik], refid[jk]), Math.Max(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]);
}
}
}