結果

問題 No.14 最小公倍数ソート
ユーザー バカらっくバカらっく
提出日時 2019-08-31 19:25:57
言語 Kotlin
(1.9.23)
結果
TLE  
実行時間 -
コード長 2,536 bytes
コンパイル時間 14,588 ms
コンパイル使用メモリ 453,204 KB
実行使用メモリ 380,356 KB
最終ジャッジ日時 2024-11-25 04:13:41
合計ジャッジ時間 116,148 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 296 ms
63,468 KB
testcase_01 AC 299 ms
98,172 KB
testcase_02 AC 298 ms
66,788 KB
testcase_03 AC 976 ms
129,968 KB
testcase_04 TLE -
testcase_05 TLE -
testcase_06 TLE -
testcase_07 TLE -
testcase_08 TLE -
testcase_09 TLE -
testcase_10 TLE -
testcase_11 TLE -
testcase_12 TLE -
testcase_13 TLE -
testcase_14 TLE -
testcase_15 TLE -
testcase_16 TLE -
testcase_17 TLE -
testcase_18 TLE -
testcase_19 TLE -
権限があれば一括ダウンロードができます
コンパイルメッセージ
Main.kt:1:10: warning: parameter 'args' is never used
fun main(args: Array<String>) {
         ^
Main.kt:2:9: warning: variable 'numberCount' is never used
    val numberCount = readLine()!!.toInt()
        ^
Main.kt:59:9: warning: variable 'list' is never used
    val list = mutableListOf<Int>()
        ^

ソースコード

diff # 

fun main(args: Array<String>) {
    val numberCount = readLine()!!.toInt()
    val numberList = readLine()!!.split(" ").map { it.toInt() }
    getPrimeList()
    numberList.forEach { getPrimeDivide(it) }
    var ans = mutableListOf<Int>()
    ans.add(numberList[0])
    var subList = numberList.drop(1).sorted().toMutableList()
    while (subList.size > 0) {
        val target = ans.last()
        var minNum = 10000
        var minKoubai = 100000000
        var minIdx = -1
        for(i in subList.indices) {
            val koubai = getMinKoubai(target, subList[i])
            if(koubai >= minKoubai) {
                continue
            }
            minNum = subList[i]
            minKoubai = koubai
            minIdx = i
            if(minKoubai == subList[i] || minKoubai == target) {
                break
            }
        }
        subList.removeAt(minIdx)
        ans.add(minNum)
    }
    println(ans.joinToString(" "))
}

val dic = mutableMapOf<Int, MutableMap<Int, Int>>()
val primeDivideDic = mutableMapOf<Int, MutableMap<Int, Int>>()
val primeList = mutableListOf<Int>()

fun getMinKoubai(num1:Int, num2:Int):Int {
    if(num1 > num2) {
        return getMinKoubai(num2, num1)
    }
    if(!dic.containsKey(num1)) {
        dic[num1] = mutableMapOf()
    }
    dic[num1]!![num2]?.let { return it }
    val keys = primeDivideDic[num1]!!.keys.union(primeDivideDic[num2]!!.keys)
    var num = 1
    keys.forEach{
        var maxCount = 1
        primeDivideDic[num1]!![it]?.let { maxCount = it }
        primeDivideDic[num2]!![it]?.let { maxCount = Math.max(maxCount, it) }
        num = num * Math.pow(it.toDouble(), maxCount.toDouble()).toInt()
    }
    dic[num1]!![num2] = num
    return num
}

fun getPrimeList() {
    val max = 10000
    val flags = arrayOfNulls<Boolean>(max + 1)
    val list = mutableListOf<Int>()
    for(i in 2..max) {
        if (flags[i] != null && flags[i]!!) {
            continue
        }
        val maxIndex = max/i
        for(j in 1..maxIndex) {
            flags[i*j] = true
        }
        primeList.add(i)
    }
}

fun getPrimeDivide(num: Int) {
    if(primeDivideDic.containsKey(num)) {
        return
    }
    val primeDivide = mutableMapOf<Int,Int>()
    var subNum = num
    for (prime in primeList) {
        if(subNum % prime > 0) {
            continue
        }
        var cnt = 0
        while (subNum%prime == 0) {
            cnt++
            subNum = subNum / prime
        }
        primeDivide[prime] = cnt
    }
    primeDivideDic[num] = primeDivide
}
0