😊

AtCoder Beginner Contest 276 A～Cのメモ

2022/11/06に公開

AtCoder

競プロ

tech

AtCoder Beginner Contest 276に参加したので記録を残しておきます。

A - Rightmost

後ろから探索して最初に見つかった位置が答えです。

fun main() {
    val s = readLine()!!
    val i = s.lastIndexOf('a')
    if(i == -1) {
        println("-1")
    } else {
        println(i+1)
    }
}

B - Adjacency List

問題文の読解に若干時間がかかってしまいました。
結局、都市から直接行ける別の都市リストを作ってそれをソートしてから出力するだけということになります。
重複がありうるのかわかってなかったですが、あったら面倒なのでSetで持っています。

import java.io.PrintWriter

fun main() {
    val (n, m) = readLine()!!.split(" ").map { it.toInt() }
    val abList = List(m) {
        readLine()!!.split(" ").map { it.toInt() }
    }
    val map = mutableMapOf<Int, MutableSet<Int>>()
    for(i in 1..n) {
        map[i] = mutableSetOf()
    }

    for(ab in abList) {
        map[ab[0]]!!.add(ab[1])
        map[ab[1]]!!.add(ab[0])
    }

    val out = PrintWriter(System.out)
    for(i in 1 .. n) {
        val list = map[i]!!
        if(list.isEmpty()) {
            out.println(0)
        } else {
            out.print(list.size)
            out.print(" ")
            out.println(list.sorted().joinToString(" "))
        }
    }

    out.flush()
}

C - Previous Permutation

難しかったです。（解けなかった）
順列の辞書順というのがまずイメージがつきづらくて、今でもよくわかってません…

解き方としては、問題文の通り順列の順番を求めてその1つ前の順列を求めるか、与えられた順列を1つ前の順列に変形するかのどちらかが考えられます。
後者のほうが簡単そうな気がしますが、私は完全に前者で行くつもりで実装してしまいました。それで順番を求めるところまではできたものの、その順番に対応した順列を求める方法がわからなくて撃沈しました。
もしかして後者のような方法のほうが簡単なのでは？と思った頃にはもう時間がほぼなく…

問題点としてはいくつか考えられますが、一つは単純に実装の手が遅いということ。もう一つは、実装しきれる目処が立っていないのに見切り発車で実装に着手してしまったことですね。
細部であれば、実装しながら考えるってことでもいいかもしれないですが、何番目の順列かという情報からそれに対応する順列をどうやって求めるか？というレベルのことはちゃんと考えないとわかるわけないですね…
そもそも本当にそんなことが可能なのかもわかってないまま実装し始めてしまったので、今考えてもアホとしか思えません。今後こういったことがないように恥を晒しておきます…

解説を見て、それ自体は可能であるとわかったのですが、どう見ても自力で導き出せるものではなかったです。
コンテスト中に書いて、解説を見て書き足して通したのが以下です。

import java.math.BigInteger

fun main() {
    val n = readLine()!!.toInt()
    val p = readLine()!!.split(" ").map { it.toInt() }

    val factorial = listOf(BigInteger.ONE) + (1..n).map { fact(it) }

    val bit = BinaryIndexedTree(n)
    var k = BigInteger.ZERO

    for(i in 0 until n) {
        k +=  ((p[i]-1).toBigInteger() - bit.sum(p[i]-1)) * factorial[n-i-1]
        bit.add(p[i], BigInteger.ONE);
    }
    k -= BigInteger.ONE

    println(kthPermutation(n, k, factorial).map { it + 1 }.joinToString(" "))
}

val mp = mutableMapOf<Int, BigInteger>()

fun fact(n: Int): BigInteger {
    if(n == 1) {
        return BigInteger.ONE
    }

    return if(mp.containsKey(n)) {
        mp[n]!!
    } else {
        val ret = n.toBigInteger() * fact(n-1)
        mp[n] = ret
        ret
    }
}

fun kthPermutation(n: Int, ik: BigInteger, factorial: List<BigInteger>): List<Int> {
    var s = (0 until n).toList()
    val l = mutableListOf<Int>()
    var k = ik
    for(i in 0 until n) {
        val a = factorial[n - 1 - i]
        val j = (k / a).toInt()
        k %= a
        l.add(s[j])
        s = s.subList(0, j) + s.subList(j+1, s.size)
    }
    return l
}

internal class BinaryIndexedTree(private val size: Int) {
    private val tree: MutableList<BigInteger> = IntArray(size+1).map { BigInteger("0") }.toMutableList()

    fun sum(ii: Int): BigInteger {
        var sum = BigInteger.ZERO
        var i = ii
        while(i > 0) {
            sum += tree[i]
            i -= i and -i
        }
        return sum
    }

    fun add(ii: Int, x: BigInteger) {
        var i = ii
        while (i <= size) {
            tree[i] += x
            i += i and -i
        }
    }
}

BinaryIndexedTree（BIT）と、階乗の計算と、それらを使って順列の何番目かを求める実装はコンテスト中にして、辞書順で何番目かをもとに順列を求める部分（kthPermutation）はコンテスト後に解説を見て書いています。

階乗は普通にループで求めればよかったような気がします。巨大な数値になるのでBigIntegerを使っています。

BITの実装や、それを使って順列の何番目かを求める実装は各所からパクっています。
特に、辞書順で何番目なのかというのはまんまそれという問題とその解説を見つけてしまったので、それに引きずられたというのはあります。

このようなものに惑わされるのは弱さ故です…
ありものを流用するのはある意味重要なスキルではあるのですが、それで完全に解き切れるのかまで考えられずに飛びついてしまったのはもうほんと大反省です。
それで途中まではできたとしても、最終的にACできなければ無意味でしかありません。

なお、与えられた順列を変形して前の順列を求める実装もやってみました。

import java.util.*

fun main() {
    val n = readLine()!!.toInt()
    val p = readLine()!!.split(" ").map { it.toInt() }.toMutableList()

    for(i in (n-1) downTo 1) {
        if(p[i-1] > p[i]) {
            val before = p.subList(0, i-1)
            val after = p.subList(i-1, n).toMutableList()

            val max = after.subList(1, after.size).filter { it < after[0] }.max()!!
            val maxIdx = after.indexOf(max)

            Collections.swap(after, 0, maxIdx)

            val list = before + after[0] + after.subList(1, after.size).sortedDescending()
            println(list.joinToString(" "))
            return
        }
    }
}

こちらを参考にしています。

こちらのほうが明らかに簡単なので、こちらに全力を振り向けていれば解けていた可能性もあります。
まあ、これはこれで法則を自力で見出だせたか怪しく、実装も添え字操作で混乱してけっこう難しかったので、やっぱり解けなかった可能性も高いですが…

教訓

考察が不十分なまま実装に着手しないこと
- 特に、中途半端に流用できそうな情報を見つけてもすぐに飛びつかず、最終的に答えが導けるかどうかまで考えること
実装スピードも鍛えたほうがいい
順列の辞書順など、数学的な知識も圧倒的に不足している

今回は特に力不足を感じました。反省を今後に活かします。

A - Rightmost

B - Adjacency List

C - Previous Permutation

教訓

Discussion