AtCoder Regular Contest 153 Aのメモ
AtCoder Regular Contest 153（ARC153）に参加したので記録を書いておきます。
ARCに参加したのは初めてです。ARCのAはABCのCくらいの難易度はあるのかなというイメージで、0完でレーティングを溶かす可能性も高かったのですが、まあ自称レーティングに執着してないマンとしてはそんなことを気にする理由はなかったと気づきました。
さて結果は？
A - AABCDDEFE
Nの具体的な制約は書かれていないですが、110000000から999999999の全探索だと間に合わないのはわかります。
出力例1のところに、美しい数の具体例として110000000,110000010,110000020と記載があります。つまり、次の美しい数とは基本的には前から8桁目をインクリメントした数ということになります。その桁が既に9となっていたら桁上りを考えないといけないですが、逆に桁上りにさえ注意すれば美しい数に関係のある桁をインクリメントすれば次の美しい数を得られます。それをN-1回実行することで欲しい数を得られる、という発想で実装しました。
しかしながら、目を覆わんばかりの醜いコードとなりました…
コメントは後から追記したものです。
fun main() {
val n = readLine()!!.toInt()
val bn = "110000000".toMutableList().map { it - '0' }.toMutableList()
var cnt = 1
while (true) {
if(cnt == n) {
break
}
bn.next()
cnt++
}
println(bn.joinToString(""))
}
fun MutableList<Int>.next() {
this.add(0, 0)
if(this[8] != 9) {
// 前から8桁目が9でなければインクリメントするだけ
this[8]++
} else {
// 前から8番目が9だったら桁上りのため0にする
this[8] = 0
// 上位の桁もインクリメントする
if(this[7] != 9) {
// 前から7番目と9番目は同じなので9番目を書き換える
this[7]++
this[9] = this[7]
} else {
// 前から7番目が9だったら桁上がりのため0にする
this[7] = 0
// 前から7番目と9番目は同じなので9番目を書き換える
this[9] = 0
// 上位の桁もインクリメントする
if(this[6] != 9) {
// 前から5番目と6番目は同じなので5番目を書き換える
this[6]++
this[5] = this[6]
} else {
// 前から6番目が9だったら桁上がりのため0にする
this[6] = 0
// 前から5番目と6番目は同じなので5番目を書き換える
this[5] = 0
// 上位の桁もインクリメントする
if(this[4] != 9) {
this[4]++
} else {
// 前から4番目が9だったら桁上がりのため0にする
this[4] = 0
// 上位の桁もインクリメントする
if(this[3] != 9) {
this[3]++
} else {
// 前から4番目が9だったら桁上がりのため0にする
this[3] = 0
// 上位の桁もインクリメントする。前から1番目と2番目は同じで、桁上りするとは考えられないのでそのままインクリメント
this[2]++
// 前から1番目と2番目は同じなのでこちらもインクリメント。桁上りを考慮しないのも同じ
this[1]++
}
}
}
}
}
this.removeAt(0)
}
コアなロジックは MutableList<Int>.next() で実装しています。これは拡張関数というKotlinの機能で、既存の型にメソッドを追加する構文です。そんなことせずに普通に引数としてMutableList<Int>をとる関数を実装すればよかったのですが、なぜかこうしていました。
この場合、thisがそのインスタンス自身を指すのでthisをひたすら書き換えています。thisが並ぶとこんなに威圧感があるとは知りませんでした…
0-indexedで考えると確実にバグらせるので最初に1-indexedに補正するためにダミーデータを挿入し、最後に除去しています。これらのメソッドは計算量としてはアレですが、9桁なのでセーフという感じです。
やっていることとしては、最初に書いた通り前から8桁目をインクリメントします。桁上りが発生する場合は素直にそれを実装し、それによって美しい数となるための条件の桁が変更されたら連動して関連する桁も変更します。
前から8番目の、桁上りも考慮したインクリメントを実装しただけで実装が終わったので前から8番目以外は桁上りによってしか変わらないということですね。
前から1番目と2番目が桁上りすると9桁ではなくなってしまうので、問題の制約からここが桁上りする前に答えが見つかるはず、ということでここは桁上りを考慮していません。
酷いコードですが、まあ一応通ったのでよかったです。こんなのよくバグらせずに実装できたなと思いますが…
ビビリながらだったこともあってか時間もかかってしまいましたし。
書き直し
あんまりなので、もうちょっとマシな実装でやり直してみました。
問題文が一つのヒントといえばヒントだったようで、つまり9桁だけど6種類の数値で構成されるので、6種類の数値の組み合わせを全探索すればいいだろうと。
それならだいたい
fun main() {
val n = readLine()!!.toInt()
val list = mutableListOf<String>()
for(a in 1..9) {
for(b in 0..9) {
for(c in 0..9) {
for(d in 0..9) {
for(e in 0..9) {
for(f in 0..9) {
list.add(listOf(a, a, b, c, d, d, e, f, e).joinToString("") { it.toString() })
}
}
}
}
}
}
println(list[n-1])
}
6重ループもそれはそれで美しくないですが、まあ最初のよりはマシですね。
途中で探索を打ち切ってもいいけど、最後まで実行しても間に合うのでまあいいやと思っています。
これならサクッと実装できたので、これを思いつけなかったのは残念ですね。
B問題？わからなすぎて早々に諦めました。
感想
ということでARC初参加でした。
0完も普通にありえましたが、ARCにしては難しくない問題だったようなので助かりました。遅れたけど一応レーティングもプラス。
しかし、もっと難しい問題でウンウン唸るつもりでいたので、少し想定と違いましたね。サンプル数1ではなんともいえないので次回以降も可能な範囲で参加してみたいと思います。
今度こそ0完かもしれませんが。
（執筆時間：41分35秒）
Discussion