🙆

【ABC263】「C - Monotonically Increasing」のメモ

2022/08/07に公開

AtCoder

競プロ

tech

LINE Verda プログラミングコンテスト（AtCoder Beginner Contest 263）のC問題を解けなかったので、解説を見て理解した（かもしれない）内容をまとめてみます。

コンテスト中に書いたコード

この問題は範囲を絞った全探索で解けるとは思ったのですが、どう実装したらいいのかはわかりませんでした。
Nが固定であれば単純な多重ループで解けるのですが、可変なのでその方法はとれません。
（まあ、Nが10以下と制約が小さいのを利用してNの値で場合分けしてそれぞれで多重ループを書いている人を見てなるほどーと思ったのですが、それはさておき）

Nが可変な場合の探索方法として、数列をN桁の(M+1)進数の数とみなして1ずつ増やしていくという方法があります。最初に思いついたのがその方法だったのでとりあえずそれで実装しました。

使用言語がC++からKotlinにしれっと変わっているのには深い理由はありません。なんとなくそうしたかったのです。

import kotlin.math.pow

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

    var num = 1
    val radix = m + 1
    val limit = radix.toDouble().pow(n).toInt()
    while(num < limit) {
        val list = toNRadix(num, radix)
        while (list.size < n) {
            list.add(0)
        }
        list.reverse()

        if(list.all { it in 1..m } && list == list.sorted() && list.distinct().size == n) {
            println(list.joinToString(" "))
        }
        num++
    }
}

private fun toNRadix(target: Int, m: Int): MutableList<Int> {
    val list = mutableListOf<Int>()
    var tmp = target
    while (tmp > 0) {
        list.add(tmp % m)
        tmp = (tmp - (tmp % m)) / m
    }
    return list
}

これは範囲を絞らない全探索ですので無駄が多く、TLEになるのが明らかではありました。（実際そうなりました。）
このアプローチだと、numを愚直に1ずつ増やすのではなく、最初から数列が単調増加となるような数まですっ飛ばすことができれば現実的な実行時間で終わるということになります。
しかし、その方法が結局わかりませんでした。仮にわかったとしても、numの増分を求めるのが面倒そうなので絶対もっといいやり方があるだろ…と思いましたが後の祭り。

解説を見て書いたコード

内容的には解説のコードをほぼそのままKotlinに翻訳しただけなのですが…

fun main() {
    val (n, m) = readLine()!!.split(" ").map { it.toInt() }
    dfs(emptyList(), n, m)
}

private fun dfs(list: List<Int>, n: Int, m: Int) {
    if(list.size == n) {
        println(list.joinToString(" "))
        return
    }

    val start = if(list.isEmpty()) {
        1
    } else {
        list.last() + 1
    }

    for(i in (start..m)) {
        dfs(list + listOf(i), n, m)
    }
}

ここで、DFSという手法があることを学びました。多重ループによる列挙は再帰で置き換えることができる、ということになります。
列挙したい対象で1重ループを回し、その中で再帰呼び出しする。そのとき、引数には要素を1つ増やしたリストを渡す。リストの件数が所定の件数になったときに処理を行い、そこが再帰の終了条件になる、と。
これの何がうれしいかというと、多重ループでいうならループのネスト数を変数の値によって柔軟に変更できる、ということになります。多重ループはソースコード上で固定されているので、二重ループなら二重ループにしかならないけど、DFSを使えばNを変えることで二重ループにも三重ループにもできます。え、、めっちゃ便利じゃん！！

愚直な全探索ももちろん可能ですが、今回のケースだと + 1した値からループを開始するようにすることで範囲を絞った探索を実現しています。

ループ内の再帰というと、流れを追おうとすると混乱するので、そのようなことはせずにもうパターンとして覚えてしまおうと思います。このように書けば列挙、探索できるぞと。

これで、要素数が可変な場合の探索（それも範囲を絞った探索）を実現する方法を覚えることができました。うれしいです。

感想

教訓

今回の敗因は単純な知識不足と思ったので、アルゴリズムの道具箱を充実させる必要がある
今回はDFSを道具箱に加えることができた

コンテスト中に書いたコード

解説を見て書いたコード

感想

教訓

Discussion