SRM 512 DIV 2

7月14日のSRM参加記録

Level One MarbleDecoration

問題：http://www.topcoder.com/stat?c=problem_statement&pm=11287&rd=14537

石を交互に並べたいんだって。

import java.util.Arrays;

public class MarbleDecoration {
    public int maxLength(int R, int G, int B) {
        int[] rgb = { R, G, B };
        Arrays.sort(rgb);
        return (rgb[1] < rgb[2]) ? rgb[1] * 2 + 1 : rgb[1] * 2;
    }
}

Level Two MysteriousRestaurant

問題：http://www.topcoder.com/stat?c=problem_statement&pm=11295&rd=14537

同じ曜日には同じ番号のメニューしか選べないなんて罠だよ罠。

public class MysteriousRestaurant {
    public int maxDays(String[] prices, int budget) {
        final int M = prices[0].length();
        int days = 0;
        int[][] a = new int[7][M];
        int[] m = new int[7];
        for (int i = 0; i < prices.length; i++) {
            int ii = i % 7;
            String price = prices[i];
            int min = Integer.MAX_VALUE;
            for (int j = 0; j < M; j++) {
                int p = convert(price.charAt(j));
                a[ii][j] += p;
                min = Math.min(min, a[ii][j]);
            }
            m[ii] = min;
            if (total(m) > budget) {
                break;
            }
            days++;
        }
        return days;
    }

    private int total(int[] a) {
        int t = 0;
        for (int b : a) {
            t += b;
        }
        return t;
    }

    private int convert(char c) {
        final String map = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
        return map.indexOf(c);
    }
}

Level Three DoubleRoshambo

問題：http://www.topcoder.com/stat?c=problem_statement&pm=11289&rd=14537

変なルールでじゃんけんしやがる。
結局解けないまま時間切れになったので、途中経過を晒します。

public class DoubleRoshambo {
    public int maxScore(String[] A, String[] E) {
        int[][] scoreTable = new int[A.length][E.length];
        for (int i = 0; i < A.length; i++) {
            for (int j = 0; j < E.length; j++) {
                scoreTable[i][j] = calculateScore(A[i], E[j]);
            }
        }
        return 0;
    }

    private int calculateScore(String a, String b) {
        int score = 0;
        for (int i = 0; i < a.length(); i++) {
            score += compare(a.charAt(i), b.charAt(i));
        }
        return score;
    }

    private int compare(char a, char b) {
        if (a == b) {
            return 0;
        }
        if ((a == 'R' && b == 'S') || (a == 'S' && b == 'P')
                || (a == 'P' && b == 'R')) {
            return 1;
        }
        return -1;
    }
}

総当りでスコア表をつくって、その中からいい感じに組み合わせを選択しようと思ってたけど、方法が思い浮かばなかった・・・。