結果
| 問題 | No.515 典型LCP |
| コンテスト | |
| ユーザー |
👑 |
| 提出日時 | 2026-11-14 18:32:22 |
| 言語 | C# (.NET 10.0.403 + ACL) |
| 結果 |
TLE
不安定
|
| 実行時間 | - |
| コード長 | 3,693 bytes |
| 記録 | |
| コンパイル時間 | 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/
ソースコード
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]);
}
}
}