C♯の勉強

C♯4.0 で TopCoder の過去問を解きます。

C# で注意すること

Tuple の == は ReferenceEquals

Tuple.Create(1, 5) == Tuple.Create(1, 5)); // False !!!
Tuple.Create(1, 5) == Tuple.Create(2, 5)); // False
Tuple.Create(1, 5).Equals(Tuple.Create(1, 5)); // True
Tuple.Create(1, 5).Equals(Tuple.Create(2, 5)); // False
  • 値の一致を見たい場合は Equals を使う
  • ValueTuple が使える場合は、可能な限りそちらを使ったほうが良い
    • ValueTuple の場合は == 使っても問題ない

BigInteger.Parse(s) の計算量は O(|s|^2)

var s = new string('1', 100000);
var b = BigInteger.Parse(s); // 数秒かかる

String のデフォルトの比較は重い

var a1 = Enumerable.Range(0, 500000).Select(i => i.ToString()).ToArray();
Array.Sort(a1); // 700 ms ぐらいかかる
var a2 = Enumerable.Range(0, 500000).Select(i => i.ToString()).ToArray();
Array.Sort(a2, StringComparer.Ordinal); // 100 ms ぐらいかかる
  • デフォルトだと Culture に基づいた文字列になるのでそもそも Ascii 順になる保証はない
  • StringComparer.Ordinal を指定すれば、Ascii 順になり、速度も数倍に鳴る
  • この問題起因で Atcoder ABC 155 C 問題で大量に TLE が発生した

空の Queue.Clear() の計算量は O(|Capacity|) (.Net Framework)

var queue = new Queue<int>(100000);
for (int i = 0; i < 10000; i++) queue.Clear(); // 数秒かかる
  • .Net Core だと修正されている
  • Clear() 系は他のコレクションクラスでも 基本 O(size) かかるので O(1) ではないという感覚を持つ必要あり。

オンラインジャッジ C# 対応状況

オンラインジャッジと C# 対応状況

OnlineJudge C# compiler C# ver source
CodeForces .Net Core 3.1 C# 8 Submit page
Google Code Jam mono 4.6.2 C# 6 https://code.google.com/codejam/resources/faq
AOJ mono 4.6.2 C# 6 http://judge.u-aizu.ac.jp/onlinejudge/status_note.jsp
Atcoder mono 6.8, .Net Core 3.1 C$ 7 https://atcoder.jp/contests/practice/rules
YukiCoder mono 6.8 C# 7 Submit page

TopCoder は調べてないけど恐らく C# 4.0 のまま

Mono と C# Version

Mono C# Version
2.8~ C# 4.0
3.0~ C# 5.0
4.0~ C# 6.0
5.0~ C# 7.0
5.10~ C# 7.2

TopCoder SRM 605: AlienAndPermutation

例として { 1, 5, 3, 4, 7, 6, 2 } から遷移できる配列を列挙する。

  • 1 5 5 5 5 7 2
  • 5 5 3 7 7 6 6
  • 5 5 5 5 7 7 7
  • 1 5 5 7 7 6 2
  • 7 7 7 7 7 7 7

眺めてみると、以下の規則性があることが分かる。

  • 同一の数字は一箇所にかたまっている。1112111のように複数箇所に別れてかたまっていない。
  • 数字の出現順は、もとの順列での出現順と同じ

この規則から以下の状態でDPが適用できる。

memo[pos, currentHeightIndex, int K, int reducedK] := P[pos...]P[currentHeightIndex..] を左から割り当てたとき K 回以下の操作で構築できる配列の個数。reducedK は、P[currentHeightIndex] を配置するための操作をすでに勘定に入れたかどうか。

P[i]P[j] を配置できるかどうかは i と j の間の最大値が P[j] の場合に限られる。この情報はあらかじめ前計算してテーブルに持っておく。

public class AlienAndPermutation {
    bool[,] CanMove;
    const int mod = 1000000007;

    int?[, , ,] memo = new int?[222, 222, 222, 2];

    int dfs(int[] P, int pos, int currentHeightIndex, int K, int reducedK) {
        if (K < 0) return 0;
        if (pos == P.Length) return 1;

        if (!memo[pos, currentHeightIndex, K, reducedK].HasValue) {
            long val = 0;

            // pos番目にP[currentHeightIndex]を移動できる場合
            if (CanMove[currentHeightIndex, pos]) {
                if (reducedK == 0 && currentHeightIndex != pos) {
                    // 元の場所とは別の位置に配置した時点で、change 操作が必要だと確定
                    val += dfs(P, pos + 1, currentHeightIndex, K - 1, 1);
                } else {
                    val += dfs(P, pos + 1, currentHeightIndex, K, reducedK);
                }
            }

            if (currentHeightIndex + 1 < P.Length) {
                val += dfs(P, pos, currentHeightIndex + 1, K, 0);
            }

            memo[pos, currentHeightIndex, K, reducedK] = (int)(val % mod);
        }
        return memo[pos, currentHeightIndex, K, reducedK].Value;
    }

    public int getNumber(int[] P, int K) {
        var n = P.Length;
        for (int i = 0; i < n; i++) P[i]--;
        this.CanMove = new bool[n, n];
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                var maxv = P.Where((_, index) => i <= index && index <= j).Max();
                if (maxv == P[i]) CanMove[i, j] = true;
                if (maxv == P[j]) CanMove[j, i] = true;
            }
        }

        return dfs(P, 0, 0, K, 0);
    }
}

TopCoder SRM606: EllysPairing

Practice だと return 0; するだけのプログラムでも StackOverFlow になってシステムテストで正当チェックができなかった。

一番出現数が多い名前 f の出現数を x とする。x が全名前の過半数以下の場合は、ペアの最大数 floor(名前の個数 / 2) がそのまま答えになる。過半数より多い場合は、全てのペアに f が含まれることから f 以外の個数が答えになる。

数式化すると min(total / 2, total - x) になるため、後は x を求める。
メモリサイズが 16MB しかないため、全数列を生成したり、Set にいれてヒストグラムを取ったりするとメモリがオーバーしてしまう。

まず 下位16bit の出現数をヒストグラムでカウントする。その中で出現数が一番多いものを求める。もし f が過半数の場合は、必ずその中に含まれている。再度その下位16bitを保持するものだけを対象にして 上位16bitの出現数の最大値が求める。その最大値が全bitを通しての最大値になる。

数列生成用の Generator クラスを作ってみたけど、yield 構文が使えればもっと単純に書けたと思う。

public class EllysPairing {
    public class Generator {
        int current = 0;
        int first;
        int mult;
        int add;
        int M;

        public Generator(int first, int mult, int add, int M) {
            this.current = first;
            this.first = first;
            this.mult = mult;
            this.add = add;
            this.M = M;
        }

        public int Next() {
            int c = current;
            current = (int)((1L * current * mult + add) & (M - 1));
            return c;
        }
    }

    public int getMax(int M, int[] count, int[] first, int[] mult, int[] add) {
        int n = count.Length;
        int total = count.Sum();
        var lowHistogram = new int[1 << 16];
        int lowMask = (1 << 16) - 1;

        for (int i = 0; i < n; i++) {
            var g = new Generator(first[i], mult[i], add[i], M);
            for (int j = 0; j < count[i]; j++) {
                lowHistogram[g.Next() & lowMask]++;
            }
        }

        int maxLowBit = 0;
        for (int i = 0; i < lowHistogram.Length; i++) {
            if (lowHistogram[maxLowBit] < lowHistogram[i]) maxLowBit = i;
        }

        var highHistogram = new int[1 << 16];

        for (int i = 0; i < n; i++) {
            var g = new Generator(first[i], mult[i], add[i], M);
            for (int j = 0; j < count[i]; j++) {
                int x = g.Next();
                if ((x & lowMask) == maxLowBit) {
                    highHistogram[x >> 16]++;
                }
            }
        }

        return Math.Min(total / 2, total - highHistogram.Max());
    }
}

TopCoder SRM 604: TorusSailing

問題文とは逆に (x, y) からスタートして 1, 9, 27 ... の直進移動で (0, 0) に移動できるかどうかを考える。

2ステップ以降は、3の倍数分しか移動できないため 1ステップ目で x, y が両方とも 3 の倍数になるように移動しなくてはならない。

x と y が両方とも 3 の倍数ではない場合は、x と y を両方移動する必要があり、それは 1ステップでできないため、"Impossble" になる。

それ以外の場合は、3 の倍数になるように x または y を移動することで (3 * p, 3 * q) で表される座標に移動できる。

あとは 3, 9, 27 ... の直進移動で (3 * p, 3 * q) から (0, 0) に到達できるかを判定する。ここで全体の座標を 3 で割ると "1, 3, 9 ... の直進移動で (p, q) から (0, 0) に到達できるを判定する" 問題となり、これは元々の問題になることから再帰的に処理できる。

public class PowerOfThree {
    public string ableToGet(int x, int y) {
        if (x == 0 && y == 0) return "Possible";
        if (x < 0) x = -x;
        if (y < 0) y = -y;
        if (x % 3 == 1) x--;
        else if (x % 3 == 2) x++;
        else if (y % 3 == 1) y--;
        else if (y % 3 == 2) y++;
        else return "Impossible";
        if (x % 3 != 0 || y % 3 != 0)
            return "Impossible";
        return ableToGet(x / 3, y / 3);
    }
}

TopCoder SRM 604: FamilyCrest

サンプルが豊富で大きなヒントになっているが、バグ無しの実装が大変な問題。

方針としては、微小距離だけ移動しても自分自身と重ならないような方向が存在するかを判定する。
以下、「移動」というのは微小距離だけ移動という意味で用いている。

2つの線分だけを着目したとき、以下のパターンに分けられる。

  1. お互い交差も接触もしていない場合
    • どの方向に移動しても重ならない
  2. 「L」 の字、「V」の字のように端点同士が重なっている場合
    • 重なっている端点から伸びる線分がなす鋭角の範囲またはその180度逆方向の範囲に移動すれば重ならない。たとえば「L」の字の場合は、(0度, 90度)の範囲、または(180度, 270度)の範囲の方向が移動可能
  3. 線分が重なっている場合
    • 線分と平行にならないように移動すれば重ならない
  4. 上記以外の「X」の字、「T」の時のように交差している場合
    • どの方向に移動しても重なってしまう。

上記から、
(4) のケースがある場合は "Finite"
(2) のケースがない場合はなんら制限がないため "Infinite"、ある場合は移動可能な角度の範囲を全て調べて共通部分が存在する場合は、"Infinite"、それ以外は "Finite" を返すプログラムを書けばよい。だけどバグ無しで実装するのがかなり大変。

(3) のケースはちゃんと無視するようにしないと (4) のケースとみなされて最後のサンプルが通らなくなる。

public class FamilyCrest {
    static public void Swap<T>(ref T a, ref T b) { T t = a; a = b; b = t; }

    static public long DotProduct(PointInt p1, PointInt p2) {
        return (long)p1.X * p2.X + (long)p1.Y * p2.Y;
    }

    static public long CrossProduct(PointInt p1, PointInt p2) {
        return (long)p1.X * p2.Y - (long)p1.Y * p2.X;
    }

    static public int CCW(PointInt p1, PointInt p2, PointInt p3) {
        p2 -= p1;
        p3 -= p1;
        var cross = CrossProduct(p2, p3);
        if (cross > 0) return +1;
        if (cross < 0) return -1;
        if (p2.X * p3.X < 0 || p2.Y * p3.Y < 0) return +2;
        if (p2.Norm < p3.Norm) return -2;
        return 0;
    }

    static public bool AreIntersect(PointInt p1, PointInt p2, PointInt p3, PointInt p4) {
        return (CCW(p1, p2, p3) * CCW(p1, p2, p4)) <= 0 &&
               (CCW(p3, p4, p1) * CCW(p3, p4, p2)) <= 0;
    }

    bool ShareVertices(PointInt p1, PointInt p2, PointInt q1, PointInt q2) {
        if (p1 == q1) return true;
        if (p1 == q2) return true;
        if (p2 == q1) return true;
        if (p2 == q2) return true;
        return false;
    }

    struct Range {
        public double FromArg, ToArg;

        public bool InRange(double arg) {
            for (int i = -10; i <= 10; i++) {
                if (FromArg + Error < arg + i * Math.PI && arg + i * Math.PI < ToArg - Error)
                    return true;
            }
            return false;
        }
    }

    const double Error = 1e-9;

    double Angle(double arg1, double arg2) {
        var angle = arg2 - arg1;
        if (angle < -Error) angle += 2 * Math.PI;
        return angle;
    }

    void AddMovableArgRange(List<Range> list, PointInt p1, PointInt p2, PointInt q1, PointInt q2) {
        if (p2 != q1) return;

        var arg1 = (p1 - p2).Arg();
        var arg2 = (q2 - p2).Arg();

        // 鋭角の範囲に移動可能
        if (Angle(arg1, arg2) > Math.PI) Swap(ref arg1, ref arg2);
        if (arg2 < arg1) arg2 += 2 * Math.PI;
        list.Add(
            new Range {
                FromArg = arg1,
                ToArg = arg2,
            }
        );
    }

    bool OnLine(PointInt p1, PointInt p2, PointInt p3) {
        return CrossProduct(p2 - p1, p3 - p1) == 0;
    }

    bool OnLine(PointInt p1, PointInt p2, PointInt p3, PointInt p4) {
        return
            OnLine(p1, p2, p3) && OnLine(p2, p3, p4)
         && OnLine(p1, p3, p4) && OnLine(p1, p2, p4);
    }

    public string canBeInfinite(int[] A, int[] B, int[] C, int[] D) {
        var p1 = new List<PointInt>();
        var p2 = new List<PointInt>();
        var n = A.Length;
        for (int i = 0; i < n; i++) {
            p1.Add(new PointInt(A[i], B[i]));
            p2.Add(new PointInt(C[i], D[i]));
        }

        // 移動可能な方向(角度)の範囲
        List<Range> ranges = new List<Range>();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (OnLine(p1[i], p2[i], p1[j], p2[j])) continue;
                if (AreIntersect(p1[i], p2[i], p1[j], p2[j])) {
                    if (ShareVertices(p1[i], p2[i], p1[j], p2[j])) {
                        AddMovableArgRange(ranges, p1[i], p2[i], p1[j], p2[j]);
                        AddMovableArgRange(ranges, p1[i], p2[i], p2[j], p1[j]);
                        AddMovableArgRange(ranges, p2[i], p1[i], p1[j], p2[j]);
                        AddMovableArgRange(ranges, p2[i], p1[i], p2[j], p1[j]);
                    } else {
                        // 端点以外に交点がある場合は、どの方向にも移動できない
                        return "Finite";
                    }
                }
            }
        }

        var args = ranges
            .SelectMany(r => new[] { r.FromArg, r.ToArg })
            .SelectMany(a => new[] { a - Math.PI, a, a + Math.PI })
            .OrderBy(a => a)
            .ToArray();

        var candidates = args
            .Zip(args.Skip(1), (a1, a2) => (a1 + a2) / 2.0)
            .ToArray();

        // 制限がないため、どの方向にも移動可能
        if (!ranges.Any()) return "Infinite";

        foreach (var arg in candidates) {
            // 制限を全て満たす移動方向が存在した
            if (ranges.All(r => r.InRange(arg))) {
                return "Infinite";
            }
        }

        return "Finite";
    }
}

TopCoder SRM 614: TorusSailing

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

流れは、だいたい以下のとおり。

  1. 全てのループを断ち切るように N + M - 1 箇所のマスを変数化
    • 斜めに変数化すれば max(N, M) 箇所でよい
  2. すべての箇所の期待値を、DP を使って (N + M - 1) 変数多項式で表す
  3. 上記の結果を元に (N + M - 1) 変数連立方程式に帰着できるため、変数の数が減ることによりガウスジョルダンや掃き出し法で解ける。

よく期待値問題で、F(n) = a * F(n - 1) + b * F(n)のような自己ループを含む漸化式になった場合、F(n) = a * F(n - 1) / (1 - b)のように移項して解くが、このとき F(n) をいったん変数化して一次方程式を解いていることになる。本問題は、このテクを一次方程式から連立方程式に拡張した問題として位置づけられる。

public class TorusSailing {
    static public void Swap<T>(ref T a, ref T b) { T t = a; a = b; b = t; }

    class Polynomial {
        public double[] Coefficient;
        public double constantTerm;

        protected Polynomial() { }

        public Polynomial(int variableNum) {
            this.Coefficient = new double[variableNum];
            this.constantTerm = 0.0;
        }

        public void Add(Polynomial p) {
            for (int i = 0; i < Coefficient.Length; i++) {
                Coefficient[i] += p.Coefficient[i];
            }
            constantTerm += p.constantTerm;
        }

        public void Divide(double p) {
            for (int i = 0; i < Coefficient.Length; i++) {
                Coefficient[i] /= p;
            }
            constantTerm /= p;
        }
    }

    Polynomial GetBasePolynomial(int posX, int posY, int N, int M) {
        if (posY == 0) {
            var p = new Polynomial(N + M - 1);
            p.Coefficient[posX] = 1.0;
            return p;
        } else if (posX == 0) {
            var p = new Polynomial(N + M - 1);
            p.Coefficient[posY - 1 + N] = 1.0;
            return p;
        }
        return null;
    }

    Polynomial[,] memo = new Polynomial[100, 100];

    Polynomial ExpectedPolynomial(int posX, int posY, int goalX, int goalY, int N, int M) {
        if (memo[posX, posY] == null) {
            var p = new Polynomial(N + M - 1);
            if (posX == goalX && posY == goalY) {
                ; // p = 0
            } else {
                int nX = (posX + 1) % N;
                int nY = (posY + 1) % M;

                var p1 = GetBasePolynomial(nX, posY, N, M) ?? ExpectedPolynomial(nX, posY, goalX, goalY, N, M);
                var p2 = GetBasePolynomial(posX, nY, N, M) ?? ExpectedPolynomial(posX, nY, goalX, goalY, N, M);

                p.Add(p1); p.constantTerm += 1.0;
                p.Add(p2); p.constantTerm += 1.0;

            }
            p.Divide(2.0);
            memo[posX, posY] = p;
        }
        return memo[posX, posY];
    }

    double[] GausianJordanElimination(double[,] mat) {
        int N = mat.GetLength(1) - 1;
        int M = mat.GetLength(0);
        var index = new int[M];
        const double Error = 1e-9;
        for (int i = 0; i < M; i++) {
            index[i] = i;
        }
        for (int i = 0; i < N; i++) {
            int row = -1;
            double pivot = Error;
            for (int j = i; j < M; j++) {
                if (Math.Abs(mat[index[j], i]) > Math.Abs(pivot)) {
                    row = j;
                    pivot = mat[index[j], i];
                }
            }
            if (row == -1) continue;
            Swap(ref index[i], ref index[row]);
            for (int j = 0; j <= N; j++) {
                mat[index[i], j] /= pivot;
            }
            for (int j = 0; j < M; j++) {
                if (i != j) {
                    double weight = mat[index[j], i];
                    for (int k = 0; k <= N; k++) {
                        mat[index[j], k] -= weight * mat[index[i], k];
                    }
                }
            }
        }
        double[] ans = new double[N];
        for (int i = 0; i < N; i++) {
            ans[i] = mat[index[i], N];
        }
        return ans;
    }

    public double expectedTime(int N, int M, int goalX, int goalY) {
        int size = N + M - 1;
        double[,] matrix = new double[size, size + 1];
        for (int i = 0; i < size; i++) {
            int x, y;
            if (i < N) {
                x = i;
                y = 0;
            } else {
                x = 0;
                y = i - N + 1;
            }
            var p = ExpectedPolynomial(x, y, goalX, goalY, N, M);
            for (int j = 0; j < size; j++) {
                matrix[i, j] = p.Coefficient[j];
                if (i == j) matrix[i, j] -= 1.0;
            }
            matrix[i, size] = -p.constantTerm;
        }

        var ans = GausianJordanElimination(matrix);
        return ans[0];
    }
}