Atcoder ABS ABC088B Card Game for Two

こんにちは、ナナオです。

前回に引き続き競プロを実施していきたいと思います。

今回の問題は以下です。

実装

以下のように実装しました。

use proconio::input;

fn main() {
    input! {
        n: u8,
        mut a: [i16; n],
    };
    a.sort_by(|a, b| b.cmp(a));
    let mut a_sum = 0;
    let mut b_sum = 0;
    for (i, &v) in a.iter().enumerate() {
        if i % 2 == 0 {
            b_sum += v;
        } else {
            a_sum += v;
        }
    }
    println!("{}", (a_sum - b_sum).abs());
}

数列を大きい順に並べ替えて、それぞれを交互に足し合わせて最終的にその差を出力するという実装ですが、これでいいみたいですね。

（ぶっちゃけ出力例がなかったらどうすればいいのかわけわからんかった。。。）

AIさんに聞いてみましたら、わかりやすい返答が返ってきました。

ケーキの分けっこで考えよう

例えば、目の前に大きさがバラバラのケーキが5個あるとします。

あなたはアリスで、先に1個選べます。友達のボブはあなたの次に選びます。

ケーキのサイズ： 10cm, 8cm, 5cm, 3cm, 2cm

もしあなたが「合計を最大にしたい」と思ったら、どれを取りますか？当然、一番大きい 10cm ですよね。

もしここであなたが「後でいいのが残るかも？」なんて遠慮して 3cm を取ったら、次にボブが 10cm を取ってしまいます。これではあなたの得点はボブに負けてしまいます。

「今ある中で一番大きいのを取る」。これが、相手に邪魔をされずに自分のスコアを一番高くする唯一の方法なんです。

…ということで、よくわかりました。確かにそうですね。

そして差は必ず正の整数になるはずなので、少し修正しました。

use proconio::input;

fn main() {
    input! {
        n: u8,
        mut a: [u16; n],
    };
    a.sort_by(|a, b| b.cmp(a));
    let mut a_sum = 0;
    let mut b_sum = 0;
    for (i, &v) in a.iter().enumerate() {
        if i % 2 == 0 {
            a_sum += v;
        } else {
            b_sum += v;
        }
    }
    println!("{}", a_sum - b_sum);
}

これで完璧ですね。

ということで今回はこれで👍

実装#

実装