結果

問題 No.14 最小公倍数ソート
コンテスト
ユーザー バカらっく
提出日時 2019-08-31 19:25:09
言語 Kotlin
(2.1.0)
結果
WA  
実行時間 -
コード長 2,530 bytes
コンパイル時間 15,452 ms
コンパイル使用メモリ 447,676 KB
実行使用メモリ 79,564 KB
最終ジャッジ日時 2024-11-25 04:09:42
合計ジャッジ時間 27,317 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1 WA * 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: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(minNum == subList[i] || minNum == 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