結果

問題 No.14 最小公倍数ソート
ユーザー バカらっくバカらっく
提出日時 2019-08-31 19:12:57
言語 Kotlin
(1.9.23)
結果
TLE  
実行時間 -
コード長 2,396 bytes
コンパイル時間 16,869 ms
コンパイル使用メモリ 455,360 KB
実行使用メモリ 460,736 KB
最終ジャッジ日時 2024-05-03 22:33:54
合計ジャッジ時間 26,642 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 326 ms
55,132 KB
testcase_01 AC 331 ms
87,648 KB
testcase_02 AC 328 ms
57,112 KB
testcase_03 AC 1,265 ms
125,792 KB
testcase_04 TLE -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
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:11:205: warning: unnecessary non-null assertion (!!) on a non-null receiver of type Int
        val nextNum = subList.minWith(java.util.Comparator { a, b -> if(getMinKoubai(target, a) == getMinKoubai(target, b)) a.compareTo(b) else getMinKoubai(target, a).compareTo(getMinKoubai(target, b))})!!
                                                                                                                                                                                                            ^
Main.kt:49: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()
        val nextNum = subList.minWith(java.util.Comparator { a, b -> if(getMinKoubai(target, a) == getMinKoubai(target, b)) a.compareTo(b) else getMinKoubai(target, a).compareTo(getMinKoubai(target, b))})!!
        val idx = subList.indexOf(nextNum)
        ans.add(nextNum)
        subList.removeAt(idx)
        if(subList.size == 1) {
            ans.add(subList[0])
        }
    }
    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