Hatena::Grouptopcoder

yambe2002の日記

2016-05-04

SRM690 Div1 Easy: WolfCardGame

22:51

本番では解けなかった。

https://community.topcoder.com/stat?c=problem_statement&pm=14248&rd=16729

解法はこちらを参考にさせていただいた。

http://mayokoex.hatenablog.com/entry/2016/05/04/120006

1~100までの数字が書いてあるカードが100枚ある。ここからK枚を選んだとき、そのサブセットの合計がどうやってもNにならないようにしたい。その組み合わせを答えよ。不可能なときは空配列を返せ。ただし、数字は、合計する際にネゲートする(負にする)こともできる。

例:選ばれたカード{1,3,4,7}は、{-1,3,4,-7}で計算することも可能

N:1~100

K:1~15

<方針>

Nで場合分けすることで解ける。

1、Nが偶数のとき

 →3の倍数のカードだけ返す。そうすれば合計が3nにしかならない。なお、Nが6の倍数のときは別に場合分けする

2、Nが6の倍数のとき

 →5の倍数のカードだけ返す。そうすれば合計が5nにしかならない。なお、Nが30の倍数のときは別に場合分けする

3、Nが30か60のとき

 →1と、7の倍数のカードだけ返す。そうすれば、合計が7n+1または7n-1にしかならない。

4、Nが90のとき

 →2と、7の倍数のカードだけ返す。そうすれば、合計が7n+2または7n-2にしかならない。

5、Nが奇数のとき

 →偶数カードだけ返せば、合計が必ず偶数になる

不可能な場合は存在しない。


public class WolfCardGame {
    int[] GetRet(int additional, int seed, int K)
    {
        var ret = new List<int>();
        if (additional > 0) ret.Add(additional);

        var val = seed;
        while (ret.Count() < K)
        {
            ret.Add(val);
            val += seed;
        }

        return ret.ToArray();
    }

    public int[] createAnswer(int N, int K) {
        if (N % 90 == 0)
            return GetRet(2, 7, K);
        if (N % 30 == 0)
            return GetRet(1, 7, K);
        if (N % 6 == 0)
            return GetRet(-1, 5, K);
        if (N % 2 == 0)
            return GetRet(-1, 3, K);
        return GetRet(-1, 2, K);
    }
}

本番は解けなかったにも関わらずレートが増えた。Div1は不思議な場所だ・・・。

2016-03-29

SRM686 Div2 Hard: BracketSequenceDiv2

00:24

解法はこちらを参考にさせていただいた。

http://pekempey.hatenablog.com/entry/2016/03/29/174037


左カッコと右カッコからなる文字列が与えられる。

任意の文字を削除したとき、正しいカッコ列は何通り作れるか。


DP[できた文字列の最後文字がある位置][開いているカッコの数] を設定する。

すると、DP[i][j]について

 DP[次の左カッコ位置][j+1] ← DP[i][j]を足す

 DP[次の右カッコ位置][j-1] ← DP[i][j]を足す

が成り立つ。

開いているカッコ数がゼロの部分を合計すれば答えになる。

public class BracketSequenceDiv2 {
    const int MOD = 1000000007;

    public int count(string s) {
        var dp = new int[s.Length, s.Length + 2];

        for (int i = 0; i < s.Length; i++)
        {
            if (s[i] == '(')
            {
                dp[i, 1] = 1;
                break;  //dont forget this!!
            }
        }

        for (int i = 0; i < s.Length; i++)
        {
            for (int j = 0; j < s.Length + 1; j++)
            {
                var nextLeftBracket = s.IndexOf('(', i + 1);
                var nextRightBracket = s.IndexOf(')', i + 1);

                if (nextLeftBracket != -1) dp[nextLeftBracket, j + 1] = (dp[nextLeftBracket, j + 1] + dp[i, j]) % MOD;
                if (nextRightBracket != -1 && j - 1 >= 0)
                {
                    dp[nextRightBracket, j - 1] = (dp[nextRightBracket, j - 1] + dp[i, j]) % MOD;
                }
            }
        }

        long ret = 0;
        for (int i = 0; i < s.Length; i++)
        {
            ret += dp[i, 0];
            ret %= MOD;
        }
        return (int)ret;
    }
}

SRM686 Div2 Mid: SegmentsAndPoints

21:37

直線上に点がいくつかある。それと同じ数だけ、直線上の範囲の組み合わせも与えられる。

点:p[]

範囲:l、r

すべての点が、どれかの範囲とペアにすることが可能か求めよ。

点の小さい方からループ:

  点の位置を含む範囲を抽出

  該当範囲のr[]が最小のものを取り出す

を繰り返すだけ。

public class SegmentsAndPoints {
    public string isPossible(int[] p, int[] l, int[] r) {
        var list = new List<Tuple<int, int>>();

        for (int i = 0; i < l.Length; i++)
        {
            var pair = new Tuple<int, int>(l[i], r[i]);
            list.Add(pair);
        }

        p = p.OrderBy(v => v).ToArray();

        for (int i = 0; i < p.Length; i++)
        {
            var tgt = list.Where(v => v.Item1 <= p[i] && v.Item2 >= p[i]).OrderBy(w => w.Item2).FirstOrDefault();
            if (tgt == null) return "Impossible";

            list.Remove(tgt);
        }

        return "Possible";
    }
}

SRM686結果:○○-

なんとギリギリでDiv1に上がってしまった。Hard解いたことないのに・・・。

SRM686 Div2 Easy: TreeAndVertex

21:30

2ヶ月ぶりのSRM本番。


木構造を表す配列Tree[]がある。ノードi+1はノードTree[i]とつながっている。

ノードをいずれか一つ取り除いた時、木はいくつに分けられるか。その最大数を求めよ。

ノードとつながっているエッジ数の最大値を返せば良い。

public class TreeAndVertex {
    public int get(int[] tree) {
        var conn = new int[101];

        for (int i = 0; i < tree.Length; i++)
        {
            conn[i + 1]++;
            conn[tree[i]]++;
        }

        return conn.Max();
    }
}

2016-02-06

SRM656 Div2 Hard: PermutationCountsDiv2(練習)

12:25

1~Nの重複のない数字の並べ方の組み合わせ数を求める。

並び替えた数字の列は、必ず以下のルールに従う。

  • 基本的に、前の数字よりも小さくなる
  • ただし、該当数字に位置がpos[]に含まれているときは、その数字は次の数字より小さくなる

[l, r)の範囲について、上記を満たす組み合わせ数を求める関数を、GetCombination(int l, int r)とする。

ある範囲内に、谷になる位置が1つだけあると仮定すると、その位置は必ず最小の値がはいる。

谷の両脇に値を入れるパターン数が、NCRで求めることができる。

(今の数-1から、谷の片側の数を選ぶパターン数になる)

谷がたくさんあるときは、分割して再帰的にGetCombination()を呼べばよい。


最初、dp[]をintで宣言してオーバーフローしてしまっていた。


public class NCR
{
    long[,] ncr;

    public NCR(int size, int MOD)
    {
        ncr = new long[size + 1, size + 1];
        for (int i = 0; i <= size; i++)
        {
            ncr[i, 0] = 1;
            for (int j = 1; j <= i; j++)
            {
                ncr[i, j] = (ncr[i - 1, j] + ncr[i - 1, j - 1]) % MOD;
            }
        }
    }

    public long GetNcr(int n, int r)
    {
        return ncr[n, r];
    }
}

public class PermutationCountsDiv2 {
    int MOD = 1000000007;

    NCR ncr;
    int N;
    bool[] lessThanNext;
    long[,] dp;    //int[]だとオーバーフローする

    bool IsLowest(int idx, int l, int r)
    {
        return (idx == l || !lessThanNext[idx - 1]) && (idx == r - 1 || lessThanNext[idx]);
    }

    int[] GetLowestPositions(int l, int r)
    {
        var ret = new List<int>();

        for (int idx = l; idx < r; idx++)
            if (IsLowest(idx, l, r)) ret.Add(idx);

        return ret.ToArray();
    }

    //return combination num of [l r)
    long GetCombination(int l, int r)
    {
        if (dp[l, r] != 0) return dp[l, r];

        long ret = 0;
        var lowestPositions = GetLowestPositions(l, r);

        foreach (var lowestPos in lowestPositions)
        {
            var cmb = lowestPos == l || lowestPos == r - 1 ? 1 : ncr.GetNcr(r - l - 1, lowestPos - l);
            ret += (((GetCombination(l, lowestPos) * GetCombination(lowestPos + 1, r)) % MOD) * cmb) % MOD;
            ret %= MOD;
        }

        dp[l, r] = ret % MOD;
        return dp[l, r];
    }

    public int countPermutations(int pN, int[] pos) 
    {
        N = pN;
        
        lessThanNext = new bool[N + 1];
        foreach (var p in pos) lessThanNext[p - 1] = true;

        ncr = new NCR(N + 2, MOD);
        dp = new long[N + 1, N + 1];

        for (int l = 0; l <= N; l++)
        {
            dp[l, l] = 1;
            if (l <= N - 1) dp[l, l + 1] = 1;
        }

        return (int)GetCombination(0, N);
    }
}

2016-01-29

SRM579 Div2 Hard: MarblePositioning(練習)

11:42

さまざまな半径のビー玉を一直線に並べた時に、最初のビー玉の接地点と最後のビー玉の接地点の距離を最小にする。

ビー玉の数が少ないので、全パターンをチェックすればよい。

最初IntからDoubleへのキャストを忘れてSystemtestで落としてしまった。

public class MarblePositioning {

    static void Swap<T>(ref T a, ref T b)
    {
        T tmp;
        tmp = a;
        a = b;
        b = tmp;
    }

    static void GetPermutation<T>(ref List<T[]> ret, T[] arry, int i, int n)
    {
        int j;
        if (i == n)
            ret.Add(new List<T>(arry).ToArray());
        else
        {
            for (j = i; j <= n; j++)
            {
                Swap(ref arry[i], ref arry[j]);
                GetPermutation(ref ret, arry, i + 1, n);
                Swap(ref arry[i], ref arry[j]); //backtrack
            }
        }
    }

    double GetDistOfTwoMarbles(int a, int b)
    {
        return 2 * Math.Sqrt((double)a * (double)b);    //キャストを忘れない!
    }

    double GetPosition(int idx, List<int> prevBalls, List<double> prevPositions, int[] radius)
    {
        double ret = 0.0;

        var currentBallRadius = radius[idx];
        for (int prevIdx = 0; prevIdx < prevBalls.Count(); prevIdx++)
        {
            var prevBall = prevBalls[prevIdx];
            var prevBallRadius = radius[prevBall];
            var prevBallPosition = prevPositions[prevIdx];

            var pos = prevBallPosition + GetDistOfTwoMarbles(currentBallRadius, prevBallRadius);
            ret = Math.Max(ret, pos);
        }

        return ret;
    }

    double GetDist(int[] pattern, int[] radius)
    {
        var balls = new List<int>();
        balls.Add(pattern.First());

        var positions = new List<double>();
        positions.Add(0);

        for(int idx = 1; idx < pattern.Length; idx++)
        {
            positions.Add(GetPosition(pattern[idx], balls, positions, radius));
            balls.Add(pattern[idx]);
        }

        return positions.Last();
    }

    public double totalWidth(int[] radius) {
        double res = double.MaxValue;

        var indices = Enumerable.Range(0, radius.Length).ToArray();
        var permutations = new List<int[]>();
        GetPermutation(ref permutations, indices, 0, radius.Length - 1);

        foreach(var pattern in permutations)
        {
            var dist = GetDist(pattern, radius);
            if(dist < res) res = dist;
        }

        return res;
    }
}

2016-01-20

下書き:SRM678 Div2 Hard: RevengeOfTheSith

13:47

N段の階段step[]があり、step[i]はi-1番目とi番目の高さの差である(下の段から。iがゼロのときは床からの高さ)。

最上段から1段ずつ降りて行ったとき、ダメージが最小になるようにしたい。

条件は、

・1段降りたときのダメージは(H-D)^2。Hは高さの差。H<=Dならノーダメージ

・床と、一番上の段以外は好きな高さに変えられる(T個まで)。ただし、段の順番は変えてはならない。

・各段の高さを変えた後で、降りるのをスタートする

・高さは整数値のみ

1 <= stepの長さ <= 50

1 <= stepの要素の値 <= 1000

1 <= D <= 1000

0 <= T <= stepの長さ-1



SRM678結果:○○-

Div1は遠い。

SRM678 Div2 Mid: AttackOfTheClones

13:37

オビさんはTシャツをN毎もっている。そして、この世界では一週間はN日である。

彼は一週間、毎日違うTシャツを着たい。Tシャツは着たら洗う必要があり、洗うのには最低でN-2日かかる。

最初の週のTシャツを着る順番と、最後の週のTシャツを着る順番が与えられる。

このとき、最後の週の順番にするまで、何週間かかるか。


もっとも日数がかかるTシャツは、最終週の位置が最初の週より前にあるもので、差が最大のもにになる。これを返せばよい。

    public int count(int[] firstWeek, int[] lastWeek) {
        var f = firstWeek.ToList();
        var l = lastWeek.ToList();

        int res = 1;

        for (int idx = lastWeek.Length - 1; idx > 0; idx--)
        {
            var tgt = f[idx];
            var tgtIdx = l.IndexOf(tgt);

            if (tgtIdx < idx) res = Math.Max(res, idx - tgtIdx + 1);
        }

        return res;
    }