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());
    }
}