No.515 典型LCP

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 76
作問者 :

koba-e964 / テスター :

ei1333333

3 ProblemId : 1408 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2017-05-06 01:56:16

問題文

文字列からなる配列 $s_{1}, \dots, s_{N}$ があります。以下のような $M$ 個のクエリに答えてください:
「 $1 \leq i < j \leq N$ を満たす整数 $i, j$ に対して、文字列 $s_{i}, s_{j}$ の最長共通接頭辞の長さを求めよ。」
$M$ 個のクエリは、シードx,dから以下の方法によって生成されます。注意深く読んで実装してください。

for k in 1 .. M
  i[k] = (x / (n - 1)) + 1
  j[k] = (x % (n - 1)) + 1
  if (i[k] > j[k])
    swap(i[k], j[k])
  else
    j[k] = j[k] + 1
  end
  x = (x + d) % (n * (n - 1))
end

ただし、計算は多倍長整数を使って行われるものとし、割り算"/"は実数としてみなした時の商の整数部分を返すものとします。

入力

 $N$ 
 $s_{1}$ 
 $⋮$ 
 $s_{N}$ 
 $M$   $x$   $d$

(2017/5/5 22:46修正: Nの最小値を1から2にしました)
$2 \leq N \leq 100000 = 10^{5}$
$| s_{i} | \geq 1$ for all $1 \leq i \leq N$
$\sum_{i} | s_{i} | \leq 800000 = 8 \times 10^{5}$
各 $s_{i}$ はラテン文字の小文字('a'から'z')からなる。
$1 \leq M \leq 3000000 = 3 \times 10^{6}$
$0 \leq x < N (N - 1)$
$0 \leq d < N (N - 1)$
$x$ , $d$ は整数である。

出力

各 $k$ に対して、 $s_{i_{k}}$ と $s_{j_{k}}$ の最長共通接頭辞の長さを計算して、その和を改行付きで1行に出力してください。

サンプル

サンプル1

入力

4
kinesis
koba
variance
kobushu
3 1 2

出力

最初のクエリにおいて、 $x = 1$ なので $i = 1, j = 3$ であり、"kinesis"と"variance"のLCPは""なので、長さは0です。
2個目では $x = 3$ なので $i = 1, j = 2$ であり、"kinesis"と"koba"のLCPは"k"なので、長さは1です。
3個目では $x = 5$ なので $i = 2, j = 4$ であり、"koba"と"kobushu"のLCPは"kob"なので、長さは3です。
最終的な出力はそれらの合計である4です。

サンプル2

入力

5
aaaaa
dadad
aaaab
abcbc
aaaac
4 1 1

出力

各クエリの結果は4,1,4,0なので、総和の9を出力します。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。