HackerRank Week of Code 28 参加日記

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)のいずれかになる。

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