結果

問題 No.14 最小公倍数ソート
コンテスト
ユーザー バカらっく
提出日時 2019-08-31 19:12:57
言語 Kotlin
(2.1.0)
結果
TLE  
実行時間 -
コード長 2,396 bytes
コンパイル時間 14,220 ms
コンパイル使用メモリ 449,984 KB
実行使用メモリ 371,548 KB
最終ジャッジ日時 2024-11-25 03:44:38
合計ジャッジ時間 118,230 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 TLE * 16
権限があれば一括ダウンロードができます
コンパイルメッセージ
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