chokudaiの日記

SRM 295 Div1 Easy BuildBridge

18:08 |

問題

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

方針

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

ソースコード

    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 |

問題

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

同じＣＤに１３の倍数の曲を詰め込んじゃだめ

ＣＤの最低必要枚数を答えよ

方針

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

ソースコード

    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 |

問題

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

方針

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

ソースコード

    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 |

問題

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

回答

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

ソースコード

ひどいのだけどｗ

    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 |

問題

長方形のグリッドに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 |

問題

問題を読むのが問題です

方針

問題を読めればやるだけ

ソースコード

   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 |

問題

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

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

方針

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 |

問題

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

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

回答

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 |

問題

木材を切って売る。

• 出荷時のサイズは全て一緒じゃないとだめ
• 切るのにお金がかかる
• 貰える金額は（出荷数）＊（長さ）＊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;
    }

ツイートする