結果
問題 |
No.962 LCPs
|
ユーザー |
![]() |
提出日時 | 2020-01-11 14:25:02 |
言語 | Kotlin (2.1.0) |
結果 |
AC
|
実行時間 | 626 ms / 2,000 ms |
コード長 | 1,625 bytes |
コンパイル時間 | 15,555 ms |
コンパイル使用メモリ | 453,396 KB |
実行使用メモリ | 99,992 KB |
最終ジャッジ日時 | 2024-11-24 22:23:20 |
合計ジャッジ時間 | 47,589 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 64 |
ソースコード
import kotlin.math.min val MOD = 1_000_000_007 fun main() { val (N) = readInts() val S = Array(N){ readLine()!!} val lcps = mutableListOf<Pair<Int, Int>>() for (i in 0 until N - 1) { var l = 0 val mx = min(S[i].length, S[i + 1].length) while(l < mx && S[i][l] == S[i + 1][l]) l++ lcps.add(Pair(i, l)) } lcps.sortBy { it.second } val t = sortedSetOf<Int>() t.add(-1) t.add(N - 1) var ans = 0L S.forEach { ans += it.length } for (lcp in lcps) { val i = lcp.first val l = (i - t.lower(i)!! - 1).toLong() val r = (t.higher(i)!! - i - 1).toLong() var lensum = (l + 1) * (r + 1) * 2 lensum += (l + 1) * r * (r + 1) / 2 lensum += l * (l + 1) / 2 * (r + 1) ans += lensum * lcp.second debug{"l:$l r:$r"} t.add(i) } println(ans) } private val isDebug = try { // なんか本番でエラーでる System.getenv("MY_DEBUG") != null } catch (t: Throwable) { false } private fun readLn() = readLine()!! private fun readInt() = readLn().toInt() private fun readStrings() = readLn().split(" ") private fun readInts() = readStrings().map { it.toInt() }.toIntArray() private fun readLongs() = readStrings().map { it.toLong() }.toLongArray() private inline fun debug(msg: () -> String) { if (isDebug) System.err.println(msg()) } private fun debug(a: LongArray) { debug{a.joinToString(" ")} } private fun debug(a: IntArray) { debug{a.joinToString(" ")} } private fun debug(a: BooleanArray) { debug{a.map{if(it) 1 else 0}.joinToString("")} } private fun debugDim(A: Array<IntArray>) { if (isDebug) { for (a in A) { debug(a) } } }