Hatena::Grouptopcoder

yambe2002の日記

|

2015-11-22

SRM658 Div2 Hard: OddEvenTreeHard(練習)

11:18

・ある木の条件として、各ノード間の距離が、①奇数②偶数③どちらでもよい、のいずれかで与えられる

・これを満たす木を答えよ


考え方

・③どちらでもよい、を条件から無くしていき、最後にそれを使って木をつくればよい

・ノードx-Aの距離が奇数、ノードy-Bの距離が奇数のとき:

 x-yの距離は奇数

 y-zの距離、x-zの距離の奇遇は同じになる

・ノードx-Aの距離が偶数、ノードy-Bの距離が偶数のとき:

 x-yの距離は偶数

 y-zの距離、x-zの距離の奇遇は同じになる

・ノードx-Aの距離とノードy-Bの距離が、奇数x偶数または偶数x奇数のとき:

 x-yの距離は奇数

 y-zの距離、x-zの距離の奇遇は反対になる

・この条件で、③どちらでもない、を奇遇で埋めていく。

・ノードを一周してもまだ「③どちらでもない」があったら、奇遇どちらかをセットして、また最初に戻る

・なお、途中で矛盾が生じたら、無効を返す

・また同ノード間の距離が奇数にセットされていた場合も無効を返す


考え方はほぼ合っていたのだが、ループが足りず「③どちらでもよい」が残っている状態で回答してしまっていた。

また、最後の条件(同ノード間に奇数がセットされていたら無効)の条件も抜けていた。

このあたりが不足していてもサンプルケースは通ってしまうので、もっと丁寧に手元ケースを考える必要があった。


public class OddEvenTreeHard {
    public int[] getTree(string[] xprm) {
        var invalid = new int[] { -1 };

        var n = xprm.Length;
        
        //扱いやすいように整数の数列にしておく
        //0:dontcare, 1:odd, 2:even
        var oddEvenTbl = new int[n, n];

        for (int i = 0; i < n; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if (i == j && xprm[i][j] == 'O') return invalid;    //この条件が抜けていた・・・

                var oddOrEven = xprm[i][j] == 'O' ? 1 : xprm[i][j] == 'E' ? 2 : 0;

                if (oddOrEven != 0)
                {
                    if ((oddEvenTbl[i, j] != 0 && oddEvenTbl[i, j] != oddOrEven) || 
                        (oddEvenTbl[j, i] != 0 && oddEvenTbl[j, i] != oddOrEven))
                    {
                        return invalid;
                    }
                    oddEvenTbl[i, j] = oddOrEven;
                    oddEvenTbl[j, i] = oddOrEven;
                }
            }
        }

        //「どちらでもよい」がなくなるまでループ
        while (true)
        {
            for (int cur = 0; cur < n; cur++)
            {
                for (int x = 0; x < n; x++)
                {
                    for (int y = 0; y < n; y++)
                    {
                        //現ノードcur、任意のノードx,yを考える
                        
                        if (oddEvenTbl[x, cur] == 0 || oddEvenTbl[y, cur] == 0) continue;

                        //x-cur、y-curのどちらも奇数なら
                        if (oddEvenTbl[x, cur] == oddEvenTbl[y, cur] && oddEvenTbl[x, cur] == 1)
                        {
                            //x-yは偶数
                            if (oddEvenTbl[x, y] == 1) return invalid;
                            oddEvenTbl[x, y] = 2;

                            //任意のzからx,yの距離は奇遇が一致する
                            for (int z = 0; z < n; z++)
                            {
                                //if(z==cur || z==x || z==y) continue;
                                if (oddEvenTbl[x, z] == 1 && oddEvenTbl[y, z] == 2) return invalid;
                                if (oddEvenTbl[x, z] == 2 && oddEvenTbl[y, z] == 1) return invalid;
                                if (oddEvenTbl[x, z] != 0) oddEvenTbl[y, z] = oddEvenTbl[x, z];
                                if (oddEvenTbl[y, z] != 0) oddEvenTbl[x, z] = oddEvenTbl[y, z];
                            }
                        }

                        //x-cur、y-curのどちらも偶数なら
                        if (oddEvenTbl[x, cur] == oddEvenTbl[y, cur] && oddEvenTbl[x, cur] == 2)
                        {
                            //x-yは偶数
                            if (oddEvenTbl[x, y] == 1) return invalid;
                            oddEvenTbl[x, y] = 2;

                            //任意のzからx,yの距離は奇遇が一致する
                            for (int z = 0; z < n; z++)
                            {
                                //if(z==cur || z==x || z==y) continue;
                                if (oddEvenTbl[x, z] == 1 && oddEvenTbl[y, z] == 2) return invalid;
                                if (oddEvenTbl[x, z] == 2 && oddEvenTbl[y, z] == 1) return invalid;
                                if (oddEvenTbl[x, z] != 0) oddEvenTbl[y, z] = oddEvenTbl[x, z];
                                if (oddEvenTbl[y, z] != 0) oddEvenTbl[x, z] = oddEvenTbl[y, z];
                            }
                        }

                        //x-cur、y-curのどちらかが奇数、どちらかが偶数なら
                        if (oddEvenTbl[x, cur] != oddEvenTbl[y, cur])
                        {
                            //x-yは奇数
                            if (oddEvenTbl[x, y] == 2) return invalid;
                            oddEvenTbl[x, y] = 1;

                            //任意のzからx,yの距離は奇遇が反対になる
                            for (int z = 0; z < n; z++)
                            {
                                //if (z == cur || z == x || z == y) continue;
                                if (oddEvenTbl[x, z] == 1 && oddEvenTbl[y, z] == 1) return invalid;
                                if (oddEvenTbl[x, z] == 2 && oddEvenTbl[y, z] == 2) return invalid;
                                if (oddEvenTbl[x, z] != 0) oddEvenTbl[y, z] = oddEvenTbl[x, z] == 1 ? 2 : 1;
                                if (oddEvenTbl[y, z] != 0) oddEvenTbl[x, z] = oddEvenTbl[y, z] == 1 ? 2 : 1;
                            }
                        }

                    }
                }
            }

            //「どちらでもよい」があったら、その1つに奇数をセットして最初からやる
            // ここの考慮が抜けていた・・・
            var found = false;
            for (int i = 0; i < n-1; i++)
            {
                for (int j = i+1; j < n; j++)
                {
                    if (oddEvenTbl[i, j] == 0)
                    {
                        oddEvenTbl[i, j] = 1;
                        oddEvenTbl[j, i] = 1;
                        found = true;
                        break;
                    }
                }
                if (found) break;
            }

            if (!found) break;
        }

        //node0をルートとして回答を作る
        var ret = new List<int>();

        //node0からの距離が奇数のものを、node0の子にする
        var firstOddNode = -1;
        for (int i = 1; i < n; i++)
        {
            if (oddEvenTbl[0, i] == 1)
            {
                if (firstOddNode == -1) firstOddNode = i;
                ret.Add(0);
                ret.Add(i);
            }
        }

        if (firstOddNode == -1) return invalid; //これはいらない、はず

        //node0からの距離が偶数のものを、node0の子の子にする
        for (int i = 1; i < n; i++)
        {
            if (oddEvenTbl[0, i] == 2)
            {
                ret.Add(firstOddNode);
                ret.Add(i);
            }
        }

        return ret.ToArray();
    }
}

2015-11-20

SRM669 Div2 Hard: LineMSTDiv2(練習)

14:05

解けなかったのでEditorialでお勉強。


・頂点数N(2~16)の完全グラフを考える

・エッジのコストは1または2。そのため全部で2^(N*(N-1)/2)パターンある

・各パターンに存在する最小全域木(MST)の数の合計を答えよ

・ただし、線になっている木のみカウントする


方針

・線の一本分だけで算出し、線の総数をかけてよい

・一本分の線のコストパターンをすべて列挙

・このパターンが最小全域木になってる場合として、各エッジについて考えていく

 1、エッジのコストが1のとき:ほかのエッジのコストが何であろうと、最小全域木になる条件を満たす

 2、エッジのコストが2のとき:このエッジの左にある頂点から右にある頂点につながるすべてのエッジは、コスト2でなければならない(コスト1があると、そこから迂回してコストのより小さい木が作れてしまう)

・1の条件であれば、エッジ左右のノード間のすべてについて、パターン数を2倍にしていく


public class LineMSTDiv2 {
    private const ulong mod = 1000000007;

    private ulong GetNum_OneLinePattern(ulong N)
    {
        ulong ret = 0;
        for (ulong mask = 0; mask < (ulong)(1 << (int)N - 1); mask++)  //線のコストパターン列挙
        {
            ulong currentNum = 1; //この線をMSTとする
            var cost2Edges = new bool[N, N]; //コスト2でなければならない組み合わせ

            for (ulong i = 0; i < N - 1; i++)
            {
                if (((mask >> (int)i) & 1) == 1)
                {
                    //エッジiとi+1の間がコスト1
                    //(0 to i) から (i+1, last) の全コンビネーションは、コスト2でなければならない
                    for (ulong l = 0; l <= i; l++) for (ulong r = i + 1; r < N; r++)
                        {
                            cost2Edges[l, r] = true;
                            cost2Edges[r, l] = true;
                        }
                }
            }

            for (ulong l = 0; l < N - 1; l++)
            {
                for (ulong r = l + 2; r < N; r++)     //n-n+1 のエッジは今の木に使ってるので無視
                {
                    if (!cost2Edges[l, r])  //コストが1でも2でもOKならパターン数を倍にする
                    {
                        currentNum *= 2;
                        currentNum %= mod;
                    }
                }
            }

            ret += currentNum;
            ret %= mod;
        }
        return ret;
    }

    // N!/2 を返しているだけ
    private ulong GetLinePatternNum(int N)
    {
        return (ulong)(BigInteger.ModPow(Enumerable.Range(1, N).Select(n => new BigInteger(n)).Aggregate((a, b) => (a * b)) / 2, 1, new BigInteger(mod)));
    }

    public int count(int N)
    {
        ulong ret = 0;

        ret = GetNum_OneLinePattern((ulong)N);

        ret = ret * GetLinePatternNum(N);

        return (int)(ret % mod);
    }
}

2015-11-18

SRM670 Div2 Hard: Treestrat(練習)

06:54

練習とはいえ、初めてDiv2Hardを通すことができた。

考え方もEditorialと同じ。これが本番だったらDiv1に上がれたかな。


問題概要

・Treeが与えられる

・Treeの各ノードは、赤・青トークンがいずれか1つあるか、もしくはブランク

・最初に赤サイドが任意の赤トークンを隣のノードに動かす(動かさなくともよい)

・次に青サイドが任意の青トークンを隣のノードに動かす(動かさなくもよい)

・ノードは複数のトークンを持てる

・青が赤を捕まえたらゲームオーバー

・赤はなるべく長く逃げようとし、青はなるべく早く捕まえようとする

・ゲームオーバーまでのラウンド数を答えよ


方針

ノードが複数のトークンを持てるため、すべての赤トークンについて捕まえられるまでの最長ラウンド数を求め、その最短を出せばよい。

赤トークンは動けるセルをすべてトライ、青トークンは、動いた後の赤トークンに近づくようにすべて動かす。

最初にワーシャルフロイトで全セル間の距離を求めておくと楽。


public class Treestrat {
    int[,] dist;
    int[] Tree, A, B;
    int N;

    private void GetDist()
    {
        dist = new int[N, N];

        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                dist[i, j] = 10000;
                if (i == j) dist[i, j] = 0;
            }
        }

        for (int i = 0; i < Tree.Length; i++)
        {
            dist[Tree[i], i+1] = 1;
            dist[i+1, Tree[i]] = 1;
        }

        for (int k = 0; k < N; k++)
        {
            for (int i = 0; i < N; i++)
            {
                for (int j = 0; j < N; j++)
                {
                    dist[i, j] = Math.Min(dist[i, j], dist[i, k] + dist[k, j]);
                }
            }
        }   
    }

    private ulong GetMask(int[] b)
    {
        ulong ret = 0;

        foreach (var val in b)
        {
            ret |= ((ulong)1 << val);
        }

        return ret;
    }

    private List<int> GetBluePos(ulong mask)
    {
        var ret = new List<int>();

        for (int i = 0; i < N; i++)
        {
            if ((mask & (ulong)1) != 0) ret.Add(i);
            mask >>= 1;
        }

        return ret;
    }

    private int[] GetNewBluePos(int tgtRedPos, List<int> bluePos)
    {
        var ret = new List<int>();
        foreach (var b in bluePos)
        {
            var newBluePos = GetNewBluePos(tgtRedPos, b);
            ret.Add(newBluePos);
        }
        return ret.ToArray();
    }

    private int GetNewBluePos(int tgtRedPos, int bluePos)
    {
        var ret = 0;
        var minDist = Int32.MaxValue;

        for (int nextPos = 0; nextPos < N; nextPos++)
        {
            if (dist[nextPos, bluePos] == 1 && dist[tgtRedPos, nextPos] < minDist)
            {
                ret = nextPos;
                minDist = dist[tgtRedPos, nextPos];
            }
        }
        return ret;
    }

    private Dictionary<Tuple<int, ulong>, int> dict = new Dictionary<Tuple<int, ulong>, int>();

    //maskは青トークンがあるノードの位置情報
    private int GetMaxTimeToKill(int redPos, ulong mask)
    {
        var bluePos = GetBluePos(mask);
        if (bluePos.Contains(redPos)) return 0;

        var key = new Tuple<int, ulong>(redPos, mask);
        if (dict.ContainsKey(key)) return dict[key];

        var ret = 0;
        for (int nextPos = 0; nextPos < N; nextPos++)
        {
            if (dist[redPos, nextPos] == 1 || redPos == nextPos)
            {
                if (bluePos.Contains(nextPos))
                {
                    ret = Math.Max(ret, 1);
                    continue;
                }

                var newBluePos = GetNewBluePos(nextPos, bluePos);
                ret = Math.Max(ret, GetMaxTimeToKill(nextPos, GetMask(newBluePos)) + 1);
            }
        }

        dict.Add(key, ret);
        return ret;
    }

    public int roundcnt(int[] t, int[] a, int[] b) {
        Tree = t;
        A = a;
        B = b;
        N = Tree.Length + 1;

        GetDist();

        int res = Int32.MaxValue;

        var mask = GetMask(b);
        foreach (var red in a)
        {
            var ans = GetMaxTimeToKill(red, mask);
            res = Math.Min(res, ans);
        }

        return res;
    }
}

2015-11-16

SRM671 Div2 Hard: BearDestroysDiv2(練習)

14:13

解けなかったのでEditorialで理解。

Editorialのコードの変数名やコメントがいまいちで読みづらかったので、書き直したバージョンをメモしておく。

このレベルが解けるようになれば、Div2の一ケタ順位にいけそう。

public class BearDestroysDiv2 {
    int W, H, MOD;
    int[, , ,] dp = new int[141, 8, 41, 1 << 7];

    // 現在地x,y以降でS本をじぶんで押すパターン数を返す
    // maskは現在地から右にW分、木がすでに無いセルを表す(折り返す。以下のCとx)
    //   | | |C|x|x|
    //   |x|x| | | |
    private long GetPatternNum(int s, int x, int y, int mask)
    {
        long res = dp[s, x, y, mask];
        if (res == -1)
        {
            res = 0;
            if (y == H)
            {
                if (s == 0)
                    res = 1;    //全セル走査済。押さないパターンだけ1つある
            }
            else if (x == W)
                res = GetPatternNum(s, 0, y + 1, mask);     //行が終わったので次の行へ。
            else
            {
                // A: 木を押さないパターン。xの位置のmaskは0になる(木が存在、巻き添えになってない)
                long A = GetPatternNum(s, x + 1, y, mask & ~(1 << x));

                // B: 木を東に押すパターン。
                long B = 0;
                bool can_east = true;
                if (((1 << x) & mask) != 0 || ((1 << (x + 1)) & mask) != 0 || (x + 1 == W))
                    can_east = false;   //現セルと東のセルに木がなかったら無理
                else
                    if (s > 0)
                        B = GetPatternNum(s - 1, x + 1, y, mask | (1 << (x + 1))); //東のセルのマスクに1をセットして次へ。Sも1つ減る
                
                // C: 木を南に押すパターン
                long C = 0;
                bool can_down = true;
                if (((1 << x) & mask) != 0 || (y + 1 == H)) //現セルに木がなかったら無理
                    can_down = false;
                else
                    if (s > 0)
                        C = GetPatternNum(s - 1, x + 1, y, mask | (1 << x)); //現セルのマスクに1をセットして次へ。Sも1つ減る

                // 木に「東」のタグがついてる
                if (can_east)
                    res += B;
                else if (can_down)
                    res += C;
                else
                    res += A;

                // 木に「南」のタグがついてる
                if (can_down)
                    res += C;
                else if (can_east)
                    res += B;
                else
                    res += A;
            }
            res %= MOD;
            dp[s, x, y, mask] = (int)res;
        }
        return (int)res;
    }

    public int sumUp(int w, int h, int mod) {
        W = w;
        H = h;
        MOD = mod;

        for (int i = 0; i < 141; i++) for (int j = 0; j < 8; j++) for (int k = 0; k < 41; k++) for (int l = 0; l < 1 << 7; l++)
            dp[i, j, k, l] = -1;

        long res = 0;
        for (long s = 0; s <= W * H / 2; s++)
        {
            res += (s * GetPatternNum((int)s, 0, 0, 0)) % MOD;
        }

        return (int)(res % MOD);
    }
}

2015-11-14

SRM672 Div2 1000 Tdetectived2 Editorialより

14:33

Edirotialのコードを理解するため、ちょっと書き直して日本語のコメントを書いたりした。

捨てるのも何なので、貼っておく。


public class Tdetectived2 {
    int n;
    string[] s;
    int[,] memo = new int[18, 1 << 18];

    // 全員の面談有無の状態がmaskだったときに
    // tgtさんが面談されるまでの最短時間を返す
    private int GetMinimumTimeBeforeAsk(int tgt, int mask)
    {
        int res = memo[tgt, mask];

        if (res == -1)
        {
            int best_time = 0;
            int max_suspecious_level = -1;

            // 全員でループ
            for (int x = 1; x < n; x++)
            {
                // この人xがまだ面談してなかったら・・・
                if (((1 << x) & mask) == 0)
                {
                    // xさんも面談済にした場合の、tgtさんまでの最短時間を取得
                    int t = 1 + ((x == tgt) ? 0 : GetMinimumTimeBeforeAsk(tgt, mask | (1 << x)));

                    int suspecious_level = 0;

                    // また全員でループ
                    for (int y = 0; y < n; y++)
                    {
                        // この人yが面談済なら、xさんへの疑いレベルをアップデート
                        if (((1 << y) & mask) != 0)
                            suspecious_level = Math.Max(suspecious_level, s[y][x] - '0');

                        // 最終回答をアップデート。疑いがもっとも濃くなった場合を使う
                        if (suspecious_level > max_suspecious_level)
                        {
                            max_suspecious_level = suspecious_level;
                            best_time = t;
                        }
                        else if ((suspecious_level == max_suspecious_level) && (best_time > t))
                        {
                            best_time = t;
                        }
                    }
                }
                res = best_time;
            }
        }
        memo[tgt, mask] = res;
        return res;
    }

    public int reveal(string[] s_prm) {
        for (int i = 0; i < 18; i++) for (int j = 0; j < 1 << 18; j++) memo[i, j] = -1;
        s = s_prm;
        n = s.Length;

        int res = 0;

        for (int i = 0; i < n; i++)
        {
            res += i * GetMinimumTimeBeforeAsk(i, 1);
        }

        return res;
    }
}

|