🐥

ABC 268 D - Unique Username

2023/10/22に公開

AtCoder

競プロ

tech

重実装問題を募集したら教えてもらったので解きました。解けてうれしい。

考察

まず $N$ の制約が非常に小さいので、全部試してもいいんじゃないかと思いました。順列ですね。順列のパターンは $N!$ 通りなので、 $N$ の最大値でも1から8までをかけあわせて40,320通り。これくらいなら全部試しても問題ありません。

ただ、アンダースコアを入れる個数が1以上なので、そのパターンを列挙した数も掛け合わせる必要があります。アンダースコアを入れるパターンをどうやって列挙するのか悩んだのですが、文字列の長さに上限があるので、各 $Si$ をアンダースコア1つで結合した文字列をベースと考えて、それに対して何個のアンダースコアを足せるかと考えました。
文字列は最大16文字までなので、たとえばベースが10文字ならあと6文字アンダースコアを入れることができます。仮に $N$ が4ならアンダースコアを入れることが可能な位置は3つ、それに対して6つのアンダースコアを配分するという感じ。配分する方法は悩みましたが、この例でいうと単純に3桁の7進数のように考えました。つまり $000$ から $666$ までを列挙すればいいだろうと。ただ、6つしか配分できないのにこれだと無駄が多いので、6つを超えたらやめるようにします。いわゆる枝刈りです。
ここまでわかれば実装できそう。

実装

以下のようになりました。

import kotlin.system.exitProcess

fun main() {
    val (n, m) = readln().split(" ").map { it.toInt() }
    val s = MutableList(n) {
        readln()
    }
    val t =(1..m).map { readln() }.toSet()

    // 順列
    val permutation = Permutation(s)
    permutation.forEach {
        val x = it.joinToString("_")
        if(x.length > 16 || x.length < 3) {
            println(-1)
            exitProcess(0)
        }

        if(x !in t) {
            println(x)
            exitProcess(0)
        }

        val rest = 16 - x.length
        rec(rest, it, t, IntArray(n - 1) { 1 }, 0)
    }

    println(-1)
}

private fun rec(maxCount: Int, list: MutableList<String>, t: Set<String>, array: IntArray, current: Int) {
    if(current > maxCount) {
        return
    } else {
        val s = join(list, array)
        if(s !in t) {
            println(s)
            exitProcess(0)
        }
    }

    for(i in array.indices) {
        array[i]++
        rec(maxCount, list, t, array, current + 1)
        array[i]--
    }
}

private fun join(list: MutableList<String>, array: IntArray): String {
    val sb = StringBuilder()
    for(i in list.indices) {
        val s = list[i]
        sb.append(s)

        if(i != array.size) {
            sb.append("_".repeat(array[i]))
        }
    }
    return sb.toString()
}

class Permutation<T>(private val list: MutableList<T>) {
    private val queue = ArrayDeque(list)

    fun forEach(action: (MutableList<T>) -> Unit) {
        forEach(0 ,0, action)
    }

    private fun forEach(count: Int, layer: Int, action: (MutableList<T>) -> Unit) {
        if(count == list.size) {
            action(list)
            return
        }

        for(i in count until list.size) {
            val elem = queue.removeFirst()
            list[layer] = elem
            forEach(count + 1, layer + 1, action)
            queue.add(elem)
        }
    }
}

Permutationはこの問題を解くために作ってみました。

Permutationがあれば、あとはアンダースコアを配分するところが実装できればいけますね。これは再帰で実装しています。

exitProcess(0) とか出てくるのがちょっと気持ち悪いですね… Permutationがinline化されていなくて、main関数自体から抜けるためのreturnができなかったためです。
このPermutationは適宜手を加えていきたいところです。
（執筆時間: 18分3秒）

考察

実装

Discussion