Kyoto University Programming Contest 2018: F - カード集め

問題記録 AtCoder KUPC2018

https://beta.atcoder.jp/contests/kupc2018/tasks/kupc2018_f

問題概要

N枚のカードを使って2人ゲームをする。先手と後手はそれぞれのターンに残っているカードから任意の1枚を選んで手持ちに加える。このときカードに書いてある数値を得点として得る。また「カードaとカードbを両方取るとボーナスとしてc点が与えられる」という特別な組み合わせがM個与えられる。最終的な先手の得点が後手より真に大きければ先手の勝ち、そうでなければ後手の勝ちである。両者が最適に行動したときの勝敗を求めよ。

N, M <= 105

解法

カードを頂点、ボーナスを辺としてグラフを作ってみる。このとき頂点にはカードの点数、辺にはボーナスの点数を持たせる。このグラフ上でゲームを考えると、「ある頂点を取ったらその頂点の点数がもらえる」「ある辺の両端の頂点をどちらも取ったらその辺の点数がもらえる」という感じになる。このままだと辺の条件のせいで考えるのが難しいが、実はこっちの方は「ある頂点を取ったら、それに繋がっている辺の半分の点数がもらえる」と言い換えることができる。なぜならば、

  1. もし辺の両端の頂点をどちらも同じプレイヤーが取っているなら、結局半分＋半分で元のボーナス点と同じ点がもらえるのと一緒
  2. もし辺の両端の頂点を別々のプレイヤーが取っているなら、どちらにも同じだけのボーナス点が加算されることになるので結局影響はゼロ

ということになるからである。そしてこの言い換えをすることで、このゲームは単純に頂点の取り合いだけを考えればよくなる。つまり両者の最適戦略が単純に「残っている中で最も点数の高い頂点を取る」になるので、各頂点に隣接辺の半分の点数を足したあとソートすれば答えが出る。

実装上の細かい点として、最初に全部の点を倍にしておけば半分にしたときも整数の範囲で点数を扱うことができる。

感想

思いついたとき天才家！？？？QQ!!となった

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, core.stdc.string;

void main() {
    auto s = readln.split.map!(to!int);
    auto N = s[0];
    auto M = s[1];
    auto S = readln.split.map!(to!long).array;

    foreach (i; 0..N) {
        S[i] *= 2;
    }

    foreach (_; 0..M) {
        s = readln.split.map!(to!int);
        S[s[0]-1] += s[2];
        S[s[1]-1] += s[2];
    }

    S.sort!"a > b";
    auto a = iota(0, N, 2).map!(i => S[i]).sum;
    auto b = iota(1, N, 2).map!(i => S[i]).sum;

    writeln(a > b ? "First" : "Second");
}