🙄

ARC146 A - Three Cardsのメモ

2023/01/14に公開

AtCoder

競プロ

tech

ARCの問題にも手を出してみました。

考察

基本的には大きい数を採用するはずですが、単純に数値として大きい順に並べるのが正解とは限りません。たとえば99と100だったら数値としては100のほうが大きいですが、99を先に並べたほうが大きくなります。
なのでソートするだけではダメなのですが、かといって全探索が間に合うような制約ではありません。

いろいろごっちゃにして考えると混乱しますが、しばらく考えて「どの3つを採用するか」と「採用した3つをどのような順番で並べるか」を別々に考えればすっきりすることに気づきました。
99と100だったら99を先に並べると書きましたが、これは後者に関する問題で、前者には関係ないと。99と100のどちらを採用するかといったら間違いなく100のほうです。

「どの3つを採用するか」については、単純に大きい数3つを選べばよさそうです。どの数を採用するかという観点だと、一番大きな位の桁の数の大きさよりも数全体としての大きさが大きいほうが優先されます。（桁数が多いほうを選ぶ）
つまり、単純に数として大きい3つを選びます。

「採用した3つをどのような順番で並べるか」ですが、最初は文字列としてソートしてみて、とかやっていたのですが、3つしかないのでこれは全探索でも問題ないと気づきました。

実装

maxのimportは残骸です…

import java.math.BigInteger
import kotlin.math.max

fun main() {
    val n = readLine()!!.toInt()
    val a = readLine()!!.split(" ").map { it.toInt() }

    val three = a.sortedDescending().take(3).map { it.toString() }

    var ans = BigInteger.ZERO
    for(i in 0 until 3) {
        for(j in 0 until 3) {
            for(k in 0 until 3) {
                if(listOf(i, j, k).distinct().size != 3) {
                    continue
                }
                val num = three[i].plus(three[j]).plus(three[k]).toBigInteger()
                if(ans < num) {
                    ans = num
                }
            }
        }
    }
    println(ans)
}

大きな数3つは、降順ソートしてから先頭の3つを取得すればいいです。

3つを決めたら、その3つの並べ方を全探索して一番大きくなったものを採用します。
3つを連結して数値にするとかなり大きくなるのでBigIntegerを使いました。しかし、今思えばLongでも別に問題ないですね…

なお、3つを文字列としてソートする解法も先に提出したのですが、これはafter_contestのケースのみで落ちました。つまり嘘解法です。

fun main() {
    val n = readLine()!!.toInt()
    val a = readLine()!!.split(" ").map { it.toInt() }

    val three = a.sortedDescending().take(3)
    println(three.sortedByDescending { it.toString() }.joinToString(""))
}

文字列として降順ソートするとうまくいかないケースがあります。たとえば1と10の2つなら110と並べるべきですが、上記の実装だと101と並んでしまいます。

じゃあどうやってソートすればいいんだ？と悩みましたが、3つしかないんだから全探索でいいじゃんと気づいた次第です。

(執筆時間：19分16秒)

考察

実装

Discussion