【覚書】ABC257-B: 1D Pawn

覚書です。

概要

URL

問題ページ
公式解説

入力

n： マス数
k： コマ数
q： 操作数
a_i： 左からi + 1つ目のコマの初期位置
l_i： i + 1番目に操作するコマの番号

n k q
a_1 a_2 ... a_k
l_1 l_2 ... l_q

操作

配列lで指定されたコマをひとつ右に動かす。このとき、

• 右に別のコマが存在する
• コマの位置が最右（それ以上右にマスが存在しない）である

場合は操作を行わない。

出力

左からindex + 1つ目のコマの初期位置を空白区切りで出力する

b_1 b_2 ... b_k

提出コード

fun main(args: Array<String>) {
    // 入力
    val (n, k, q) = readLine()!!.split(" ").map(String::toInt)
    val a = readLine()!!.split(" ").map(String::toInt)  // 各コマの初期位置
    val l = readLine()!!.split(" ").map(String::toInt)  // 操作

    // マスを定義
    var math = MutableList(n) { 0 }

    // マス上にコマを配置
    for(i in a.indices) math[a[i] - 1] = i + 1

    // コマの位置を記録
    var pieceIndexes = mutableListOf<Int>()
    math.forEachIndexed { index, i ->
        if(i != 0) pieceIndexes.add(index)
    }

    // 操作
    var mathIndex: Int  // 指定したコマの存在するマス
    for(i in l) {
        mathIndex = pieceIndexes[i - 1]

        // 例外処理
        if(mathIndex + 1 >= math.size) {
            continue
        }
        if(math[mathIndex + 1] != 0) {
            continue
        }

        math[mathIndex + 1] = math[mathIndex]
        math[mathIndex] = 0
        pieceIndexes[i - 1]++
    }

    // 出力
    var out = mutableListOf<Int>()
    math.forEachIndexed { index, it ->
        if(it != 0) out.add(index + 1)
    }
    println(out.joinToString(" "))
}

課題点

• 「コマの初期位置を記録する配列」「マス状態を記録する配列」「移動したコマの位置を記録する配列」など、同じオブジェクトの状態を扱う変数が複数に分かれている
  • これによって記述中にすごく混乱した
  • そもそも一時配列に擬似的にマスを再現する必要がない（各コマの経過だけ追えばいい）

解決法

• 変数aを各コマの位置遷移を記録する変数として利用する

付記

配列への挿入に+=演算子を利用していたが、実行環境では対応していない(コンパイルエラーを吐いてしまった)ため、MutableList.add()で代用している。

リファクタリング後

fun main(args: Array<String>) {
    val (n, k, q) = readLine()!!.split(" ").map(String::toInt)
    var a = readLine()!!.split(" ").map(String::toInt).toMutableList()  // 各コマの初期位置
    val l = readLine()!!.split(" ").map(String::toInt)  // 操作

    l.forEach {
        // コマが端にある場合はパス
        if(a[it - 1] == n) {
            return@forEach
        // 最右のコマなら動かす(14行目のIndexError対策)
        } else if(it == k) {
            a[it - 1] += 1
        // 動かすコマの移動先にコマがなければ動かす
        } else if((a[it - 1] + 1) < a[it]) {
            a[it - 1] += 1
        }
    }

    // 出力
    println(a.joinToString(" "))
}