TopCoder SRM 614: CycleColoring

第一段階で、各々の長さの彩色パターンを DP で求めて、
第二段階で、第一段階で求めた彩色パターンを使って、同じような DP を構築する。

K 色全てを状態にするのではなく、開始地点と同じ色かそうでないかの２通りだけの状態を考えれば良い。

具体的な処理はソースコード参照。

mod の処理がややこしいので、ライブラリ化した ModInt クラスを使って、楽している。

public class CycleColoring {
    const int SameColor = 0;
    const int DifferentColor = 1;

    public int countColorings(int[] vertexCount, int[] fromVertex, int[] toVertex, int K) {
        var N = vertexCount.Length;
        // dp[n, SameColor] = n 個並んだ頂点をグラフについてを隣り合った頂点に異なる色を塗ったときに 
        //                    1番目とn番目が同じ色になるような彩色のパターン数。1番目の色は固定
        var dp = new ModInt[1000005, 2];
        dp[1, SameColor] = 1;
        dp[1, DifferentColor] = 0;
        for (int i = 2; i < dp.GetLength(0); i++) {
            var all = (dp[i - 1, DifferentColor] + dp[i - 1, SameColor]) * (K - 1); // 各々の状態から遷移先は K - 1 通り
            dp[i, SameColor] = dp[i - 1, DifferentColor];
            dp[i, DifferentColor] = all - dp[i, SameColor];
        }

        // 開始地点は、K 通りに彩色できる
        ModInt SameColorWithStart = K;
        ModInt DiffColorWithStart = 0;
        for (int i = 0; i < vertexCount.Length; i++) {
            var cycleLength = vertexCount[i];
            int enterIndex = toVertex[(i - 1 + N) % N];
            int exitIndex = fromVertex[i];

            int length1 = Math.Abs(exitIndex - enterIndex);
            int length2 = cycleLength - length1;

            // サイクルの彩色パターン数（一箇所の色は固定）
            var allColoringCyclePattern = dp[cycleLength, DifferentColor];
            // 入り口と出口が同じ色の場合の彩色パターン数
            var sameEnterAndExitColoringPattern = dp[length1 + 1, SameColor] * dp[length2 + 1, SameColor];
            // 入り口と出口が異なる色の場合の彩色パターン数
            var diffEnterAndExitColoringPattern = allColoringCyclePattern - sameEnterAndExitColoringPattern;

            ModInt nextSameColorWithStart =
                 SameColorWithStart * sameEnterAndExitColoringPattern +
                 DiffColorWithStart * diffEnterAndExitColoringPattern / (K - 1);
            ModInt nextDiffColorWithStart =
                (SameColorWithStart + DiffColorWithStart) * allColoringCyclePattern - nextSameColorWithStart;

            SameColorWithStart = nextSameColorWithStart;
            DiffColorWithStart = nextDiffColorWithStart;
        }

        return SameColorWithStart.ToInt();
    }
}

public struct ModInt {
    static private int mod = 1000000007;
    private long value;

    public ModInt(long x) {
        this.value = x;
        Normalize();
    }

    static private long RegularMod(long x, int mod) {
        if (x >= mod) return x % mod;
        if (x >= 0) return x;
        return (mod - RegularMod(-x, mod)) % mod;
    }

    static public void SetModValue(int m) {
        ModInt.mod = m;
    }

    private void Normalize() {
        this.value = RegularMod(value, mod);
    }

    public override string ToString() {
        return value.ToString();
    }

    public int ToInt() {
        return (int)this.value;
    }

    public static bool operator ==(ModInt c1, ModInt c2) {
        return c1.value == c2.value;
    }

    public static bool operator !=(ModInt c1, ModInt c2) {
        return !(c1 == c2);
    }

    public static ModInt operator +(ModInt x, ModInt y) {
        return new ModInt(x.value + y.value);
    }
    public static ModInt operator -(ModInt x, ModInt y) {
        return new ModInt(x.value - y.value);
    }
    public static ModInt operator *(ModInt x, ModInt y) {
        return new ModInt(x.value * y.value);
    }
    public static ModInt operator /(ModInt x, ModInt y) {
        return new ModInt(x.value * Inverse(y.value, mod));
    }

    static private long ExtendedGcd(long a, long b, ref long x, ref long y) {
        if (b == 0) {
            x = 1; y = 0;
            return a;
        } else {
            long d = ExtendedGcd(b, a % b, ref y, ref x);
            y -= a / b * x;
            return d;
        }
    }

    static private long Inverse(long a, long mod) {
        long x = 0, y = 0;
        if (ExtendedGcd(a, mod, ref x, ref y) == 1)
            return (x + mod) % mod;
        else
            throw new Exception("Invalid inverse " + a + " " + mod);
    }

    public static implicit operator ModInt(long x) {
        return new ModInt(x);
    }

    public override bool Equals(object obj) {
        if (obj == null) {
            return false;
        }
        return this.value.Equals(((ModInt)obj).value);
    }

    public override int GetHashCode() {
        return this.value.GetHashCode();
    }
}

TopCoder SRM 614: MinimumSquare

解説は、TopCoder SRM614 解説 を参考にしてください。

\(O(N^3)\) 解です。

public class MinimumSquare {
    struct Point {
        public long X, Y;
    }

    public long minArea(int[] x, int[] y, int K) {
        var points = x.Zip(y, (X, Y) => new Point { X = X, Y = Y })
            .OrderBy(p => p.Y)
            .ToArray();
        long ans = long.MaxValue;

        var xs = x.Distinct().ToArray();
        Array.Sort(xs);

        for (int j = 0; j < xs.Length; j++) {
            for (int i = 0; i <= j; i++) {
                var listY = new List<int>();
                long width = xs[j] - xs[i];
                var pointsInXRange = points
                    .Where(p => xs[i] <= p.X && p.X <= xs[j])
                    .ToArray();
                var minHeight = pointsInXRange.Zip(pointsInXRange.Skip(K - 1), (p1, pK) => pK.Y - p1.Y)
                    .DefaultIfEmpty(long.MaxValue)
                    .Min();
                if (minHeight == long.MaxValue) continue;
                var side = Math.Max(width, minHeight) + 2;
                ans = Math.Min(ans, side * side);
            }
        }

        return ans;
    }
}

TopCoder SRM614: TorusSailingEasy

解法については、 TopCoder SRM614 解説 を参考にしてください。

public class TorusSailingEasy {
    int reach(int N, int M, int x, int y) {
        for (int p = x; p < N * M; p += N) if (p % M == y) return p;
        return -1;
    }

    public double expectedTime(int N, int M, int goalX, int goalY) {
        var r1 = reach(N, M, goalX, goalY);
        var r2 = reach(N, M, (N - goalX) % N, (M - goalY) % M);
        if (r1 == -1 || r2 == -1) return -1;
        return r1 * r2;
    }
}

TopCoder SRM 614: MinimumSquareEasy

解法については TopCoder SRM614 解説 を参考にしてください。

public class MinimumSquareEasy {
    public long minArea(int[] x, int[] y) {
        int n = x.Length;
        long minSide = long.MaxValue;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                var xs = new List<int>();
                var ys = new List<int>();
                for (int k = 0; k < n; k++) {
                    if (i == k || j == k) continue;
                    xs.Add(x[k]);
                    ys.Add(y[k]);
                }
                var side = Math.Max(xs.Max() - xs.Min(), ys.Max() - ys.Min()) + 2;
                minSide = Math.Min(minSide, side);
            }
        }
        return minSide * minSide;
    }
}

TopCoder SRM614: MicroStrings

初 Writerした回。本問は非担当。

再帰できる場合は再帰したほうがかっこいい。

public string makeMicroString(int A, int D) {
    if (A < 0) return "";
    return A + makeMicroString(A - D, D);
}

TopCoder SRM613: TaroFriends

ある２匹の猫が互いに背を向けている場合、両方の猫の向きを直して、向かい合わせることで必ず移動後の位置の差が小さくなる。

つまり任意の猫のペアが向かい合っているような初期状態だけを考えればよく、そのような状態は |coordinates|+1 通りしかないのでそれらを全て試す。

public class TaroFriends {
    public int getNumber(int[] coordinates, int X) {
        int ans = int.MaxValue;
        Array.Sort(coordinates);
        for (int i = 0; i <= coordinates.Length; i++) {
            var front = coordinates.Take(i).Select(p => p + X);
            var back = coordinates.Skip(i).Select(p => p - X);
            var moved = front.Concat(back);
            ans = Math.Min(ans, moved.Max() - moved.Min());
        }
        return ans;
    }
}

TopCoder SRM613: TaroString

'A','C','T'以外の文字を削除した後に、文字列が "CAT" になっているかを判定する。

public class TaroString {
    public string getAnswer(string S) {
        S = new String(S.Where(c => "CAT".Contains(c)).ToArray());
        return S == "CAT" ? "Possible" : "Impossible";
    }
}