AGC 122-D We Like AGC (Kotlin) - あるエンジニアのAtCoder奮闘記

irisruneです。~~500点問題が厳しいので~~予定を変更して先週扱わなかったこの問題を。コードがかなり長いです。

Twitterで検索をしたら糸口というかほぼ答えが見つかったので解いてみました。 …が方針変更が激しくて変数名とかがめちゃくちゃになってます。

fun initList(lmChar : MutableList<MutableList<MutableList<MutableList<MutableList<Long>>>>>){
    val l3 = mutableListOf<MutableList<MutableList<MutableList<Long>>>>()
    for(b3 in 0..3) {
        val l2 = mutableListOf<MutableList<MutableList<Long>>>()
        for (b2 in 0..3) {
            val l1 = mutableListOf<MutableList<Long>>()
            for (b1 in 0..3) {
                val l0 = mutableListOf<Long>()
                for (b0 in 0..3) {
                    if(b0 + b1 + b2 + b3 == 0) l0.add(1L)
                    else l0.add(0L)
                }
                l1.add(l0)
            }
            l2.add(l1)
        }
        l3.add(l2)
    }
    lmChar.add(l3)
}

fun nextStep(lmChar : MutableList<MutableList<MutableList<MutableList<MutableList<Long>>>>>, i : Int){
    val l3 = mutableListOf<MutableList<MutableList<MutableList<Long>>>>()
    for(b3 in 0..3) {
        val l2 = mutableListOf<MutableList<MutableList<Long>>>()
        for (b2 in 0..3) {
            val l1 = mutableListOf<MutableList<Long>>()
            for (b1 in 0..3) {
                val l0 = mutableListOf<Long>()
                for (b0 in 0..3) {
                    val flag = calculator(listOf(b3, b2, b1, b0))
                    val value =
                        lmChar[i - 1][1][b3][b2][b1] + lmChar[i - 1][2][b3][b2][b1] + lmChar[i - 1][3][b3][b2][b1] + lmChar[i - 1][0][b3][b2][b1]
                    l0.add((value % 1000000007L) * flag)
                }
                l1.add(l0)
            }
            l2.add(l1)
        }
        l3.add(l2)
    }
    lmChar.add(l3)
}

fun calculator(l : List<Int>) : Long{
    if(l[0] == 1 && l[1] == 2 && l[2] == 3) return 0L
    if(l[0] == 2 && l[1] == 1 && l[2] == 3) return 0L
    if(l[0] == 1 && l[1] == 3 && l[2] == 2) return 0L
    if(l[1] == 1 && l[2] == 2 && l[3] == 3) return 0L
    if(l[1] == 2 && l[2] == 1 && l[3] == 3) return 0L
    if(l[1] == 1 && l[2] == 3 && l[3] == 2) return 0L
    if(l[0] == 1 && l[2] == 2 && l[3] == 3) return 0L
    if(l[0] == 1 && l[1] == 2 && l[3] == 3) return 0L
    return 1L
}

fun main(args: Array<String>){
    val n = readLine()!!.toInt()
    val lmChar = mutableListOf<MutableList<MutableList<MutableList<MutableList<Long>>>>>()
    initList(lmChar)
    for(i in 1..n) nextStep(lmChar, i)
    var retValue = 0L
    for(b3 in 0..3){
        for(b2 in 0..3){
            for(b1 in 0..3){
                for(b0 in 0..3){
                    retValue += lmChar[n][b3][b2][b1][b0]
                    retValue %= 1000000007L
                }
            }
        }
    }
    println(retValue)
}

『後ろ3文字を使ってDPする』という解法を自分なりに解釈して実装した結果がこれです。とりあえず躓いたポイントは、

Char型でfor文を回す方法がわからなかったので'A'=1,'G'=2,'C'=3,'T'=0としてInt型で扱うことに。
当初はMutableList<MutableMap<List<Int>, Long>>を使っていたが計算が上手くいかなかったので多次元リストに。
- 結論を言えば原因は次のポイント。
関数nextStep内でvalueを計算する際、式右辺の途中で改行が混ざると正しく計算できなかったので改行をやめた。

自力でDPを思いつかなかった所から躓いてるわけですが、この問題は実装力もかなり求められてますね… Kotlinの仕様を把握しきれていない点もあると思うので精進しましょう。

コードレビュー

lmCharという変数名が実態と全く乖離している。
- 当初はChar型で扱う予定だったがfor文が回せないとコードが肥大化するので断念。
- Mapを使う予定だったが多次元Listにした。
3/2/1文字前を表す変数としてb3/2/1と名付けているが意図がわかりにくい。
- bはbackではなくbaseだったりもする。

そもそものデータ構造の使い方とかがまずいのでコードレビューする箇所にキリがないですね。

雑記

同作問者のABC119-CでもそうでしたがDFSが出てこないのを何とかしたいです。
エクサウィザーズ2019は配点見て人権がないと思ってましたがAB早解きでパフォが盛れるコンテストでしたね。
今週は過去問を扱うことになりそうです。