2016-08-01

AGC002の参加日記

AGC第二回。2完397位/662人で惨敗。

整数a,bが与えられたとき、a, a+1, ..., bすべての積の符号を求めよ。

aとbが両方負のときは、個数の偶奇で解が変わる。

if (a > 0 && b > 0)
    Console.WriteLine("Positive");
else if ( (a <= 0 && b >= 0) || (a >= 0 && b <= 0))
    Console.WriteLine("Zero");
else
    Console.WriteLine(Math.Abs(a - b) % 2 == 0 ? "Negative" : "Positive");

B - Box and Ball

箱がN個あり、1番目の箱には赤いボールが、それ以外の箱には白いボールが1つずつ入っている。以下のM回の操作を行ったとき、最終的に赤いボールが入っている可能性のある箱は何個か。
・箱xからボールを取り出し、箱yに移す

それぞれの箱に入っているボールの数と、赤いボールが入っているかもしれない箱の集合を保持しながらシミュ―レーションする。ボールの数を管理しないと、箱が空になる場合に対処できない。

var num = new int[n + 1];
for (int i = 1; i < n + 1; i++) num[i] = 1;

var ret = new HashSet<int>() { 1 };
for (int i = 0; i < m; i++)
{
    str = Console.ReadLine().Split();
    var x = Int32.Parse(str[0]);
    var y = Int32.Parse(str[1]);

    if (ret.Contains(x)) ret.Add(y);
    num[x]--;
    num[y]++;
    if (num[x] == 0) ret.Remove(x);
}
Console.WriteLine(ret.Count());

C - Knot Puzzle

長さa[1], a[2], … a[N]のロープがある。1<=i<=N-1について、ロープiの右端とロープi+1の左端が結ばれている。繋がれているロープの長さの合計がL以上なら、どれか一つを解くことができる。すべての結び目を解くことは可能か。可能ならその手順も出力せよ。
2 <= N <= 10^5
1 <= a[i] <= 10^9
1 <= L <= 10^9

最後に残る2つのロープの合計長がL以上なら、そこに至るまでの手順はどのようでもよい。よって、長さがL以上になる2つの連続するロープを探し、そこだけを残して左右から解けばよい。

var tgt = -1;
for (int i = 0; i < n - 1; i++)
{
    if (a[i] + a[i + 1] >= l)
    {
        tgt = i;
        break;
    }
}

if (tgt == -1)
{
    Console.WriteLine("Impossible");
    return;
}

Console.WriteLine("Possible");
for (int i = 0; i < tgt; i++)
    Console.WriteLine(i + 1);
for (int i = n - 1; i > tgt; i--)
    Console.WriteLine(i);

閃けばひどく単純に解けるが、思いつかないとかなり嵌るタイプの問題だった。

D - Stamp Rally

N頂点M辺の無向グラフがある。頂点は1~N、辺は1~Mに番号が振ってある。以下のクエリごとの最小スコアを求めよ。
・頂点xとy、および整数zが与えられる
・xまたはyから任意に頂点を訪れていく
・訪れた頂点数がzになったとき、辺の番号の最大値がスコアとなる
3 <= N <= 10^6
N-1 <= M <= 10^5
1 <= クエリ数(Q) <= 10^5

「クエリjのスコアをk以下にできるか？」という判定で二分探索をする。スコアがk以下になるかどうかは、UnionFindに辺1からkまでの頂点を結合していき、xとyが含まれる集合の頂点数がz以上になっているかで判断できる。
クエリの数が多いので、二分探索は並列に行わないと間に合わない。

class Query
{
    public int X;
    public int Y;
    public int Z;

    //最終解が(left, Right]に存在する
    public int Left;
    public int Right;        
}

こんな風にクエリごとに二分探索のLeftとRightを持ち、エッジ1~Nのループ内で、今のエッジ番号がkに一致するクエリをアップデートしていく。

while (true)
{
    if (queries.Count(v => v.Right - v.Left > 1) == 0) break;

    var tgts = new Dictionary<int, List<Query>>();

    //これだと通らない。まだv.Leftが解答の可能性が残っている
    //foreach (var query in queries.Where(v => v.Right - v.Left > 1))
    foreach(var query in queries)
    {
        var mid = (query.Left + query.Right) / 2;
        if (!tgts.ContainsKey(mid)) tgts.Add(mid, new List<Query>());
        tgts[mid].Add(query);
    }
    if (tgts.Count() == 0) break;
                
    var unionFind = new UnionFind(n);
    for (int e = 0; e < m; e++)
    {
        unionFind.Unite(edges[e].Item1, edges[e].Item2);  //2頂点を結合
        if (tgts.ContainsKey(e))
        {
            foreach (var query in tgts[e])    //どれかのクエリの (Left + Right) / 2 なら該当クエリをアップデート
            {
                var sum = unionFind.Size(query.X);
                if (!unionFind.Same(query.X, query.Y)) sum += unionFind.Size(query.Y);
                if (sum >= query.Z)
                    query.Right = e;
                else
                    query.Left = e;
            }
        }
    }
}

手持ちのUnionFindにSize()を実装していなかったので追加しておいた。

2016-07-31

天下一プログラマーコンテスト2016予選Aの参加日記

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

2完の141位/446人。さっさともう一問解けるようになりたい。

A - 天下一プログラマーゲーム

1~100の数のうち、3と5のいずれでも割り切れない数の合計を求めよ。

Console.WriteLine(Enumerable.Range(1, 100).Where(s => s % 3 != 0 && s % 5 != 0).Sum());

このFizzbuzz的難問が解ければ上位0.5%のプログラマのはず。
参考：どうしてプログラマに・・・プログラムが書けないのか?

B - PackDrop

N台の機器からなるネットワークがある。ネットワークは根付き木の形をしていて、機器0がルートである。このとき、機器間にPackDropという、0.01の確率でパケットを破壊する装置をいくつか置くことができる。子を持たない機器B(1)…B(M)それぞれに対し、機器0からの望ましいパケット到達率が与えられたとき、最少のPackDropの個数を求めよ。

なるべくルートの近くにPackDropを置くようにすればよい。

class Program
{
    static void Main(string[] args)
    {
        var str = Console.ReadLine().Split();
        var n = Int32.Parse(str[0]);
        var m = Int32.Parse(str[1]);
        var e = new List<List<int>>();
        for (int i = 0; i < n; i++) e.Add(new List<int>());

        for (int i = 1; i <= n - 1; i++)
        {
            var p = Int32.Parse(Console.ReadLine());
            e[i].Add(p);
            e[p].Add(i);
        }

        var pd = new int[n];
        for (int i = 0; i < n; i++) pd[i] = 0;

        for (int i = 0; i < m; i++)
        {
            str = Console.ReadLine().Split();
            var b_ = Int32.Parse(str[0]);
            var c_ = Int32.Parse(str[1]);
            pd[b_] = c_;
        }

        foreach (var c in e[0])
            Dfs(0, c, pd, e);

        var ret = 0;
        Dfs2(0, ref ret, 0, 0, pd, e);
        Console.WriteLine(ret);
    }

    static int Dfs(int prev, int idx, int[] pd, List<List<int>> e)
    {
        if (pd[idx] != 0) return pd[idx];
        var ret = Int32.MaxValue;

        foreach (var c in e[idx])
        {
            if (c == prev) continue;
            ret = Math.Min(ret, Dfs(idx, c, pd, e));
        }

        pd[idx] = ret;
        return ret;
    }

    static void Dfs2(int prev, ref int sum, int val, int idx, int[] pd, List<List<int>> e)
    {
        sum += (pd[idx] - val);
        foreach (var c in e[idx])
        {
            if (c == prev) continue;
            Dfs2(idx, ref sum, pd[idx], c, pd, e);
        }
    }
}

C - 山田山本問題

文字列AiとBiがそれぞれN個与えられる(i:0~N-1)。アルファベットの順番を任意に変え、すべてのAiがBiより辞書順で小さくなるようにしたい。そのようなアルファベットの並びはあるか。ある場合は、辞書順最小のものを出力せよ。

アルファベット26文字をノードとするDAGを、Kahnのアルゴリズムを使ってトポロジカルソートをすればよい。入次数0の頂点集合を優先キューにすることで、最終的な解が辞書順最小になる。

static void Main(string[] args)
{
    var edges = new List<List<int>>();
    for (int i = 0; i < 26; i++) edges.Add(new List<int>());

    var n = Int32.Parse(Console.ReadLine());

    for (int i = 0; i < n; i++)
    {
        var str = Console.ReadLine().Split();
        var astr = str[0];
        var bstr = str[1];

        var idx = 0;
        while (idx < Math.Min(astr.Length, bstr.Length) && astr[idx] == bstr[idx]) idx++;
        if (idx == Math.Min(astr.Length, bstr.Length))
        {
            if (astr.Length > bstr.Length)
            {
                Console.WriteLine(-1);
                return;
            }
            continue;
        }
        edges[astr[idx] - 'a'].Add(bstr[idx] - 'a');
    }

    var ret = new List<int>();

    var inEdgeNum = new int[26];
    for (int i = 0; i < edges.Count(); i++)
        foreach (var e in edges[i]) inEdgeNum[e]++;

    var que = new PriorityQueue<int>();
    for (int i = 0; i < 26; i++)
    {
        if (inEdgeNum[i] == 0) que.Push(i);
    }

    while (que.Count() > 0)
    {
        var val = que.Pop();
        ret.Add(val);

        foreach (var e in edges[val])
        {
            inEdgeNum[e]--;
            if (inEdgeNum[e] == 0) que.Push(e);
        }
    }

    Console.WriteLine(ret.Count() == 26 ? ret.Select(v => ((char)(v + 'a')).ToString()).Aggregate((a, b) => a + b) : "-1");
}

D - グラフィカルグラフ

重複のない大文字のアルファベットからなる無向木がある。この木の各頂点に接続する辺の本数は、4本以下である。
この木を100x100以下のマスで視覚的に表示せよ。

適当な根を選び、DFSで頂点を置いていけばよい。頂点数が26以下なので、距離を2^26、2^(26-1)、・・・と半分にしていけば、必ず重なることはない。表示する前に100x100に入るように整形する。

class Program
{
    static long[] dx = new long[] { -1, 0, 1, 0 };
    static long[] dy = new long[] { 0, 1, 0, -1 };

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

        var edges = new List<List<int>>();
        for (int i = 0; i < n; i++) edges.Add(new List<int>());

        for (int i = 0; i < n - 1; i++)
        {
            var str = Console.ReadLine().Split();
            var v = str[0][0] - 'A';
            var w = str[1][0] - 'A';
            edges[v].Add(w);
            edges[w].Add(v);
        }

        var posX = new long[n];
        var posY = new long[n];
        Dfs(-1, 0, 0, 1 << 26, 0, 0, posX, posY, edges);

        Clean(posX);
        Clean(posY);

        var ret = new char[53, 53];
        for (int i = 0; i < 53; i++)
            for (int j = 0; j < 53; j++)
                ret[i, j] = '.';

        for (int i = 0; i < posX.Length; i++)
        {
            ret[posX[i], posY[i]] = (char)(i + 'A');
        }

        AddLines(ret, edges);
            
        Console.WriteLine("53 53");
        for (int i = 0; i < ret.GetLength(0); i++)
        {
            for (int j = 0; j < ret.GetLength(1); j++)
            {
                Console.Write(ret[i, j]);
            }
            Console.WriteLine();
        }
    }

    static void Dfs(int predDir, int prev, int idx, long dist, long currentX, long currentY, long[] posX, long[] posY, List<List<int>> edges)
    {
        posX[idx] = currentX;
        posY[idx] = currentY;

        var dir = predDir == -1 ? 0 : (predDir + 3) % 4;    //avoid to go backward
        foreach(var next in edges[idx])
        {
            if (next == prev) continue;

            var nextPosX = currentX + (dx[dir] * dist);
            var nextPosY = currentY + (dy[dir] * dist);

            Dfs(dir, idx, next, dist / 2, nextPosX, nextPosY, posX, posY, edges);
            dir = (dir + 1) % 4;
        }        
    }

    static void Clean(long[] pos)
    {
        var values = pos.Distinct().OrderBy(v => v).ToList();
        for (int i = 0; i < pos.Count(); i++)
        {
            pos[i] = values.IndexOf(pos[i]) * 2 + 1;
        }
    }

    static void AddLines(char[,] ret, List<List<int>> edges)
    {
        for (int i = 0; i < ret.GetLength(0); i++)
        {
            for (int j = 0; j < ret.GetLength(1); j++)
            {
                if (ret[i, j] != '.' && ret[i, j] != '-' && ret[i, j] != '|')
                {
                    for (int dir = 0; dir < 4; dir++)
                    {
                        DrawLine(ret, i, j, dir, edges[ret[i, j] - 'A']);
                    }
                }
            }
        }
    }

    static void DrawLine(char[,] ret, int x, int y, int dir, List<int> children)
    {
        var drawChar = dir == 0 || dir == 2 ? '|' : '-';

        var curX = x + dx[dir];
        var curY = y + dy[dir];
        while (curX >= 0 && curX < ret.GetLength(0) && curY >= 0 && curY < ret.GetLength(1) && ret[curX, curY] == '.')
        {
            curX += dx[dir];
            curY += dy[dir];
        }

        if (curX >= 0 && curX < ret.GetLength(0) && curY >= 0 && curY < ret.GetLength(1) && children.Contains(ret[curX, curY] - 'A'))
        {
            curX = x + dx[dir];
            curY = y + dy[dir];
            while (ret[curX, curY] == '.')
            {
                ret[curX, curY] = drawChar;
                curX += dx[dir];
                curY += dy[dir];
            }
        }
    }
}

2016-07-25

World CodeSprint 5の参加日記

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

3完＋1部分点で暫定349位/6403人。難易度Moderateを1つ落としたのが悔しい。
https://www.hackerrank.com/contests/world-codesprint-5/challenges

CamelCase

CamelCaseの文字列に、英単語がいくつあるか答えよ。

大文字の数＋１を返せばよい。

Console.WriteLine(str.Count(s => s >= 'A' && s <= 'Z') + 1);

String Construction

空文字列pに以下の操作を行い、文字列sを作りたい。最小のコストを答えよ。
・p末尾に任意の文字を足す（1ドル）
・p内の部分文字列を、p末尾に足す（0ドル）

2度目以降に使う文字にはコストがかからないので、sから重複を排除した文字数を答えればよい。

Console.WriteLine(s.Distinct().Count());

Short Palindrome

英小文字のみからなる文字列sが与えられる。このとき、次の条件を満たす部分文字列が、s内にいくつあるか答えよ。
・任意のインデックスa,b,c,d（0 <= a < b < c < d）について、s[a]==s[d]かつs[b]==s[c]
1 <= |s| <= 10^6、解答は10^9+7のModを出力する

動的計画法を次のように定義して解いた。
dp_1[i][j]：0~iの文字jの個数
dp_2[i][l][m]：0~iで、{…,文字l,…,文字m,…}になっているパターン数
　→ dp_2[i][l][s[i]] = dp_1[i-1][l] + dp_2[i-1][l][s[i]]
dp_3[i][j][k]：0~iで、{…,文字j,…,文字k,…,文字k,…}になっているパターン数
　→ dp_3[i][j][s[i]] = dp_2[i-1][l][s[i]] + dp_3[i-1][j][s[i]]
このまま実装するとメモリが不足するので、配列の再利用を行っている。

const ulong mod = 1000000007;

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

    var dp_1 = new ulong[26];
    var dp_2 = new ulong[26, 26];
    var dp_3 = new ulong[26, 26];
    
    ulong ret = 0;
    for (int i = 0; i < s.Length; i++)
    {
        var c = s[i] - 'a';
        for (int x = 0; x < 26; x++)
        {
            ret += dp_3[c, x];
            ret %= mod;
        }

        for (int x = 0; x < 26; x++)
        {
            dp_3[x, c] += dp_2[x, c];
            dp_3[x, c] %= mod;
        }

        for (int x = 0; x < 26; x++)
        {
            dp_2[x, c] += dp_1[x];
            dp_2[x, c] %= mod;
        }

        dp_1[c]++;
        dp_1[c] %= mod;
    }

    Console.WriteLine(ret);
}

Editorialよりすっきりした解だと思うのだが、どうだろうか。

Longest Increasing Subsequence Arrays

長さmのInt型の配列を作る。このとき、部分列として、必ず{1,2,3,…n}が含まれるようにしたい。可能なパターン数を答えよ。
1 <= m <= 5x10^5、1 <= n <= 10^5
n <= m
解答は10^9+7のModを出力する

Editorialより。S[n]の位置+1をループすることで求めることができる。
f:id:yambe2002:20160725053056p:plain

static Int64 Solve(Int64 m, Int64 n)
{
    Int64 ret = 0;
    Int64 nPowX = 1;

    var n1PowX = ModPow(n - 1, m - n, mod);
    var invN1 = ModInv(n - 1, mod);

    for (Int64 x = 0; x <= m - n; x++)
    {
        //これだと大きいケースでTLEになる
        //var n1PowX = ModPow(n - 1, m - n - x, mod);
        
        //Invを掛けていく方法では、最終的に1になってはくれない
        if (m - n - x == 0) n1PowX = 1;

        var value = (Nck((int)(m - x - 1), (int)(n - 1)) * nPowX % mod) * n1PowX;
        value %= mod;

        ret += value;
        if (ret >= mod) ret -= mod;

        nPowX *= n;
        nPowX %= mod;

        n1PowX *= invN1;
        n1PowX %= mod;
    }

    return ret;
}

(n-1)^(m-n-x)をループ内で直接求めるとTLEになるので、(n-1)^(-1)のModを掛けていくことで算出する。ただし、この方法だと最終的に(n-1)^0のとき解が1になってくれないので、その場合だけ直接1をアサインすることになる。
ModPow()、Nck()、ModInv()は個人ライブラリより。

Balanced Forest

ノード数nの木があり、各ノードにはc[i]個のコインが付いている。ここで、どれかのノードにコインがcw個付いたノードを足し、n+1ノードの木にする。この木の2つのエッジを切ったとき、出来た3つの木が同じ数のコインを持つようにしたい。cwの最小値を求めよ。不可能な場合は-1とする。
1 <= n <= 5x10^4
1 <= c[i] <= 10^9
部分点(30%)
1 <= n <= 100
1 <= c[i] <= 100
部分点(50%)
1 <= n <= 2000
1 <= c[i] <= 10^9

本番では50%の部分点だった。エッジでループし、該当エッジをカットしたときの小さいほうが、最終的な3つの木の1つとなり得るかを判定している。そのとき、予め「ノードAからみたノードB以降の木の合計値」を求めることで計算量を削減した。
https://www.hackerrank.com/contests/world-codesprint-5/challenges/balanced-forest/submissions/code/6349361

Editorialによると、ノード1をルートとし、各ノードに子ノードのコイン合計を持つことで、O(n Log(n))で算出できる。これは本番で場合分けがうまくいかず、断念したやり方だった。
Editorialサンプルの変数名やコメントを直したものが以下。

static Int64 Solve()
{
    // Nodeクラスの配列を作成
    // 各Nodeについて、サブ木の合計、DFSの到着時間、およびDFSのLeave時間を保持する
    Dfs(1, 0);

    // サブ木合計値から、最小の到着時間、最大の到着時間とそれぞれのノードインデックスを保持する辞書を作成する
    for (int i = 1; i <= n; i++)
    {
        if (!minArrivalTime_BySum.ContainsKey(c[i].SumOfSubtree))
        {
            minArrivalTime_BySum[c[i].SumOfSubtree] = c[i].ArriveTime;
            maxArrivalTime_BySum[c[i].SumOfSubtree] = c[i].ArriveTime;
            idxOfMinArrivalTime_BySum[c[i].SumOfSubtree] = i;
            idxOfMaxArrivalTime_BySum[c[i].SumOfSubtree] = i;
        }
        else
        {
            if (minArrivalTime_BySum[c[i].SumOfSubtree] > c[i].ArriveTime)
            {
                minArrivalTime_BySum[c[i].SumOfSubtree] = c[i].ArriveTime;
                idxOfMinArrivalTime_BySum[c[i].SumOfSubtree] = i;
            }
            if (maxArrivalTime_BySum[c[i].SumOfSubtree] < c[i].ArriveTime)
            {
                maxArrivalTime_BySum[c[i].SumOfSubtree] = c[i].ArriveTime;
                idxOfMaxArrivalTime_BySum[c[i].SumOfSubtree] = i;
            }
        }
    }

    minCw = (Int64)1e15;

    // 木のコイン合計が偶数、かつちょうど半分のサブ木合計があったら、その値が解になり得る
    if (sum % 2 == 0 && maxArrivalTime_BySum.ContainsKey(sum / 2)) minCw = sum / 2; 

    // 全ノードのループ
    for (int i = 1; i <= n; i++)
    {
        if (3 * c[i].SumOfSubtree <= sum)   // この時は、該当サブ木にcwを足すことを試す
            TryAddCw_ToSubTree(i);
        else if (2 * c[i].SumOfSubtree < sum)   // サブ木合計を、最終的な1/3の１つとできるか試す
            TryAddCw_ToAnotherTree(i);
    }
    return minCw == (Int64)1e15 ? -1 : minCw;
}

static void TryAddCw_ToSubTree(int x)
{
    if ((sum - c[x].SumOfSubtree) % 2 == 0) //サブ木以外が2で割れなければ無理
    {
        Int64 p = (sum - c[x].SumOfSubtree) / 2;    //最終的な1/3のコイン数

        if (maxArrivalTime_BySum.ContainsKey(p) && (c[idxOfMaxArrivalTime_BySum[p]].ArriveTime > c[x].ArriveTime || c[idxOfMaxArrivalTime_BySum[p]].LeaveTime < c[x].ArriveTime))
            minCw = Math.Min(minCw, p - c[x].SumOfSubtree);                
        else if (minArrivalTime_BySum.ContainsKey(p) && (c[idxOfMinArrivalTime_BySum[p]].ArriveTime > c[x].ArriveTime || c[idxOfMinArrivalTime_BySum[p]].LeaveTime < c[x].ArriveTime)) 
            minCw = Math.Min(minCw, p - c[x].SumOfSubtree);
        else if (minArrivalTime_BySum.ContainsKey(p + c[x].SumOfSubtree) && 
                c[idxOfMinArrivalTime_BySum[p + c[x].SumOfSubtree]].ArriveTime < c[x].ArriveTime && 
                c[idxOfMinArrivalTime_BySum[p + c[x].SumOfSubtree]].LeaveTime >= c[x].ArriveTime) 
            minCw = Math.Min(minCw, p - c[x].SumOfSubtree);
        else if (maxArrivalTime_BySum.ContainsKey(p + c[x].SumOfSubtree) &&
                c[idxOfMaxArrivalTime_BySum[p + c[x].SumOfSubtree]].ArriveTime < c[x].ArriveTime && 
                c[idxOfMaxArrivalTime_BySum[p + c[x].SumOfSubtree]].LeaveTime >= c[x].ArriveTime) 
            minCw = Math.Min(minCw, p - c[x].SumOfSubtree);

        return;
    }
}

static void TryAddCw_ToAnotherTree(int x)
{
    Int64 add = 3 * c[x].SumOfSubtree - sum;

    if (minArrivalTime_BySum[c[x].SumOfSubtree] != maxArrivalTime_BySum[c[x].SumOfSubtree]) minCw = Math.Min(minCw, add);
    else if (minArrivalTime_BySum.ContainsKey(c[x].SumOfSubtree - add) && (c[idxOfMinArrivalTime_BySum[c[x].SumOfSubtree - add]].ArriveTime < c[x].ArriveTime || c[idxOfMinArrivalTime_BySum[c[x].SumOfSubtree - add]].ArriveTime > c[x].LeaveTime)) minCw = Math.Min(minCw, add);
    else if (maxArrivalTime_BySum.ContainsKey(c[x].SumOfSubtree - add) && (c[idxOfMaxArrivalTime_BySum[c[x].SumOfSubtree - add]].ArriveTime < c[x].ArriveTime || c[idxOfMaxArrivalTime_BySum[c[x].SumOfSubtree - add]].ArriveTime > c[x].LeaveTime)) minCw = Math.Min(minCw, add);
    else if (minArrivalTime_BySum.ContainsKey(2 * c[x].SumOfSubtree - add)) minCw = Math.Min(minCw, add);

    return;
}

//// 省略

class Node
{
    public Int64 SumOfSubtree; //c[i].s - sum of values in subtree rooted in i
    public int ArriveTime;  //time when dfs arrived in i-th node
    public int LeaveTime; //time when dfs leave i-th node ( all children are marked)
};

TryAddCw_ToSubTree()とTryAddCw_ToAnotherTree()で細かい場合分けをしているが、ノードのコイン数は必ず1以上なのだから、もっと簡略化できそうな気がする。
（あるノードのサブ木合計値が、そのノードの子で発生することは有り得ないため）

2016-07-17

AGC001の参加日記

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

AGC第一回。参加者1200人超でめでたい。2完で318位でした。
Editorial：https://agc001.contest.atcoder.jp/data/agc/001/editorial.pdf

A: BBQ Easy - AtCoder Grand Contest 001 | AtCoder

バーベキュー用の串が2N本ある。1つの串焼きに2本の串を使う。1つの串焼きに使える具材は、短いほうの串の長さに等しい。最大でいくつの具材を串焼きにできるか。

串をソートしてペアを作り、それぞれの短いほうの和を求めればよい。標準入出力の凡ミスで二回もWAを出してしまった。

public static int Solve(int[] l)
{
    var ret = 0;
    l = l.OrderByDescending(v => v).ToArray();
    for (int i = 0; i < l.Length - 1; i+=2)
        ret += Math.Min(l[i], l[i + 1]);
    return ret;
}

B: Mysterious Light - AtCoder Grand Contest 001 | AtCoder

1辺の長さがNの鏡3つを、反射面を内側に向けて正三角形状に組み合わせる。三角形の頂点をa,b,cとする。
辺abのある点x(aからの距離X)から、辺bcと水平に光を発射する。この光は、鏡に当たると反射するが、さらに光の軌跡に当たっても反射する不思議な性質がある。この光は、必ず元の点に戻ってくることが証明できる。光の軌跡の長さを求めよ。
2<=N<=10^12、1<=X<=N-1、NとXは整数

f:id:yambe2002:20160717004008p:plain
dfs(a,b)を、現在地（上図）からの、残りの距離を返す関数と定義して再帰的に解いた。
なおNの最大値が大きいので、Intだとオーバーフローする。

public static UInt64 Solve(UInt64 n, UInt64 x)
{
    var ret = x + (n - x);
    ret += dfs(x, n - x);
    return ret;
}
 
public static UInt64 dfs(UInt64 a, UInt64 b)
{
    if (a == 0 || b == 0) return 0;
    if (b % a == 0)
    {
        return a * 2 * (b / a - 1) + a;
    }
 
    var ret = (2 * a) * (b / a);
    if (a % (b % a) == 0) return ret + ((b % a) * 2) * (a / (b % a)) - b % a;
 
    ret += ((b % a) * 2) * (a / (b % a));
    return ret + dfs(a % (b % a), b % a);
}

良く分からないが、なんと3*GCD()で一発で解くこともできるらしい。

C: Shorten Diameter - AtCoder Grand Contest 001 | AtCoder

N頂点の木がある。直径をK以下にするためには、最少でいくつの頂点を削除する必要があるか。

各頂点（Kが奇数なら辺）で、距離K/2を超える頂点の数をもとめ、その最小値が解答になる。

public class Solver
{
    static int maxDist;
    static List<List<int>> edges;

    public static int Solve(int n, int k, List<List<int>> e)
    {
        maxDist = k / 2;
        edges = e;

        var ret = Int32.MaxValue;
        for (int i = 0; i < n; i++ )
        {
            if (k % 2 == 0)
                ret = Math.Min(ret, Dfs(i, -1, 0));
            else
                foreach(var j in e[i]) 
                    ret = Math.Min(ret, Dfs(i, j, 0) + Dfs(j, i, 0));
        }
        return ret;
    }

    static int Dfs(int cur, int prev, int dist)
    {
        var ret = dist > maxDist ? 1 : 0;
        foreach (var next in edges[cur])
        {
            if (next == prev) continue;
            ret += Dfs(next, cur, dist + 1);
        }
        return ret;
    }
}

本番では、①木の直径を求め②Kを超えていたらに端を削除、を繰り返してTLEだった。
部分点がない問題なので、TLEになりそうな時点で、実装せず別解法を考えるべきだった。

D: Arrays and Palindrome - AtCoder Grand Contest 001 | AtCoder

長さMの数列Aが与えられる。Aの総和はNである。このとき、以下を満たす数列Bを解答せよ。
次の条件を満たす長さNの文字列が、すべて同じ文字になる
　先頭のa1文字、続くa2文字、さらに続くa3文字...はすべて回文
　先頭のb1文字、続くb2文字、さらに続くb3文字...はすべて回文

Aの中央にある奇数長の回文が3個以上なら、Bを作ることは不可能。
それ以外なら、まず奇数を左右の端に移動したのち、どちらかの端から１つずつずらして取ったものが解答になる。

// return value: a, b.length, b
public static Tuple<List<int>, int, List<int>> Solve(int n, int m, List<int> a)
{
    if (a.Count(v => v % 2 == 1) > 2) return null;

    if (m == 1)
    {
        List<int> ret;
        if (a[0] > 2) ret = new List<int>() { a[0] - 1, 1 };
        else ret = a.ToList();
        return new Tuple<List<int>, int, List<int>>(a, ret.Count(), ret);
    }

    //move odd items to first and last
    if (a.Count(v => v % 2 == 1) > 0)
    {
        var fst = a.First(v => v % 2 == 1);
        a.Remove(fst);
        a.Insert(0, fst);
        var lst = a.Last(v => v % 2 == 1);
        var lstIdx = a.LastIndexOf(lst);
        a.RemoveAt(lstIdx);
        a.Add(lst);
    }

    var b = new List<int>() { a.Last() + 1 };
    for (int i = a.Count - 2; i > 0; i--)
    {
        b.Add(a[i]);
    }
    if (a[0] > 1) b.Add(a[0] - 1);
    b.Reverse();

    return new Tuple<List<int>, int, List<int>>(a, b.Count(), b);
}

こういう問題だとLINQがとても便利。

2016-07-12

ARC053 - ARC057メモ（練習）

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

ARC057
A: 2兆円 - AtCoder Regular Contest 057 | AtCoder

所持金がt円ある。ある日の所持金がt円なら、次の日には1+Kt円増えている。二兆円に達するのは何日後か。

やるだけだが、k=0のケースを考慮しないとTLEになる。

public double Solve(double a, double k)
{
    if (k == 0) return 2E12 - a < 0 ? 0 : 2E12 - a;

    double n = 0;
    while (true)
    {
        if (a >= 2E12) break;
        a += (1 + k * a);
        n++;
    }
    return n;
}

B: 高橋君ゲーム - AtCoder Regular Contest 057 | AtCoder

N日間、それぞれa[i]回のゲームを行う。i日目の勝率が0~i-1日目までの勝率より真に高かったらその日は機嫌が良い。合計でK回ゲームに勝ったとすると、機嫌のよかった日数の最大値はいくつか。

なかなか解けずに苦しんだが、問題の読み違えのせいだった。
dp[i][j]を、i日目までにj回勝率があがる場合の、最小のそれまでの勝利日数とする。
dp[i+1][]は、負けた場合と、勝率が上がりギリギリの勝利数の2パターンで計算していけば求まる。
最終的に、dp[N][j]がK以下になる最大のjが答えになる。

public class Solver
{
    const int INF = 500000 * 2000 + 1;

    int[] sum;
    List<int> _a;
    public int Solve(int n, int k, List<int> a)
    {
        if (a.Sum() == k) return 1;

        _a = a;
        sum = new int[a.Count()];
        sum[0] = a[0];
        for (int i = 1; i < a.Count(); i++)
        {
            sum[i] = sum[i - 1] + a[i];
        }

        var dp = new int[n, n + 1];
        for (int i = 0; i < n; i++) for (int j = 0; j < n + 1; j++) dp[i, j] = INF;
        for (int i = 0; i < n; i++) dp[i, 0] = 0;

        dp[0, 1] = a[0] > 0 ? 1 : 0;

        for (int i = 1; i < n; i++)
        {
            for (int j = 1; j < n + 1; j++)
            {
                dp[i, j] = Math.Min(dp[i - 1, j], GetMinWinNum(dp[i - 1, j - 1], i));
            }
        }

        var ret = 0;
        for (int i = 1; i < n + 1; i++)
        {
            if (dp[n - 1, i] > k) continue;
            ret = Math.Max(ret, i);
        }

        return ret;
    }

    int GetMinWinNum(int prevWinSum, int idx)
    {
        if (prevWinSum == INF) return INF;
        var prevWinRate = (double)prevWinSum / (double)sum[idx - 1];
        var needWinCnt = (int)Math.Ceiling(prevWinRate * (double)_a[idx]);
        if ((double)needWinCnt / (double)_a[idx] <= prevWinRate) needWinCnt++;
        if (needWinCnt > _a[idx]) return INF;
        return prevWinSum + needWinCnt;
    }
}

ARC056
A: みんなでワイワイみかん - AtCoder Regular Contest 056 | AtCoder

K個以上のみかんを買いたい。みかんは1個A円、もしくはL個B円。最小の支払金額を求めよ。A, B, C <= 10^9、L <= 10^9、B <= A*L

ぜんぶA円で買う・なるべくB円で買って残りをA円で買う・ぜんぶB円で買う、の３パターンしかない。intだとオーバーフローする。

static ulong Solve(ulong a, ulong b, ulong k, ulong l)
{
    return Math.Min(k * a, Math.Min((k / l) * b + (k % l) * a, ((k / l) + 1) * b));
}

B: 駐車場 - AtCoder Regular Contest 056 | AtCoder

駐車スペースがN個あり、それぞれ1~Nに番号が振られている。各駐車スペースは双方向にM本の道でつながっている。そして駐車スペースSが入口につながっている。車i(1~N)が順番に入口から入り、かつ自分の番号の駐車スペースに停めるとき、無事に駐車できる車はどれか。

駐車スペースiに車iが駐車できるというこは、Sからiまでに、i以上の頂点のみからなる経路が存在することと同じ。Dijkstra変種で解ける。

public class Solver
{
    public static IEnumerable<int> Solve(int n, int s, List<List<int>> e)
    {
        var dist = new int[n];
        for (int i = 0; i < n; i++) dist[i] = -1;

        var que = new PriorityQueue<ComparablePair<int, int>>();    //desc by score
        que.Push(new ComparablePair<int, int>(s, s));

        while (que.Count() > 0)
        {
            var nextPair = que.Pop();
            var score = nextPair.Item1;
            var node = nextPair.Item2;
            if (dist[node] >= score) continue;

            dist[node] = score;

            foreach (var next in e[node])
                que.Push(new ComparablePair<int, int>(Math.Min(next, score), next));
        }

        return Enumerable.Range(1, n).Where(v => dist[v - 1] >= v - 1);
    }
}

TLEに苦しんだけど、標準出力をFlushしてないというオチだった（ずっとアルゴリズムを疑って改善してた）。
以下のコードを忘れずに付けるようにしなければ。

Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false });
foreach (var r in Solver.Solve(n, s - 1, e))
{
    Console.WriteLine(r);
}
Console.Out.Flush();

C: 部門分け - AtCoder Regular Contest 056 | AtCoder

社員がN人いて、各社員間は信頼度w[i,j]が定まっている。この会社をいくつかの部門に分けるとき、スコアを最大化せよ。
スコアは、(部門の数) x K - (異なる部門に属する2人の信頼度の総和)
1<=N<=17, 1<=w[i,j]<=10^16, 1<=K<=10^16

次のように言い換えることができる

NxNの重み付き無向グラフの頂点を彩色する
使われた色の数xK-異なる色の間の重みの総和＝スコア
スコアの最大値はいくらか

Nが最大17であることに着目する。
DP[S]を頂点集合Sの解答だとすると、Sの部分集合tとuについて
　DP[S] = dp[t] + k - (t-u間の重みの総和)
となる。
ある集合xの重み総和sub[x]は、その部分集合y・zについて
　sub[x] = sub[y] + suz[z] + (y-z間の重みの総和)
なので、
　DP[S] = dp[t] + k - sub[S] + sub[t] + sub[u]
と変形することができる。

public int Solve(int n, int k, int[,] w)
{
    // すべての部分集合のコスト合計
    var sub = new int[1 << 17];
            
    for (int b = 0; b < 1 << n; b++)
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                if (((1 << i) & b) != 0 && ((1 << j) & b) != 0) sub[b] += w[i, j];

    // dp[S] は集合Sの解
    var dp = new int[1 << 17];
    for (int i = 0; i < 1 << n; i++)
        dp[i] = k;

    // Sを集合tと集合uに分解したとき、
    // dp[S]は dp[t] + k - sub[S] + sub[t] + sub[u] になる
    for (int s = 0; s < 1 << n; s++)
    {
        for (int t = (s - 1) & s; t > 0; t = (t - 1) & s)
        {
            dp[s] = Math.Max(dp[s], dp[t] + k - sub[s] + sub[t] + sub[s - t]);
        }
    }

    return dp[(1 << n) - 1];    //dp[1 << n - 1] は通らないので注意！
}

ARC055
A: 数え上げ - AtCoder Regular Contest 055 | AtCoder

1以上100以下の整数Nが与えられる。10^N+7を出力せよ。

1のあとN-1個のゼロを出力し、最後に7を出せばよい。

public string Solve(int n)
{
    var ret = new StringBuilder();
    ret.Append("1");
    for (int i = 0; i < n - 1; i++) ret.Append("0");
    ret.Append("7");
    return ret.ToString();
}

B: せんべい - AtCoder Regular Contest 055 | AtCoder

大きさ1～Nのせんべいがランダムな順番に与えられる。大きさはそれぞれ１つずつ。与えられた時点で、食べるか食べないかを決定する。すでに見たせんべいの大小関係のみ分かる。最適戦略をとったとき、最大のせんべいNを食べることができる確率はいくらか。ただし、K枚までしか食べることはできない。
1<=K<=N<=1000

難しかった…。
今のせんべいが過去最大なら、(1)食べる(2)食べないのどちらかになる。
i番目のせんべいが過去最大になる確率は1/i、そうでない確率は1-1/i。
DFSで解けるが、「これまでの最大をすでに食べたか否か」を持たないとうまく遷移できない。

public class Solver
{
    int _n;
    double[, ,] dp;
    public double Solve(int n, int k)
    {
        _n = n;

        dp = new double[n, k + 1, 2];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < k + 1; j++)
                for (int l = 0; l < 2; l++)
                    dp[i, j, l] = -1;

        return dfs(0, k, 0);
    }

    double dfs(int idx, int k, int ateMaxVal)
    {
        if (idx == _n) return ateMaxVal;
        if (dp[idx, k, ateMaxVal] != -1) return dp[idx, k, ateMaxVal];

        //current one is not max
        //rate: i - 1 / i
        var ret = ((double)(idx + 1 - 1) / (double)(idx + 1)) * dfs(idx + 1, k, ateMaxVal);

        //current one is max
        //rate: 1 / i

        //don't eat
        var temp = (1.0 / (double)(idx + 1)) * dfs(idx + 1, k, 0);

        //eat
        if(k > 0)
            temp = Math.Max(temp, (1.0 / (double)(idx + 1)) * dfs(idx + 1, k - 1, 1));

        ret+=temp;

        dp[idx, k, ateMaxVal] = ret;
        return ret;
    }
}

C: ABCAC - AtCoder Regular Contest 055 | AtCoder

長さNの文字列Sが与えられる。３つの空でない文字列A,B,Cを使い、S=ABCACと表現できる組み合わせは何通りか。

愚直に解いたら部分点になった。

public int Solve(char[] s)
{
    var ret = 0;
    for (int ai = 0; ai < s.Length; ai++)
        for (int ci = s.Length - 1; ci > ai; ci--)
            if (Meet(s, ai, ci)) ret++;
    return ret;
}

bool Meet(char[] s, int ai, int ci)
{
    var alen = ai + 1;
    var clen = s.Length - ci;
    var blen = s.Length - alen - alen - clen - clen;

    if(alen <= 0 || blen <= 0 || clen <= 0) return false;

    //check a
    while (ai >= 0)
    {
        if (s[ai] != s[alen + blen + clen + ai]) return false;
        ai--;
    }

    //check c
    while (ci < s.Length)
    {
        if (s[ci] != s[ci - clen - alen]) return false;
        ci++;
    }

    return true;
}

ABC/ACの切れ目を全探索してゆく。このとき、AとCが両方存在できれば有効になる。
ACの存在を効率よく判定する方法は、ローリングハッシュでの二分探索や、Z-algorithmを使うやり方がある。
参考
ローリングハッシュ：蟻本(第二版)P.332
Z-algorithm：文字列の頭良い感じの線形アルゴリズムたち３ - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ

ARC054
A: 動く歩道 - AtCoder Regular Contest 054 | AtCoder

円周Lの動く歩道がある。動く歩道は、時計回りに1秒間にs進んでいる。唯一の出口が最北点から時計回りに距離Dにあり、いま距離Sにいる。1秒間にY歩けるとき、最短で何秒後に出口に着けるか。

時計回りと反時計回りを試す。

public double Solve(int l, int x, int y, int s, int d)
{
    double leftDist = s > d ? Math.Abs(s - d) : l - Math.Abs(s - d);
    double rightDist = d > s ? Math.Abs(s - d) : l - Math.Abs(s - d);

    return s == d ? 0.0 : Math.Min(rightDist / (double)(y + x), y - x <= 0 ? double.MaxValue : leftDist / (double)(y - x));
}

B: ムーアの法則 - AtCoder Regular Contest 054 | AtCoder

現在のコンピューター性能でP年かかるタスクがある。コンピューターは、1.5年ごとに処理能力が2倍になる。なるべく早いタスクの終了時間を求めよ。（タスクは中断できないものとする）
0<=P<=10^18

x年後にタスク処理を始めるとするとき、終了時間はx+P/(2^(x/1.5))になる。これは凸関数なので、三分探索で求めることができる。
間違えてタスクの開始時間を返していたのに気づかず手間取った。
ちなみに、微分すれば一発で答えが出せるようだ。

public double Solve(double p)
{
    double l = 0;
    double r = p;

    //ternary search
    while(r - l > 1E-10)
    {
        var m1 = l + (r - l) / 3.0;
        var m2 = l + (r - l) * 2.0 / 3.0;

        var t1 = m1 + p / Math.Pow(2.0, m1 / 1.5);
        var t2 = m2 + p / Math.Pow(2.0, m2 / 1.5);

        if (t1 < t2)
        {
            r = m2;
        }
        else
        {
            l = m1;
        }
    }

    return (l + r) / 2.0 + p / Math.Pow(2.0, ((l + r) / 2.0) / 1.5);    //この計算を忘れていた
}

ARC053
A: ドミノ色塗り - AtCoder Regular Contest 053 | AtCoder

H x Wのタイルがある。上下または左右に隣り合う２マスを選びたい。選び方は何通りか。

2 x W x H - (W + H) が答え。

Console.WriteLine(2 * h * w - w - h);

B: 回文分割 - AtCoder Regular Contest 053 | AtCoder

英小文字からなる文字列Sを適当にならびかえ、それを分割していくつかの回文文字列を作る。この回文文字列の長さの最小値をなるべく大きくしたい。この値を求めよ。

奇数個の文字を１つずつ、出来上がる回文文字列の中心に配置する。そして残った文字（すべて偶数個）をなるべく均等に割り振ればよい。

public static int Solve(string s)
{
    var num = new int[26];
    foreach (var c in s) num[c - 'a']++;

    var devideNum = 0;
    foreach (var n in num) if (n % 2 == 1) devideNum++;

    if(devideNum == 0) return s.Length;

    var ret = 1 + (((s.Length - devideNum) / 2) / devideNum) * 2;
    return ret;
}

C: 魔法使い高橋君 - AtCoder Regular Contest 053 | AtCoder

N個の魔法がある。i番目の魔法を唱えると、a[i]℃温度が上がったのち、b[i]℃温度が下がる。魔法を唱える順番を調整し、気温の最大値をなるべく小さくしたい。この気温を答えよ。

温度が下がる魔法と上がる魔法に分け、下がる魔法をa[i]の昇順、上がる魔法をb[i]の降順でソートする。あとは下がる魔法→上がる魔法の順番で唱える。

public static Int64 Solve(int n, Int64[][] m)
{
    var magics_dec = m.Where(v => v[0] < v[1]).OrderBy(v => v[0]);
    var magics_inc = m.Where(v => v[0] >= v[1]).OrderByDescending(v => v[1]);

    Int64 ret = 0, cur = 0;
    foreach (var magic in magics_dec.Concat(magics_inc))
    {
        ret = Math.Max(ret, cur + magic[0]);
        cur += magic[0] - magic[1];
    }
    return ret;
}

これもintだとオーバーフローする。
部分的に正答になったときは、まずオーバーフローを疑うのが基本になりそう。

2016-07-11

Topcoder Open 2016 Marathon Match(Round 3)の参加日記

C# プログラミングコンテストマラソンマッチ Topcoder

制約が多くて面倒な問題だった。そのせいか、レート中位~下位の参加者がずいぶん少なかった。
結果は暫定62位/101人の定位置。

問題概要

長さ１の正方形セルSxS個で構成されるマップがある
各セルはタイプ（0~9）が設定されている
マップ上にはN個のアイテムとN個のターゲットがある
アイテムの近く（距離10^-3以内）に止まると、該当アイテムを拾う
ターゲットの近くで止まると、持っているアイテムを落とす
1つのターゲットに落とすのは1つのアイテム
持てるアイテムの最大値はcapacityで与えられる
すべてのアイテムをターゲットに落とさなければならない
スタート地点はマップの外周から距離10^-3以内ならどこでもよい
このとき、なるべく小さいコストで全アイテムをターゲットに落とすのが目的
コストは、セルタイプx移動距離。タイプの違うセルをまたぐときは、さらにタイプ差の二乗が可算される
1回のステップでは、1つ以内のセルしかまたげない
セルボーダーから距離10^-3以内には止まってはならない。
ステップ間は10^-3以上の距離をおくこと
S:10~50、タイプ数2~10、アイテム数:5~S*S/10、capacity:1~10

https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16704&pm=14283

方針

Dijkstraでアイテム・ターゲット・エッジセル間の距離を求める
Dijkstraの結果を使い、アイテムとターゲットでTSP（ビームサーチ）
TSP結果から有効解を作成（経路復元）
有効解を改善（貪欲＋焼きなまし）

上位との比較

全体的な方針は一緒
TS部分で大きな差がついている
TSは焼きなましの人と、2optなどTSP特有のアルゴリズムの人がいる
Dijkstraも、単純なセル間ではなくセルをさらに分割してる人もいた

反省
TSP部分で大きなスコア差が付いている。TSPがイマイチなのは気づいていたが、それより4の改善部分に時間を使ってしまった。
目についた部分を適当に改善するのではなく、どこに手を付けるべきかまず分析するべきだった。

2016-06-25

Topcoder Marathon Match Round90 勉強メモ

プログラミングコンテストマラソンマッチ Topcoder

2位のEvbCFfp1XBさんのコードを読んでみる。
https://community.topcoder.com/longcontest/?module=ViewProblemSolution&pm=14094&rd=16495&cr=23100980&subnum=3

問題文はこちら。
https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16495&pm=14094

方針（Forumより）

ランダムに~~ポイント0~~ポイント1未満のターゲットを選ぶ ※コードより修正
ターゲットにポイント1が入るか、ループ回数が10になるまで以下を繰り返す

ターゲット近くの同色ボールを選ぶ
そのボールの近くのボールを1~10個選ぶ ※上で選んだボール含む
選んだボールでビームサーチ（Max Depth=20、幅250)

情報の持ち方

class Board {
    public static final int WALL = 1 << 27;
    public static final int EMPTY = 1 << 28;
    public static final int[] DR = { 0, 1, 0, -1, };
    public static final int[] DC = { -1, 0, 1, 0, };
    public static final int[] DELTA = { -1, 64, 1, -64, };
    public static final int SHIFT = 6;
    public static final int MASK = (1 << SHIFT) - 1;
    public static final int[] ballIndex = new int[64 * 64];
    public static final long[][] hashes = new long[64 * 64][10];
    public int[][] distanceFromTarget;
    public static final int[] targetIndex = new int[64 * 64];
    public List<ColoredPoint> balls = new ArrayList<>();
    public List<ColoredPoint> targets = new ArrayList<>();
    public int R;
    public int C;
    public long hash = 0;
    int countPoint1;
    private ArrayList<State> moveHistory = new ArrayList<>();  // ボールを動かした履歴

    /// 省略 ///

    // ボールをある方向へ動かす
    public void next(int ballIndex, int direction) {
        ColoredPoint ball = balls.get(ballIndex);

        State current = new State(null, ballIndex, ball.z, direction, 0);
        moveHistory.add(current);
        {
            int index1 = targetIndex[ball.z];
            if (index1 != EMPTY && getTargetColor(index1) == ball.color) {
                countPoint1--;
            }
        }
        hash ^= hashes[ball.z][ball.color];

        // ボールを転がす。この更新のやりかたは参考になる  DELTA = { -1, 64, 1, -64, };
        int delta = DELTA[direction];
        int z = ball.z;
        this.ballIndex[z] = EMPTY;
        do {
            z += delta;
        } while (this.ballIndex[z] == EMPTY);
        z -= delta;
        ball.z = z;
        this.ballIndex[z] = ballIndex;

        hash ^= hashes[ball.z][ball.color];
        {
            int index1 = targetIndex[ball.z];
            if (index1 != EMPTY && getTargetColor(index1) == ball.color) {
                countPoint1++;
            }
        }
    }

    /// 省略 ///
}

class State {
    State parent;
    public int index;
    public int z;
    public int direction;
    public double score;
    public int numMoves;

    /// 省略 ///
}

class State2 implements Comparable<State2> {
    State2 parent;
    public int index;
    public int z;
    public int direction;
    public double score;
    public double distance;  // ビームサーチ用。ターゲットまでの（最短）距離合計
    public int numMoves;

    /// 省略 ///
}

巨大なboardクラスを用意している。履歴はStateクラスで持つ。State2はビームサーチ用。

メインルーチン

private void solve() {
    for (; timeManager.getSecond() < 9.5;) {

        if (board.getScorePoint1() > 0.999) {
            break;
        }

        // スコアが1未満のターゲット
        ArrayList<Integer> targetsScore0 = getTargetsScore0();

        // ランダムに１つ選ぶ
        IntArray targetIndexes = new IntArray();
        int targetIndex = targetsScore0.get((int) (targetsScore0.size() * rng.nextDouble()));
        targetIndexes.add(targetIndex);

        // 近隣ボールの選ぶ数。ランダムに試す
        int[] ns = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, };
        Utils.shuffle(ns, rng);
        for (int maxN : ns) {
            if (board.getTargetScore(targetIndex) > 0.999) {
                break;
            }
            if (timeManager.getSecond() > 9.5) {
                break;
            }

            // ターゲットから最寄りの同色ボール
            int nearestSameColorBallIndex = getSameColorScore0BallsDistanceFromTargetAscending(targetIndex).get(0).second;

            ArrayList<Pair<Double, Integer>> balls = getBallsDistanceFromBallAscending(nearestSameColorBallIndex);

            // 同色ボールの近くのボールmaxN個
            IntArray ballIndexes = new IntArray();
            int n = Math.min(maxN, balls.size());
            for (int i = 0; i < n; i++) {
                ballIndexes.add(balls.get(i).second);
            }

            int currentNumMoves = board.numMoves();
            int maxStep = 20;
            int maxBeamWidth = (int) (5 * 1000 / maxStep);
            countBeamsearch++;

            // ビームサーチ
            ArrayList<State> moves = beamsearch(ballIndexes, maxStep, maxBeamWidth, targetIndexes);

            if (moves == null) {
                continue;
            }
            for (State state : moves) {
                assert board.canMove(state.index, state.direction);
                board.next(state.index, state.direction);
            }

            // ベストスコアなら保持
            if (board.getScorePoint1() > bestScore && board.numMoves() < board.maxNumRolls()) {
                bestScore = board.getScorePoint1();
                bestSolution = board.getSolution();
            } else {
                // ベストでなく、ターン数に余裕がないようなら棄却
                if ((double) board.numMoves() / board.maxNumRolls() > 0.99 * timeManager.getSecond() / 9.5) {
                    for (; board.numMoves() > currentNumMoves;) {
                        board.previous();
                    }
                }
            }
        }
    }
}

単純にN個のボールを選ぶのではなく、1個～10個と少ないほうから試している。後の参考になりそう。

ビームサーチの部分

// 動かすボール、最大深さ、ビーム幅、対象ターゲット（１つだけ）
private ArrayList<State> beamsearch(IntArray ballIndexes, int maxStep, int maxBeamWidth, IntArray targetIndexes) {
    ArrayList<State2> currents = new ArrayList<>();
    ArrayList<State2> nexts = new ArrayList<>();
    ArrayList<State2> all = new ArrayList<>();  // 探索にでてきた全ノード。最後に一番いいやつを選ぶ

    int currentNumMoves = board.numMoves();

    used.clear();
    used.add(board.hash);

    // 初手の集合currentsを得る
    for (int i = 0; i < ballIndexes.length; i++) {
        int ballIndex = ballIndexes.values[i];
        ColoredPoint ball = board.balls.get(ballIndex);
        int z = ball.z; // zはボール位置のIntパック
        for (int direction = 0; direction < 4; direction++) {
            if (!board.canMove(ballIndex, direction)) {
                continue;
            }

            board.next(ballIndex, direction);
            if (used.add(board.hash)) {
                double score = getSumScore(ballIndexes);
                double distance = getSumMinDistance(ballIndexes, targetIndexes);
                distance += 1e-2 * rng.nextDouble();
                currents.add(new State2(null, ballIndex, z, direction, score, distance, 1));
            }
            board.previous();
        }
    }


    for (int step = 0; step < maxStep; step++) {
        if (currents.size() == 0) {
            break;
        }
        int beamWidth = Math.min(maxBeamWidth, currents.size());            
        Utils.select(currents, 0, currents.size(), beamWidth);  // currentsをスコア＞距離でソートか？最初のビーム幅分のみ抽出？
        for (int beam = 0; beam < beamWidth; beam++) {
            State2 currentState = currents.get(beam);

            all.add(currentState);

            {
                ArrayList<State2> currentStateList = reverse2(toList(currentState));    // 初手からcurrentStateまでの手のリスト
                ArrayList<State> res = new ArrayList<>();
                for (State2 state : currentStateList) {
                    res.add(new State(null, state.index, state.z, state.direction, state.score));
                }

                board.set(res, currentNumMoves);   // boardをcurrentStateにする
            }

            {
                assert getSumScore(ballIndexes) == currentState.score;
                if (currentState.score > ballIndexes.length - 1e-9) {
                    break;
                }
            }
            for (int i = 0; i < ballIndexes.length; i++) {
                int ballIndex = ballIndexes.values[i];
                ColoredPoint ball = board.balls.get(ballIndex);
                int z = ball.z;
                for (int direction = 0; direction < 4; direction++) {
                    if (!board.canMove(ballIndex, direction)) {
                        continue;
                    }

                    int nextZ = board.simulateNext(ball, direction);    // 該当の方向へ動かしてみたときのz

                    long currentHash = board.hash;

                    boolean add = used.add(currentHash ^ (board.hashes[z][ball.color] ^ board.hashes[nextZ][ball.color]));

                    // 使ってないHashになるなら
                    if (add) {
                        // scoreとdistanceを計算
                        double nextScore = currentState.score;
                        {
                            int index1 = board.targetIndex[z];
                            if (index1 != Board.EMPTY && board.getTargetColor(index1) == ball.color) {
                                nextScore--;
                            }
                        }
                        {
                            int index1 = board.targetIndex[nextZ];
                            if (index1 != Board.EMPTY && board.getTargetColor(index1) == ball.color) {
                                nextScore++;
                            }
                        }
                        double score = nextScore;

                        double nextDistance = currentState.distance;
                        int targetIndex = targetIndexes.values[0];
                        if (board.distanceFromTarget[targetIndex][z] == 0 && board.getTargetColor(targetIndex) != ball.color) {
                            nextDistance -= 1e9;
                        } else {
                            nextDistance -= board.distanceFromTarget[targetIndex][z];
                        }
                        if (board.distanceFromTarget[targetIndex][nextZ] == 0 && board.getTargetColor(targetIndex) != ball.color) {
                            nextDistance += 1e9;
                        } else {
                            nextDistance += board.distanceFromTarget[targetIndex][nextZ];
                        }
                        double distance = nextDistance;

                        distance += 1e-2 * rng.nextDouble();    // これは・・・？
                                                                // ちょっとバラけさせると探索が良くなるのか？

                        // 次手の集合nextsに加える
                        nexts.add(new State2(currentState, ballIndex, z, direction, score, distance, currentState.numMoves + 1));
                    }
                }
            }
        }
        {
            ArrayList<State2> swap = currents;
            currents = nexts;
            nexts = swap;
        }
        nexts.clear();

    }
    for (; board.numMoves() > currentNumMoves;) {
        board.previous();
    }

    if (all.size() == 0) {
        return null;
    }

    Collections.sort(all);
    ArrayList<State2> allList = reverse2(toList(all.get(0)));
    ArrayList<State> res = new ArrayList<>();
    for (State2 state : allList) {
        res.add(new State(null, state.index, state.z, state.direction, state.score));
    }
    return res;

}

ループで幅優先ビームサーチをしている。各NodeはState2クラスで保持していて、これが親へのポインタを持っているようだ。

この人のコードはかなり読みやすかった。
Javaだからか、それとも書き方が自分に似ているからだろうか。いずれにしても、とても参考になる。

かなり強い方なので、他のマッチのコードも読んでみても良さそうだ。