結果

問題 No.14 最小公倍数ソート
ユーザー バカらっくバカらっく
提出日時 2019-08-31 19:05:51
言語 Kotlin
(1.9.23)
結果
TLE  
実行時間 -
コード長 2,404 bytes
コンパイル時間 13,568 ms
コンパイル使用メモリ 453,324 KB
実行使用メモリ 354,784 KB
最終ジャッジ日時 2024-11-25 03:27:20
合計ジャッジ時間 117,024 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 306 ms
60,340 KB
testcase_01 AC 281 ms
56,932 KB
testcase_02 AC 282 ms
63,980 KB
testcase_03 AC 2,011 ms
141,432 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:50: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).toMutableList()
    while (subList.size > 1) {
        val target = ans.last()
        subList.sortWith(java.util.Comparator { a, b -> if(getMinKoubai(target, a) == getMinKoubai(target, b)) a.compareTo(b) else getMinKoubai(target, a).compareTo(getMinKoubai(target, b))})
        if(subList.size == 2) {
            ans.addAll(subList)
            break
        } else {
            ans.add(subList[0])
            subList = subList.drop(1).toMutableList()
        }
    }
    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