U&U [Aizu Competitive Programming Camp 2018 Day 2 B]

https://onlinejudge.u-aizu.ac.jp/beta/room.html#ACPC2018Day2/problems/B

考察過程

1. まだBなのにむずかしめに見える（制約も大きいし）
2. 簡単な所が無いか探す
3. 最適戦略があるのではないか？
4. UKUが勝つ時とうしが勝つ時で最適な方を選択？

解法

https://onlinejudge.u-aizu.ac.jp/beta/review.html#ACPC2018Day2/3149557

最適戦略として「勝つ方はなるべく人数を残す」「負ける方はなるべく人数をへらす」とする方針。
どちらのチームが勝つかを2通り試して、効率が良い方を採用する。

solve1は「UKUがなるべく倒す、うしがなるべく残す」の戦略
solve2は「UKUがなるべく残す、うしがなるべく倒す」の戦略
　
taosu関数はなるべく倒す、nokosu関数はなるべく残すように動いたときの
(n,m1,m2) := n回の攻撃で、体力1がm1人、体力2がm2人としたときの動き

ll N, M;
//---------------------------------------------------------------------------------------------------
pair<ll, ll> taosu(ll n, ll m1, ll m2) {
    ll c1 = min(n, m1);
    m1 -= c1;
    n -= c1;

    ll c2 = min(n / 2, m2);
    m2 -= c2;
    n -= c2 * 2;

    ll c21 = min(m2, n);

    m2 -= c21;
    m1 += c21;

    return { m1, m2 };
}
//---------------------------------------------------------------------------------------------------
pair<ll, ll> nokosu(ll n, ll m1, ll m2) {
    ll c2 = min(m2, n);

    n -= c2;
    m2 -= c2;
    m1 += c2;

    ll c1 = min(n, m1);

    n -= c1;
    m1 -= c1;

    return { m1, m2 };
}
//---------------------------------------------------------------------------------------------------
ll solve1() { // ukuが勝つ
    ll n2 = N, n1 = 0;
    ll m2 = M, m1 = 0;

    ll res = 0;
    while (0 < n2 + n1 and 0 < m2 + m1) {
        tie(m1, m2) = taosu(n1 + n2, m1, m2);
        if (m1 + m2 == 0) return res;

        res++;

        tie(n1, n2) = nokosu(m1 + m2, n1, n2);
        if (n1 + n2 == 0) return res;

        res++;
    }
}
//---------------------------------------------------------------------------------------------------
ll solve2() { // うしが勝つ
    ll n2 = N, n1 = 0;
    ll m2 = M, m1 = 0;

    ll res = 0;
    while (0 < n2 + n1 and 0 < m2 + m1) {
        tie(m1, m2) = nokosu(n1 + n2, m1, m2);
        if (m1 + m2 == 0) return res;

        res++;

        tie(n1, n2) = taosu(m1 + m2, n1, n2);
        if (n1 + n2 == 0) return res;

        res++;
    }
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    ll ans = infl;
    chmin(ans, solve1());
    chmin(ans, solve2());
    cout << ans << endl;
}