TopCoder SRM 147 DIV 1 Medium 練習

問題

立方体の惑星に龍が六匹、それぞれの面に棲んでいる。

食事の際、龍はそれぞれ隣り合った四面にいる龍の食事を盜もうとして、結果としてそれぞれの食事の四分の一を盜んでくる。

最初にそれぞれの龍が食事を持っている量が与えられるので、指定の回数だけ全員が盜みを繰り返したあと、上の面に乗っている龍が持っている食事の量を求めなさい。

解

まあやるだけ。分数の実装がめんどくさかった。

四面から四分の一盜ってくるんだけど、逆に四面からそれぞれ四分の一盜られるので、そこに気付けば計算は楽。

using System;
using System.Text;
using System.Text.RegularExpressions;
using System.Collections;
using System.Collections.Generic;

public class Fraction {
    public long p, q;    // p/q
    public Fraction(long p_, long q_)
    {
        p = p_;
        q = q_;
        Reduction();
    }
    public Fraction(Fraction f, long q_)
    {
        p = f.p;
        q = f.q * q_;
        Reduction();
    }
    private static long gcd(long a, long b)
    {
        return b == 0 ? a : gcd(b, a % b);
    }
    public void Reduction()
    {
        long t = gcd(p, q);
        p /= t;
        q /= t;
    }
    public static Fraction Add(Fraction l, Fraction r)
    {
        long t = gcd(l.q, r.q);
        long np, nq;
        np = l.p * (r.q / t); nq = l.q * (r.q / t);
        np += r.p * (l.q / t);
        return new Fraction(np, nq);
    }
    public override string ToString()
    {
        Reduction();
        if (q == 1)
            return p.ToString();
        return p + "/" + q;
    }
}

public class Dragons {
    public string snaug(int[] initialFood, int rounds) {
        Fraction[] foods = new Fraction[initialFood.Length];

        for (int i = 0; i < initialFood.Length; ++i)
            foods[i] = new Fraction(initialFood[i], 1);

        for (int i = 0; i < rounds; ++i)
        {
            Fraction[] next = new Fraction[initialFood.Length];
            for (int j = 0; j < initialFood.Length; ++j)
            {
                int pos = j | 1;
                next[j] = new Fraction(0, 1);
                for (int k = 1; k <= 4; ++k)
                {
                    int t = (pos + k) % 6;
                    next[j] = Fraction.Add(next[j], new Fraction(foods[t], 4));
                }
            }
            next.CopyTo(foods, 0);
        }
        return foods[2].ToString();
    }
}