TopCoder SRM612: EmoticonsDiv2

「入力済みのEmoticonsの個数」「ClipBoard上のEmoticonsの個数」で動的計画法を構成する。\(O(smiles^2)\)

public class EmoticonsDiv2 {
    static public void UpdateMin<T>(ref T x, T newValue) where T : IComparable<T> { if (x.CompareTo(newValue) > 0) x = newValue; }

    public int printSmiles(int smiles) {
        var dp = new int[smiles + 1, smiles + 1];
        const int inf = 1 << 28;
        for (int i = 0; i <= smiles; i++) {
            for (int j = 0; j <= smiles; j++) {
                dp[i, j] = inf;
            }
        }
        dp[1, 0] = 0;
        for (int i = 0; i <= smiles; i++) {
            for (int j = 0; j <= smiles; j++) {
                if (dp[i, j] == inf) continue;
                UpdateMin(ref dp[i, i], dp[i, j] + 1);
                if (i + j <= smiles) {
                    UpdateMin(ref dp[i + j, j], dp[i, j] + 1);
                }
            }
        }
        return E.Range(0, smiles + 1).Min(s => dp[smiles, s]);
    }
}

TopCoder SRM612: LeftAndRightHandedDiv2

S に含まれている "RL" を個数をカウントする。

public class LeftAndRightHandedDiv2 {
    public int count(string S) {
        return S.Zip(S.Skip(1), (c1, c2) => c1 == 'R' && c2 == 'L' ? 1 : 0).Sum();
    }
}

TopCoder SRM622: FibonacciDiv2

ある程度の数までフィボナッチ数を求めてから、差分の最小値を求める。

public class FibonacciDiv2 {
    public IEnumerable<int> GetFibonacci() {
        List<int> f = new List<int>();
        f.Add(0);
        f.Add(1);
        while (true) {
            var x = f[f.Count - 2] + f[f.Count - 1];
            if (x >= 1000000000) break;
            f.Add(x);
        }
        return f;
    }

    public int find(int N) {
        return GetFibonacci().Select(x => Math.Abs(N - x)).Min();
    }
}

TopCoder SRM622: BoxesDiv2

一番小さな箱を２つ選んで、一段階サイズが大きいの箱に入れる。これを箱が１つだけになるまで繰り返す。

public class BoxesDiv2 {
    int ToPower2(int x) {
        for (int i = 0; i <= 20; i++) {
            if (x <= (1 << i))
                return i;
        }
        return -1;
    }

    public int findSize(int[] candyCounts) {
        var candies = candyCounts.Select(ToPower2).ToList();
        while (candies.Count() > 1) {
            candies.Sort();
            candies.Add(Math.Max(candies[0], candies[1]) + 1);
            candies.RemoveAt(0);
            candies.RemoveAt(0);
        }
        return 1 << candies.Single();
    }
}

TopCoder SRM611: ElephantDrinkingEasy

象が水を飲むときは、一番近いものを選ぶ。つまりそれぞれの象について、水を飲む場合はどこまで鼻を伸ばすかは一意に決まっている。

上側の象と下側の象が水を飲むかどうかは、\(2^{2n}\) 通り。上下の象が鼻を伸ばすかどうかが決まれば、左右の象がそれぞれ水を飲めるかどうかは一意に決まる。

よって上下の象が水を飲む飲まないパターンを全て試せばよい。\( O(n^2*2^{2n}) \)

public class ElephantDrinkingEasy {
    public int maxElephants(string[] map) {
        int n = map.Length;
        var topWater = new int[n];
        var bottomWater = new int[n];
        for (int i = 0; i < n; i++) {
            topWater[i] = bottomWater[i] = -1;
            for (int j = 0; j < n; j++) {
                if (map[j][i] == 'Y') {
                    if (topWater[i] == -1) topWater[i] = j;
                    bottomWater[i] = j;
                }
            }
        }
        int ans = 0;
        for (int topBit = 0; topBit < (1 << n); topBit++) {
            for (int bottomBit = 0; bottomBit < (1 << n); bottomBit++) {
                var existNose = new bool[n, n];
                int drinkableElephantNum = 0;
                for (int i = 0; i < n; i++) {
                    var topElephant = (topBit & (1 << i)) != 0;
                    var bottomElephant = (bottomBit & (1 << i)) != 0;
                    if (topElephant && topWater[i] != -1) {
                        drinkableElephantNum++;
                        for (int row = 0; row <= topWater[i]; row++) {
                            existNose[row, i] = true;
                        }
                    }
                    if (bottomElephant && bottomWater[i] != -1) {
                        if (topElephant && topWater[i] == bottomWater[i]) continue;
                        drinkableElephantNum++;
                        for (int row = bottomWater[i]; row < n; row++) {
                            existNose[row, i] = true;
                        }
                    }
                }
                for (int row = 0; row < n; row++) {
                    // left elephant
                    for (int col = 0; col < n; col++) {
                        if (existNose[row, col]) break;
                        existNose[row, col] = true;
                        if (map[row][col] == 'Y') {
                            drinkableElephantNum++;
                            break;
                        }
                    }
                    // right elephant
                    for (int col = n - 1; col >= 0; col--) {
                        if (existNose[row, col]) break;
                        existNose[row, col] = true;
                        if (map[row][col] == 'Y') {
                            drinkableElephantNum++;
                            break;
                        }
                    }
                }
                ans = Math.Max(ans, drinkableElephantNum);
            }
        }
        return ans;
    }
}

TopCoder SRM610: MiningGoldEasy

全マスへの移動を考えるのではなく、残っている gold がある箇所と同じ行または列に移動することを考える。そうすると、移動箇所はたかだか 50*50 だけになる。

あとは、「座標」と「日数」で動的計画法を適用すればよい。 \(O(|event|^4) \)

public class MiningGoldEasy {
    int N, M;
    int[] event_i, event_j;

    int?[, ,] memo = new int?[50, 50, 50];

    int GetCost(int row, int col, int eventIndex) {
        return N + M - Math.Abs(event_i[eventIndex] - row) - Math.Abs(event_j[eventIndex] - col);
    }

    int dfs(int rowIndex, int colIndex, int cur = 0) {
        if (cur == event_i.Length)
            return 0;

        var row = event_i[rowIndex];
        var col = event_j[colIndex];

        if (!memo[rowIndex, colIndex, cur].HasValue) {
            int val = 0;
            int cost = GetCost(row, col, cur);
            for (int i = cur; i < event_i.Length; i++) {
                val = Math.Max(val, dfs(i, colIndex, cur + 1) + cost);
                val = Math.Max(val, dfs(rowIndex, i, cur + 1) + cost);
            }

            memo[rowIndex, colIndex, cur] = val;
        }

        return memo[rowIndex, colIndex, cur].Value;
    }

    public int GetMaximumGold(int N, int M, int[] event_i, int[] event_j) {
        this.N = N;
        this.M = M;
        this.event_i = event_i;
        this.event_j = event_j;
        int ans = 0;
        for (int i = 0; i < event_i.Length; i++) {
            for (int j = 0; j < event_j.Length; j++) {
                ans = Math.Max(ans, dfs(i, j));
            }
        }

        return ans;
    }
}

TopCoder SRM610: DivideByZero

問題文通り実装するだけだけど、Div2 Easy にしてはやや複雑。

public class DivideByZero {
    public int CountNumbers(int[] numbers) {
        var newElements = (
            from A in numbers
            from B in numbers
            let C = A / B
            where A > B && !numbers.Contains(C)
            select C
        ).Distinct().ToArray();

        if (!newElements.Any()) return numbers.Length;
        return CountNumbers(numbers.Concat(newElements).ToArray());
    }
}