yu/logs/*

技術メモ など

AtCoder ABC276 C 解法メモ (Kotlinで)prev_permutationしたい ※ついでにnext_permutationも

前にnext_permutationの実装で試行錯誤したものの、すっかり忘れてしまっていたので備忘を兼ねて

解いていた問題

atcoder.jp

解法メモ

  • いろいろ参考にしてnext_permutation、prev_permutation相当のものを事前に実装しておいちゃう
    • 今回の問題はprev_permutationがあればサクッと解ける
    • ↓が事前に準備しておいたnext_permutationと、事後的に準備したprev_permutation
    /**
     * next_permutation
     * 受け取ったリストの次の順列にarrayを更新する
     * [1, 2, 3, 4, 5] -> [1, 2, 3, 5, 4]
     *
     * コードの参考: https://koboshi-kyopro.hatenablog.com/entry/2021/07/21/193611
     * コメントの参考: https://qiita.com/Nikkely/items/0ddca51b3c0e60afbaab
     */
    fun nextPermutation(array: MutableList<Int>): Boolean {
        // i: array[i] < array[i + 1]を満たすもののうちインデックス最大のものを探す。のでdownToでループ
        for (i in array.lastIndex - 1 downTo 0) {
            if (array[i] < array[i + 1]) {
                // j: 末尾から探索して初めて現れるarray[i]より値が大きい要素のインデックスを探す。
                for (j in array.lastIndex downTo i + 1) {
                    if (array[j] > array[i]) {
                        // 見つけた。array[i]とarray[j]を入れ替える
                        val tmp = array[i]
                        array[i] = array[j]
                        array[j] = tmp

                        // i+1以降の要素を昇順に並べ替える
                        // i番目までは入れ替え済みor関係ないので、i+1番目からをtakeLastで取得してソート
                        val tmpArray = array.takeLast(array.size - (i + 1)).sorted()
                        tmpArray.forEachIndexed { index, e ->
                            // tmpArrayのindex == arrayのi+1+indexなので、ソート済みの値で上書きしていく
                            array[i + 1 + index] = e
                        }

                        return true
                    }
                }
            }
        }
        return false
    }

    /**
     * prev_permutation
     * 受け取ったリストの前の順列にarrayを更新する
     * [1, 2, 3, 5, 4] -> [1, 2, 3, 4, 5]
     *
     * nextPermutationをベースに不等号、ソート順を修正
     * 修正方針の参考:https://qiita.com/HMMNRST/items/26786552a2660735d34f
     */
    fun prevPermutation(array: MutableList<Int>): Boolean {
        // i: array[i] < array[i + 1]を満たすもののうちインデックス最大のものを探す。のでdownToでループ
        for (i in array.lastIndex - 1 downTo 0) {
            if (array[i] > array[i + 1]) {
                // j: 末尾から探索して初めて現れるarray[i]より値が小さい要素のインデックスを探す。
                for (j in array.lastIndex downTo i + 1) {
                    if (array[j] < array[i]) {
                        // 見つけた。array[i]とarray[j]を入れ替える
                        val tmp = array[i]
                        array[i] = array[j]
                        array[j] = tmp

                        // i+1以降の要素を降順に並べ替える
                        // i番目までは入れ替え済みor関係ないので、i+1番目からをtakeLastで取得してソート
                        val tmpArray = array.takeLast(array.size - (i + 1)).sortedDescending()
                        tmpArray.forEachIndexed { index, e ->
                            // tmpArrayのindex == arrayのi+1+indexなので、ソート済みの値で上書きしていく
                            array[i + 1 + index] = e
                        }

                        return true
                    }
                }
            }
        }
        return false
    }

処理フローのメモ

ざっくりした流れ

  • iを決める
  • jを決める
  • i,jをswap
  • iより後ろをソート
  • ↑の流れがベースで次の順列を求めるか前の順列を求めるかで不等号やソート順が逆になる

(とても)汚い概略図

ほぼ自分用です、すみません。でも理解できている人には不要だと思うし、理解が甘ければ実際に書いてみるとイメージアップしやすいかと思うので、大丈夫だと思います(?)

提出した回答

参考