Hatena::Grouptopcoder

yambe2002の日記

 | 

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();
    }
}
 |