TopCoder SRM620: PairGame

Div2Medium の派生版。

\((a,b)\)と\((c,d)\) それぞれから逆方向に変換していって、それらの共通部分での最大値を返せば良い。

public class PairGame {
    public IEnumerable<Tuple<int, int>> Get(int a, int b) {
        var set = new List<Tuple<int, int>>();
        while (a > 0 && b > 0) {
            set.Add(new Tuple<int, int>(a, b));
            if (a < b) b -= a;
            else a -= b;
        }
        return set;
    }

    public int maxSum(int a, int b, int c, int d) {
        return Get(a, b)
            .Intersect(Get(c, d))
            .Select(p => p.Item1 + p.Item2)
            .DefaultIfEmpty(-1)
            .Max();
    }
}