結果

問題 No.15 カタログショッピング
コンテスト
ユーザー バカらっく
提出日時 2019-08-31 21:25:14
言語 Kotlin
(2.3.20)
コンパイル:
kotlinc _filename_ -include-runtime -d main.jar
実行:
kotlin main.jar
結果
TLE  
実行時間 -
コード長 1,573 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 14,460 ms
コンパイル使用メモリ 491,704 KB
実行使用メモリ 477,336 KB
最終ジャッジ日時 2026-05-19 20:35:08
合計ジャッジ時間 26,495 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5 TLE * 2 -- * 3
権限があれば一括ダウンロードができます
コンパイルメッセージ
Main.kt:36:38: warning: 'fun <T> Iterable<T>.sumBy(selector: (T) -> Int): Int' is deprecated. Use sumOf instead.
    if(subTotal + itemList.drop(idx).sumBy { it.value } < total) {
                                     ^^^^^

ソースコード

diff #
raw source code 

import java.lang.StringBuilder

fun main(args: Array<String>) {
    val(n,s) = readLine()!!.trim().split(" ").map { it.toInt() }
    total = s
    for(i in 1..n) {
        itemList.add(Item(i-1, readLine()!!.toInt()))
    }
    itemList.sortByDescending { it.value }
    val ans = getAns(0, 0).sortedDescending()
    ans.forEach { println(convAns(it)) }
}

fun convAns(num:Int):String {
    val ans = StringBuilder()
    for(i in itemList.indices) {
        val key = 1 shl (itemList.lastIndex - i)
        if(num and key > 0) {
            ans.append(" ")
            ans.append(i + 1)
        }
    }
    return ans.toString().substring(1)
}

var total = 0
class Item(val index:Int, val value:Int)
val itemList = mutableListOf<Item>()

val dic = mutableMapOf<Int, MutableMap<Int, List<Int>>>()

fun getAns(idx:Int, subTotal:Int):List<Int> {
    if(subTotal > total) {
        return mutableListOf()
    }
    if(subTotal + itemList.drop(idx).sumBy { it.value } < total) {
        return mutableListOf()
    }
    if(subTotal == total) {
        return mutableListOf(0)
    }
    if(idx > itemList.lastIndex) {
        return mutableListOf()
    }
    if(!dic.containsKey(idx)) {
        dic[idx] = mutableMapOf()
    }
    dic[idx]!![subTotal]?.let { return it }

    val ans = mutableListOf<Int>()
    val ret1 = getAns(idx + 1, subTotal + itemList[idx].value)
    val ret2 = getAns(idx + 1, subTotal)
    val key = 1 shl (itemList.lastIndex - itemList[idx].index)
    ans.addAll(ret1.map { it + key })
    ans.addAll(ret2)
    dic[idx]!![subTotal]= ans
    return ans
}
0