2017-02-10

イントロソートを安定ソートとして習作(C#)

C#で安定ソートを行うときはLinqのOrderBy()が一般的だが、OrderByはクイックソートなのでワースト計算量がO(N^2)になってしまう。ここでは、これを回避したソートを習作してみる。

ちなみにC++のstable_sort()だと、安定マージソートをつかってこの問題を回避している。配列を再帰的に分割していき、長さが閾値(15)未満になったら挿入ソートに切り替えるようだ。
https://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USERS-4.4/a01347.html#l03409

これをそのまま移植してもOKなのだが、それでは面白くないので、ここではArray.Sort()のイントロソートを強引に安定化することにする。イントロソートは最初はクイックソートを行い、再帰のレベルがある値を超えたらヒープソートに切り替えるといもので、高速なクイックソートの利点を利用しつつ最悪ケースを回避するアルゴリズムだ。基本的にはこの２つのソートを安定版に作り替えればよい。

以下のMS実装を参考にした。

イントロソート（Array.Sort())
https://referencesource.microsoft.com/#mscorlib/system/array.cs,2a2126edd9ca7eb4
クイックソート（Linq）
https://referencesource.microsoft.com/#System.Core/System/Linq/Enumerable.cs,1395017e067e5a34

static public void StableSort<T>(List<T> list) where T : IComparable
{
    int[] map = new int[list.Count()];
    for (int i = 0; i < list.Count(); i++) map[i] = i;
    StableSort(list, map, 0, list.Count() - 1, (int)Math.Floor(Math.Log(list.Count(), 2)) * 2);

    var tmp = list.ToArray();
    for (int i = 0; i < list.Count(); i++)
    {
        list[i] = tmp[map[i]];
    }
}

static void StableSort<T>(List<T> list, int[] map, int left, int right, int depthLimit) where T : IComparable
{
    if (left >= right) return;

    //stable heap sort
    if (depthLimit == 0)
    {
        StableSort_HeapSort(list, map, left, right);
        return;
    }

    //stable quick sort
    do
    {
        int i = left;
        int j = right;
        int x = map[i + ((j - i) >> 1)];
        do
        {
            while (i < list.Count() && CompareKeys(list, x, map[i]) > 0) i++;
            while (j >= 0 && CompareKeys(list, x, map[j]) < 0) j--;
            if (i > j) break;
            if (i < j)
            {
                int temp = map[i];
                map[i] = map[j];
                map[j] = temp;
            }
            i++;
            j--;
        } while (i <= j);
        if (j - left <= right - i)
        {
            if (left < j) StableSort(list, map, left, j, depthLimit - 1);
            left = i;
        }
        else
        {
            if (i < right) StableSort(list, map, i, right, depthLimit - 1);
            right = j;
        }
    } while (left < right);
}

static void StableSort_HeapSort<T>(List<T> list, int[] map, int lo, int hi) where T : IComparable
{
    int n = hi - lo + 1;
    for (int i = n / 2; i >= 1; i = i - 1)
    {
        StableSort_HeapSort_DownHeap(list, map, i, n, lo);
    }
    for (int i = n; i > 1; i = i - 1)
    {
        Swap(map, lo, lo + i - 1);
        StableSort_HeapSort_DownHeap(list, map, 1, i - 1, lo);
    }
}

static void StableSort_HeapSort_DownHeap<T>(List<T> list, int[] map, int i, int n, int lo) where T : IComparable
{
    int d = map[lo + i - 1];
    int child;
    while (i <= n / 2)
    {
        child = 2 * i;
        if (child < n && CompareKeys(list, map[lo + child - 1], map[lo + child]) < 0)
        {
            child++;
        }
        if (!(CompareKeys(list, d, map[lo + child - 1]) < 0))
            break;
        map[lo + i - 1] = map[lo + child - 1];
        i = child;
    }
    map[lo + i - 1] = d;
}

static void Swap(int[] map, int i, int j)
{
    var tmp = map[i];
    map[i] = map[j];
    map[j] = tmp;
}

static int CompareKeys<T>(List<T> list, int index1, int index2) where T : IComparable
{
    var c = list[index1].CompareTo(list[index2]);
    if (c == 0)
    {
        return index1 - index2;
    }
    return c;
}

当然、ほとんどの場合でOrderByのほうが少し速い。ワーストケースではこちらのほうが大幅に良いパフォーマンスが出るはず・・・だがうまくテストケースを作れなかった。

2017-02-07

平衡二分探索木を使ったsetとmultisetの実装（C#）

C# アルゴリズム

C++のsetとmultisetに相当するコレクションをC#で実装してみる。

set
順序付けされたデータを重複を排除して保持するもの。C#のSortedSetとほぼ同じだが、lower_bound()とupper_bound()が使える。データの追加・削除・検索いずれもO(logN)。

multiset
順序付けされたデータを重複を許容しながら保持するもの。C#に類似のものはない。setと同じく、lower_bound()とupper_bound()がある。データの追加・削除・検索いずれもO(logN)。

lower_bound()は該当値以上になる最小Indexを、upper_bound()は該当値より大きくなる最小Indexを返す関数で、いずれもO(logN)になる。

どちらも平衡二分探索木で実現できる。平衡二分探索木は二分探索木を、木構造がなるべく偏らないように工夫したものである（偏ると効率が悪くなる＝O(N)に近くなる）。ここではRandomized Binary Search Tree(RBST)と呼ばれる、値を追加するときに、なるべく木の高さの偏りがなくなるよう、追加候補の位置に重みづけをしてランダム選択する方法で実装してみる。

詳細はこちらが参考になった
プログラミングコンテストでのデータ構造 2 ～平衡二分探索木編～

/// <summary>
/// Self-Balancing Binary Search Tree
/// (using Randamized BST)
/// </summary>
public class SB_BinarySearchTree<T> where T : IComparable
{
    public class Node
    {
        public T Value;
        public Node LChild;
        public Node RChild;
        public int Count;     //size of the sub tree

        public Node(T v)
        {
            Value = v;
            Count = 1;
        }
    }

    static Random _rnd = new Random();

    public static int Count(Node t)
    {
        return t == null ? 0 : t.Count;
    }

    static Node Update(Node t)
    {
        t.Count = Count(t.LChild) + Count(t.RChild) + 1;
        return t;
    }

    public static Node Merge(Node l, Node r)
    {
        if (l == null || r == null) return l == null ? r : l;

        if ((double)Count(l) / (double)(Count(l) + Count(r)) > _rnd.NextDouble())
        {
            l.RChild = Merge(l.RChild, r);
            return Update(l);
        }
        else
        {
            r.LChild = Merge(l, r.LChild);
            return Update(r);
        }
    }

    /// <summary>
    /// split as [0, k), [k, n)
    /// </summary>
    public static Tuple<Node, Node> Split(Node t, int k)
    {
        if (t == null) return new Tuple<Node, Node>(null, null);
        if (k <= Count(t.LChild))
        {
            var s = Split(t.LChild, k);
            t.LChild = s.Item2;
            return new Tuple<Node, Node>(s.Item1, Update(t));
        }
        else
        {
            var s = Split(t.RChild, k - Count(t.LChild) - 1);
            t.RChild = s.Item1;
            return new Tuple<Node, Node>(Update(t), s.Item2);
        }
    }

    public static Node Remove(Node t, T v)
    {
        if (Find(t, v) == null) return t;
        return RemoveAt(t, LowerBound(t, v));
    }

    public static Node RemoveAt(Node t, int k)
    {
        var s = Split(t, k);
        var s2 = Split(s.Item2, 1);
        return Merge(s.Item1, s2.Item2);
    }

    public static bool Contains(Node t, T v)
    {
        return Find(t, v) != null;
    }

    public static Node Find(Node t, T v)
    {
        while (t != null)
        {
            var cmp = t.Value.CompareTo(v);
            if (cmp > 0) t = t.LChild;
            else if (cmp < 0) t = t.RChild;
            else break;
        }
        return t;
    }

    public static Node FindByIndex(Node t, int idx)
    {
        if (t == null) return null;

        var currentIdx = Count(t) - Count(t.RChild) - 1;
        while (t != null)
        {
            if (currentIdx == idx) return t;
            if (currentIdx > idx)
            {
                t = t.LChild;
                currentIdx -= (Count(t == null ? null : t.RChild) + 1);
            }
            else
            {
                t = t.RChild;
                currentIdx += (Count(t == null ? null : t.LChild) + 1);
            }
        }

        return null;
    }

    public static int UpperBound(Node t, T v)
    {
        var torg = t;
        if (t == null) return -1;

        var ret = Int32.MaxValue;
        var idx = Count(t) - Count(t.RChild) - 1;
        while (t != null)
        {
            var cmp = t.Value.CompareTo(v);
                
            if (cmp > 0)
            {
                ret = Math.Min(ret, idx);
                t = t.LChild;
                idx -= (Count(t == null ? null : t.RChild) + 1);
            }
            else if (cmp <= 0)
            {
                t = t.RChild;
                idx += (Count(t == null ? null : t.LChild) + 1);
            }
        }
        return ret == Int32.MaxValue ? Count(torg) : ret;
    }

    public static int LowerBound(Node t, T v)
    {
        var torg = t;
        if (t == null) return -1;

        var idx = Count(t) - Count(t.RChild) - 1;
        var ret = Int32.MaxValue;
        while (t != null)
        {
            var cmp = t.Value.CompareTo(v);
            if (cmp >= 0)
            {
                if (cmp == 0) ret = Math.Min(ret, idx);
                t = t.LChild;
                if (t == null) ret = Math.Min(ret, idx);
                idx -= t == null ? 0 : (Count(t.RChild) + 1);
            }
            else if (cmp < 0)
            {
                t = t.RChild;
                idx += (Count(t == null ? null : t.LChild) + 1);
                if (t == null) return idx;
            }
        }
        return ret == Int32.MaxValue ? Count(torg) : ret;
    }

    public static Node Insert(Node t, T v)
    {
        var ub = LowerBound(t, v);
        return InsertByIdx(t, ub, v);
    }

    static Node InsertByIdx(Node t, int k, T v)
    {
        var s = Split(t, k);
        return Merge(Merge(s.Item1, new Node(v)), s.Item2);
    }

    public static IEnumerable<T> Enumerate(Node t)
    {
        var ret = new List<T>();
        Enumerate(t, ret);
        return ret;
    }

    static void Enumerate(Node t, List<T> ret)
    {
        if (t == null) return;
        Enumerate(t.LChild, ret);
        ret.Add(t.Value);
        Enumerate(t.RChild, ret);
    }
}

平衡二分探索木ができてしまえば、setは簡単に作ることができる。

/// <summary>
/// C-like set
/// </summary>
public class Set<T> where T : IComparable
{
    protected SB_BinarySearchTree<T>.Node _root;

    public T this[int idx]{ get { return ElementAt(idx); } }

    public int Count()
    {
        return SB_BinarySearchTree<T>.Count(_root);
    }

    public virtual void Insert(T v)
    {
        if (_root == null) _root = new SB_BinarySearchTree<T>.Node(v);
        else
        {
            if (SB_BinarySearchTree<T>.Find(_root, v) != null) return;
            _root = SB_BinarySearchTree<T>.Insert(_root, v);
        }
    }

    public void Clear()
    {
        _root = null;
    }

    public void Remove(T v)
    {
        _root = SB_BinarySearchTree<T>.Remove(_root, v);
    }

    public bool Contains(T v)
    {
        return SB_BinarySearchTree<T>.Contains(_root, v);
    }

    public T ElementAt(int k)
    {
        var node = SB_BinarySearchTree<T>.FindByIndex(_root, k);
        if (node == null) throw new IndexOutOfRangeException();
        return node.Value;
    }

    public int Count(T v)
    {
        return SB_BinarySearchTree<T>.UpperBound(_root, v) - SB_BinarySearchTree<T>.LowerBound(_root, v);
    }

    public int LowerBound(T v)
    {
        return SB_BinarySearchTree<T>.LowerBound(_root, v);
    }

    public int UpperBound(T v)
    {
        return SB_BinarySearchTree<T>.UpperBound(_root, v);
    }

    public Tuple<int, int> EqualRange(T v)
    {
        if (!Contains(v)) return new Tuple<int, int>(-1, -1);
        return new Tuple<int, int>(SB_BinarySearchTree<T>.LowerBound(_root, v), SB_BinarySearchTree<T>.UpperBound(_root, v) - 1);
    }

    public List<T> ToList()
    {
        return new List<T>(SB_BinarySearchTree<T>.Enumerate(_root));
    }
}

setのInsert()で重複を許容すればmultisetになる。

/// <summary>
/// C-like multiset
/// </summary>
public class MultiSet<T> : Set<T> where T : IComparable
{
    public override void Insert(T v)
    {
        if (_root == null) _root = new SB_BinarySearchTree<T>.Node(v);
        else _root = SB_BinarySearchTree<T>.Insert(_root, v);
    }
}

2017-01-25

HackerRank Week of Code 28 参加日記

C# プログラミングコンテスト

111位/10432人でレート微増だった。Easy問題は省略する。
https://www.hackerrank.com/results/w28/yambe2002

The Great XOR

整数xが与えられたとき、以下を満たす整数aの個数を答えよ。
a XOR x > x
0 < a < x
1 <= x <= 10^9

例えばx=b10101111とすると、aの候補は
b0001nnnn
b01nnnnnn
となる(nは1と0どちらでもよい）。よって答えはb0101000になる。

public static long GetAns(long x)
{
    var ret = ~x;
    var idx = 63;
    while (idx > 0 && (x >> idx) % 2 == 0) idx--;
    return ret & (((long)1 << idx) - 1);
}

Lucky Number Eight

0-9からなる文字列s(長さn)が与えられる。sのサブシーケンスを10進数の数字とみなしたとき、これが8で割り切れるパターン数を求めよ。
1 <= n <= 200000

nが大きいのでサブシーケンスの列挙はできない。8の倍数を次のように場合分けして考える。
・1桁の8の倍数(0,8)
s[i]が該当するパターン数
・2桁の8の倍数(00, 08, ... 96)
s[i]x10+s[j] が該当するパターン数　（j>i)
・3桁以上の8の倍数
3桁の8の倍数(000, 008, ... 992)について
s[i]x100+s[j]x10+s[k] が該当するパターンを列挙(k>j>i)。
下3桁が8の倍数の数字はすべて8の倍数なので、iの位置に応じてパターン数を算出する

static long mod = 1000000007;

static void Main(string[] args)
{
    var n = Int32.Parse(Console.ReadLine());
    var s = ReadLine();
    Console.WriteLine(GetAns(s));
}

public static long GetAns(string s)
{
    long ret = 0;

    var arr = s.Select(c => Int32.Parse(c.ToString())).ToArray();

    // take 1 digit
    foreach (var c in arr)
    {
        if (c % 8 == 0)
        {
            ret++;
            ret %= mod;
        }
    }

    // take 2 digits
    ret += Get2Digits(arr);
    ret %= mod;

    // take 3+ digit
    ret += Get3Digits(arr);
    ret %= mod;

    return ret;
}

public static long Get2Digits(int[] arr)
{
    long ret = 0;
    var two_digits = Enumerable.Range(0, 13).Select(i => i * 8).ToArray();  //0-96

    foreach (var cand in two_digits)
    {
        var rightVal = cand % 10;
        var leftVal = cand / 10;
        var rightCnt = 0;

        for (int i = arr.Length - 1; i >= 0; i--)
        {
            if (arr[i] == leftVal)
            {
                ret += rightCnt;
                ret %= mod;
            }

            if (arr[i] == rightVal) rightCnt++;
        }
    }

    return ret;
}

public static long Get3Digits(int[] arr)
{
    long ret = 0;
    var three_digits = Enumerable.Range(0, 125).Select(i => i * 8).ToArray();  //0-992

    foreach (var cand in three_digits)
    {
        var ldigit = cand / 100;
        var mdigit = (cand / 10) % 10;
        var rdigit = cand % 10;
        long one_cnt = 0;
        long two_cnt = 0;

        for (int i = arr.Length - 1; i >= 0; i--)
        {
            if (arr[i] == ldigit)
            {
                ret += ModPow(2, i, mod) * two_cnt;
                ret %= mod;
            }
            if (arr[i] == mdigit)
            {
                two_cnt += one_cnt;
                two_cnt %= mod;
            }
            if (arr[i] == rdigit) one_cnt++;
        }
    }

    return ret;
}

The Value of Friendship

1~nで番号付けされたn人の生徒がいる。また、xとyが友達になることを示すペア(x, y)がm個あたえられる。さらに
・xとyが友達のときは、yとxも友達
・xとyが友達でyとzが友達のときは、xとzも友達
とする。
それぞれの生徒の友達の数をすべて合計したものをtotalと呼ぶ。友達になる順番は任意に変えることができる。友達ペアを適用するたびにtotalを求めたとき、その合計の最大を求めよ。
1 <= q <= 16 (クエリ数)
1 <= n <= 10^5
1 <= m <= min(n(n-1)/2, 2 x 10^5)

すべての友達情報を反映させたあと、Totalに影響が少ない順（友達グループの小さい順）に1人ずつ友達から外していって計算する。このとき、閉ループを作る友達情報は先に計算する。グループ情報の保持や閉ループ検出にはUnionFindを使えばよい。

public static long GetAns(int n, List<Tuple<int, int>> friends)
{
    long ret = 0;

    var unionFind = new UnionFind();

    // 閉ループになる友達情報
    var relationCreatingClosedLoopNum = 0;
    foreach (var f in friends)
    {
        if (unionFind.IsSameGroup(f.Item1, f.Item2))
        {
            relationCreatingClosedLoopNum++;
            continue;
        }
        unionFind.Unite(f.Item1, f.Item2);
    }

    var groups = unionFind.GetGroups().Where(v => v != 0).Select(v => v + 1).ToList();
    groups.Sort();
    groups.Reverse();

    long currentVal = 0;
    foreach (var g in groups)
    {
        currentVal += g * (g - 1);
    }

    // 閉ループの分は、情報を削除してもトータルが変わらない
    ret = currentVal;
    ret += currentVal * relationCreatingClosedLoopNum;

    while (groups.Count() > 0)
    {
        // 小さいグループから処理
        var num = groups.Last();
        groups.RemoveAt(groups.Count() - 1);
        
        // 該当グループ以外の分
        currentVal -= num * (num - 1);
        ret += currentVal * (num - 1);

        // 該当グループの分
        num--;
        while (num > 1)
        {
            ret += num * (num - 1);
            num--;
        }
    }

    return ret;
}

public class UnionFind
{
    private class Node
    {
        public Node Parent { get; set; }
        public int Rank { get; set; }
        public HashSet<Node> Children;

        public Node()
        {
            Children = new HashSet<Node>();
        }
    }

    private Dictionary<object, Node> _dict = new Dictionary<object, Node>();

    private Node Root(object data)
    {
        if (!_dict.ContainsKey(data))
        {
            var node = new Node();
            _dict.Add(data, node);
            return node;
        }
        else
        {
            var node = _dict[data];
            return Find(node);
        }
    }

    private Node Find(Node node)
    {
        if (node.Parent == null) return node;
        return node.Parent = Find(node.Parent);
    }

    public void Unite(IComparable x, IComparable y)
    {
        var xRoot = Root(x);
        var yRoot = Root(y);
        if (xRoot == yRoot) return;

        if (xRoot.Rank < yRoot.Rank)
        {
            ChangeParent(yRoot, xRoot);
        }
        else
        {
            ChangeParent(xRoot, yRoot);
            if (xRoot.Rank == yRoot.Rank) xRoot.Rank++;
        }
    }

    void ChangeParent(Node parent, Node childRoot)
    {
        if (childRoot.Parent != null) childRoot.Parent.Children.Remove(childRoot);

        childRoot.Parent = parent;
        childRoot.Parent.Children.Add(childRoot);

        foreach (var child in childRoot.Children.ToList())
        {
            ChangeParent(parent, child);
        }
    }

    public bool IsSameGroup(IComparable x, IComparable y)
    {
        return Root(x) == Root(y);
    }

    public List<long> GetGroups()
    {
        var ret = new List<long>();

        foreach (var r in _dict.Values.Where(d => d.Parent == null))
        {
            ret.Add(r.Children.Count());
        }

        return ret;
    }
}

Choosing White Balls

横一列に並んだn個のボールがある。ボールは黒か白に色がついている。このとき、k回ボール拾い上げて、なるべく多くの白ボールを拾いたい。拾い上げi回目について(1 <= i <= k)、
・1からn-i+1までの数字xを選ぶ
・端からx番目のボールを拾う。端は左右どちらでもよい
の条件がある。最善手を取ったときの、白ボールの個数の期待値を求めよ。
1 <= k <= n < 30

メモ化再帰で解くだけけだが、本番ではいくつかのケースでTLEになっていた。Dictionaryのキーチェック・値取得を行う部分で

if (dict.ContainsKey(key)) val = dict[key];

のようにしていたのが非効率だった。

dict.TryGetValue(key, out val);

このようにTryGetValue()を使ったほうが、内部的な検索が一回で済むので早いようだ。
参考：
http://stackoverflow.com/questions/9382681/what-is-more-efficient-dictionary-trygetvalue-or-containskeyitem
https://referencesource.microsoft.com/#mscorlib/system/collections/generic/dictionary.cs,2e5bc6d8c0f21e67

public static double GetAns(int n, int k, string s)
{
    _n = n;
    _memo.Clear();

    var state = GetState(s);
    state = (int)Flip(state, n);
    return GetAns(k, state);
}

static long Flip(long balls, int n)
{
    var balls2 = Reverse32(balls) >> (32 - n);
    return Math.Min(balls, balls2);
}
        
public static long Reverse32(long value)
{
    var n = value >> 16 | value << 16;
    n = n >> 0x8 & 0x00ff00ff | n << 0x8 & 0xff00ff00;
    n = n >> 0x4 & 0x0f0f0f0f | n << 0x4 & 0xf0f0f0f0;
    n = n >> 0x2 & 0x33333333 | n << 0x2 & 0xcccccccc;
    n = n >> 0x1 & 0x55555555 | n << 0x1 & 0xaaaaaaaa;
    return n;
}

public static int GetState(string s)
{
    var ret = 0;

    for (int i = 0; i < s.Length; i++)
    {
        ret <<= 1;
        ret |= (s[i] == 'W') ? 1 : 0;
    }

    return ret;
}

public static long Pack(int n, int k, long state)
{
    return state + ((long)n << 32) + ((long)k << 40);
}

static Dictionary<long, double> _memo = new Dictionary<long, double>();

public static double GetAns(int k, long state)
{
    return Dfs(_n, k, state);
}

public static double Dfs(int n, int k, long state)
{
    if (state == 0) return 0;
    if (k == 0) return 0;

    state = Flip(state, n);

    double ret = 0;
    var packed = Pack(n, k, state);

    // これだとTLEになる・・・
    //if (_memo.ContainsKey(packed)) return _memo[packed];

    // こっちのほうが早いようだ
    double result;
    if (_memo.TryGetValue(packed, out result))
        return result;

    double cnt = 0;
    double sum = 0;

    // 1 <= x <= n - i + 1
    for (int x = 1; x <= n; x++)
    {
        // left
        var bit = 1L << x - 1;
        var ball1 = Remove(state, x - 1);
        var sum_left = Dfs(n - 1, k - 1, ball1) + ((state & bit) != 0 ? 1 : 0);

        // right
        bit = 1L << (n - 1 - x + 1);
        var ball2 = Remove(state, n - 1 - x + 1);
        var sum_right = Dfs(n - 1, k - 1, ball2) + ((state & bit) != 0 ? 1 : 0);

        sum += Math.Max(sum_left, sum_right);

        cnt++;
    }
    ret = sum / cnt;

    _memo.Add(packed, ret);

    return ret;
}

static long Remove(long balls, int i)
{
    var bit = 1L << i;
    balls &= ~bit;
    var mask = bit - 1;
    return (balls & mask) | (balls & ~mask & long.MaxValue) >> 1;
}

Suffix Rotation

英小文字からなる文字列sがある。各ターンで以下の作業ができるとき、最小何ターンで辞書順最小の文字列に変換することができるか答えよ。
・任意のインデックスiを選ぶ。iは過去に選ばれたインデックスより大きくなければならない
・1回かそれ以上、i以降の文字列をローテートする。方向は左右どちらでもよい
1 <= g <= 100 (sの個数)
1 <= |s| <= 1000

DPで求めることができるが、次の考慮が必要になる。

・ローテーションの作業をインデックスで持つ
たとえばIndex=0の位置で左に３つローテーションする場合、実際に回すと以下のようになるが
abcdef -> defabc　（ローテーション）
次のようにインデックス位置の移動で表すことが可能。
abcdef -> abcdef　（インデックス位置）
^-----------^---

・小さい文字から削除して処理
sを直接1文字ずつ処理するループ回数が膨大になるが、文字種ごとに処理すれば外のループは26回で済むようになる。さらに、たとえばsがbaacaaadaeでaを削除することを考えると、どの順番で行おうが残る文字列はbcdeになる（ターン回数は3）。そして、次のインデックスはbcdeの位置(0,3,7,9)のいずれかになる。

これらを考慮すると、注目している文字と現在のインデックスだけ保持すればよいことが分かる。
（実装は省略）

2017-01-12

HackerRank Week of Code - 26 参加日記

C# プログラミングコンテスト

398位/6951人でレート減してしまった。いつも数学の問題が多いと順位を落としてしまう。以下Easy問は省略。

Twins

整数iとjがいずれも素数、かつ距離が2のとき、これらをペアであるとする。整数nとmが与えられたとき、区間[n,m]にはいくつのペアが存在するか。ただし、(i, j)と(j, i)は同じペアと扱う。
1 <= n <= m <= 10^9
m - n <= 10^6

あらかじめエラトステネスの篩を使って区間内の素数を列挙し、あとはi=n..m-2でループしてiとi+2が両方素数の場合をカウントすればよい。

// n, m <= 10^9, m - n <= 10^6
public static int GetAns(int n, int m)
{
    var isPrime = new bool[m - n + 1];
    SegSieve(n, m + 1, isPrime);
    var ret = 0;
    for (int i = n; i <= m - 2; i++)
    {
        if (isPrime[i - n] && isPrime[i - n + 2]) ret++;
    }
    return ret;
}

// returns primes in [a, b)
public static void SegSieve(int a, int b, bool[] isPrime)
{
    for (int i = 0; i < isPrime.Length; i++) isPrime[i] = true;
    for (int i = 0; i < isPrime.Length; i++)
    {
        if (i + a < 2) isPrime[i] = false;
    }

    var sqrtb = (int)Math.Ceiling(Math.Sqrt(b));

    // prime table of [0, sqrt[b])
    var primeTable_0_b = new int[sqrtb];
    var primeTable_0_b_is = new bool[sqrtb];

    Sieve(primeTable_0_b, primeTable_0_b_is);

    foreach (var p in primeTable_0_b)
    {
        if (p == -1) continue;
        var st = (a / p) * p;
        if (st == 0) st = p;
        if (st == p) st += p;
        while (st < b)
        {
            if (st >= a) isPrime[st - a] = false;
            st += p;
        }
    }
}

public static void Sieve(int[] prime, bool[] isPrime)
{
    for (int i = 0; i < prime.Length; i++) prime[i] = -1;
    for (int i = 0; i < isPrime.Length; i++) isPrime[i] = true;
    isPrime[0] = isPrime[1] = false;

    var idx = 0;
    for (int i = 2; i < isPrime.Length; i++)
    {
        if (isPrime[i])
        {
            prime[++idx] = i;
            for (int j = 2 * i; j < isPrime.Length; j += i) isPrime[j] = false;
        }
    }
}

Music on the Street

無限に長いストリート上に、ポイントa_0、a_1、... a_nが設置されている。a_0より前のストリートではある曲のジャンルが、a_0とa_1の間ではまた別の曲のジャンルが演奏されている（a_nからあとも同様）。ある人がある地点からポイントが大きくなる方向に時速1マイルでmマイル歩くとき、同じジャンルの曲をh_min時間以上、h_max時間以内だけ聞きたい。これを満足するスタート地点のいずれかを求めよ。
1 <= n <= 10^6
abs(a_i) <= 10^9、a_iは昇順で与えられる
1 <= h_min <= h_max <= 10^9
1 <= m <= 10^9

スタート地点の候補は限られているので、そのすべてで条件に合致するかトライする。予めボーダー間がすべて条件を満たすかどうかを管理する区間木を作っておけばよい。また、歩き始めのIndexや終点のIndexを求めるにはLowerBoundとUpperBoundも必要になる。
本番ではRmq内の配列サイズが足りず、1問RLEになっていた。

class Program
{
    public static long n;
    public static List<long> a;
    public static long m;
    public static long hmin;
    public static long hmax;

    public static Rmq _rmq;

    static void Main(string[] args)
    {
        n = long.Parse(Console.ReadLine());
        a = ReadLine().Split().Select(v => long.Parse(v)).ToList();
        var str = Console.ReadLine().Split();
        m = long.Parse(str[0]);
        hmin = long.Parse(str[1]);
        hmax = long.Parse(str[2]);
        Console.WriteLine(GetAns());
    }

    public static long GetAns()
    {
        // from left
        for (int i = 0; i < a.Count(); i++)
        {
            if (Ok(a[i] - hmin))
            {
                return a[i] - hmin;
            }
            if (Ok(a[i] - hmax))
            {
                return a[i] - hmax;
            }
            if (Ok(a[i]))
            {
                return a[i];
            }
        }

        //from right
        for (int i = a.Count() - 1; i >= 0; i--)
        {
            if (Ok(a[i] + hmin - m))
            {
                return a[i] + hmin - m;
            }
            if (Ok(a[i] + hmax - m))
            {
                return a[i] + hmax - m;
            }
            if (Ok(a[i] - m))
            {
                return a[i] - m;
            }
        }

        return -1000;
    }

    public static bool Ok(long pos)
    {
        var stIdx = (int)UpperBound(a, pos);
        if (stIdx >= a.Count() - 1) stIdx = a.Count() - 1;
        if (stIdx < 0) stIdx = 0;

        // check current pos to next bound
        if (!OkDist(pos, a[stIdx])) return false;

        var edIdx = (int)LowerBound(a, pos + m);
        edIdx--;
        if (edIdx >= a.Count() - 1) edIdx = a.Count() - 1;
        if (edIdx < 0) edIdx = 0;

        // check last bound to last pos
        if (!OkDist(a[edIdx], pos + m)) return false;

        // check intervals are all OK
        return OkIntervals(stIdx, edIdx);
    }

    public static bool OkIntervals(int idx1, int idx2)
    {
        if (idx1 == idx2) return true;
        if (idx1 + 1 == idx2) return OkDist(a[idx1], a[idx2]);

        if (_rmq == null)
        {
            _rmq = new Rmq();
            _rmq.Init((int)n + 1);

            for (int i = 0; i < n - 1; i++)
            {
                if (!OkDist(a[i], a[i + 1]))
                {
                    _rmq.Update(i, 0);
                }
                else
                {
                    _rmq.Update(i, 1);
                }
            }
        }
        return _rmq.Query(idx1, idx2) == 1;
    }

    public static bool OkDist(long pos1, long pos2)
    {
        var gap = pos2 - pos1;
        if (gap == 0) return true;
        return gap >= hmin && gap <= hmax;
    }

    public static long LowerBound(List<long> ar, long val)
    {
        long lb = -1;
        long ub = ar.Count();

        while (ub - lb > 1)
        {
            var mid = (lb + ub) / 2;
            if (ar[(int)mid] >= val)
            {
                ub = mid;
            }
            else
            {
                lb = mid;
            }
        }

        return ub;
    }

    public static long UpperBound(List<long> ar, long val)
    {
        long lb = -1;
        long ub = ar.Count();

        while (ub - lb > 1)
        {
            var mid = (lb + ub) / 2;
            if (ar[(int)mid] <= val)
            {
                lb = mid;
            }
            else
            {
                ub = mid;
            }
        }

        return lb + 1;
    }
}

public class Rmq
{
    const int MAX_N = 2000005;
    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 < _dat.Length; i++) _dat[i] = Int32.MaxValue;
    }

    public void Update(int k, int a)
    {
        k += _n - 1;
        _dat[k] = a;
        while (k > 0)
        {
            k = (k - 1) / 2;
            _dat[k] = Math.Min(_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 Int32.MaxValue;
        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.Min(vl, vr);
        }
    }
}

Satisfactory Pairs

正の整数nが与えられたとき、ax + bx = n に解が存在する(a, b)のパターン数を求めよ(a < b、x,yは正の整数）。
4 <= n <= 3x10^5

axでイテレートし、その内部でax・byの約数の組み合わせを作って、該当するものを合算していけばよい。

public static int GetAns(int n)
{
    // 使う約数を準備
    var divs = new List<int>[n + 1];
    for (int i = 1; i <= n; i++)
    {
        for (int j = i; j <= n; j += i)
        {
            if (divs[j] == null) divs[j] = new List<int>();
            divs[j].Add(i);
        }
    }

    int ct = 0;
    for (int xa = 1; xa < n; xa++)
    {
        int yb = n - xa;
        foreach (var a in divs[xa])
        {
            foreach (var b in divs[yb])
            {
                var x = xa / a;

                // x <= b / gcd(a, b) は
                // 同じ(a,b)ペアでxが最小のもののみをカウント
                if (a < b && x <= b / gcd(a, b))
                {
                    ct++;
                }
            }
        }
    }

    return ct;
}

public static int gcd(int a, int b)
{
    while (b > 0)
    {
        int c = a;
        a = b;
        b = c % b;
    }
    return a;
}

2017-01-12

Facebook Hacker Cup 2017 Qualification Round 参加日記

C# プログラミングコンテスト

○○×で予選通過。R1は時間的に参加できるかどうか微妙だ。

Progress Pie
進捗パイチャートと点Xがあたえられたとき、Xがチャートの色付き部分に入っているかどうかを判定する。
点の位置とチャートの進捗p(%)を0%からの角度に変換して求めた。

public static bool GetAns(int p, int x, int y)
{
    x -= 50;
    y -= 50;

    // 特殊なケース
    if (x == 0 && y == 0) return p > 0;
    if (p == 0) return false;

    // 中心から遠すぎる
    if (x * x + y * y > 2500) return false;

    var theta = Math.PI * 2 * (p / 100.0);

    // 垂直線(0%線)と中心-点Xの角度を求め、象限ごとに処理する
    var pt = new Pt(x, y);
    var theta_pt = Math.Asin(pt.Cross(_zero) / (pt.Norm() * _zero.Norm()));
    if (x < 0 && y < 0) //3rd
    {
        theta_pt = Math.PI - theta_pt;
    }
    else if (x < 0) //4th
    {
        theta_pt = Math.PI * 2 + theta_pt;
    }
    else if (y < 0) //2nd
    {
        theta_pt = Math.PI - theta_pt;
    }

    return theta_pt <= theta;
}

Lazy Loading
重さの異なるN個の荷物を、なるべく多くの回数で運ぶ。ただし一回50ポンド以上は運ばなければならない。また、まとめて運んでいる荷物は、その中で一番重い荷物x個数でトータルの重さと嘘をつくことができる。
残っている荷物で最も重いものを1つと、軽いほうから50ポンドと虚偽できるまで運ぶのを繰り返せばよい。

public static int GetAns(List<int> w)
{
    var ret = 0;

    while (w.Count() > 0)
    {
        w.Sort();
        if (w.Count() * w[w.Count() - 1] < 50) break;
        w = w.Skip((int)Math.Ceiling((double)50 / (double)w[w.Count() - 1]) - 1).ToList();
        w.Remove(w.Last());
        ret++;
    }

    return ret;
}

Fighting the Zombie
部分的には、Y面のサイコロをN回振ったとき、その合計がある数N以上になる確率を求める問題になる。
dp[i, j]をi回振って合計がjになる確率と定義すれば、
dp[i + 1, j + 1] += dp[i, j] / N
dp[i + 1, j + 2] += dp[i, j] / N
...
dp[i + 1, j + N] += dp[i, j] / N
と更新して最終的な確率がすべて求められる。
（実装は省略）

2016-12-15

HackerRank Week of Code - 25 参加日記

C# プログラミングコンテスト

25位/7510人の自己ベスト。Hardの１問を正答できたのと、Hard/Expertの部分点を取れたのが大きかった。以下、難易度Easyのものは省略する。

Baby Step, Giant Step

2次元上の座標(0,0)から(d,0)に移動する最小のステップ数を求めよ。ただし、1回のステップでは距離aまたは距離bのみ進むことができる。a,b,dの組み合わせはq個与えられるので、それぞれについて答えること。
1 <= q <= 10^5
1 <= a <= b <= 10^9
0 <= d <= 10^9

x座標軸上のみで考えると、(x1,0)から(x2,0)まで移動するステップ数は、
１、x2-x1がaまたはb：1
２、x2-x1がb*2より小さい：2
３、それ以外：(x1+b,0)から(x2,0)までのステップ数+1
となる。愚直に再帰で実装するとStackOverflowになるので、３の部分はループでbを足していく。

public static int GetAns(int a, int b, int d)
{
    var ret = 0;
    if (d > 2 * b)
    {
        ret = (d - 2 * b) / b;
        d -= ret * b;
    }
    while (d > b * 2)
    {
        d -= a;
        ret++;
    }

    if (d == a || d == b)
        ret += 1;
    else if (d != 0)
        ret += 2;

    return ret;
}

Stone Division

2人のプレーヤーが次のゲームを戦う。いずれも最善手を指したときに、勝利するのはどちらか。
・n個の石でできた山が１つある
・m個の一意なInt型の集合S = { ${ s_0, s_1, ..., s_{m-1} }$ }がある
・プレーヤーは交互に手を指す。手番では、Sから任意の ${ s_i }$ と任意の山１つを選んで、その集まりを ${s_i}$ 個の山に分割する。このとき、分割された集合は同数である必要がある
・指せる手がないプレーヤーが負けとなる
1 <= n <= 10^18
1 <= m <= 10
2 <= ${s_i}$ <= 10^18

NimやGrundy数の理解が前提。本番ではWL-Algorithmで解いて部分正答だった。
参考：grundy数を習得したかった - nanikakaのAOJ航海日誌
${ g(x) }$ を１つの山にx個の石があるときのGrundy数とする。
xをkで割ったとき、Grungy数は
${ g(d)\,xor\,g(d)\,xor\,...\,xor\,g(d)\,\, (k\,times) }$
となる。よって、kが偶数のときは0、奇数のときはg(d)に一致する。（＝kが偶数なら勝ち）

class Program
{
    static List<long> s;
    static Dictionary<long, bool> dict = new Dictionary<long, bool>();

    static void Main(string[] args)
    {
        var str = Console.ReadLine().Split();
        var n = long.Parse(str[0]);
        var m = Int32.Parse(str[1]);
        s = Console.ReadLine().Split().Select(st => long.Parse(st)).ToList();
        Console.WriteLine(GetAns(n) ? "First" : "Second");
    }

    static bool GetAns(long n)
    {
        var ret = false;
        if (dict.ContainsKey(n)) return dict[n];

        foreach (var k in s)
        {
            if (n % k != 0) continue;
            ret |= k % 2 == 0;
            if (ret) break;
            ret |= !GetAns(n / k);
            if (ret) break;
        }

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

Good Point

二次平面上に、n個の厳密な凸多角形と、m個の楕円(Ellipse)がある。すべての多角形と楕円が重なる点を求めよ。該当点は存在することが保障されている。また、該当するものであれば、どの点を答えても良い。
1 <= n <= 500
3 <= ${v_i }$ <= 1500 (多角形iの頂点数)
3 <= ${ \sum_{i=0}^{n-1} v_i }$ <= 1500
1 <= m <= 1500
各座標は[ -10^4, 10^4 ]の範囲にある
楕円のSemi Major Axisは10^4以下の整数
誤差は10^-4まで許容

本番でこれが解けたのはうれしい。
凸多角形と楕円が重なる部分は、かならず凸型の図形になる。よって、最終的な凸型図形までの距離をf(x, y)とすると、xおよびyを固定してできる関数f(A, y), f(x, B)はいずれも凹型の曲線になる。なのでXとYそれぞれで三分探索すれば解が求められる。

class Program
{
    static void Main(string[] args)
    {
        //polygon
        var polygons = new List<Polygon>();
        var n = Int32.Parse(Console.ReadLine());
        for (int i = 0; i < n; i++)
        {
            var polygon = new Polygon();
            var v = Int32.Parse(Console.ReadLine());
            for (int j = 0; j < v; j++)
            {
                var str = Console.ReadLine().Split();
                var x = Int32.Parse(str[0]);
                var y = Int32.Parse(str[1]);
                polygon.AddPoint(new Pt(x, y));
            }
            polygons.Add(polygon);
        }

        //ellipses
        var ellipses = new List<Ellipse>();
        var m = Int32.Parse(Console.ReadLine());
        for (int i = 0; i < m; i++)
        {
            var str = Console.ReadLine().Split();
            var x1 = Int32.Parse(str[0]);
            var y1 = Int32.Parse(str[1]);
            var x2 = Int32.Parse(str[2]);
            var y2 = Int32.Parse(str[3]);
            var a = Int32.Parse(str[4]);
            ellipses.Add(new Ellipse(x1, y1, x2, y2, a));
        }

        var lx = -10001.0;
        var rx = 10001.0;
        var ly = -10001.0;
        var ry = 10001.0;

        // ternary search in x
        for (int i = 0; i < 48; i++)
        {
            var x1 = lx + (rx - lx) / 3;
            var x2 = rx - (rx - lx) / 3;

            var ly_x1 = -10001.0;
            var ry_x1 = 10001.0;
            var x1Score = GetScore_TernaryY(ref ly_x1, ref ry_x1, x1, ellipses, polygons);

            var ly_x2 = -10001.0;
            var ry_x2 = 10001.0;
            var x2Score = GetScore_TernaryY(ref ly_x2, ref ry_x2, x2, ellipses, polygons);

            if (x2Score > x1Score)
            {
                //remove right
                rx = x2;
            }
            else
            {
                //remove left
                lx = x1;
                ly = ly_x2;
                ry = ry_x2;
            }
        }

        Console.WriteLine(lx);
        Console.WriteLine(ly);
    }

    static double GetScore_TernaryY(ref double ly, ref double ry, double x, List<Ellipse> ellipses, List<Polygon> polygons)
    {
        var score = GetScore(x, ly, ellipses, polygons);
        for (int i = 0; i < 48; i++)
        {
            var y1 = ly + (ry - ly) / 3;
            var y2 = ry - (ry - ly) / 3;

            var y1Score = GetScore(x, y1, ellipses, polygons);
            var y2Score = GetScore(x, y2, ellipses, polygons);

            if (y2Score > y1Score)
            {
                //remove right
                ry = y2;
            }
            else
            {
                //remove left
                ly = y1;
                score = y2Score;
            }
        }
        return score;
    }

    static double GetScore(double x, double y, List<Ellipse> ellipses, List<Polygon> polygons)
    {
        return GetScore(new Pt(x, y), ellipses, polygons);
    }

    static double GetScore(Pt pt, List<Ellipse> ellipses, List<Polygon> polygons)
    {
        return ellipses.Sum(e => e.GetDist(pt)) + polygons.Sum(p => p.GetDist(pt));
    }
}


public class Polygon
{
    public List<Edge> Edges;

    List<Pt> _points;

    public Polygon()
    {
        Edges = new List<Edge>();
        _points = new List<Pt>();
    }

    public void AddPoint(Pt point)
    {
        _points.Add(point);
        if (_points.Count >= 2)
        {
            Edges.Add(new Edge(_points[_points.Count() - 2], _points[_points.Count() - 1]));
        }
    }

    public double GetDist(Pt pt)
    {
        double minDist = Double.MaxValue;
        var inside = true;

        for (int i = 0; i < Edges.Count(); i++)
        {
            if (!IsCcw(pt, Edges[i].p1, Edges[i].p2))
            {
                inside = false;
            }

            minDist = Math.Min(minDist, Edges[i].Dist(pt));
        }

        return inside ? 0 : minDist;
    }

    public bool IsCcw(Pt p, Pt p1, Pt p2)
    {
        return Pt.Ccw(p, p1, p2) == 1;
    }
}

public class Ellipse
{
    public Pt P1;
    public Pt P2;
    public double A;
    public double D;

    public Ellipse(double x1, double y1, double x2, double y2, double a)
    {
        P1 = new Pt(x1, y1);
        P2 = new Pt(x2, y2);
        A = a;
        D = 2 * a;
    }

    public double GetDist(Pt pt)
    {
        var ret = P1.Dist(pt) + P2.Dist(pt);
        return ret <= D ? 0 : (ret - D) / 2;
    }
}

PtとEdgeは個人ライブラリのもの。

DAG Queries

頂点数n、辺数mのDAGが与えられる。すべての頂点vは値として整数a[v]持ち、これの初期値は0である。次のクエリの結果を答えよ。クエリは3タイプある。
1. 1 u x: 頂点uから訪れることのできる頂点vについて、a[v]をxに更新する
2. 2 u x: 頂点uから訪れることのできる頂点vについて、a[v]>xならa[v]をxに更新する
3. u: a[u]を出力する
2 <= n <= 10^5
1 <= m, q <= 10^5 (qはクエリの数)
0 <= x <= 10^9

すべてのクエリをため込んで出力のたびにa[v]を算出する方法も、クエリが来るたびに各a[i]を算出する方法もTLEになる。平方分割を使って解決する。

すべてのクエリをローカル変数に保持
クエリタイプ2について、 ${ \sqrt{q} }$ くらいのブロックごとに、ブロックkの時点でクエリ2だけでa[v]の値がどうなるかの情報、type_2[k][v]を作成する
クエリを最初から処理：(1)クエリ1はキューque1に入れていく。que1のサイズが ${ \sqrt{q} }$ を超えたらその時点でクエリ1だけで値がどうなるかの情報type_1[v]を作成する(2)クエリ3が来たらtype_2とtype_1を使って出力値を計算

Editorialによると、グラフすべてを計算しようとするとメモリが足りなくなるので、グラフを3つくらいに分割して3回処理を回す必要がある。
理屈はわかるのだが、C#で実装したらTLEになってしまった・・・。

2016-10-26

HackerRank Week of Code - 24 参加日記

C# プログラミングコンテスト

392位/9177人。難易度Hardの「XOR Matrix」が解けそうで解けなく3日ほど苦しんだ(結果は部分正解)。Easy問題は省略する。

Simplified Chess Engine

盤の大きさが4x4、かつクイーン・ルーク・ナイト・ビショップだけが存在するミニチェスを考える。勝利条件は相手のクイーンを取ることとする。盤面g個が与えられたとき、ｍ手以内に先手が必勝かどうかをそれぞれ答えよ。
先手後手それぞれ、クイーンが１個、ルークが０~2個、ナイトとビショップが合計0~２個ある
1 <= g <= 200
1 <= m <= 6

十分に小さいゲーム木なので、MinMax法で簡単に求められる。ただし実装が少し重い。ちなみに、所定の手数までの勝敗なので、Zobrist Hashなどで同一局面を排除するとWAになる。

class Program
{
    enum PIECES { EMPTY, Q, N, B, R, q, n, b, r };

    static void Main(string[] args)
    {
        var g = Int32.Parse(Console.ReadLine());

        while( g > 0 )
        {
            var str = Console.ReadLine().Split();
            var w = Int32.Parse(str[0]);
            var b = Int32.Parse(str[1]);
            var m = Int32.Parse(str[2]);
            var board = GetInitBoard();

            while ( w > 0 ) 
            {
                SetPiece_Init(true, board, Console.ReadLine().Split());
                w--;
            }

            while ( b > 0 ) 
            {
                SetPiece_Init(false, board, Console.ReadLine().Split());
                b--;
            }

            if (MinMax('W', board, m)) Console.WriteLine("YES");
            else Console.WriteLine("NO");

            g--;
        }
    }

    static PIECES[,] GetInitBoard()
    {
        var ret = new PIECES[4, 4];
        for (int row = 0; row < 4; row++)
        {
            for (int col = 0; col < 4; col++)
            {
                ret[row, col] = PIECES.EMPTY;
            }
        }
        return ret;
    }

    static void SetPiece_Init(bool isWhite, PIECES[,] board, string[] inStrs)
    {
        var piece = GetPiece(!isWhite ? inStrs[0].ToLower()[0] : inStrs[0][0]);
        var col = inStrs[1][0] - 'A';
        var row = inStrs[2][0] - '1';
        MovePiece(board, -1, -1, row, col, piece).Item2;
    }

    static PIECES GetPiece(char p)
    {
        switch (p) {
            case 'Q':
                return PIECES.Q;
            case 'N':
                return PIECES.N;
            case 'B':
                return PIECES.B;
            case 'R':
                return PIECES.R;
            case 'q':
                return PIECES.q;
            case 'n':
                return PIECES.n;
            case 'b':
                return PIECES.b;
            case 'r':
                return PIECES.r;
        }
        return PIECES.EMPTY;
    }

    //return IsTerminalState
    static bool MovePiece(PIECES[,] board, int prevRow, int prevCol, int row, int col, PIECES piece)
    {
        var isTerminal = false;

        if (prevRow != -1) board[prevRow, prevCol] = PIECES.EMPTY;

        if (board[row, col] != PIECES.EMPTY)
        {
            if (board[row, col] == PIECES.Q || board[row, col] == PIECES.q) isTerminal = true;
        }

        board[row, col] = piece;
        return isTerminal;
    }

    static char GetNextTurn(char turn)
    {
        return turn == 'W' ? 'B' : 'W';
    }

    static bool IsHisPiece(char turn, PIECES piece)
    {
        if(piece == PIECES.EMPTY) return false;

        if (turn == 'W')
            return piece == PIECES.Q || piece == PIECES.N || piece == PIECES.B || piece == PIECES.R;

        if (turn == 'B')
            return piece == PIECES.q || piece == PIECES.n || piece == PIECES.b || piece == PIECES.r;

        return false;
    }

    static bool Win(PIECES[,] board, char turn)
    {
        bool Q_exist = false;
        bool q_exist = false;

        for (int row = 0; row < 4; row++)
        {
            for (int col = 0; col < 4; col++)
            {
                if(board[row, col] == PIECES.Q) Q_exist = true;
                if(board[row, col] == PIECES.q) q_exist = true;
            }
        }

        if(turn == 'W' && !q_exist) return true;
        if(turn == 'B' && !Q_exist) return true;
        return false;
    }

    static PIECES[,] CopyBoard(PIECES[,] org)
    {
        var ret = new PIECES[4, 4];
        for (int row = 0; row < 4; row++)
        {
            for (int col = 0; col < 4; col++)
            {
                ret[row, col] = org[row, col];
            }
        }
        return ret;
    }

    static bool IsInRange(int row, int col)
    {
        return IsInRange(row) && IsInRange(col);
    }

    static bool IsInRange(int pos)
    {
        return pos >= 0 && pos < 4;
    }

    static int[,] Moves_N = new int[,]
    {
        { 2, 1}, { 1, 2}, { -1, 2}, { -2, 1}, { -2, -1}, { -1, -2}, { 1, -2}, { 2, -1},
    };

    static bool IsEnemy(PIECES p, PIECES p2)
    {
        if (p == PIECES.Q || p == PIECES.R || p == PIECES.B || p == PIECES.N)
            return p2 == PIECES.q || p2 == PIECES.r || p2 == PIECES.b || p2 == PIECES.n;

        if (p == PIECES.q || p == PIECES.r || p == PIECES.b || p == PIECES.n)
            return p2 == PIECES.Q || p2 == PIECES.R || p2 == PIECES.B || p2 == PIECES.N;

        return false;
    }

    static void TryMove(ref List<Tuple<int, int>> moves, PIECES[,] board, int row, int col, PIECES piece, int rowDiff, int colDiff)
    {
        row += rowDiff;
        col += colDiff;

        while (IsInRange(row, col))
        {
            if (board[row, col] == PIECES.EMPTY)
            {
                moves.Add(new Tuple<int, int>(row, col));
            }
            else if(IsEnemy(piece, board[row, col]))
            {
                moves.Add(new Tuple<int, int>(row, col));
                break;
            }
            else
            {
                break;
            }
            row += rowDiff;
            col += colDiff;
        }
    }

    static List<Tuple<int, int>> GetNextPositions(int row, int col, PIECES piece, PIECES[,] board)
    {
        var ret = new List<Tuple<int, int>>();

        if (piece == PIECES.N || piece == PIECES.n)
        {
            for (int i = 0; i < Moves_N.GetLength(0); i++)
            {
                var nextRow = row + Moves_N[i, 0];
                var nextCol = col + Moves_N[i, 1];
                if (IsInRange(nextRow, nextCol))
                {
                    if(board[nextRow, nextCol] == PIECES.EMPTY || IsEnemy(piece, board[nextRow, nextCol]))
                        ret.Add(new Tuple<int, int>(nextRow, nextCol));
                }
            }
        }
        else
        {
            switch (piece)
            {
                case PIECES.Q:
                case PIECES.q:
                    TryMove(ref ret, board, row, col, piece, 1, 0);
                    TryMove(ref ret, board, row, col, piece, 0, 1);
                    TryMove(ref ret, board, row, col, piece, -1, 0);
                    TryMove(ref ret, board, row, col, piece, 0, -1);
                    TryMove(ref ret, board, row, col, piece, 1, 1);
                    TryMove(ref ret, board, row, col, piece, -1, 1);
                    TryMove(ref ret, board, row, col, piece, 1, -1);
                    TryMove(ref ret, board, row, col, piece, -1, -1);
                    break;
                case PIECES.R:
                case PIECES.r:
                    TryMove(ref ret, board, row, col, piece, 1, 0);
                    TryMove(ref ret, board, row, col, piece, 0, 1);
                    TryMove(ref ret, board, row, col, piece, -1, 0);
                    TryMove(ref ret, board, row, col, piece, 0, -1);
                    break;
                case PIECES.B:
                case PIECES.b:
                    TryMove(ref ret, board, row, col, piece, 1, 1);
                    TryMove(ref ret, board, row, col, piece, -1, 1);
                    TryMove(ref ret, board, row, col, piece, 1, -1);
                    TryMove(ref ret, board, row, col, piece, -1, -1);
                    break;
            }
        }

        return ret;
    }

    //turn: 'W' or 'B'
    //return true if the player won
    static bool MinMax(char turn, PIECES[,] board, int depth)
    {
        //White could not capture black's Qween within m moves
        if (depth == 0) return turn == 'W' ? false : true;

        var nextTurn = GetNextTurn(turn);

        for (int row = 0; row < 4; row++)
        {
            for (int col = 0; col < 4; col++)
            {
                if (IsHisPiece(turn, board[row, col]))
                {
                    foreach (var nextPos in GetNextPositions(row, col, board[row, col], board))
                    {
                        var nextBoard = CopyBoard(board);
                        var nextIsTerm = MovePiece(nextBoard, row, col, nextPos.Item1, nextPos.Item2, board[row, col]);

                        if (nextIsTerm)
                        {
                            if (Win(nextBoard, turn)) return true;
                        }
                        else
                        {
                            if (!MinMax(nextTurn, nextBoard, depth - 1)) return true;
                        }
                    }
                }
            }
        }
        return false;
    }
}

XOR Matrix

数列a[0], a[1]... a[n]が与えられる。次の操作をm-1回行ったときの最終的な値を出力せよ。

i < n-1 ならa[i]へ XOR(a[i], a[i+1])を代入

i = n-1 ならa[i]へ XOR(a[i], a[0])を代入

1 <= n <= 10^5
0 <= m <= 10^18 - 1
0 <= a[j] <= 10^9

たとえば要素0にXOR加算する要素は、
1
1 1
1 0 1
1 1 1 1
1 0 0 0 1
1 1 0 0 1 1
1 0 1 0 1 0 1
1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 1
のようにパスカルのフラクタルと同じ形になる。
(最上段は初期状態、その後は上から、操作１終了後、操作２終了後・・・の順)
パスカルのフラクタルがすべて1になるのは2^k回目のときで、その次の状態が該当要素と最終要素のXORになる。よって、現在の状態から2^kだけ飛ばして計算することが可能。
要素0以外も、シフトするだけで同じパターンとなる。

static void Main(string[] args)
{
    var str = Console.ReadLine().Split();
    var n = Int32.Parse(str[0]);
    var m = long.Parse(str[1]);
    var a = ReadLine().Split().Select(s => long.Parse(s)).ToArray();

    m--;
    while (m > 0)
    {
        long cnt = 1;
        while (cnt << 1 <= m)
        {
            cnt <<= 1;
        }

        var tmp = new long[a.Length];
        for (long i = 0; i < a.Length; i++)
        {
            tmp[i] = a[i] ^ a[(i + cnt) % a.Length];
        }
        a = tmp;
        m -= cnt;
    }

    foreach (var v in a)
    {
        Console.Write(v.ToString() + " ");
    }
    Console.WriteLine();
}

Shashank and the Palindromic Strings

文字列のリスト ${ a = [a_0, a_1, ..., a_{n-1} ] }$ がq個与えられる。それぞれについて次の条件を満たすパターン数を答えよ。

${ s_{i} }$ を ${a_{i}}$ の空文字以外のサブシーケンスとしたとき、 ${s_0 + s_1+ ...+ s_{n-1}}$ が回文になる

1 <= q <= 50
1 <= n <= 50

全文字列を連結した文字列sを考える。DPを次のように定義する。
${ dp[r, c, was1, was2] }$ ：セグメント[r, c]で回文になるサブシーケンスのパターン数。
　was1: s[r]の元文字列にある文字を含むかどうか
　was2: s[c]の元文字列にある文字を含むかどうか
更新条件は２通りある。
１. s[r]とs[c]の元文字列が同じとき

// ｒ・ｃの元文字列を使わないのは空文字のパターンのみ
dp[r, c, 0, 0] = 1;

// s[r]とs[l]を回文として使わないパターン
dp[r, c, 1, 1] = dp[r, c - 1, 1, 1] + dp[r + 1, c, 1, 1];
dp[r, c, 1, 1] -= dp[r + 1, c - 1, 1, 1]; // 重複を排除

// s[r]とs[l]を回文として使うパターン
if (s[r] == s[c])
{
    dp[r, c, 1, 1] += dp[r + 1, c - 1, 1, 1];
    dp[r, c, 1, 1] += dp[r + 1, c - 1, 0, 0];
}

２. s[r]とs[c]の元文字列が違うとき
２-１. s[r+1]とs[r]の元文字列が違い、さらにs[c-1]とs[c]の元文字列が違う場合

// rが元文字列の右端で、cが元文字列の左端のとき

// どちらの文字列も使わない場合は、その内側の結果と同じ
dp[r, c, 0, 0] = (r + 1 == c ? 1 : dp[r + 1, c - 1, 1, 1]);

// どちらかの文字列を使う場合は、使わない側をはぶいたパターン数に一致
dp[r, c, 1, 0] = dp[r, c - 1, 1, 1];
dp[r, c, 0, 1] = dp[r + 1, c, 1, 1];

// どちらも使うとき。s[r]とs[c]が一致しないと0になる
dp[r, c, 1, 1] = (s[r] == s[c] ? dp[r, c, 0, 0] : 0);

２-２. s[r+1]とs[r]の元文字列が違うが、s[c-1]とs[c]の元文字列は同じ場合

// s[r]が元文字列の右端だがs[c]は元文字列の左端ではないとき

dp[r, c, 0, 0] = dp[r, c - 1, 0, 0];    //s[r]、s[c]いずれの元文字列も使わない
                                        //dp[r + 1, c - 1, 0, 0]のような気がするが・・・？
dp[r, c, 1, 0] = dp[r, c - 1, 1, 0];    //s[r]の元文字列を使う
dp[r, c, 0, 1] = dp[r + 1, c, 1, 1];    //s[r]の元文字列を使わない
dp[r, c, 1, 1] = dp[r, c - 1, 1, 1];    //どっちも使う->s[r]を使うしかない

if (s[r] == s[c])
{
    //s[r]とs[c]が同じなら、この２つを回文に使うパターンが追加される
    dp[r, c, 1, 1] += dp[r + 1, c - 1, 1, 1];
    dp[r, c, 1, 1] += dp[r + 1, c - 1, 1, 0];

    //元文字列が隣り合っていた場合！
    if (A[r] + 1 == A[c])
    {
        dp[r, c, 1, 1]++; // 1増えるのみ
    }
}

２-３. s[r+1]とs[r]の元文字列が同じだが、s[c-1]とs[c]の元文字列は違う場合
　（２-２と同様）
２-４. s[r+1]とs[r]の元文字列も、s[c-1]とs[c]の元文字列も違う場合

// s[r]が元文字列の右端ではなく、s[c]が元文字列の左端ではないとき

// どちらの元文字列も使わないときは1つ内側の結果と同じ
dp[r, c, 0, 0] = dp[r + 1, c - 1, 0, 0];

// 片方の元文字列を使わないときは、使わない側を１つ内側にした結果と同じ
dp[r, c, 0, 1] = dp[r + 1, c, 0, 1];
dp[r, c, 1, 0] = dp[r, c - 1, 1, 0];

// どちらの元文字列も使うとき
dp[r, c, 1, 1] = dp[r + 1, c, 1, 1] + dp[r, c - 1, 1, 1];
dp[r, c, 1, 1] -= dp[r + 1, c - 1, 1, 1];   // 重複を排除

if (s[r] == s[c])
{
    // s[r]とs[c]が同じ文字なら、両方の元文字列を使うパターンに
    // 内側の結果すべてが加算される
    dp[r, c, 1, 1] += dp[r + 1, c - 1, 1, 1];
    dp[r, c, 1, 1] += dp[r + 1, c - 1, 1, 0];
    dp[r, c, 1, 1] += dp[r + 1, c - 1, 0, 1];
    dp[r, c, 1, 1] += dp[r + 1, c - 1, 0, 0];
}

最終的な実装は省略。