結果

問題 No.133 カードゲーム
ユーザー mikhail
提出日時 2020-06-07 20:44:12
言語 Kotlin
(2.1.0)
結果
AC  
実行時間 300 ms / 5,000 ms
コード長 18,996 bytes
コンパイル時間 30,249 ms
コンパイル使用メモリ 491,932 KB
実行使用メモリ 50,088 KB
最終ジャッジ日時 2024-12-23 21:12:40
合計ジャッジ時間 35,690 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 19
権限があれば一括ダウンロードができます
コンパイルメッセージ
Main.kt:15:10: warning: parameter 'args' is never used
fun main(args: Array<String>) {
         ^
Main.kt:257:76: warning: unnecessary non-null assertion (!!) on a non-null receiver of type Long
fun max(vararg values: Long) = if (values.isEmpty()) -INF else values.max()!!
                                                                           ^
Main.kt:258:75: warning: unnecessary non-null assertion (!!) on a non-null receiver of type Long
fun min(vararg values: Long) = if (values.isEmpty()) INF else values.min()!!
                                                                          ^

ソースコード

diff #
プレゼンテーションモードにする

import java.io.*
import java.lang.*
import java.math.*
import java.util.*
// Constant
val sc = FastScanner()
val pw = PrintWriter(System.out)
const val MOD = 1000000007L
const val INF = 9223372036854775807L
// Main
fun main(args: Array<String>) {
    solve()
    pw.flush()
}
// Global
fun solve() {
    val n = nextLong()
    val a = nextLongAry(n)
    val b = nextLongAry(n)
    val aPerm = Permutation(n)
    aPerm.init()
    var win = 0
    var battle = 0
    while (aPerm.hasNext()) {
        val aStep = aPerm.nextPerm()
        val bPerm = Permutation(n)
        bPerm.init()
        while (bPerm.hasNext()) {
            val bStep = bPerm.nextPerm()
            var aSum = 0L
            var bSum = 0L
            for (i in 0 until n) {
                val aNow = a[aStep[i]]
                val bNow = b[bStep[i]]
                if(aNow > bNow) aSum++
                else if(bNow > aNow) bSum++
            }
            battle++
            if(aSum > bSum) win++
        }
    }
    println(win.toDouble() / battle)
}
// Rule
operator fun String.get(index: Long): Char {
    if (index !in 0L..Int.MAX_VALUE) throw IllegalArgumentException()
    return this[index.toInt()]
}
operator fun CharArray.get(index: Long): Char {
    if (index !in 0L..Int.MAX_VALUE) throw IllegalArgumentException()
    return this[index.toInt()]
}
operator fun CharArray.set(index: Long, value: Char) {
    if (index !in 0L..Int.MAX_VALUE) throw IllegalArgumentException()
    this[index.toInt()] = value
}
operator fun IntArray.get(index: Long): Int {
    if (index !in 0L..Int.MAX_VALUE) throw IllegalArgumentException()
    return this[index.toInt()]
}
operator fun IntArray.set(index: Long, value: Int) {
    if (index !in 0L..Int.MAX_VALUE) throw IllegalArgumentException()
    this[index.toInt()] = value
}
operator fun LongArray.get(index: Long): Long {
    if (index !in 0L..Int.MAX_VALUE) throw IllegalArgumentException()
    return this[index.toInt()]
}
operator fun LongArray.set(index: Long, value: Long) {
    if (index !in 0L..Int.MAX_VALUE) throw IllegalArgumentException()
    this[index.toInt()] = value
}
operator fun DoubleArray.get(index: Long): Double {
    if (index !in 0L..Int.MAX_VALUE) throw IllegalArgumentException()
    return this[index.toInt()]
}
operator fun DoubleArray.set(index: Long, value: Double) {
    if (index !in 0L..Int.MAX_VALUE) throw IllegalArgumentException()
    this[index.toInt()] = value
}
operator fun <T> Array<T>.get(index: Long): T {
    if (index !in 0L..Int.MAX_VALUE) throw IllegalArgumentException()
    return this[index.toInt()]
}
operator fun <T> Array<T>.set(index: Long, value: T) {
    if (index !in 0L..Int.MAX_VALUE) throw IllegalArgumentException()
    this[index.toInt()] = value
}
operator fun <T> MutableList<T>.get(index: Long): T {
    if (index !in 0L..Int.MAX_VALUE) throw IllegalArgumentException()
    return this[index.toInt()]
}
operator fun <T> MutableList<T>.set(index: Long, value: T) {
    if (index !in 0L..Int.MAX_VALUE) throw IllegalArgumentException()
    this[index.toInt()] = value
}
val LongArray.siz: Long
    get() = size.toLong()
val <T> Array<T>.siz: Long
    get() = size.toLong()
val <T> MutableList<T>.siz: Long
    get() = size.toLong()
val <T> MutableSet<T>.siz: Long
    get() = size.toLong()
val String.len: Long
    get() = length.toLong()
// Output
fun println(v: String) {
    pw.println(v)
}
fun print(v: String) {
    pw.print(v)
}
// Input
fun next() = sc.next()
fun nextLong() = sc.nextLong()
fun nextLongs() = readLine()!!.split(" ").map { it.toLong() }
fun nextDouble() = next().toDouble()
fun nextAry(n: Long): Array<String> {
    val ary = ary(n)
    for (i in 0 until n) ary[i] = next()
    return ary
}
fun nextLongAry(n: Long): LongArray {
    val ary = longAry(n)
    for (i in 0 until n) ary[i] = nextLong()
    return ary
}
fun nextDoubleAry(n: Long): DoubleArray {
    val ary = doubleAry(n)
    for (i in 0 until n) ary[i] = nextDouble()
    return ary
}
// Statement
fun ary(n: Long, init: String = "") = Array(n.toInt()) { init }
fun charAry(n: Long, init: Char = ' ') = CharArray(n.toInt()) { init }
fun longAry(n: Long, init: Long = 0L) = LongArray(n.toInt()) { init }
fun doubleAry(n: Long, init: Double = 0.0) = DoubleArray(n.toInt()) { init }
fun boolAry(n: Long, init: Boolean = false) = Array(n.toInt()) { init }
fun nodeAry(n: Long) = Array(n.toInt()) { Node(it.toLong()) }
fun ary2(n: Long, m: Long, init: String = "") = Array(n.toInt()) { ary(m, init) }
fun charAry2(n: Long, m: Long, init: Char = ' ') = Array(n.toInt()) { charAry(m, init) }
fun longAry2(n: Long, m: Long, init: Long = 0) = Array(n.toInt()) { longAry(m, init) }
fun doubleAry2(n: Long, m: Long, init: Double = 0.0) = Array(n.toInt()) { doubleAry(m, init) }
fun boolAry2(n: Long, m: Long, init: Boolean = false) = Array(n.toInt()) { boolAry(m, init) }
fun ary3(n: Long, m: Long, k: Long, init: String = "") = Array(n.toInt()) { ary2(m, k, init) }
fun charAry3(n: Long, m: Long, k: Long, init: Char = ' ') = Array(n.toInt()) { charAry2(m, k, init) }
fun longAry3(n: Long, m: Long, k: Long, init: Long = 0L) = Array(n.toInt()) { longAry2(m, k, init) }
fun doubleAry3(n: Long, m: Long, k: Long, init: Double = 0.0) = Array(n.toInt()) { doubleAry2(m, k, init) }
fun boolAry3(n: Long, m: Long, k: Long, init: Boolean = false) = Array(n.toInt()) { boolAry2(m, k, init) }
fun list() = mutableListOf<String>()
fun longList() = mutableListOf<Long>()
fun doubleList() = mutableListOf<Double>()
fun strSet() = mutableSetOf<String>()
fun longSet() = mutableSetOf<Long>()
fun doubleSet() = mutableSetOf<Double>()
fun <E, V> map() = mutableMapOf<E, V>()
// Monoid
val addFunc = {a: Long, b: Long -> a + b}
val mulFunc = {a: Long, b: Long -> a * b}
val maxFunc = {a: Long, b: Long -> max(a, b)}
val minFunc = {a: Long, b: Long -> min(a, b)}
val gcdFunc = {a: Long, b: Long -> gcd(a, b)}
val lcmFunc = {a: Long, b: Long -> lcm(a, b)}
val xorFunc = {a: Long, b: Long -> a xor b}
fun calc(a: Long, b: Long, op: (Long, Long) -> Long) = op(a, b)
// Extension
fun LongArray.lowerBound(n: Long): Long {
    var ok = this.size.toLong()
    var ng = -1L
    while (abs(ok - ng) > 1) {
        val mid = (ok + ng) / 2
        if (this[mid] >= n) ok = mid
        else ng = mid
    }
    return ok
}
fun DoubleArray.lowerBound(n: Double): Long {
    var ok = this.size.toLong()
    var ng = -1L
    while (abs(ok - ng) > 1) {
        val mid = (ok + ng) / 2
        if (this[mid] >= n) ok = mid
        else ng = mid
    }
    return ok
}
fun MutableList<Long>.longLowerBound(n: Long): Long {
    var ok = this.size.toLong()
    var ng = -1L
    while (abs(ok - ng) > 1) {
        val mid = (ok + ng) / 2
        if (this[mid] >= n) ok = mid
        else ng = mid
    }
    return ok
}
fun MutableList<Double>.doubleLowerBound(n: Double): Long {
    var ok = this.size.toLong()
    var ng = -1L
    while (abs(ok - ng) > 1) {
        val mid = (ok + ng) / 2
        if (this[mid] >= n) ok = mid
        else ng = mid
    }
    return ok
}
fun LongArray.cumsum(op: (Long, Long) -> Long): LongArray {
    val s = longAry(this.size + 1L)
    s[1] = this[0]
    for (i in 1 until this.size) s[i + 1] = calc(s[i], this[i], op)
    return s
}
fun MutableMap<String, Int>.counting(n: Long) {
    repeat(n.toInt()) {
        val a = next()
        if (this.containsKey(a)) this[a] = this[a]!! + 1
        else this[a] = 1
    }
}
fun MutableMap<Long, Int>.longCounting(n: Long) {
    repeat(n.toInt()) {
        val a = nextLong()
        if (this.containsKey(a)) this[a] = this[a]!! + 1
        else this[a] = 1
    }
}
// Mathematics
fun abs(n: Long): Long = Math.abs(n)
fun abs(n: Double): Double = Math.abs(n)
fun max(vararg values: Long) = if (values.isEmpty()) -INF else values.max()!!
fun min(vararg values: Long) = if (values.isEmpty()) INF else values.min()!!
tailrec fun gcd(a: Long, b: Long): Long = if (b == 0L) a else if (a % b == 0L) b else gcd(b, (a % b))
fun lcm(a: Long, b: Long): Long = a / gcd(a, b) * b
fun erathos(n: Long): LongArray {
    val res = LongArray(n.toInt() + 1) { it.toLong() }
    for (i in 2..n) {
        if(i * i > n) break
        for (j in i * i..n step i) {
            if(res[j] == j) res[j] = i
        }
    }
    res[0] = -1L
    res[1] = -1L
    return res
}
fun modAdd(a: Long, b: Long) = if(a + b >= MOD) a + b - MOD else a + b
fun modpow(a: Long, n: Long, p: Long = MOD): Long {
    var res = 1L
    var ar = a
    var nr = n
    while (nr > 0) {
        if ((nr and 1) == 1L) res = res * ar % p
        ar = ar * ar % p
        nr = nr shr 1
    }
    return res
}
fun modinv(a: Long, p: Long = MOD): Long = modpow(a, p - 2, p)
fun ncr(n: Long, r: Long): Long {
    var a = 1L
    var b = 1L
    for (i in 1..r) {
        a = a * (n + 1 - i) % MOD
        b = b * i % MOD
    }
    return modinv(b, MOD) * a % MOD
}
class Combination(private val max: Long) {
    private val fac = longAry(max)
    private val finv = longAry(max)
    private val inv = longAry(max)
    private val p = MOD
    fun init() {
        fac[0] = 1
        fac[1] = 1
        finv[0] = 1
        finv[1] = 1
        inv[1] = 1
        for (i in 2 until max) {
            fac[i] = fac[i - 1] * i % p
            inv[i] = p - inv[p % i] * (p / i) % p;
            finv[i] = finv[i - 1] * inv[i] % p
        }
    }
    fun com(n: Long, r: Long): Long = if (n < r || (n < 0 || r < 0)) 0L else fac[n] * (finv[r] * finv[n - r] % p) % p
}
class Permutation(private val n: Long, private var searched: Long = 0L, private var nextIndex: Long = 0L) {
    private val size = fact(n)
    private val permList = longAry2(size, n)
    private tailrec fun fact(n: Long, ans: Long = 1L): Long {
        return if (n == 0L) ans
        else fact(n - 1, ans * n)
    }
    fun init() {
        create(0, longAry(n), boolAry(n))
    }
    private fun create(num: Long, list: LongArray, flag: Array<Boolean>) {
        if (num == n) {
            permList[searched] = list.copyOf()
            searched++
        }
        for (i in 0 until n) {
            if (flag[i]) continue
            list[num] = i
            flag[i] = true
            create(num + 1, list, flag)
            flag[i] = false
        }
    }
    fun hasNext(): Boolean {
        return if (nextIndex < size) {
            true
        } else {
            nextIndex = 0
            false
        }
    }
    fun nextPerm(): LongArray = permList[nextIndex++]
}
// String
fun zAlgo(s: String): LongArray {
    val n = s.len
    val res = longAry(n)
    var i = 1L
    var j = 0L
    while(i < n) {
        while (i + j < n && s[j] == s[i + j]) j++
        res[i] = j
        if(j == 0L) {
            i++
            continue
        }
        var k = 1L
        while (i + k < n && k + res[k] < j) {
            res[i + k] = res[k]
            k++
        }
        i += k
        j -= k
    }
    return res
}
// Graph
data class Node(val id: Long, var past: Long = -1, val edges: MutableList<Edge> = mutableListOf())
data class Edge(val from: Long, val to: Long, val cost: Long = 1L)
fun dfs(nodes: Array<Node>, now: Long, seen: Array<Boolean>) {
    seen[now] = true
    for (edge in nodes[now].edges) {
        if (seen[edge.to]) continue
        dfs(nodes, edge.to, seen)
    }
}
fun bfs(nodes: Array<Node>, start: Long): LongArray {
    val queue = ArrayDeque<Long>()
    queue.add(start)
    val dist = longAry(nodes.size.toLong(), -1L)
    dist[start] = 0L
    while (queue.isNotEmpty()) {
        val now = queue.poll()
        for (edge in nodes[now].edges) {
            if (dist[edge.to] != -1L) continue
            dist[edge.to] = dist[now] + 1
            queue.add(edge.to)
        }
    }
    return dist
}
fun dijkstra(nodes: Array<Node>, start: Long): LongArray {
    val queue = PriorityQueue<Pair<Long, Long>>(16) { x, y ->
        return@PriorityQueue when {
            x.second < y.second -> -1
            x.second > y.second -> 1
            else -> 0
        }
    }
    queue.add(Pair(start, 0L))
    val dist = longAry(nodes.size.toLong(), INF / 2)
    dist[start] = 0
    while (queue.isNotEmpty()) {
        val now = queue.poll()
        val v = now.first
        if (dist[v] < now.second) continue
        for (e in nodes[v].edges) {
            if(dist[e.to] > dist[v] + e.cost) {
                dist[e.to] = dist[v] + e.cost
                queue.add(Pair(e.to, dist[e.to]))
            }
        }
    }
    return dist
}
class GridGraph(
    private val h: Long,
    private val w: Long,
    val nodes: Array<Node> = Array((h * w).toInt()) { Node(it.toLong()) },
    private val edges: IntArray = IntArray((h * w).toInt()) { 0 }
) {
    private val up = 1
    private val right = 2
    private val down = 4
    private val left = 8
    private val queue: ArrayDeque<Long> = ArrayDeque()
    private val startPos = longList()
    private fun pos(y: Long, x: Long) = y * w + x
    fun canUp(v: Long) = (edges[v] and 1) == 1
    fun canRight(v: Long) = ((edges[v] shr 1) and 1) == 1
    fun canDown(v: Long) = ((edges[v] shr 2) and 1) == 1
    fun canLeft(v: Long) = ((edges[v] shr 3) and 1) == 1
    fun init(s: Array<String>, check: Char = '.', road: Char = '.', start: Char = 'S') {
        for (i in 0 until h) {
            for (j in 0 until w) {
                if(s[i][j] != check && s[i][j] != start) continue
                if(i > 0 && s[i - 1][j] == road) edges[pos(i, j)] += up
                if(i < h - 1 && s[i + 1][j] == road) edges[pos(i, j)] += down
                if(j > 0 && s[i][j - 1] == road) edges[pos(i, j)] += left
                if(j < w - 1 && s[i][j + 1] == road) edges[pos(i, j)] += right
                if(s[i][j] == start) {
                    queue.add(pos(i, j))
                    startPos.add(pos(i, j))
                }
            }
        }
    }
    fun addStart(y: Long, x: Long) {
        startPos.add(pos(y, x))
        queue.add(pos(y, x))
    }
    fun bfs(): LongArray {
        val dist = longAry(h * w, -1L)
        for (i in startPos) {
            dist[i] = 0L
        }
        while (queue.isNotEmpty()) {
            val v = queue.poll()
            if(canUp(v) && dist[v - w] == -1L) {
                queue.add(v - w)
                dist[v - w] = dist[v] + 1L
            }
            if(canDown(v) && dist[v + w] == -1L) {
                queue.add(v + w)
                dist[v + w] = dist[v] + 1L
            }
            if(canLeft(v) && dist[v - 1] == -1L) {
                queue.add(v - 1)
                dist[v - 1] = dist[v] + 1L
            }
            if(canRight(v) && dist[v + 1] == -1L) {
                queue.add(v + 1)
                dist[v + 1] = dist[v] + 1L
            }
        }
        return dist
    }
}
// Data Structure
class UnionFind(size: Long) {
    private val par = LongArray(size.toInt()) { it.toLong() }
    private val size = longAry(size, 1L)
    private val diffWeight = longAry(size, 0L)
    fun root(x: Long): Long {
        return if (par[x] == x) {
            x
        } else {
            val r = root(par[x])
            diffWeight[x] += diffWeight[par[x]]
            par[x] = r
            par[x]
        }
    }
    fun weight(x: Long): Long {
        root(x)
        return diffWeight[x]
    }
    fun diff(x: Long, y: Long) = abs(weight(y) - weight(x))
    fun same(x: Long, y: Long): Boolean = root(x) == root(y)
    fun unite(x: Long, y: Long, d: Long) {
        var w = d
        w += weight(x)
        w -= weight(y)
        var a = root(x)
        var b = root(y)
        if (a == b) return
        if (size[a] < size[b]) {
            var tmp = a
            a = b
            b = tmp
            w = -w
        }
        size[a] += size[b]
        par[b] = a
        diffWeight[b] = w
    }
    fun size(x: Long): Long = size[root(x)]
}
class SegmentTree(
    private val a: LongArray,
    private val op: (Long, Long) -> Long,
    private val def: Long = 0,
    private val size: Int = a.size,
    private val n: Int = Integer.highestOneBit(size) shl 1
) {
    private val nodes = longAry(2L * n - 1, def)
    fun init() {
        for (i in 0 until size) nodes[i + n - 1] = a[i]
        for (i in n - 2 downTo 0) nodes[i] = calc(nodes[2 * i + 1], nodes[2 * i + 2], op)
    }
    fun update(x: Long, value: Long) {
        var index = x + n - 1
        nodes[index] = value
        while (index > 0) {
            index = (index - 1) / 2
            nodes[index] = calc(nodes[2 * index + 1], nodes[2 * index + 2], op)
        }
    }
    fun get(a: Long, b: Long) = getSub(a, b, 0L, 0L, n.toLong())
    private fun getSub(a: Long, b: Long, k: Long, l: Long, r: Long): Long {
        return when {
            r <= a || b <= l -> def
            a <= l && r <= b -> nodes[k]
            else -> {
                val vl = getSub(a, b, k * 2 + 1, l, (l + r) / 2)
                val vr = getSub(a, b, k * 2 + 2, (l + r) / 2, r)
                calc(vl, vr, op)
            }
        }
    }
    fun joinToString(separator: String) = nodes.drop(n - 1).take(size).joinToString(separator)
}
// Scanner
class FastScanner {
    private val sin: InputStream = System.`in`
    private val buffer: ByteArray = ByteArray(1024) { 0 }
    private var ptr = 0
    private var buflen = 0
    private fun hasNextByte(): Boolean {
        return when {
            ptr < buflen -> true
            else -> {
                ptr = 0
                buflen = sin.read(buffer)
                buflen > 0
            }
        }
    }
    private fun readByte(): Int {
        return when {
            hasNextByte() -> buffer[ptr++].toInt()
            else -> -1
        }
    }
    private fun isPrintableChar(c: Int) = c in 33..126
    fun hasNext(): Boolean {
        while (hasNextByte() && !isPrintableChar(buffer[ptr].toInt())) ptr++
        return hasNextByte()
    }
    fun next(): String {
        if (!hasNext()) throw NoSuchElementException()
        val sb = StringBuilder()
        var b = readByte()
        while (isPrintableChar(b)) {
            sb.appendCodePoint(b)
            b = readByte()
        }
        return sb.toString()
    }
    fun nextLong(): Long {
        if (!hasNext()) throw NoSuchElementException()
        var n = 0L
        var minus = false
        var b = readByte()
        if (b.toChar() == '-') {
            minus = true
            b = readByte()
        }
        if (b.toChar() !in '0'..'9') throw NumberFormatException()
        while (true) {
            when {
                b.toChar() in '0'..'9' -> {
                    n *= 10
                    n += b.toChar() - '0'
                }
                b == -1 || !isPrintableChar(b) -> return if (minus) -n else n
                else -> throw NumberFormatException()
            }
            b = readByte()
        }
    }
//    "The world doesn't need you."
//
//    fun nextInt(): Int {
//        val nl = nextLong()
//        if (nl !in Int.MIN_VALUE..Int.MAX_VALUE) throw NumberFormatException()
//        return nl.toInt()
//    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0