Hatena::Grouptopcoder

chokudaiの日記

 | 

2010-09-26

SRM 462 Div1 Easy

15:50 | SRM 462 Div1 Easy - chokudaiの日記 を含むブックマーク はてなブックマーク - SRM 462 Div1 Easy - chokudaiの日記 SRM 462 Div1 Easy - chokudaiの日記 のブックマークコメント

問題

省略

回答

2分探索で値を求めていく 0.0は認められないので注意

public class AgeEncoding {
    public double getRadix(int age, string candlesLine)
    {
        int i;
        double min = 0.0;
        double max = 200;
        double eps = 1e-9;

        if (Math.Abs(calc(candlesLine, min) - calc(candlesLine, max)) < eps)
        {
            if (Math.Abs(calc(candlesLine, min) - age) < eps) return -2.0;
            else return -1.0;
        }

        for (i = 0; i < 100; i++)
        {
            double mid = (min + max) / 2;
            double now = calc(candlesLine, mid);
            if (age <= now) max = mid;
            else min = mid;
        }

        if (min < eps) return -1.0;
        if (max > 101) return -1.0;

        return min;
    }

    double calc(string s, double a)
    {
        int i;
        double res = 0;
        for (i = 0; i < s.Length; i++)
        {
            if (s[s.Length - 1 - i] == '1')
            {
                res += Math.Pow(a, i);
            }
        }
        return res;
    }
}

SRM 483 Div1 Medium Bribes

15:31 | SRM 483 Div1 Medium Bribes - chokudaiの日記 を含むブックマーク はてなブックマーク - SRM 483 Div1 Medium Bribes - chokudaiの日記 SRM 483 Div1 Medium Bribes - chokudaiの日記 のブックマークコメント

問題

省略

回答

前後8人しか影響を与えないので、bitDPで頑張る

public class Bribes
{
    const int mask = (1 << 8) - 1;
    const int mask2 = (1 << 9) - 1;
    const int MAX = 9999;

    public int minBribes(int[] influence, int[] resistance)
    {
        int[,] dp = new int[1 << 8, 1 << 9];
        int i, j, k, l;
        int len = resistance.Length;
        
        for (l = 0; l < len; l++)
        {
            int[] first = new int[1 << 8];
            int[] second = new int[1 << 9];
            int[,] nextdp = new int[1 << 8, 1 << 9];

            for (i = 0; i <= mask2; i++)
                for (j = 0; j < 9; j++)
                    if ((i & (1 << j)) != 0)
                    {
                        if (i <= mask)
                        {
                            if (l - j - 1 < 0) first[i] = -1;
                            else first[i] += influence[l - j - 1] / (1 << (j + 1));
                        }
                        if (l + j >= len) second[i] = -1;
                        else second[i] += influence[l + j] / (1 << (j));
                    }
            for (i = 0; i <= mask; i++)
                for (j = 0; j <= mask2; j++)
                    nextdp[i, j] = MAX;

            for (i = 0; i <= mask; i++)
            {
                if (first[i] < 0) continue;
                for (j = 0; j <= mask2; j++)
                {
                    if (second[j] < 0) continue;
                    if (dp[i, j] == MAX) continue;

                    if (first[i] + second[j] >= resistance[l])
                    {
                        int nexti = ((i << 1) + j % 2) & mask;
                        int nextj = (j >> 1);
                        nextdp[nexti, nextj + (1 << 8)]
                            = Math.Min(nextdp[nexti, nextj + (1 << 8)], dp[i, j] + j % 2);
                        nextdp[nexti, nextj]
                            = Math.Min(nextdp[nexti, nextj], dp[i, j] + j % 2);
                    }
                }
            }
            dp = (int[,])nextdp.Clone();
        }
        int res = MAX;
        for (i = 0; i <= mask; i++) res = Math.Min(res, dp[i, 0]);
        if (res == MAX) return -1;
        else return res;

    }
}

SRM 483 Div1 Easy BestApproximationDiv1

14:16 | SRM 483 Div1 Easy BestApproximationDiv1 - chokudaiの日記 を含むブックマーク はてなブックマーク - SRM 483 Div1 Easy BestApproximationDiv1 - chokudaiの日記 SRM 483 Div1 Easy BestApproximationDiv1 - chokudaiの日記 のブックマークコメント

問題

0 <= A < B <= maxDenで、string numberと一致する桁数がもっとも多いA/Bを出力せよ

同一の場合は、A,Bがもっとも小さいものを出力

回答

やるだけ

public class BestApproximationDiv1 {

    int besta, bestb;

    public string findFraction(int maxDen, string number)
    {
        long basenum = (long)(double.Parse(number) * 1000000 + 0.5);
        int a, b;
        int maxmatch = -1;
        int besta = 999, bestb = 999;
        for (a = 0; a <= maxDen; a++)
        {
            for (b = a + 1; b <= maxDen; b++)
            {
                long temp = (long)((a * 1000000.0 / b) + 1e-9);
                int match = getCollectDigits(basenum, temp);
                if (match > maxmatch)
                {
                    maxmatch = match;
                    besta = a;
                    bestb = b;
                }
            }
        }
        return String.Concat(besta, "/", bestb, " has ", maxmatch, " exact digits");
    }

    int getCollectDigits(long a, long b)
    {
        int i;
        int res = 0;
        int first = 1000000;
        for (i = 0; i < 7; i++)
        {
            if ((a / first) % 10 == (b / first) % 10) res++;
            else break;
            first /= 10;
        }
        return res;
    }
}
 |