AGC 032 A Limited Insertion (Kotlin) - あるエンジニアのAtCoder奮闘記

irisruneです。今回は少し長めに書いてみました。

この問題は解き方は明確なんですが、そこにたどり着くまでが長かったので思考面に重点を当てたいと思います。~~前回言った糸口は嘘でした。~~

fun main(args: Array<String>){
    val n = readLine()!!.toInt()
    val ln = readLine()!!.split(" ").map(String::toInt).toMutableList()
    val lRet = mutableListOf<Int>()
    while(ln.size > 0){
        for(i in ln.size.downTo(0)){
            if(i == 0){
                println(-1)
                return
            }
            if(ln[i - 1] == i){
                lRet.add(ln[i - 1])
                ln.removeAt(i - 1)
                break
            }
        }
    }
    lRet.reverse()
    lRet.forEach{
        println(it)
    }
}

解き方は解説の通り、数列の（1始まりの）インデックスと項の値が一致するもののうち、一番右の（インデックスが大きい）ものを取り除いて出力の末尾に加える操作を繰り返せばいいだけです。操作ができなくなった時点で数列が空でなければ元の数列は作れないことになります。

…なんですが、この問題は割と入力例が簡単すぎて違う解法でもできそうに見えてしまうのが罠だと思います。例えば、入力例3の

9
1 1 1 2 2 1 2 3 2

については、

1 1 122 1232

というように1始まりのブロックに分けて考えることでなんとなく出力例3が導けそうに見えてきます。

ですが、入力として例えば

5
1 2 3 2 4

が与えられたとき、数列を前から舐めるだけでは

を導くのは困難だと思います。少なくとも自分は方法が思いつきませんでした。

ここでなぜ数列を前から舐める方法が困難になるかを考えることにします。そもそも入力された数列が作成できないケースはというと、例えば

5
1 2 4 2 3

のように、インデックスより大きな値を持つ項が存在する数列は作ることができません。逆に、この条件さえ満たさない数列は作成できてしまうということが $N$ が小さいケースで試すと見えてきます。~~証明はできてません。~~

そのため作成される数列の自由度が高いことから、数列を前から舐めながら作成手順を導き出すのは困難になってしまいます。

そこから解答に行き着くまでですが、自分の場合は

という形が急に見えたので解くことができました。~~ここまで書いて結局フィーリングですか？~~

とりあえず今回の問題の教訓は提示された入力例以外にも怪しいものを試してみることだと思います。TLEがネックになりそうな問題には使えないですが…

コードレビュー

~~調べるのが面倒だったので~~ループにラベルを付けていないおかげで作成手順がない場合の処理がやや強引。
~~これまた調べるのが面倒だったので~~入力リストのインデックスを1始まりにしていないので項の値と比較する際にズレが生じている。
- 要素1のリストを用意してplusメソッドを使えばいい。その他部分は適宜修正。

val ln = listOf(-1).plus(readLine()!!.split(" ").map(String::toInt)).toMutableList()

雑記

逆詐称でもない400点問題で早解きしてもパフォ1300行かないのはレベルが高すぎますね…
次回記事は明日開催のエクサウィザーズ2019を扱う予定です。リアルタイムで参加できるかは未定ですが。