💡

ABC 118 C - Monsters Battle Royaleのメモ

2023/09/23に公開

AtCoder

競プロ

tech

解いてみました。

考察

自分がモンスターと戦うわけじゃないんかって思いましたがまあそれはどうでもいいとして。

ランダムってどういうことなのかと少し思いましたが、あり得るパターンの中での最小値を求めるということなので最小値になるパターン以外は考えなくてよく、つまり攻撃については自由に選んでいいと理解しました。
攻撃回数については直接的には上限がないので、体力が最小のモンスターが他のモンスターを駆逐することでそれが最小になる、つまり体力が最小のモンスターの体力が答えになるのではと最初は思いました。しかしC問題がそんなに簡単なはずもなく、また例2が反証となっていました。

なので例2で考えてみます。

入力例 2

4
5 13 8 1000000000

出力例 2

最初に書いたのが正しいのだとしたら答えは5のはずですが、実際には1となっています。どのような経過で1になるのか少し考えてみましたが、たとえば以下のようなパターンがあり得そうでした。

1番目のモンスターが3番目のモンスターを攻撃し、3番目のモンスターの体力が3になる
3番目のモンスターが4番目のモンスターを333333333回攻撃し、4番目のモンスターの体力が1になる
4番目のモンスターが1番目のモンスターを5回攻撃し、1番目のモンスターは死ぬ
4番目のモンスターが2番目のモンスターを13回攻撃し、2番目のモンスターは死ぬ
4番目のモンスターが3番目のモンスターを3回攻撃し、3番目のモンスターは死ぬ

これで4番目のモンスターが最後に生き残ったモンスターとなり、その残り体力である1が答えになると。

なので「体力が最小のモンスターが他のモンスターを駆逐することでそれが最小になる」というの自体は間違っていないのですが、その最小の体力は初期値とは限らず、他のモンスターから攻撃を受けて減った後の体力の可能性がありますと。
つまり、単純に全パターンの中であり得る体力の最小値を求めればいいことになります。攻撃パターンは自由に選べるため、体力が最小となったモンスターが生き残れるかどうかは考えなくていい（生き残らせればいい）と。

じゃあそれをどうやって求めればいいのかというと、ここでけっこう詰まったのですが、結論としては単純に全部調べればいいとなりました。
まずは $Ai$ のうち最小値を求めます。それから $Ai$ の各値について最小値で割った余りを求めます。欲しいのは各モンスターについて死なないギリギリまで攻撃した場合の体力ですが、それは割った余りで求められます。それで、求めた値の中で元々の最小値よりも小さいもの（0は除く）が見つかった場合はその新しい最小値で同じ操作をします。それを新たな最小値が得られなくなるまで繰り返せば答えが得られます。

すごく当たり前な感じに見えますが、これだと $O(N)$ の操作を何度も実行することになるので間に合わないのではと思って、なかなかこのやり方にたどり着きませんでした。
しかし、実際には $10^5$ という制約のもとではそんなに大した回数にならないことがわかりました。
以下のようなしょうもないコードで確認してみました。

fun main() {
    var n = 100000

    while (true) {
        val nn = (1..n).maxOfOrNull { n % it }
        println(nn)

        if(nn == null || n == nn) {
            break
        }
        n = nn
    }
}

出力結果は以下の通り。

つまり最大でも16回程度。この程度であれば定数倍とみなして、全体の計算量も $O(N)$ と考えてよさそうです。

実装

けっこうミスったのですが…最終的には以下のコードになりました。

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

    var minNum = a.min()
    var minChanged = true

    while (minChanged) {
        minChanged = false

        var currentMin = -1
        for(i in 0 until n) {
            val mod = a[i] % minNum

            if(mod !=0 && mod < minNum) {
                currentMin = mod
                minChanged = true
                a[i] = currentMin
            }
        }

        if(minChanged) {
            minNum = currentMin
        }
    }

    println(minNum)
}

気をつけるのは割った余りが0の場合は除外するのと、最小値として採用した要素については割った余りの値に更新しておく必要があること、逆にそれ以外の要素については元の値のままとしておくこと、くらいですかね。

ミスったポイントとしては、値を更新するのを忘れていたとか、一旦見た要素を再度見ないようにするという謎の制御を入れてしまった、とかですね…しょうもない。
一応、考え方としては最小値としている要素自身を割るのはおかしいので除外するのがいいのですが、値を更新しているので自身を割った余りは必ず0ですし、0だったら無視するわけなので、結果的に実装としては特に気にしなくてよくなっているという感じです。

（執筆時間: 1時間1分37秒）

考察

実装

Discussion