HackerRank Week of Code 33 参加日記

262位/11880人。Easy問は省略する。

Transform to Palindrome

n種類の文字で構成された、長さmの文字列sがある。ここで、Transform[x,y]は、文字xをyへ、または文字yをxへ変換できることを意味する。k個のTransformが与えられたとき、sを変換してなるべく長いPalindromic Subsequenceの長さを求めよ。

同じTransformグループの文字を、UnionFindを使ってすべて同じ文字に変換する。そして文字列の最長Palindromic Subsequenceを求めればよい。これはDPの有名問題。
Longest palindromic subsequence - PEGWiki

public static int GetAns(List<int[]> transforms, int[] s)
{
    Transform(s, transforms);
    return GetLPS(s);
}

// Change letters in the same group to the same letter
public static void Transform(int[] s, List<int[]> transforms)
{
    var unionFind = new UnionFind();
    foreach (var t in transforms)
    {
        unionFind.Unite(t[0], t[1]);
    }
    for (int i = 0; i < s.Length; i++)
    {
        s[i] = (int)unionFind.RootValue(s[i]);
    }
}

// Longest Palindromic Subsequence: O(N^2)
public static int GetLPS(int[] s)
{
    var dp = new int[s.Length + 1, s.Length + 1];
    for (int i = s.Length; i >= 0; i--)
    {
        for (int j = i; j < s.Length + 1; j++)
        {
            if (i == j) dp[i, j] = 0;
            if (j - i == 1) dp[i, j] = 1;
            if (j - i > 1 && s[i] != s[j - 1]) dp[i, j] = Math.Max(dp[i + 1, j], dp[i, j - 1]);
            if (j - i > 1 && s[i] == s[j - 1]) dp[i, j] = 2 + dp[i + 1, j - 1];
        }
    }
    return dp[0, s.Length];
}

(UnionFindの実装は省略)

Palindromic table

n*m座標のグリッドそれぞれに、0~9の数字が入っている。任意の四角形を取り出したとき、中にある数字を並び替えて回文を作りたい。面積が最大になるように四角形を選び出せ。回文は前ゼロを含んではならない。また、面積1の四角形はいずれも有効とする。
1 <= n, m <= 10^5
n * m <= 10^5

ある範囲で回文ができるかどうかは、
・すべての文字種が偶数個である
・または１つの文字種だけが奇数個である
で判断できる。文字の種類は10個しかないので、その偶奇を10ビットで管理する。

if (i > 0) hash_sum[i][j] = hash_sum[i - 1][j];
if (j > 0) hash_sum[i][j] ^= hash_sum[i][j - 1];
if (i > 0 && j > 0) hash_sum[i][j] ^= hash_sum[i - 1][j - 1];
hash_sum[i][j] ^= hashTable[table[i][j]];

こうすれば、hash_sum[i][j]は、座標(0,0)から(i,j)までの偶奇情報になる。すると任意の範囲での偶奇情報は、XORすることで簡単に求められるようになる。
次にyでループする。あるy範囲(d,u)に対して考えたとき、まずy方向のHash値(偶奇情報)をマージしてしまう。

for (var x = 0; x < m; x++)
    hash_line[x] = hash_sum[u][x] ^ (d > 0 ? hash_sum[d - 1][x] : 0);

そうしたら、「あるHash値(偶奇情報)になる最後のx位置」を保管する。2^10パターンしかないので、辞書よりも配列を使うと早い。

var dict = new int[1 << 10 + 1];
for (int i = 0; i < 1 << 10 + 1; i++) dict[i] = -1;
for (var x = 0; x < m; x++) dict[hash_line[x]] = x;

最後にxの左位置でループする(l)。各lに対し「すべての文字が偶数個になる」または「1文字だけ奇数になる」パターンを列挙し、それぞれの最後のx位置rをdict[]から探し出す。見つかったらこの四角形(u, l, d, r)で回文を作ることができる。

for (var l = 0; l < m; l++)
{
    // すべて偶数個
    candHashes[0] = l > 0 ? hash_line[l - 1] : 0;

    // １種類だけ奇数個
    for (int i = 0; i <= 9; i++)
        candHashes[i + 1] = hashTable[i] ^ (l > 0 ?  hash_line[l - 1] : 0);

    foreach (var candHash in candHashes)
    {
        r = dict[candHash];
        if (r == -1) continue;

        var newArea = (u - d + 1) * (r - l + 1);
        if (newArea <= maxArea) continue;   // もっと大きい面積の解がすでにある

        maxArea = newArea;
        ret = new Tuple<int, int, int, int, int>(maxArea, d, l, u, r);
    }
}

もう一つの条件「回文は前ゼロを含んではならない」は、四角形の面積に対し、ゼロが多すぎるか否かで判断できる。範囲内のゼロの数は、ゼロの累積和を作っておけば簡単に求めることができる。
以下は全コード。

public static Tuple<int, int, int, int, int> GetAns(int n, int m, List<List<int>> table)
{
    // nで二重ループするので、n>mのときは反転させる。Flip()の実装は省略
    var flipped = false;
    if (n > m)
    {
        table = Flip(table);
        var tmp = n;
        n = m;
        m = tmp;
        flipped = true;
    }

    var hashTable = Enumerable.Range(0, 10).Select(v => 1 << v).ToArray();
    var zero_num_sum = GetZeroNumSum(table);
    var hash_sum = GetHashSum(table, hashTable);

    // 返り値。面積, r1, c1, r2, c2
    var ret = new Tuple<int, int, int, int, int>(1, 0, 0, 0, 0);
    var maxArea = 1;

    var candHashes = new int[11];
    var zero_sum_line = new int[m];
    var hash_line = new int[m];
    int r;

    for (int d = 0; d < n; d++)
    {
        for (int u = d; u < n; u++)
        {
            for (var x = 0; x < m; x++)
                zero_sum_line[x] = zero_num_sum[u][x] - (d > 0 ? zero_num_sum[d - 1][x] : 0);

            for (var x = 0; x < m; x++)
                hash_line[x] = hash_sum[u][x] ^ (d > 0 ? hash_sum[d - 1][x] : 0);

            // あるHash値(偶奇情報)になる最後のx位置
            var dict = new int[1 << 10 + 1];
            for (int i = 0; i < 1 << 10 + 1; i++) dict[i] = -1;
            for (var x = 0; x < m; x++) dict[hash_line[x]] = x;

            for (var l = 0; l < m; l++)
            {
                // すべて偶数個
                candHashes[0] = l > 0 ? hash_line[l - 1] : 0;

                // １種類だけ奇数個
                for (int i = 0; i <= 9; i++)
                    candHashes[i + 1] = hashTable[i] ^ (l > 0 ?  hash_line[l - 1] : 0);

                foreach (var candHash in candHashes)
                {
                    r = dict[candHash];
                    if (r == -1) continue;

                    var newArea = (u - d + 1) * (r - l + 1);
                    if (newArea <= maxArea) continue;  // もっと大きい面積の解がすでにある

                    // ゼロの数を判定
                    var zeroNum = zero_sum_line[r] - (l > 0 ? zero_sum_line[l - 1] : 0);
                    if (newArea - zeroNum < 2) continue;

                    maxArea = newArea;
                    ret = new Tuple<int, int, int, int, int>(maxArea, d, l, u, r);
                }
            }
        }
    }

    if (flipped) Flip(ret);
    return ret;
}

public static List<List<int>> GetZeroNumSum(List<List<int>> table)
{
    var ret = new List<List<int>>();
    for (int i = 0; i < table.Count; i++)
    {
        var list = Enumerable.Range(0, table[0].Count).Select(v => 0).ToList();
        ret.Add(list);
    }

    for (int i = 0; i < table.Count; i++)
    {
        for (int j = 0; j < table[0].Count; j++)
        {
            if (i > 0) ret[i][j] = ret[i - 1][j];
            if (j > 0) ret[i][j] += ret[i][j - 1];
            if (i > 0 && j > 0) ret[i][j] -= ret[i - 1][j - 1];
            ret[i][j] += table[i][j] == 0 ? 1 : 0;
        }
    }

    return ret;
}

public static List<List<int>> GetHashSum(List<List<int>> table, int[] hashTable)
{
    var ret = new List<List<int>>();
    for (int i = 0; i < table.Count; i++)
    {
        var list = Enumerable.Range(0, table[0].Count).Select(v => 0).ToList();
        ret.Add(list);
    }

    for (int i = 0; i < table.Count; i++)
    {
        for (int j = 0; j < table[0].Count; j++)
        {
            if (i > 0) ret[i][j] = ret[i - 1][j];
            if (j > 0) ret[i][j] ^= ret[i][j - 1];
            if (i > 0 && j > 0) ret[i][j] ^= ret[i - 1][j - 1];
            ret[i][j] ^= hashTable[table[i][j]];
        }
    }

    return ret;
}

この問題が解けたのはうれしかった。あとは難易度Expertに手が出るようになれば…。

Bonnie and Clyde

ノード数nの無向グラフが与えられる。ノードu,v,wについて、u-wパスとv-wパスが存在するか答えよ。ただし、2つのパスは同じノードを共有できない。
1 <= n <= 10^5
1 <= m(エッジ数) <= min( n*(n-1)/2, 2*10^5 )
1 <= q(クエリ数) <= 10^5

ノードをVertex Biconnected Componentsに分解して、Block-Cut Treeを作ることで解くことができる。Block-Cut TreeはVertex Biconnected ComponentsおよびArticulation(元ノードのうち橋になっているもの)をノードにして作成された木。
基本的にはBlock-Cut Tree上でu-w-vのパス有無を判定するだけだが、wがArticulationの場合は追加判定が必要になる。

if (lca_uw == lca_vw)
{
    if (bicc.Articulations.Contains(orgW) && (bicc.Tree.DP[0][w] == lca_uv || bicc.Tree.DP[0][lca_uv] == w)) return "YES";
}
if (lca_vw == lca_uv)
{
    if (bicc.Articulations.Contains(orgW) && (bicc.Tree.DP[0][w] == lca_uw || bicc.Tree.DP[0][lca_uw] == w)) return "YES";
}
if (lca_uv == lca_uw)
{
    if (bicc.Articulations.Contains(orgW) && (bicc.Tree.DP[0][w] == lca_vw || bicc.Tree.DP[0][lca_vw] == w)) return "YES";
}

このように、u-LCA(u,v)-vを考えたとき、wのすぐ隣がこのLCA(u,v)ならOKになる。
また、与えられる木は連結とは限らないので、その判定も追加で必要。

public static List<string> GetAns(int n, int m, List<int[]> edges, List<int[]> queries)
{
    var bicc = new BICC_BlockCut(n);
    foreach (var edge in edges) bicc.AddEdge(edge[0] - 1, edge[1] - 1);
    bicc.Calc();
    bicc.BuildTree();

    return queries.Select(q => GetAns(n, bicc, q)).ToList();
}

public static string GetAns(int n, BICC_BlockCut bicc, int[] query)
{
    var u = query[0] - 1;
    var v = query[1] - 1;
    var w = query[2] - 1;

    var orgU = u;
    var orgV = v;
    var orgW = w;

    // same start pos but w is different
    if (u == v && u != w) return "NO";

    // already goaled
    if (u == w && v == w) return "YES";

    // same component
    if (bicc.InSameComp(u, v) && bicc.InSameComp(v, w) && bicc.InSameComp(u, w)) return "YES";

    u = bicc.NodeToComponentId[u];
    v = bicc.NodeToComponentId[v];
    w = bicc.NodeToComponentId[w];

    // should be in the same tree
    if (!bicc.Tree.InSameTree(u, v) || !bicc.Tree.InSameTree(v, w) || !bicc.Tree.InSameTree(u, w)) return "NO";

    if (bicc.Tree.Level[v] < bicc.Tree.Level[u])
    {
        var tmp = u;
        u = v;
        v = tmp;
    }

    var lca_vw = bicc.Tree.Lca(v, w);
    var lca_uv = bicc.Tree.Lca(u, v);
    var lca_uw = bicc.Tree.Lca(u, w);

    if (lca_uw == lca_vw)
    {
        if (bicc.Articulations.Contains(orgW) && (bicc.Tree.DP[0][w] == lca_uv || bicc.Tree.DP[0][lca_uv] == w)) return "YES";
    }
    if (lca_vw == lca_uv)
    {
        if (bicc.Articulations.Contains(orgW) && (bicc.Tree.DP[0][w] == lca_uw || bicc.Tree.DP[0][lca_uw] == w)) return "YES";
    }
    if (lca_uv == lca_uw)
    {
        if (bicc.Articulations.Contains(orgW) && (bicc.Tree.DP[0][w] == lca_vw || bicc.Tree.DP[0][lca_vw] == w)) return "YES";
    }

    return bicc.Tree.HasShortPath(u, v, w) ? "YES" : "NO";
}

public class BICC_BlockCut
{
    List<List<int>> _graph;
    int _n;

    // results
    public HashSet<int> Articulations;
    public List<List<Tuple<int, int>>> ComponentEdges;
    public List<HashSet<int>> ComponentNodes;
    public List<int> NodeToComponentId;

    // tree of BICC
    public Tree Tree;
    public List<int> SizeOfComponents;

    public BICC_BlockCut(int n)
    {
        _n = n;
        _graph = Enumerable.Range(0, n).Select(v => new List<int>()).ToList();
    }

    public void AddEdge(int s, int t)
    {
        _graph[s].Add(t);
        _graph[t].Add(s);
    }

    List<SortedSet<int>> _nodeToComponentIds;

    int T;
    int[] ord;
    int[] low;
    int[] depth;
    Stack<Tuple<int, int>> stack;

    public void Calc()
    {
        ComponentEdges = new List<List<Tuple<int, int>>>();

        low = Enumerable.Range(0, _n).Select(v => -1).ToArray();
        depth = Enumerable.Range(0, _n).Select(v => -1).ToArray();
        ord = Enumerable.Range(0, _n).Select(v => -1).ToArray();
        stack = new Stack<Tuple<int, int>>();

        for (int i = 0; i < _n; i++)
        {
            if (ord[i] == -1)
            {
                T = 0;
                Dfs(i);
            }
        }

        _nodeToComponentIds = Enumerable.Range(0, _n).Select(v => new SortedSet<int>()).ToList();
        ComponentNodes = new List<HashSet<int>>();

        for (int cId = 0; cId < ComponentEdges.Count(); cId++)
        {
            var edges = ComponentEdges[cId];
            var hash = new HashSet<int>();
            foreach (var e in edges)
            {
                hash.Add(e.Item1);
                hash.Add(e.Item2);
                _nodeToComponentIds[e.Item1].Add(cId);
                _nodeToComponentIds[e.Item2].Add(cId);
            }
            ComponentNodes.Add(hash);
        }
    }

    void Dfs(int i)
    {
        low[i] = ord[i] = T++;
        for (int j = 0; j < _graph[i].Count(); j++)
        {
            var to = _graph[i][j];
            if (ord[to] == -1)
            {
                depth[to] = depth[i] + 1;
                stack.Push(new Tuple<int, int>(i, to));
                Dfs(to);
                low[i] = Math.Min(low[i], low[to]);
                if (ord[i] == 0 || low[to] >= ord[i])
                {
                    var edges = new List<Tuple<int, int>>();
                    while (true)
                    {
                        if (IsEq(stack.Peek(), i, to)) break;
                        edges.Add(stack.Pop());
                    }
                    edges.Add(stack.Pop());
                    ComponentEdges.Add(edges);
                }
            }
            else if(depth[to] < depth[i] - 1)
            {
                low[i] = Math.Min(low[i], ord[to]);
                stack.Push(new Tuple<int, int>(i, to));
            }
        }
    }

    bool IsEq(Tuple<int, int> edge, int u, int v)
    {
        return (edge.Item1 == u && edge.Item2 == v) || (edge.Item1 == v && edge.Item2 == u);
    }

    // need to run Calc() first
    public void BuildTree()
    {
        var tuple = GetTreeGraph();
        Tree = new Tree(ComponentNodes.Count() + _n, tuple.Item1.Select(v => v.ToList()).ToList(), tuple.Item2);
    }

    Tuple<List<HashSet<int>>, HashSet<int>> GetTreeGraph()
    {
        Articulations = new HashSet<int>();

        var C = ComponentNodes.Count();
        SizeOfComponents = Enumerable.Range(0, C + _n).Select(v => 0).ToList();

        var graph = Enumerable.Range(0, C + _n).Select(v => new HashSet<int>()).ToList();
        NodeToComponentId = Enumerable.Range(0, C + _n).Select(v => -1).ToList();
        var extra = Enumerable.Range(0, C + _n).Select(v => -1).ToList();

        for (int i = 0; i < _nodeToComponentIds.Count(); i++)
        {
            var tmpv = _nodeToComponentIds[i];

            if (_graph[i].Count() == 0)  // isolated
            {
                NodeToComponentId[i] = C + i;
                extra[C + i] = 0;
                SizeOfComponents[C + i] = 1;
            }
            else if (tmpv.Count() == 1) // in single comp
            {
                NodeToComponentId[i] = tmpv.First();
                extra[tmpv.First()] = 0;
                SizeOfComponents[tmpv.First()]++;
            }
            else // articulation vertex
            {
                Articulations.Add(i);

                NodeToComponentId[i] = C + i;
                extra[C + i] = 0;
                SizeOfComponents[C + i]++;
                foreach (var j in tmpv)
                {
                    extra[j] = 0;
                    SizeOfComponents[j]++;
                    graph[C + i].Add(j);
                    graph[j].Add(C + i);
                }
            }
        }

        var extraHash = new HashSet<int>();
        for (int i = 0; i < extra.Count(); i++)
        {
            if (extra[i] == -1) extraHash.Add(i);
        }

        return new Tuple<List<HashSet<int>>, HashSet<int>>(graph, extraHash);
    }

    public bool InSameComp(int u, int v)
    {
        return _nodeToComponentIds[u].Intersect(_nodeToComponentIds[v]).Count() > 0;
    }
}

// basic tree with Lca() and Asc()
public class Tree
{
    public int[] Level;

    int LOGN = 20;
    public int[][] DP;

    int _n;
    List<List<int>> _graph;
    HashSet<int> _ignoreNodes;

    public Tree(int n)
    {
        Init(n);

        _graph = Enumerable.Range(0, n).Select(v => new List<int>()).ToList();
        _ignoreNodes = new HashSet<int>();
    }

    public Tree(int n, List<List<int>> graph, HashSet<int> ignoreNodes)
    {
        Init(n);

        _graph = graph;
        _ignoreNodes = ignoreNodes;
        Calc();
    }

    void Init(int n)
    {
        _n = n;
        Level = new int[n];
        DP = Enumerable.Range(0, LOGN).Select(v => Enumerable.Range(0, n).Select(w => 0).ToArray()).ToArray();
    }

    public void AddEdge(int s, int t)
    {
        _graph[s].Add(t);
        _graph[t].Add(s);
    }

    // working for calc()
    int[] arr;
    int currComp;
    int[] dep;
    int[] vis;
    int T;

    public void Calc()
    {
        arr = new int[_n];
        currComp = 0;
        dep = new int[_n];
        vis = new int[_n];
        T = 0;

        for (int i = 0; i < _n; i++)
        {
            if (vis[i] == 0 && !_ignoreNodes.Contains(i))
            {
                currComp++;
                Dfs(i, i);
            }
        }

        for (int i = 1; i < LOGN; i++)
        {
            for (int j = 0; j < _n; j++)
            {
                if (!_ignoreNodes.Contains(j))
                {
                    DP[i][j] = DP[i - 1][DP[i - 1][j]];
                }
            }
        }
    }

    void Dfs(int u, int p)
    {
        if (vis[u] != 0) return;

        Level[u] = Level[p] + 1;
        DP[0][u] = p;
        arr[u] = ++T; 
        vis[u] = currComp;
        foreach (var w in _graph[u])
            if (w != p)
                Dfs(w, u);
        dep[u] = T++;
    }

    public bool InSameTree(int a, int b)
    {
        return vis[a] == vis[b];
    }

    public int Lca(int a, int b)
    {
        if (Level[a] > Level[b])
        {
            var tmp = a;
            a = b;
            b = tmp;
        }
        int d = Level[b] - Level[a];

        for (int i = 0; i < LOGN; i++)
        {
            if (((1 << i) & d) != 0) b = DP[i][b];
        }

        if (a == b) return a;

        for (int i = LOGN - 1; i >= 0; i--)
        {
            if (DP[i][a] != DP[i][b])
            {
                a = DP[i][a];
                b = DP[i][b];
            }
        }

        return DP[0][a];
    }

    // p is Anc of u
    public bool Anc(int p, int u)
    {
        return (arr[u] >= arr[p] && dep[u] <= dep[p]);
    }

    // has short path: u - w - v
    public bool HasShortPath(int u, int v, int w)
    {
        if (!InSameTree(u, v) || !InSameTree(v, w)) return false;

        if (Level[u] > Level[v])
        {
            var tmp = v;
            v = u;
            u = tmp;
        }

        int LCA = Lca(u, v);
        bool ok = false;
        ok |= Anc(w, u);
        ok |= Anc(w, v);
        ok &= Anc(LCA, w);
        return ok;
    }
}

ずいぶんと解けそうで解けず苦しんだ。。。