AtCoder:9 ABC085C – Otoshidama

24/12/202025/12/2020

https://atcoder.jp/contests/abs/tasks/abc085_c
問題文は上記リンクを参照。

for文の数を減らすことが高速化のポイントです。
if分の方がfor文よりも圧倒的に早いので、条件が合わない場合直ぐにループを抜けるように条件チェックをします。
これは業務で書くプログラムでも一般的に行われる高速化の方法です。
その他一般的に行われる高速化の手法としては以下のようなものがあります。

• インスタンス化を減らす
• ボクシングを減らす

Kotlinではラベルを付けることにより、returnやbreakの位置を指定することができます。
これを使えばbreakを繰り返さなくても一度で繰り返し処理を終えることができます。

    loop@ for (i in 0..N) {
        for (j in 0..N - i) {
                break@loop
            }
        }
    }

上記のloop@がラベル定義で、for文が入れ子になっていますが、break@loopとラベルを指定することで一度で繰り返し処理を終えることができます。

以下のような書き方がありました。

for (x in 0..N) {
for (y in 0..N – x) {
val z = N – x – y
if (10000 * x + 5000 * y + 1000 * z == Y) {
println(“$x $y $z")
return
}
}
}

https://atcoder.jp/contests/abs/submissions/16092237

確かに既存の処理では、

x = i
y = j
z = N - i - j

といったように最終的にfor文の添え字をお札の枚数として代入していましたので、上記のように書けますね。