Codechef May Challenge 2017 参加日記

アルゴリズム プログラミングコンテスト

CodechefのLong Challengeに初参加した。221位/7492人

Chef and his daily routine

Chefの一日は必ず、料理・食事・睡眠の順番である。１日の行動ログが料理'C'、食事'E'、睡眠'S'の形式で与えられたとき、これが有効かどうかを答えよ。
1 <= N（ログの長さ）<= 10^5

C・E・Sの順番になっているかチェックすればよい。ただし、Cが無いなど抜けている場合もOKになる。

public static string GetAns(string s)
{
    var vals = "CES";
    var idx = 0;

    for (int i = 0; i < vals.Length; i++)
    {
        while (idx < s.Length && s[idx] == vals[i]) idx++;
    }

    return idx == s.Length ? "yes" : "no";
}


Courses in an university

大学のコースがN個あり、難易度順に昇順で並んでる。各コースは難易度のより低いコースを履修要件としてもつことがある。配列a[i]は、コースiが必要とする履修要件コースの数である。このとき、他コースの履修要件となっていないコースの数を最大にしたい。この数を答えよ。
1 <= N <= 10^5
0 <= a[i] <= i

各コースごと、なるべく難易度の低いコースを必要数だけ要件に割り当てればよい。

public static int GetAns(int n, int[] a)
{
    var ret = a.Length;
    for (int i = 1; i < a.Length; i++)
    {
        ret = Math.Min(ret, a.Length - a[i]);
    }
    return ret;
}


Median of adjacent maximum numbers

長さ2N(Nは奇数)の整数列Aが与えられる。配列Bを、B[i] = Max(A[2 * i - 1], A[2 * i]) としたとき、Bの中央値が最大になるようにAを並び替えよ。その中央値とAを解答すること。
1 <= N <= 50000
1 <= A[i] <= 2*N

Aをソートし、上位1/4をBに割り当てる。

public static Tuple<int, int[]> GetAns(int n, int[] a)
{
    var ret = a;
    var sorted = a.OrderBy(v => v).ToArray();

    for (int i = 0; i < a.Length / 2; i++) ret[i * 2] = sorted[i];
    for (int i = 0; i < a.Length / 2; i++) ret[i * 2 + 1] = sorted[i + a.Length / 2];

    return new Tuple<int, int[]>(ret[a.Length / 2], ret);
}


Chef and Sub Array

長さNのBinary配列Aがあるとき、次の２種類のクエリに対応せよ。
・Aを右に1シフト
・連続したK要素内における1の数の最大値を出力
1 <= N, K, P <= 10^5 (Pはクエリ数)

配列sumsを
　sums[i] = A[i:i+K]の1の数
とすると、シフトが無いと仮定したとき解は
　Max(sums[k]) k: 0~N-k
になる。これは範囲内の最大値を求めているだけなので、セグメント木を使えばO(logN)で求められる。
そして、現在のA配列の始まる位置を管理していけば(Aが右シフトするたび-1を加算)、実際に求めるsums上の範囲が計算できる。

public static List<int> GetAns(int n, int k, int p, int[] a, string req)
{
    var sums = new int[a.Length];   //sums from current to current + k
    var wk = a.Concat(a).ToArray();

    k = Math.Min(k, a.Length);

    var sum = 0;
    for (int i = 0; i < wk.Length && i < a.Length + k; i++)
    {
        if (i >= k)
        {
            sums[i - k] = sum;
        }
        sum += wk[i];
        if (i >= k)
        {
            sum -= wk[i - k];
        }
    }

    var ret = new List<int>();

    var seg = new SegTree_max();
    seg.Init(sums.Length);
    for (int i = 0; i < sums.Length; i++) seg.Update(i, sums[i]);

    var limit = a.Length;
    foreach (var r in req)
    {
        if (r == '!') { limit--; if (limit == 0) limit = a.Length; }
        else
        {
            var maxVal = 0;

            // max from [0, limit - k]
//                    for (int i = 0; i <= limit - k ; i++) maxVal = Math.Max(maxVal, sums[i]);
            maxVal = Math.Max(maxVal, seg.Query(0, limit - k + 1));

            // max from [limit, Math.Min(a.Length - 1, a.Length + limit - k)]
//                    for (int i = limit; i <= Math.Min(a.Length - 1, a.Length + limit - k); i++) maxVal = Math.Max(maxVal, sums[i]);
            maxVal = Math.Max(maxVal, seg.Query(limit, Math.Min(a.Length, a.Length + limit - k + 1)));
            
            ret.Add(maxVal);
        }
    }

    return ret;
}

public class SegTree_max
{
    const int MAX_N = 1 << 17;
    int _n;
    int[] _dat = new int[2 * MAX_N - 1];

    public void Init(int n)
    {
        _n = 1;
        while (_n < n) _n *= 2;
        for (int i = 0; i < 2 * _n - 1; i++) _dat[i] = 0;
    }

    public void Update(int k, int a)
    {
        k += _n - 1;
        _dat[k] = a;
        while (k > 0)
        {
            k = (k - 1) / 2;
            _dat[k] = Math.Max(_dat[k * 2 + 1], _dat[k * 2 + 2]);
        }
    }

    public int Query(int a, int b)
    {
        return Query(a, b, 0, 0, _n);
    }

    int Query(int a, int b, int k, int l, int r)
    {
        if (r <= a || b <= l) return 0;
        if (a <= l && r <= b) return _dat[k];
        else
        {
            var vl = Query(a, b, k * 2 + 1, l, (l + r) / 2);
            var vr = Query(a, b, k * 2 + 2, (l + r) / 2, r);
            return Math.Max(vl, vr);
        }
    }
}


Blocked websites

N個のウェブサイトについて、それぞれファイヤーウォールでブロックするべきか否かの情報が与えられる。これを元にファイヤーウォールにフィルタをいくつか設定したい。最小のフィルタ長の合計を求めよ。なおウェブサイトは、Prefixがフィルタのいずれかと一致した場合にブロックされる。不可能な場合は-1を返すこと。
サイト名は英小文字のみ
1 <= N <= 2*10^5
サイト長の合計は2*10^5以下
同じサイト名は存在しない

Trie木で管理すればよい。それぞれのノードに、フィルタ対象サイトの一部かどうか・フィルタ対象外の子があるか・フィルタ対象サイトの最終文字になってるか、などの情報を持つ。再帰でDFSを実装すれば楽だが、StackOverflowが怖かったのでBFSにした。
＊GetAns()に冗長なチェックがたくさんあるが、問題文だけだと省いてよいか曖昧だった

public static List<string> GetAns(List<string> toFilter, List<string> notFilter)
{
    if (toFilter.Contains(""))
    {
        if (notFilter.Count() > 0) return null;
        return new List<string> { "" };
    }

    if (notFilter.Contains("") && toFilter.Count() > 0) return null;

    // no two sites have same name
    var concat = toFilter.Concat(notFilter);
    if (concat.Count() != concat.Distinct().Count()) return null;

    // length should not exceed 
    if (concat.Sum(c => c.Length) > 200000) return null;

    var trie = new Trie();
    foreach (var f in toFilter) trie.AddString(f, true);
    foreach (var n in notFilter) trie.AddString(n, false);

    var ret = trie.GetAns();
    if (ret != null) ret.Sort();

    if (ret != null && ret.Sum(r => r.Length) > 200000) return null;

    return ret;
}

public class Trie
{
    public class Node
    {
        public Node Parent;
        public char CharToParent;

        // 'a' - 'z'
        public Node[] Children;

        public bool IsFilter;
        public bool HasNofilterChildren;
        public bool IsLastCharOfFilter;

        public Node(bool isFilter)
        {
            Children = new Node[26];
            IsFilter = isFilter;
        }

        public Node Add(char c, bool isFilter, bool isLastCharOfFilter)
        {
            if (Children[c - 'a'] == null) Children[c - 'a'] = new Node(isFilter);

            Children[c - 'a'].IsFilter |= isFilter;
            Children[c - 'a'].HasNofilterChildren |= !isFilter;
            Children[c - 'a'].IsLastCharOfFilter |= isLastCharOfFilter;


            Children[c - 'a'].Parent = this;
            Children[c - 'a'].CharToParent = c;

            return Children[c - 'a'];
        }

        public string GetString()
        {
            var ret = new StringBuilder();
            var cur = this;

            while (cur.Parent != null)
            {
                ret.Append(cur.CharToParent);
                cur = cur.Parent;
            }

            return new string(ret.ToString().Reverse().ToArray());
        }
    }

    Node _root = new Node(false);

    public void AddString(string str, bool isFilter)
    {
        var node = _root;
        for (var idx = 0; idx < str.Length; idx++)
        {
            node = node.Add(str[idx], isFilter, isFilter && idx == str.Length - 1);
        }
    }

    public List<string> GetAns()
    {
        var ret = new List<string>();
        var stack = new Stack<Node>();
        stack.Push(_root);

        while (stack.Count() > 0)
        {
            var node = stack.Pop();

            if (node.IsFilter && !node.HasNofilterChildren && node != _root)
            {
                ret.Add(node.GetString());
                continue;
            }

            if (node.IsFilter && node.Children.All(c => c == null ? true : !c.IsFilter))
            {
                return null;
            }

            if (node.IsLastCharOfFilter && node.Children.Any(c => c == null ? false : c.HasNofilterChildren))
            {
                return null;
            }

            for (int i = 0; i < 26; i++)
            {
                if (node.Children[i] != null)
                {
                    stack.Push(node.Children[i]);
                }
            }
        }

        return ret;
    }
}


Chef and Subsequences

要素数Nの整数列Aから、積がKを超えないサブシーケンスの組み合わせ数を答えよ。
1 <= N <= 30
1 <= K, A[i] <= 10^18

半分全列挙。Aの上半分とtop、下半分をbottomとする。まずbottomの全組み合わせについて積を求め、bottomValues[]に保管する。このときKを超える分はカウントしておく。次にtopの全組み合わせについて積を求め、BottomValuesから閾値を超える分(掛けるとKを超える値)の個数をカウントする（LowerBound()を使えばよい）。そして全組み合わせ数からカウント分を引けば答えとなる。

public static long GetAns(long k, long[] a)
{
    if (a.Length == 1) return a[0] <= k ? 1 : 0;

    var top = a.Take(a.Length / 2).ToArray();
    var bottom = a.Skip(a.Length / 2).ToArray();

    var bottomValues = new List<long>();
    for (int mask = 1; mask < 1 << bottom.Length; mask++)
    {
        long cur = 1;
        for (int i = 0; i < a.Length; i++)
        {
            if (((mask >> i) & 1) == 1) cur = Mux(cur, bottom[i]);
            if (cur > k) break;
        }
        bottomValues.Add(cur);
    }
    bottomValues.Sort();

    long ret = 0;
    ret += (bottomValues.Count() - LowerBound(bottomValues, k + 1));

    for (int mask = 1; mask < 1 << top.Length; mask++)
    {
        long cur = 1;
        for (int i = 0; i < a.Length; i++)
        {
            if (((mask >> i) & 1) == 1) cur = Mux(cur, top[i]);
            if (cur > k) break;
        }

        if (cur > k)
        {
            ret++;
            ret += bottomValues.Count();
        }
        else
        {
            long thres = k % cur == 0 ? k / cur + 1 : (long)Math.Ceiling((double)k / (double)cur);
            ret += (bottomValues.Count() - LowerBound(bottomValues, thres));
        }
    }

    return ((1 << a.Length) - 1) - ret;
}

static long Mux(long v1, long v2)
{
    try {  return checked(v1 * v2); }
    catch { return long.MaxValue; }
}

static int LowerBound(List<long> ar, long val)
{
    var lb = -1;
    var ub = ar.Count();
    while (ub - lb > 1)
    {
        var mid = (lb + ub) / 2;
        if (ar[mid] >= val)
            ub = mid;
        else
            lb = mid;
    }
    return ub;
}


Gotham PD

根をRとするノード数Nのツリーを考える。各ノードはそれぞれIDと暗号キーを持っている。このとき、次の２つのタイプのクエリがQ個与えられたときの結果を答えよ。
0 v u k：暗号キーkをもつノードuをノードvにつなげて追加する
1 v k：値aとbを出力する。aはノードvからRまでのパス上に存在するノードのうちでXOR(a, k)が最小になるもので、bはXOR(a, k)が最大になるもの
1 <= N <= 100,000
1 <= Q <= 200,000
1 <= R, u[i], v[i], key, k[i] <= 2^31 - 1
すべてのIDは一意
ノードuをノードvに追加するとき、ノードvからRまでのパスがすでに存在する。
※実際の問題では、標準入出力のやり取りにややこしいルールがあったが、省略する。

「ノードuをノードvに追加するとき、ノードvからRまでのパスがすでに存在する」ので、ルートRからあるノードまでのパスは、一度作成されると変わることが無い。この固定されたパス上の値をk[]とすると
・XOR(k[i], Key)が最大(最小)になるKeyを探せ
という部分問題になり、これは0と1で作るTrie木を作っておけば効率的に求めることができる。
あとは元のツリーを平方分割し、ある深さごとのノードに範囲内を管理するTrie木を作成しておけば良い。
(下のコードは深さ11000ごとに無条件でTrie木を作成してるが、遅延評価にすればもっと効率が良いはず)

static void Main(string[] args)
{
    var s = Console.ReadLine().Split().Select(v => Int32.Parse(v)).ToArray();
    var n = s[0];
    var q = s[1];
    s = Console.ReadLine().Split().Select(v => Int32.Parse(v)).ToArray();
    var r = s[0];
    var key = s[1];

    var graph = new Graph();
    graph.AddNode(r, key, -1);

    for (int i = 0; i < n - 1; i++)
    {
        s = Console.ReadLine().Split().Select(val => Int32.Parse(val)).ToArray();
        var u = s[0];
        var v = s[1];
        var k = s[2];
        graph.AddNode(u, k, v);
    }

    var last_ans = 0;
    for (int i = 0; i < q; i++)
    {
        s = Console.ReadLine().Split().Select(val => Int32.Parse(val)).ToArray();
        var t = s[0] ^ last_ans;

        if (t == 0)
        {
            var v = s[1] ^ last_ans;
            var u = s[2] ^ last_ans;
            var k = s[3] ^ last_ans;
            graph.AddNode(u, k, v);
        }
        else
        {
            var v = s[1] ^ last_ans;
            var k = s[2] ^ last_ans;

            var ans = graph.GetAns(v, k);
            var min_ans = ans.Item1;
            var max_ans = ans.Item2;

            Console.WriteLine(min_ans + " " + max_ans);

            last_ans = min_ans ^ max_ans;
        }
    }
}

public class Graph
{
    public static int TRIE_THRES = 11000; 

    Node _rootNode;
    Dictionary<int, Node> _nodeDict = new Dictionary<int, Node>();

    class Node
    {
        public int Key;
        public Node Parent;

        public int Depth;

        public Trie Trie;

        public Node ParentTrieNode;

        public Node(int key, Node parent, int depth)
        {
            Key = key;
            Parent = parent;

            Depth = depth;

            if (depth != 0 && (depth % Graph.TRIE_THRES) == 0)
            {
                Trie = GetTrie();
            }
        }

        Trie GetTrie()
        {
            var ret = new Trie();
            var current = this;

            while (current != null && current.Trie == null)
            {
                ret.AddNode(current.Key);
                current = current.Parent;
            }
            this.ParentTrieNode = current;

            return ret;
        }

        public Tuple<int, int> GetAns(int key)
        {
            var minVal = Int32.MaxValue;
            var maxVal = -1;
            var current = this;

            while (current != null)
            {
                if (current.Trie == null)
                {
                    minVal = Math.Min(minVal, current.Key ^ key);
                    maxVal = Math.Max(maxVal, current.Key ^ key);
                    current = current.Parent;
                }
                else
                {
                    minVal = Math.Min(minVal, current.Trie.GetMin(key));
                    maxVal = Math.Max(maxVal, current.Trie.GetMax(key));
                    current = current.ParentTrieNode;
                }
            }

            return new Tuple<int, int>(minVal, maxVal);
        }
    }

    public void AddNode(int id, int key, int parentId)
    {
        if (parentId == -1)
        {
            _rootNode = new Node(key, null, 0);
            _nodeDict.Add(id, _rootNode);
        }
        else
        {
            var parent = _nodeDict[parentId];
            var node = new Node(key, parent, parent.Depth + 1);
            _nodeDict.Add(id, node);
        }
    }

    public Tuple<int, int> GetAns(int id, int key)
    {
        return _nodeDict[id].GetAns(key);
    }
}

public class Trie
{
    Node _rootNode = new Node(null);

    class Node
    {
        public int Key; // only last node has it

        public Node Parent;
        public Node ZeroNode;
        public Node OneNode;

        public Node(Node parent)
        {
            Parent = parent;
        }

        public Node AddNode(int val)
        {
            if (val == 0)
            {
                if (ZeroNode == null) ZeroNode = new Node(this);
                return ZeroNode;
            }
            else
            {
                if (OneNode == null) OneNode = new Node(this);
                return OneNode;
            }
        }
    }

    public void AddNode(int key)
    {
        var currentTrieNode = _rootNode;
        for (int i = 30; i >= 0; i--)
        {
            currentTrieNode = currentTrieNode.AddNode((key >> i) & 1);
        }
        currentTrieNode.Key = key;
    }

    public int GetMin(int key)
    {
        return GetMinMax(true, key);
    }

    public int GetMax(int key)
    {
        return GetMinMax(false, key);
    }

    int GetMinMax(bool isMin, int key)
    {
        var curNode = _rootNode;
        for (int i = 30; i >= 0; i--)
        {
            var val = (key >> i) & 1;

            if (!isMin)
            {
                // max
                if (val == 1 && curNode.ZeroNode != null)
                {
                    curNode = curNode.ZeroNode;
                }
                else if (val == 0 && curNode.OneNode != null)
                {
                    curNode = curNode.OneNode;
                }
                else if (curNode.ZeroNode != null)
                {
                    curNode = curNode.ZeroNode;
                }
                else
                {
                    curNode = curNode.OneNode;
                }
            }
            else
            {
                // min
                if (val == 1 && curNode.OneNode != null)
                {
                    curNode = curNode.OneNode;
                }
                else if (val == 0 && curNode.ZeroNode != null)
                {
                    curNode = curNode.ZeroNode;
                }
                else if (curNode.OneNode != null)
                {
                    curNode = curNode.OneNode;
                }
                else
                {
                    curNode = curNode.ZeroNode;
                }
            }
        }

        return curNode.Key ^ key;
    }
}


Long Sandwich

長さNのサンドイッチがある。これを長さ1~Kのいくつかのサンドイッチに切る方法はいくつあるか。ただし、サンドイッチの数はなるべく少なくしたい。サンドイッチの数と、切る方法の数（MでModをとること）を答えよ。
1 <= N <= 10^18
1 <= K <= 10^18
2 <= M <= 10^6

詳しくはここにあるが、nCr Mod xの問題に帰結することができる。
May Long Contest Editorial – codedecode0111 – Medium
ただし、xは素数とは限らないのがこの問いの難しいところ。よくわからないので保留（放置）・・・。
http://m00nlight.github.io/algorithm/2015/04/11/hackerrank-ncr
http://hamayanhamayan.hatenablog.jp/entry/2017/05/26/123020



Chef and Battleship

Sea Battleという以下のゲームをプレーするAIを作成せよ。サーバー側のAIが対戦相手となる。
・敵、味方それぞれに10x10のボードがある
・駒の種類と数は、サイズ1x4のサブマリン1個、サイズ1x3のデストロイヤー2個、サイズ1x2のクルーザー3個、サイズ1x2のバトルシップ4個
・駒の配置は任意に作成できる。ただし、駒どおしは隣り合ってはならない（斜めも含む）
・ターン制のゲーム
・相手ボードは見えない
・相手のボードの好きなセルを爆撃できる。このとき、当たらなかった・当たった・当たって撃墜した、の情報が知らされる
・当たった場合は連続で爆撃できる
・船のあるセルすべてに当たれば撃墜
・先にすべての船を撃墜したほうが勝ち
・先手はプレーヤー
サーバーAIはランダムに空白セルを爆撃する。このとき、当たったら上下左右いずれかの隣を続けて爆撃する。また、空白セルでも船が無いと分かっているセルは無視する（すでに爆撃をトライした、残りの船がサイズ的に収まらない、撃墜した船に隣り合っている）。

サーバーAIとほぼ同じだが、追加で
・初期配置はなるべく隅に寄せる
・なるべく連続する空白セルの中央を打つ
・当たった後の追撃は、盤の中央に近いもの、また連続する空白セルがあるものを優先
の処理を入れた。
これでだいたい平均的なスコアだった。上位者はもっと細かくセルごとに船の存在確率を計算しているようだった。
※実装は省略