Hatena::Grouptopcoder

chokudaiの日記

 | 

2010-11-07

SRM 295 Div1 Easy BuildBridge

18:08 | SRM 295 Div1 Easy BuildBridge - chokudaiの日記 を含むブックマーク はてなブックマーク - SRM 295 Div1 Easy BuildBridge - chokudaiの日記 SRM 295 Div1 Easy BuildBridge - chokudaiの日記 のブックマークコメント

問題

長さLのカードを重ねて、倒れないように長さDの橋を作る時、最低枚数を求めてね!

方針

Σ(L/2k)>=Dになればおk

ソースコード

    public int howManyCards(int D, int L)
    {
        double res = 0;
        double eps = 1e-9;
        for (int i = 1; ; i++)
        {
            res += (double)L / i / 2;
            if (res + eps > D) return i;
        }
    }

SRM 296 Div1 Easy NewAlbum

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

問題

同じ長さの曲をCDに詰め込む

同じCDに13の倍数の曲を詰め込んじゃだめ

CDの最低必要枚数を答えよ

方針

色々気をつけながらとくだけ

ソースコード

    public int leastAmountOfCDs(int nSongs, int length, int cdCapacity)
    {
        int num = (cdCapacity+1) / (length + 1);
        if (num % 13 == 0) num--;
        int temp = (nSongs + num - 1) / num;
        int nokori = nSongs - num * (temp - 1);
        if (nokori % 13 == 0)
        {
            if (temp == 1 || nokori == num - 1) temp++;
        }
        return temp;
    }

SRM 297 Div1 Easy OptimalQueues

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

問題

なんか待ち行列があるからよくわかんない条件で一番短くなるようにするみたい

方針

ソートしてそれぞれ試すだけみたい

ソースコード

    public int minWaitingTime(int[] clientArrivals, int tellerCount, int serviceTime)
    {
        Array.Sort(clientArrivals);
        Array.Reverse(clientArrivals);
        int res = 0;
        for (int i = 0; i < clientArrivals.Length; i++)
            res = Math.Max(res, i / tellerCount * serviceTime + clientArrivals[i]);
        return res + serviceTime; 
    }

SRM 298 Div1 Easy FibonacciPositioning

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

問題

フィボナッチで線形補完してね!

回答

フィボナッチで線形補完する

ソースコード

ひどいのだけどw

    public double getFPosition(int n)
    {
        if (n == 1) return 2.0;
        int i;
        int[] ar = new int[100000];
        ar[0] = 1;
        ar[1] = 1;
        for (i = 2; i < 100000; i++)
        {
            ar[i] = ar[i - 1] + ar[i - 2];
        }
        for (i = 1; i < 100000; i++)
        {
            if (ar[i] >= n)
            {
                return i + 1 - (double)(ar[i] - n) / (ar[i] - ar[i - 1]);
            }
        }
        return 0;
    }

SRM 299 Div1 Easy Projections

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

問題

長方形のグリッドに1*1の障害物があったりなかったりする

前から見た時と右から見たときにどう見えるかが示される

障害物の最大数・最小数を答えなさい

方針

最大数:前から見たときの障害物個数*右から見たときの障害物個数

最小数:max(前から見たときの障害物個数,右から見たときの障害物個数)

よって数えるだけ

ソースコード

    public int[] count(string front, string right)
    {
        int i;
        int a = 0, b = 0;
        for (i = 0; i < front.Length; i++) if (front[i] == 'x') a++;
        for (i = 0; i < right.Length; i++) if (right[i] == 'x') b++;
        return new int[] { Math.Max(a,b), a*b };
    }

SRM 386 Div1 Easy CandidateKeys

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

問題

問題を読むのが問題です

方針

問題を読めればやるだけ

ソースコード

   public int[] getKeys(string[] table)
    {
        int len = 1 << table[0].Length;
        bool[] superkey = new bool[len];
        int i, j, k;
        int max = -1, min = 1000;
        for (i = 0; i < len; i++)
        {
            Dictionary<string, int> dic = new Dictionary<string, int>();
            for (j = 0; j < table.Length; j++)
            {
                string s = "";
                for (k = 0; k < table[j].Length; k++)
                {
                    if ((i & (1 << k)) != 0) s += table[j][k];
                }
                if (dic.ContainsKey(s)) break;
                dic[s] = 1;
            }
            if (j != table.Length) continue;
            superkey[i] = true;
            int now = 0;
            for (j = 0; j < table[0].Length; j++)
            {
                if ((i & (1 << j)) != 0)
                {
                    now++;
                    if (superkey[i - (1 << j)]) break;
                }
            }
            if (j == table[0].Length)
            {
                min = Math.Min(min, now);
                max = Math.Max(max, now);
            }
        }
        if (max < 0) return new int[0];
        else return new int[2] { min, max };
    }

SRM 385 Div1 Easy UnderscoreJustification

13:41 | SRM 385 Div1 Easy UnderscoreJustification - chokudaiの日記 を含むブックマーク はてなブックマーク - SRM 385 Div1 Easy UnderscoreJustification - chokudaiの日記 SRM 385 Div1 Easy UnderscoreJustification - chokudaiの日記 のブックマークコメント

問題

  • 文字列を構成する単語の集合
  • 最終的に作りたい文字列の長さ

が与えられる。間に均一にスペースを入れる時(差が1以下ならどういう入れ方でもおk)、辞書順最小なものを作りなさい

方針

  1. まず共通で入れるべきスペースの数を入れる
  2. 前の方から、次の文字が大文字なところの前に入れる
  3. 後ろの方から、次の文字が小文字なところの前に入れる

おわり

ソースコード

    public string justifyLine(string[] words, int width)
    {
        int i, len = words.Length - 1;
        for (i = 0; i < words.Length; i++) width -= words[i].Length;
        int[] ar = new int[len];
        for (i = 0; i < len; i++) ar[i] = width / len;
        width -= width / len * len;
        for (i = 0; i < len && width != 0; i++)
        {
            if (words[i + 1][0].CompareTo('_') >= 0)
            {
                width--;
                ar[i]++;
            }
        }
        for (i = len-1; i >= 0 && width != 0; i--)
        {
            if (words[i + 1][0].CompareTo('_') < 0)
            {
                width--;
                ar[i]++;
            }
        }
        string result = "";
        for (i = 0; i < len; i++)
        {
            result += words[i];
            for (int j = 0; j < ar[i]; j++) result += "_";
        }
        return result + words[len];
    }

SRM 384 Div1 Easy Library

13:18 | SRM 384 Div1 Easy Library - chokudaiの日記 を含むブックマーク はてなブックマーク - SRM 384 Div1 Easy Library - chokudaiの日記 SRM 384 Div1 Easy Library - chokudaiの日記 のブックマークコメント

問題

ある図書館の「本の名前」「置いてある部屋」「閲覧権限」の3つが与えられる

入れる部屋の集合と、その人の権限レベルの集合が与えられた時に、入手できる本の種類数を答えよ

回答

mapやらDictionaryやら どうとでもなる

ソースコード

    public int documentAccess(string[] records, string[] userGroups, string[] roomRights)
    {
        Dictionary<string, int> userdic = new Dictionary<string, int>();
        Dictionary<string, int> roomdic = new Dictionary<string, int>();
        Dictionary<string, int> recdic = new Dictionary<string, int>();
        int i;
        for (i = 0; i < userGroups.Length; i++) userdic[userGroups[i]] = 1;
        for (i = 0; i < roomRights.Length; i++) roomdic[roomRights[i]] = 1;
        for (i = 0; i < records.Length; i++)
        {
            string[] st = records[i].Split(' ');
            if (userdic.ContainsKey(st[2]) && roomdic.ContainsKey(st[1])) recdic[st[0]] = 1;
        }
        return recdic.Count;
    }

SRM 383 Div1 Easy Planks

13:06 | SRM 383 Div1 Easy Planks - chokudaiの日記 を含むブックマーク はてなブックマーク - SRM 383 Div1 Easy Planks - chokudaiの日記 SRM 383 Div1 Easy Planks - chokudaiの日記 のブックマークコメント

問題

木材を切って売る。

  • 出荷時のサイズは全て一緒じゃないとだめ
  • 切るのにお金がかかる
  • 貰える金額は(出荷数)*(長さ)*woodvalue

収益最大化しなさいっ

方針

全探査

ソースコード

    public int makeSimilar(int[] lengths, int costPerCut, int woodValue)
    {
        int result = 0;
        int i,j;
        for (i = 1; i <= 10000; i++)
        {
            int now = 0;
            for (j = 0; j < lengths.Length; j++)
            {
                int plus = 0;
                plus += lengths[j] / i * woodValue * i;
                if (lengths[j] % i == 0 && lengths[j] >= i) plus -= (lengths[j] / i - 1) * costPerCut;
                else plus -= (lengths[j] / i) * costPerCut;
                now += Math.Max(0, plus);
            }
            result = Math.Max(result, now);
        }
        return result;
    }

AnitaAnita 2012/07/10 07:13 Got it! Thanks a lot again for helnpig me out!

cqjqcowuqqmcqjqcowuqqm 2012/07/10 16:35 hkDpK5 <a href="http://xgrkysedhwcl.com/">xgrkysedhwcl</a>

maubcamaubca 2012/07/12 12:47 mCIKTN <a href="http://pibfomngcqgb.com/">pibfomngcqgb</a>

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/chokudai/20101107
 |