Submission #65957456

---

Source Code Expand

import java.util.*
import kotlin.math.round
import kotlin.random.Random

@Suppress("unused")
fun next() = readln()

@Suppress("unused")
fun nextInt() = next().toInt()

@Suppress("unused")
fun nextLong() = next().toLong()

@Suppress("unused")
fun nextDouble() = next().toDouble()

@Suppress("unused")
fun nextList() = next().split(" ")

@Suppress("unused")
fun nextIntList() = next().split(" ").map { it.toInt() }

@Suppress("unused")
fun nextLongList() = next().split(" ").map { it.toLong() }

@Suppress("unused")
fun nextDoubleList() = next().split(" ").map { it.toDouble() }

const val ALPHABET = 6
val CHAR_TO_IDX = mapOf('a' to 0, 'b' to 1, 'c' to 2, 'd' to 3, 'e' to 4, 'f' to 5)

fun main() {
    val (N, M, _) = nextIntList()
    val spList = Array(N) { SP("", 0) }
    for (i in spList.indices) {
        val (s, p) = next().split(" ")
        spList[i] = SP(s, p.toInt())
    }


    val sorted = spList.sortedByDescending { it.p }.take(3)
    val probList = Array(M) { Prob('a', IntArray(M)) }

    val A = Array(M) { IntArray(M) }

    val countAlphabet = BooleanArray(6) { false }
    for (i in sorted.indices) {
        val s = sorted[i].s
        val p = sorted[i].p
        var previous = s[0] - 'a'
        for (i in 0 until s.length - 1) {
            var next = s[i + 1] - 'a'
            if (countAlphabet[next]) {
                countAlphabet[next] = false
                next += 6
            } else {
                countAlphabet[next] = true
            }
            A[previous][next] += (p / 3)
            previous = next
        }
    }

    var c = 'a'
    for (i in A.indices) {
        val sum = A[i].sum()
        if (sum != 0) {
            for (j in A[i].indices) {
                A[i][j] = (A[i][j] * 100) / sum
            }
            var newSum = A[i].sum()
            if (newSum != 100) {
                for (j in A[i].indices) {
                    if (A[i][j] == 0) {
                        continue
                    }
                    A[i][j]++
                    newSum++
                    if (newSum == 100) {
                        break
                    }
                }
            }
        } else {
            A[i][0] = 100
        }
        probList[i] = Prob(c, A[i])
        if (c == 'f') {
            c = 'a'
        } else {
            c++
        }
    }

    val S = probList.map { it.c }.toCharArray()
    var score = 0
    for (sp in spList) {
        var count = 0
        // 100文字分を実際に100回生成して、
        for (i in 0 until 100) {
            val sb = StringBuilder()
            var now = 0
            for (j in 0 until 100) {
                sb.append(S[now])
                var acc = 0
                val r = Random.nextInt(100)
                for (k in A[now].indices) {
                    acc += A[now][k]
                    if (acc > r) {
                        now = k
                        break
                    }
                }
            }
            if (sb.contains(sp.s)) {
                count++
            }
        }

        score += round((count.toDouble() / 100) * sp.p).toInt()
    }

    for (p in probList) {
        println("${p.c} ${p.a.joinToString(" ")}")
    }
}

data class SP(val s: String, val p: Int)
class Prob(val c: Char, val a: IntArray)

// --- Aho-Corasick実装 ---
class AhoCorasick {
    val root = 0
    var size = 1
    val to = Array(1000) { IntArray(ALPHABET) { -1 } }
    val fail = IntArray(1000) { 0 }
    val output = Array(1000) { mutableListOf<Int>() }

    fun add(s: String, id: Int) {
        var v = root
        for (ch in s) {
            val c = CHAR_TO_IDX[ch]!!
            if (to[v][c] == -1) to[v][c] = size++
            v = to[v][c]
        }
        output[v].add(id)
    }

    fun build() {
        val q: Queue<Int> = LinkedList()
        for (c in 0 until ALPHABET) {
            if (to[root][c] != -1) {
                q.add(to[root][c])
                fail[to[root][c]] = root
            } else {
                to[root][c] = root
            }
        }
        while (q.isNotEmpty()) {
            val v = q.poll()
            for (c in 0 until ALPHABET) {
                val u = to[v][c]
                if (u == -1) continue
                var f = fail[v]
                while (to[f][c] == -1) f = fail[f]
                fail[u] = to[f][c]
                output[u].addAll(output[fail[u]])
                q.add(u)
            }
        }
    }
}

Submission Info

Compile Error

Main.kt:51:14: warning: name shadowed: i
        for (i in 0 until s.length - 1) {
             ^

Judge Result