Codechef June Challenge 2017 参加日記

966位/9366人の自己ワースト記録。追い上げが甘かった。以下、易しい問題(全体の正答率が高いもの)は省略する。

Chef and the Feast

N個の料理と、それぞれを食べたときの満足度A[i]が与えられる。次の条件ですべての料理を食べたとき、得られる満足度の合計を最大化せよ。
・料理からSubsetを選択
・Subsetを食べる。このときの満足度は、Subsetの数x各満足度の和
1 <= N <= 10^5
-10^8 <= A[i] <= 10^8

基本的に満足度が正の料理は1つのSubsetとして食べ、負の料理は1つずつ食べる。ただし、あまり負の値が大きくないものは、正のSubsetに加えたほうが良い場合もある。なので負のものを小さい順に正のSubsetに加えて試していけばよい。

public static long GetAns(long[] a)
{
    var negs = a.Where(v => v < 0).OrderByDescending(v => v).ToArray();
    var posCnt = a.Count(v => v >= 0);
    var posSum = a.Where(v => v >= 0).Sum();

    var ret = posCnt * posSum + negs.Sum();

    var allNegSum = negs.Sum();
    if (negs.Count() > 0)
    {
        var negsSum = 0L;
        for (int i = 0; i < negs.Length; i++)
        {
            negsSum += negs[i];
            var newRet = (posCnt + (i + 1)) * (posSum + negsSum) + (allNegSum - negsSum);
            ret = Math.Max(ret, newRet);
        }
    }

    return ret;
}


Pairwise union of sets

整数[1,K]のSubsetがN個与えられる。Subsetからペアを選んだとき、そのUnionが1~Kすべてを含む組み合わせ数を求めよ。
1 <= N, K <= 2500
1 <= len[i] <= K
1 <= len[1] + len[2] + ... + len[N] <= 10000
(len[i]はSubset[i]の長さ)

Subsetのペア組み合わせすべてを判定すればよい。各Subsetの状態(最大2500ビット分)をInt64型の配列で表せば、計算量はO(N^2 * K/64)程度なので間に合う。

static Bit[] bits = new Bit[2501];

public static long GetAns(int n, int k, List<int[]> sets)
{
    for (int i = 0; i < sets.Count; i++) bits[i] = new Bit(sets[i]);

    long ret = 0;
    for (int i = 0; i < sets.Count() - 1; i++)
    {
        for (int j = i + 1; j < sets.Count(); j++)
        {
            if (bits[i].Match(bits[j], k)) ret++;
        }
    }
    return ret;
}

public class Bit
{
    public ulong[] Data = new ulong[40];

    public Bit(int[] listData)
    {
        foreach (var data in listData) Set(data - 1);
    }

    public void Set(int idx)
    {
        Data[idx / 64] |= (1ul << idx % 64);
    }

    public bool Match(Bit b2, int k)
    {
        if (k % 64 != 0)
        {
            var idx = k / 64;
            var val = Data[idx] | b2.Data[idx];
            if (val != (1UL << k % 64) - 1) return false;
            k -= k % 64;
        }

        for (int i = 0; i < k; i += 64)
        {
            var d = Data[i / 64] | b2.Data[i / 64];
            if (d != ulong.MaxValue) return false;
        }

        return true;
    }
}


Triplets

3つの整数を引数にとる関数f(x,y,z)は、y>=xかつy>=zのときは(x+y)*(y+z)、それ以外ならゼロを返す。配列A、B、Cが与えられたとき、f(A[i], B[j], C[k])の合計を求めよ。解答は1000000007でMODして出力すること。
1 <= len(A), len(B), len(C) <= 100000
1 ≤ A[i], B[i], C[i] ≤ 1000000000

Bを固定値bで考える。さらに、A・Cからb以上の要素のみ取り出した配列をそれぞれa、cとする。
a: a[0], a[1], a[2],...
b
c: c[0], c[1], c[2],...
すると求める値は、
(a[0]+b)(b+c[0])+(a[0]+b)(b+c[1])+ ... +
(a[1]+b)(b+c[0])+(a[1]+b)(b+c[1])+ ....
...
となる。これを変形すると
(a[0]+b)*{(cの数)*b + (cの合計)}+
(a[1]+b)*{(cの数)*b + (cの合計)}+
...
それぞれの右辺が同じなので
{(aの合計)+(aの数)*b)}*{(cの数)*b + (cの合計)}
となる。
Aからb以上の要素を取り出すのには、予めAをソートして二分探索を使えばよい。
(a[]の合計)などは、予めAをソートし、合計していったものを配列で持っておけば簡単に求められる。
サンプルはC++。C#だとTLEになってしまうようだ。CodechefのC#はバージョンが低いせいか、Array.Sort()がちょっと遅い気がする。

long long MOD = 1000000007;
 
void getSumArray(long long *ar, long long *ret, int n)
{
    for (int i = 0; i < n; i++)
    {
        ret[i] = ((i == 0 ? 0 : ret[i - 1]) + ar[i]) % MOD;
    }
}
 
int main()
{
    int t;
    scanf("%d", &t);
 
    while ( t > 0 )
    {
        int p, q, r;
        scanf("%d %d %d", &p, &q, &r);
 
        long long a[p];
        long long b[q];
        long long c[r];
 
        for(int i = 0; i < p ; i++)
        {
            scanf("%lld", &a[i]);
        }
        for(int i = 0; i < q ; i++)
        {
            scanf("%lld", &b[i]);
        }
        for(int i = 0; i < r ; i++)
        {
            scanf("%lld", &c[i]);
        }
        
        sort(a, a + p);
        sort(c, c + r);
 
        long long aSum[p];
        long long cSum[r];
 
        getSumArray(a, aSum, p);
        getSumArray(c, cSum, r);
 
        long long ret = 0;
        for (int i = 0; i < q; i++)
        {
            long long y = b[i];
            int aUb = min(p - 1, lower_bound(a, a + p, y + 1) - a - 1);
            int cUb = min(r - 1, lower_bound(c, c + r, y + 1) - c - 1);
            
            if (aUb < 0 || cUb < 0) continue;
 
            ret += ((aUb + 1) * y % MOD + aSum[aUb]) * ((cUb + 1) * y % MOD + cSum[cUb]) % MOD;
            ret %= MOD;
        }
 
        cout << ret << endl;
        t--;
    }
} 


Chef and Prime Queries

長さNの整数列Aがある。整数L,R,X,YからなるクエリがQ個与えられるので、それぞれに対し次の疑似コード結果を回答せよ。

F(L, R, X, Y) {
     result := 0
     for( i = X to i = Y )  {
         if( isPrime(i) ) {
             for( j = L to j = R ) {
                  number := a[j]
                  exponent := 0
                  while( number % i == 0 ) {
                     exponent := exponent + 1 
                     number := number/i
                  }
                  result := result + exponent
              }
         }
     }
     return result
}

1 <= N, Q <= 10^5
1 <= L <= R <= N
1 <= X <= Y <= 10^6
2 <= A[i] <= 10^6

問題を言い換えると、
・Aの部分配列[L:R]を抜き出し、
・要素それぞれの素因数のうち、X以上Y以下の部分について
・階乗部分の合計を求めよ
となり、セグメント木で解くことができる。各セグメントには、範囲内の素因数分解した値を配列でもつ。たとえば
A[0]=12, A[1]=10, A[2]=18
だとすると、セグメントでもつ値は
Seg[0]=[2,2,3]
Seg[1]=[2,5]
Seg[2]=[2,3,3]
Seg[0:1]=[2,2,2,3,5]
Seg[1:2]=[2,2,3,3,5]
Seg[0:2]=[2,2,2,2,2,3,3,3,5,5]
となる。あとは対象セグメントからX以上Y以下の要素数を回答すればよい(二分探索)。

public static List<int> GetAns(int[] a, List<Tuple<int, int, int, int>> queries)
{
    var sieve = GetSieve(1000001);
    var factTable = GetFactTable(a, sieve);

    var segTree = new SegTree(a, factTable);

    return queries.Select(q => segTree.Query(q.Item1 - 1, q.Item2, q.Item3, q.Item4)).ToList();
}

public static List<List<int>> GetFactTable(int[] a, int[] sieve)
{
    var ret = new List<List<int>>();
    foreach (var v in a) ret.Add(GetFactList(v, sieve));
    return ret;
}

public static List<int> GetFactList(int value, int[] sieve)
{
    var ret = new List<int>();

    while (true)
    {
        if (sieve[value] == 0)
        {
            ret.Add(value);
            break;
        }
        ret.Add(sieve[value]);
        value /= sieve[value];
    }

    ret.Reverse();
    return ret;
}

public static int[] GetSieve(int n)
{
    var ret = new int[n + 1];
    for (int i = 0; i < ret.Length; i++) ret[i] = 0;
    ret[0] = ret[1] = -1;
    for (int i = 2; i < ret.Length; i++)
    {
        if (ret[i] != 0) continue;
        for (int j = i + i; j < ret.Length; j += i)
        {
            ret[j] = i;
        }
    }
    return ret;
}

public class SegTree
{
    int _n;
    SegNode[] _dat;

    public class SegNode
    {
        // sorted
        public List<int> Factors;

        public SegNode(List<int> factors)
        {
            Factors = factors;
        }

        public SegNode(SegNode s1, SegNode s2)
        {
            if (s1 == null && s2 != null)
            {
                Factors = s2.Factors;
                return;
            }
            if (s1 != null && s2 == null)
            {
                Factors = s1.Factors;
                return;
            }
                
            Factors = new List<int>();
            if (s1 == null && s2 == null) return;

            int l1 = 0, l2 = 0;
            while (l1 < s1.Factors.Count() && l2 < s2.Factors.Count())
            {
                while (l1 < s1.Factors.Count() && l2 < s2.Factors.Count() && 
                    s1.Factors[l1] < s2.Factors[l2])
                {
                    Factors.Add(s1.Factors[l1]);
                    l1++;
                }
                while (l1 < s1.Factors.Count() && l2 < s2.Factors.Count() && 
                    s1.Factors[l1] > s2.Factors[l2])
                {
                    Factors.Add(s2.Factors[l2]);
                    l2++;
                }
                while (l1 < s1.Factors.Count() && l2 < s2.Factors.Count() && 
                    s1.Factors[l1] == s2.Factors[l2])
                {
                    Factors.Add(s1.Factors[l1]);
                    l1++;
                    Factors.Add(s2.Factors[l2]);
                    l2++;
                }
            }
            while (l1 < s1.Factors.Count())
            {
                Factors.Add(s1.Factors[l1]);
                l1++;
            }
            while (l2 < s2.Factors.Count())
            {
                Factors.Add(s2.Factors[l2]);
                l2++;
            }
        }

        public int Query(int x, int y)
        {
            var ret = LowerBound(Factors, y + 1);
            if (ret >= Factors.Count()) ret = Factors.Count();

            var xl = UpperBound(Factors, x - 1);
            if (xl > 0) ret -= xl;
            return ret;
        }

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

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

            return ub;
        }

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

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

            return lb + 1;
        }
    }

    int[] _a;
    List<List<int>> _factTable;

    public SegTree(int[] a, List<List<int>> factFable)
    {
        _a = a;
        _factTable = factFable;

        _n = 1;
        while (_n < a.Count()) _n *= 2;
        ConstructTree();
    }

    void ConstructTree()
    {
        _dat = new SegNode[_n * 2];
        ConstructTree(0, 0, _a.Count());
    }

    void ConstructTree(int k, int l, int r)
    {
        // bottom-most
        if (l == r - 1)
        {
            _dat[k] = new SegNode(_factTable[l]);
            return;
        }

        ConstructTree(k * 2 + 1, l, (l + r) / 2);
        ConstructTree(k * 2 + 2, (l + r) / 2, r);
        _dat[k] = new SegNode(_dat[k * 2 + 1], _dat[k * 2 + 2]);
    }

    public int Query(int a, int b, int x, int y)
    {
        return Query(a, b, 0, 0, _a.Count(), x, y);
    }

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


Saboteur (Challenge)

ノード数N・エッジ数Mからなる連結の無向グラフがある。ノードの破壊にはcost[i]の費用がかかる。なるべく少ないコストで、グラフからループを取り除いたときのトータルコストを求めよ。ただし、最終的なグラフは連結でなければならない。
1 <= N <= 10^4
N-1 <= M <= 5*10^4
1 <= cost[i] <= 10^5
テストケースは、(1)N<=20(2)N<=40(3)M=N(4)M<=N+3(5)完全グラフ(6)ランダム、のいずれかの条件で作成される。

次の方針で平均より少し上くらいの結果だった。
1、完全グラフのとき(M=N*(N-1)/2)は、最もコストの大きい2ノード以外をすべて破壊して終了
2、次数1のノードを、隣のノードにまとめてしまう(コストは合算する)。これでループの一部となるノードのみとなる
3、次数とコストの降順+乱数でノードを並び替える
4、ノードをひとつずつ取り出して、閉ループができないようにグラフを作っていく
5、あまったノードは破壊対象とし、解答の候補に入れる
6、時間があるなら3へ戻る
実装:https://www.codechef.com/viewsolution/14190840
上位陣は完全グラフかどうかだけでなく、6つのデータタイプのそれぞれを判断して別のロジックを用意しているようだ。
例:https://www.codechef.com/viewsolution/14237992

HackerRank Week of Code 33 参加日記

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


Transform to Palindrome

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

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

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

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

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

(UnionFindの実装は省略)


Palindromic table

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    return ret;
}

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

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

    return ret;
}

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


Bonnie and Clyde

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    List<SortedSet<int>> _nodeToComponentIds;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

        if (a == b) return a;

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

        return DP[0][a];
    }

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

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

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

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

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

Codechef May Challenge 2017 参加日記

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

Chef and his daily routine

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

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

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

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

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


Courses in an university

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

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

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


Median of adjacent maximum numbers

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

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

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

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

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


Chef and Sub Array

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

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

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

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

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

    var ret = new List<int>();

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

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

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

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

    return ret;
}

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

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

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

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

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


Blocked websites

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

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

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

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

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

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

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

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

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

    return ret;
}

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

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

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

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

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

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


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

            return Children[c - 'a'];
        }

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

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

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

    Node _root = new Node(false);

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

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

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

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

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

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

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

        return ret;
    }
}


Chef and Subsequences

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

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

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

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

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

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

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

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

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

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

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


Gotham PD

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

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

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

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

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

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

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

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

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

            last_ans = min_ans ^ max_ans;
        }
    }
}

public class Graph
{
    public static int TRIE_THRES = 11000; 

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

    class Node
    {
        public int Key;
        public Node Parent;

        public int Depth;

        public Trie Trie;

        public Node ParentTrieNode;

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

            Depth = depth;

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

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

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

            return ret;
        }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

        return curNode.Key ^ key;
    }
}


Long Sandwich

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

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



Chef and Battleship

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

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

HackerRank Week of Code 32 参加日記

396位/8447人の不本意な結果。レートも少し落ちた。
以下、Easy問題は省略する。


Circular Walk

次の式が与えられる。
 { R[i]  = (R[i-1] \times g + seed) \, mod \, p }
円周上にn個の点(0~n-1)があったとき、点iから距離R[i]までジャンプすることができる。たとえばR[i]が2であれば、{i-1, i-1, i, i+1, i+2}へジャンプできる。点sから点tまでの最少ジャンプ数を答えよ。不可能な場合は-1を出力すること。
1 <= n <= 10^7
0 <= s, t <= n
1 <= p <= n
0 <= R[0], g, seed < p

現在地から到達できる最小点と最大点を保持してイテレーションしていけばよい。セグメント木で効率よく求められそうだが、nが小さいので愚直にループして間に合う。実装では面倒なエッジ処理を避けるため、最初にR[]を3つつなげ直線とみなして解いた。

public static int GetAns(int n, int s, int t, int r_0, int g, int seed, int p)
{
    var r = GetR(r_0, n, g, seed, p);
    return GetAns(n, s, t, r);
}

public static int[] GetR(int r_0, int n, int g, int seed, int p)
{
    var ret = new int[n];
    ret[0] = r_0;
    for (int i = 1; i < n; i++)
    {
        ret[i] = (ret[i - 1] * g + seed) % p;
    }
    return ret;
}

public static int GetAns(int n, int s, int t, int[] r)
{
    var newR = new int[r.Length * 3];
    for (int i = 0; i < r.Length; i++)
    {
        newR[i] = newR[i + n] = newR[i + 2 * n] = r[i];
    }

    var ts = new List<int>{ t, t + n, t + 2 * n };
    var left = s + n;
    var right = s + n;
    var oldLeft = -1;
    var oldRight = -1;

    var ret = 0;
    while (true)
    {
        if (left < 0 || right >= newR.Length) break;  //fail safe

        foreach (var tc in ts)
        {
            if (left <= tc && tc <= right) return ret;
        }

        var newLeft = left;
        var newRight = right;

        var cur = left;
        while (cur <= right)
        {
            if (oldLeft != -1 && cur == oldLeft) cur = oldRight + 1;

            newLeft = Math.Min(newLeft, cur - newR[cur]);
            newRight = Math.Max(newRight, cur + newR[cur]);

            cur++;
        }

        if (newLeft == left && newRight == right) break;    //no change -> no answer
        oldLeft = left;
        oldRight = right;
        left = newLeft;
        right = newRight;

        ret++;
    }

    return -1;
}


Geometric Trick

a,b,cからなる長さnの文字列sがある。次を満たす(i,j,k)の組み合わせ数を答えよ。

  • s[i] = "a", s[j] = "b", s[k] = "c"
  • (j + 1)^2 = (i + 1)(k + 1)

1 <= n <= 5 x 10^5

i*kが平方数のとき、iの素因数のうちべき乗数が奇数のものと、とkの素因数のうちべき乗数が奇数のものが一致する。たとえば
i = 3^2 * 5^1 * 7*2
k = 5^3 * 11*2
とすると、べき乗数が奇数になっている素因数はi、kともに5で一致しているため、i*kは平方数になる。
これを利用し、i、kすべてについてこの情報(べき乗数が奇数の素因数組み合わせ)が同じものどおしで、i*kがj*jの集合に存在するかチェックすればよい。情報の一致不一致はHash化して判断する。また、素因数分解はエラトステネスの篩の応用で高速に求められる。

// s[i] = 'a', s[j] = 'b', s[k] = 'c'
// (j + 1) ^ 2 = (i + 1)(k + 1)
public static long GetAns(string s)
{
    var Is = new List<int>();
    var J_pows = new HashSet<long>();
    var Ks = new List<int>();
    for (int i = 0; i < s.Length; i++)
    {
        if (s[i] == 'a') Is.Add(i + 1);
        if (s[i] == 'b') J_pows.Add((long)(i + 1) * (i + 1));
        if (s[i] == 'c') Ks.Add(i + 1);
    }

    // sieve (2-s.Length + 1)
    var p = new int[s.Length + 2];
    for (int i = 2; i < p.Length; i++)
    {
        if (p[i] != 0) continue;
        for (int j = i; j < p.Length; j += i) p[j] = i;
    }

    // hash list
    var rnd = new Random();
    var hashList = new long[s.Length + 2];
    for (int i = 1; i < hashList.Length; i++) hashList[i] = ((hashList[i - 1] * 37L + 123847L) << 31) + rnd.Next();

    // prime hash => i/j values
    var i_hashes = GetHashes(Is, p, hashList);
    var k_hashes = GetHashes(Ks, p, hashList);

    var ret = 0L;

    foreach (var hash in i_hashes.Keys)
    {
        foreach (var i in i_hashes[hash])
        {
            if (!k_hashes.ContainsKey(hash)) continue;
            foreach(var k in k_hashes[hash])
            {
                if (J_pows.Contains((long)i * k)) ret++;
            }
        }
    }

    return ret;
}

static Dictionary<long, List<int>> GetHashes(List<int> values, int[] primes, long[] hashes)
{
    var ret = new Dictionary<long, List<int>>();
    foreach (var v in values)
    {
        var hash = GetHash(v, primes, hashes);
        if (!ret.ContainsKey(hash)) ret.Add(hash, new List<int>());
        ret[hash].Add(v);
    }
    return ret;
}

static long GetHash(int value, int[] primes, long[] hashes)
{
    if (value == 1) return 0;
    var curIdx = value;
    var ret = 0L;
    do
    {
        ret ^= hashes[primes[curIdx]];
        curIdx /= primes[curIdx];
    } while (curIdx > 1);

    return ret;
}


Balls and Boxes

n種類の色があり、色iのボールがA[i]個ある。さらにm個の箱があり、箱jにはC[j]個のボールが入る。

  • 箱には、同色のボールは2個以上は入らない
  • 色iのボールを箱jに入れると、B[i][j]のキャンディーがもらえる
  • 箱にC[j]個より多くのボールを入れると、ペナルティとして超過分^2のキャンディを払う

のとき、なるべく多くのキャンディーを稼げ。
1 <= n, m <= 100
1 <= A[i] <= 100
0 <= C[i] <= 100
0 <= B[i][j] <= 10^3

次のような最小費用流の問題に還元できる(Uは大きな値)。
f:id:yambe2002:20170602124236j:plain
最小費用はたとえば
U - ボーナス[0]
U - ボーナス[1] + ペナルティ
U
U - ボーナス[3]
のような合計値になる(色2は箱に入れられていない)。最終的に求めたいのはボーナスとペナルティの合計だから、Sum(A)*Uからこの値を引いたものが解答になる。

public static int GetAns(int n, int m, int[] a, int[] c, int[][] b)
{
    var total = a.Sum();

    var graph = new MinCostFlow(n + m + 2 + 1);
    var s = n + m;
    var t = s + 1;

    var U = 3000;

    // colors
    for (int col = 0; col < n; col++)
    {
        graph.AddEdge(s, col, a[col], 0);
        graph.AddEdge(col, t, a[col], U);
    }

    // boxes
    for (int box = 0; box < m; box++)
    {
        var boxNode = box + n;

        // ordinal
        graph.AddEdge(boxNode, t, c[box], 0);

        // additional
        for (int j = 1; j <= 30; j++)
        {
            graph.AddEdge(boxNode, t, 1, 2 * j - 1);
        }
    }

    for (int col = 0; col < n; col++)
    {
        for (int box = 0; box < m; box++)
        {
            var boxNode = box + n;
            graph.AddEdge(col, boxNode, 1, U - b[col][box]);
        }
    }

    var flow = U * total - graph.GetMinCostFlow(s, t, total);
    return flow;
}

public class MinCostFlow
{
    const int INF = 1 << 30;

    class Edge
    {
        public int v, r;
        public int c, w;
        public Edge(int v, int c, int w, int r)
        {
            this.v = v;
            this.c = c;
            this.w = w;
            this.r = r;
        }
    }

    List<List<Edge>> _graph;

    public MinCostFlow(int n)
    {
        _graph = new List<List<Edge>>();
        for (int i = 0; i < n; i++) _graph.Add(new List<Edge>());
    }

    public void AddEdge(int u, int v, int c, int w)
    {
        int x = _graph[u].Count();
        int y = _graph[v].Count();
        _graph[u].Add(new Edge(v, c, w, y));
        _graph[v].Add(new Edge(u, 0, -w, x));
    }

    List<T> GetList<T>(int size)
    {
        var ret = new List<T>();
        for (int i = 0; i < size; i++) ret.Add(default(T));
        return ret;
    }

    public int GetMinCostFlow(int s, int t, int f)
    {
        int n = _graph.Count();
        int ret = 0;
        var h = GetList<int>(n);
        var dist = GetList<int>(n);
        var cap = GetList<int>(n);
        var use = GetList<int>(n);

        while (f > 0)
        {
            var q = new PriorityQueue<ComparablePair<int, int>>(1);
            for (int i = 0; i < dist.Count(); i++) dist[i] = INF;
            dist[s] = 0;
            cap[s] = f;
            q.Push(new ComparablePair<int, int>(0, s));
            while (q.Count() != 0)
            {
                var d = -q.Peek().Item1;
                var u = q.Peek().Item2;
                q.Pop();
                if (dist[u] != d)
                {
                    continue;
                }
                foreach (var e in _graph[u])
                {
                    if (e.c > 0 && dist[e.v] > dist[u] + e.w + h[u] - h[e.v])
                    {
                        dist[e.v] = dist[u] + e.w + h[u] - h[e.v];
                        q.Push(new ComparablePair<int, int>(-dist[e.v], e.v));
                        use[e.v] = e.r;
                        cap[e.v] = Math.Min(cap[u], e.c);
                    }
                }
            }
            if (dist[t] == INF)
            {
                return -1;
            }
            int v = t;
            while (v != s)
            {
                int u = _graph[v][use[v]].v;
                int x = _graph[v][use[v]].r;
                int y = use[v];
                _graph[u][x].c -= cap[t];
                _graph[v][y].c += cap[t];
                ret += cap[t] * _graph[u][x].w;
                v = u;
            }
            for (int i = 0; i < n; i++)
            {
                h[i] += dist[i];
            }
            f -= cap[t];
        }
        return ret;
    }
}

MinCostFlowは蟻本より。C#だとTLEぎりぎりになるようだ。なお本番ではMinCostの算出にPrimal-Dualを使っていたのと、二分探索でFlowを固定して最小費用を複数回もとめたので多くのケースでTLEになっていた。

HackerRank Week of Code 30 参加日記

289位/10554人でレートほぼ変化なし。以下、難易度EasyとMediumのものは省略する。

Poles

斜面上にn本のポールがあり、それぞれ高度x[i]と重さw[i]が与えられる(高度はユニーク)。これをk本のスタックにまとめたい。
・スタック位置はもともとポールがあった場所のみ有効
・ポールは下にのみ移動できる
・移動には、(ポールの重さx高度差)のコストがかかる
このときの最小コストを求めよ。
1 <= k < n <= 5000
1 <= w[i], x[i] <= 10^6
ポールは高度順(昇順)で与えられる

以下、ポールの順序を逆転して考える(0が一番上、n-1が一番下。必ず1番下のポール位置を使うことがヒントになる)。
F(n, k)を、ポール0~nでk個のスタックを作ったときの最小コストと定義する。
{F(n, k) = \min_{ 1 \leq x \leq n } F(n-1, k-1) + \sum_{i=x}^{n}(x_i - x_n) * w_i}
{F(n, k) = \min_{ 1 \leq x \leq n } F(n-1, k-1) + \sum_{i=x}^{n} x_i * w_i - \sum_{i=x}^{n} x_n * w_i}
{F(n, k) = \min_{ 1 \leq x \leq n } F(n-1, k-1) + \sum_{i=x}^{n} x_i * w_i - x_n * \sum_{i=x}^{n} w_i}
{A(n) = \sum_{i=1}^{n} w_i}{ B(n) = \sum_{i=1}^{n} x_i * w_i }とすると、
{F(n, k) = \min_{1 \leq x \leq n} F(x-1, k-1) + B(n) - B(n-1) - x_n * [A(n) - A(x-1)] }
{F(n, k) = B(n) - x_n * A(n) + \min_{1 \leq x \leq n} F(x-1,k-1) - B(x-1) + x_n * A(n-1)}
このように展開すると、まず{B(n) - x_n * A(n)}の部分は予め計算すれば定数時間で求めることができる。
そして、{\min_{1 \leq x \leq n} F(x-1,k-1) - B(x-1) + x_n * A(n-1)}の部分は、独立項{F(x-1,k-1) - B(x-1)}、傾き{A(n-1)}の線集合について、最小値を求めることと同義。傾き{ A(n-1) }は単調増加しているので、Convex Hull Trickを使うといちいちループせずとも効率よく求めることができる。
Convex Hull Trickはこのサイトが分かりやすかった。
http://wcipeg.com/wiki/Convex_hull_trick

class Program
{
    const int MAXN = 5000;
    static double[] weight = new double[MAXN + 5];
    static double[] pos = new double[MAXN + 5];
    static double[] A = new double[MAXN + 5];
    static double[] B = new double[MAXN + 5];
    static double[] F = new double[MAXN + 5];
    static double[,] dp = new double[MAXN, 2];

    static void Main(string[] args)
    {
        int N, K, x, k;

        var s = Console.ReadLine().Split().Select(v => Int32.Parse(v)).ToList();
        N = s[0];
        K = s[1];

        for (x = N - 1; x >= 0; --x)
        {
            s = Console.ReadLine().Split().Select(v => Int32.Parse(v)).ToList();
            pos[x] = s[0];
            weight[x] = s[1];
        }

        for (x = 0; x < N; ++x)
        {
            A[x] = weight[x] + (x > 0 ? A[x - 1] : 0);
            B[x] = pos[x] * weight[x] + (x > 0 ? B[x - 1] : 0);
            F[x] = dp[x, 1] = B[x] - pos[x] * A[x];
        }

        var convexHullTrick = new ConvexHullTrick();

        for (k = 2; k <= K; ++k)
        {
            convexHullTrick.Init();

            convexHullTrick.AddLine(A[k - 2], dp[k - 2, (k - 1) & 1] - B[k - 2]);

            for (x = k - 1; x < N; ++x)
            {
                if (k == x + 1)
                    dp[x, k & 1] = 0;
                else
                    dp[x, k & 1] = F[x] + convexHullTrick.Query(pos[x], true);

                convexHullTrick.AddLine(A[x], dp[x, (k - 1) & 1] - B[x]);
            }
        }

        Console.WriteLine((double)dp[N - 1, K & 1]);
    }
}

public class ConvexHullTrick
{
    class Line
    {
        public double A;
        public double B;

        public Line(double a, double b)
        {
            A = a;
            B = b;
        }

        public double GetY(double x)
        {
            return A * x + B;
        }
    }

    Deque<Line> lines = new Deque<Line>();

    public void Init()
    {
        lines.Init();
    }

    // y = ax + b
    public void AddLine(double a, double b)
    {
        Insert(new Line(a, b));
    }

    double Area(Line a, Line b, Line c)
    {
        var ax = (b.A - a.A);
        var bx = (c.B - a.B);
        var ay = (c.A - a.A);
        var by = (b.B - a.B);
        return ax * bx - ay * by;
    }

    bool Cw(Line a, Line b, Line c)
    {
        return Area(a, b, c) < 0;
    }

    void Insert(Line l)
    {
        while (lines.Count > 1 && Cw(lines[lines.Count - 2], lines[lines.Count - 1], l))
        {
            lines.PopBack();
        }

        if (lines.Count == 1)
        {
            if (lines[0].B > l.B)
                lines.PushBack(l);
        }
        else
        {
            lines.PushBack(l);
        }
    }

    public double Query(double x, bool canRemoveFrontLines = false)
    {
        if (lines.Count == 0)
        {
            return 0;
        }

        if (canRemoveFrontLines)
        {
            while (lines.Count > 1 && lines[0].GetY(x) > lines[1].GetY(x))
            {
                lines.PopFront();
            }
            return lines[0].GetY(x);
        }
        else
        {
            for (int i = 0; i < lines.Count - 1; i++)
            {
                if (lines[i].GetY(x) < lines[i + 1].GetY(x))
                {
                    return lines[i].GetY(x);
                }
            }
        }

        return lines[lines.Count - 1].GetY(x);
    }
}

DequeはC++のDequeをC#で実装した個人ライブラリのもの。List等だとTLEになる。


Range Modular Queries

整数の数列{ A = [ a_0, a_1, ..., a_{n-1} ] }が与えられる。次にq個のクエリが"left right x y"の形で与えられる。クエリごとに、数列で以下の条件を満たす要素数を答えよ。
{ left \leq i \leq right}
{ a_i \equiv y (mod \, x) }
(制約)
1 <= n, q, <= 4 x 10^4
0 <= a[i] <= 4 x 10^4
0 <= left <= right < n
1 <= x <= x x 10^4
0 <= y < x

・xが小さいとき
あらかじめ、x,yのすべての組み合わせについて、a[i]%x==y を満たす要素番号を配列で持てばよい。Left・Rightで二分探索すればO(logN)で求めることができる。
・xが大きいとき
xが大きいとあらかじめ準備することが不可能になる。その代わりa[i]の組み合わせ数が小さくなるので、こちらを列挙できる。同様に、あり得るa[i]の組み合わせ分だけそれぞれ要素番号を持っておけば、Left・Rightでの二分探索が可能になる。

class Program
{
    static int N = 40000;
    static int K = 200; //sqrt(N)

    static void Main(string[] args)
    {
        Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false });

        // [x, y] => list of all indices satisfy a[i] % x == y
        var pos = new List<int>[K + 2, K + 2];
        for (int i = 0; i < K + 2; i++) for (int j = 0; j < K + 2; j++) pos[i, j] = new List<int>();

        // [z] => list of all indices satisfy a[i] == z
        var poss = new List<int>[N + 1];
        for (int i = 0; i < N + 1; i++) poss[i] = new List<int>();

        int n, q;
        var str = Console.ReadLine().Split().Select(v => Int32.Parse(v)).ToArray();
        n = str[0];
        q = str[1];

        var a = ReadLine().Split().Select(v => Int32.Parse(v)).ToArray();

        for (var i = 1; i < K; i++)
        {
            for (int j = 0; j < n; j++)
            {
                pos[i, a[j] % i].Add(j);
            }
        }

        for (var i = 0; i < n; i++)
        {
            poss[a[i]].Add(i);
        }

        for (var i = 0; i < q; i++)
        {
            str = Console.ReadLine().Split().Select(v => Int32.Parse(v)).ToArray();
            var l = str[0];
            var r = str[1];
            var x = str[2];
            var y = str[3];

            int ans = 0;
            if (x < K)
            {
                int st = LowerBound(pos[x, y], l);
                int en = UpperBound(pos[x, y], r);
                --en;
                if (en - st + 1 >= 1) ans += en - st + 1;
            }
            else
            {
                // iterate through all a[i] candidates that satisfy a[i] % x == y
                for (int z = y; z <= 40000; z += x)
                {
                    // count the number within the range
                    int st = LowerBound(poss[z], l);
                    int en = UpperBound(poss[z], r);
                    --en;
                    if (en - st + 1 >= 1) ans += en - st + 1;
                }
            }

            Console.WriteLine(ans);
        }

        Console.Out.Flush();
    }
}

LowerBound()とUpperBound()は個人ライブラリのもの。


A Graph Problem

以下の2つを定義する。
・無向グラフGの三角形の数を、辺(u, v)・(u, w)・(v, w)がGの辺であるトリプル{u, v, w}(順序は問わない)の数と定義する
・グラフG'を、三角形の数/頂点数が最大となるグラフGのvertex-induced sub-graphと定義する
Gが与えられたとき、G'のいずれか一つを出力せよ。
1 <= 頂点数 <= 50

例として、次のグラフを考える。
f:id:yambe2002:20170408022715p:plain
これを以下のようなS-Tグラフに変換する。
f:id:yambe2002:20170408022722p:plain
このグラフをよく観察すると、
・m = 0.1のとき
最大フローは三角形の数より小さい
・m = 0.333...のとき
最大フローは三角形の数より小さい。三角形Aからのフローは1になるが、三角形B+Cからのフローが2に満たないので。
・m = 0.5のとき
最大フローは三角形の数と等しくなる。三角形Aからのフローは1、三角形B+Cからのフローが2になる。
・mがそれより大きいとき
最大フローは三角形の数と等しくなる
となっている。つまり、ちょうどフローと三角形の数が等しくなる場合のmが、求める「三角形の数/頂点数が最大」となることが分かる。よって、mを使って二分探索すれば解が求められる。
最終的な解は、「ちょうどフローと三角形の数が等しくなる場合」よりも少しだけ小さいmを使って最大フローを求めたときの、T側の集合(Maximum Closure Problemの最適解ではないほうの集合)になる。

class Program
{
    static double MAX_FLOW = double.MaxValue;

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

        // graph
        var g = new bool[n, n];
        for (var i = 0; i < n; i++)
        {
            var s = Console.ReadLine().Split().Select(v => v == "1").ToArray();
            for (var j = 0; j < n; j++)
            {
                g[i, j] = s[j];
            }
        }

        // triangles
        var t = new List<Tuple<int, int, int>>();
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < i; ++j)
            {
                for (int k = 0; k < j; ++k)
                {
                    if (g[i, j] && g[j, k] && g[k, i])
                    {
                        t.Add(new Tuple<int, int, int>(i, j, k));
                    }
                }
            }
        }

        int S, T;
        S = t.Count() + n;
        T = t.Count() + n + 1;
        Dinic graph = new Dinic();

        double l = 0, r = 50 * 50 * 50;
        while ((r - l) > 1e-10)
        {
            double m = (l + r) / 2;

            graph.Init();
                
            for (var i = 0; i < n; i++)
            {
                graph.AddEdge(S, t.Count() + i, m);
            }
            for (var i = 0; i < t.Count(); i++)
            {
                graph.AddEdge(t.Count() + t[i].Item1, i, MAX_FLOW);
                graph.AddEdge(t.Count() + t[i].Item2, i, MAX_FLOW);
                graph.AddEdge(t.Count() + t[i].Item3, i, MAX_FLOW);
                graph.AddEdge(i, T, 1);
            }

            var x = graph.GetMaxFlow(S, T);

            if (t.Count() > x)
            {
                l = m;
            }
            else
            {
                r = m;
            }

        }

        var ret = graph.GetStCut(S).Where(v => v >= t.Count() && v != S && v != T).Select(v => v - t.Count());
        Console.WriteLine(ret.Count());
        foreach (var v in ret) Console.Write((v + 1) + " ");
        Console.WriteLine();
    }
}

Dinicは個人ライブラリのもの。

Maximum closure problem

Maximum closure problem の学習まとめ。以下のサイトを参考にした。

Closure problem - Wikipedia
http%3A%2F%2Friot.ieor.berkeley.edu%2F~dorit%2Fpub%2Fscribe%2Flec11%2FLec11posted.pdf&usg=AFQjCNEhubnfNuotTV0_wrbkGGdEF9UHMA&sig2=ewamZFzAoKgnMP5FaFV5cA&bvm=bv.151325232,d.amc *1

Maximum closure problemとは、ノードに重み(正負あり)の付いた有向グラフがあたえられたとき、重みの合計値が最大になるグラフのClosedなサブセットを求める問題である。
Closedのグラフとは、グラフの全ノードについて、その下流ノードがすべてそのグラフに属するもの。たとえば下の図だと、(a)はClosedだが(b)はClosedではない。
f:id:yambe2002:20170331101834p:plain
(*1より抜粋)


求め方
次のようなS-Tグラフを作成する。
・Sから正の重みがついたノードへ、その重み付きのエッジを追加
・Tから負の重みがついたノードへ、その重み付きのエッジを追加
・それ以外のエッジは、重み∞にする
そしてS-Tの最小カットを行い、S側の集合が求めるサブセットになる。

例えば次のような元グラフがあったとする。
f:id:yambe2002:20170331101642p:plain

これをS-Tグラフ化したものが以下になる。(点線が最小カット)
f:id:yambe2002:20170331101655p:plain
S側の集合{b, c, d, e, g}が最大のClosedセットであり、重みの合計値は6になっている。

有向グラフ {G} について、{ (s \cup S, t \cup T) }{ G_{s, t} }の最小カットであれば、{S}{G}の重みの合計が最大になっているclosedセットである。({ G_{s, t} }{ G }から作成した{s-t}グラフ)

証明
{ W^+ \equiv { j \in V | w_i > 0 }}{ W^- \equiv { j \in V | w_i \leq 0  }}とする。
f:id:yambe2002:20170331103755p:plain
(*1より抜粋)

{ W^{+}}は定数なので、 { C( s \cup S, t \cup T ) }を最小化するということは、{ \sum_{ i \in S } W_i }の最大化と同じことがわかる。

最小s-tカットの求め方は、以下のスライドが分かりやすかった。
https://www.slideshare.net/KuoE0/acmicpc-minimum-cut

また、Dinicという方法で最小カット(最大フロー)を求める方法はこちらが参考になる。
https://www.slideshare.net/KuoE0/acmicpc-dinics-algorithm


DinicのC#実装

public class Dinic
{
    public class Edge
    {
        public int V;
        public double C;
        public Edge N;
        public Edge B;
    }

    Edge[] _pool = new Edge[0];
    int _topIdx;

    Edge[] _adj = new Edge[0];

    public int MaxIdx;
    int _minV;

    public Dinic()
    {
        Expand(ref _pool, 128, true);
        Expand(ref _adj, 128, false);
        Init();
    }

    public void Init()
    {
        for (int i = 0; i < _adj.Length; i++) _adj[i] = null;
        _topIdx = 0;
        MaxIdx = 0;
        _minV = Int32.MaxValue;
    }

    void Expand(ref Edge[] edges, int size, bool fillWithEmptyEdge = false)
    {
        if (edges.Length <= size)
        {
            var newEdges = new Edge[Math.Max(size, edges.Length * 2)];
            for (int i = 0; i < edges.Length; i++) newEdges[i] = edges[i];
            if (fillWithEmptyEdge)
            {
                for (int i = edges.Length; i < newEdges.Length; i++)
                {
                    newEdges[i] = new Edge();
                }
            }
            edges = newEdges;
        }
    }

    public void AddEdge(int u, int v, double c, double bc = 0)
    {
        MaxIdx = Math.Max(MaxIdx, Math.Max(u + 1, v + 1));
        _minV = Math.Min(_minV, Math.Min(u, v));

        Expand(ref _pool, _topIdx + 1, true);
        Expand(ref _adj, MaxIdx);

        _pool[_topIdx].V = v;
        _pool[_topIdx].C = c;
        _pool[_topIdx].N = _adj[u];
        _adj[u] = _pool[_topIdx];
        _topIdx++;

        _pool[_topIdx].V = u;
        _pool[_topIdx].C = bc;
        _pool[_topIdx].N = _adj[v];
        _adj[v] = _pool[_topIdx];
        _topIdx++;

        _adj[u].B = _adj[v];
        _adj[v].B = _adj[u];

        if (u == v)
        {
            _adj[u].N.B = _adj[u];
            _adj[v].B = _adj[v].N;
        }
    }

    int[] _d;
    int[] _q;
    int _qh;
    int _qt;
    Edge[] _cur;

    public double GetMaxFlow(int s, int t)
    {
        MaxIdx = Math.Max(MaxIdx, Math.Max(s + 1, t + 1));
        _minV = Math.Min(_minV, Math.Min(s, t));

        _d = new int[MaxIdx];
        _q = new int[MaxIdx];
        _cur = new Edge[MaxIdx];

        double f = 0;

        while (ReLabel(s, t))
        {
            for (int i = 0; i < MaxIdx; i++) _cur[i] = _adj[i];
            f += Augument(s, t, s, double.MaxValue);
        }

        return f;
    }

    bool ReLabel(int s, int t)
    {
        for (int i = 0; i < MaxIdx; i++) _d[i] = Int32.MaxValue;
        _d[_q[_qh = _qt = 0] = t] = 0;
        while (_qh <= _qt)
        {
            var u = _q[_qh++];

            for (var i = _adj[u]; i != null; i = i.N)
            {
                if (i.B.C != 0 && _d[i.V] > _d[u] + 1)
                {
                    _d[i.V] = _d[u] + 1;
                    if ((_q[++_qt] = i.V) == s)
                    {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    double Augument(int s, int t, int u, double e)
    {
        if (u == t) return e;
        double f = 0;

        for (var i = _cur[u]; i != null; i = i.N)
        {
            if (i.C > 0 && _d[u] == _d[i.V] + 1)
            {
                var df = Augument(s, t, i.V, Math.Min(e, i.C));
                if (df > 0)
                {
                    i.C -= df;
                    i.B.C += df;
                    e -= df;
                    f += df;
                }
            }
            if (!(e > 0)) break;
        }

        return f;
    }

    // (S, T)
    public Tuple<List<int>, List<int>> GetStCut(int s)
    {
        var used_flg = new bool[MaxIdx];

        Dfs(s, used_flg);

        var ret_s = new List<int>();
        var ret_t = new List<int>();
        for (int i = _minV; i < MaxIdx; i++)
        {
            if (!used_flg[i])
            {
                ret_t.Add(i);
            }
            else
            {
                ret_s.Add(i);
            }
        }

        return new Tuple<List<int>, List<int>>(ret_s, ret_t);
    }

    void Dfs(int u, bool[] used_flg)
    {
        if (used_flg[u]) return;
        used_flg[u] = true;

        for (var i = _adj[u]; i != null; i = i.N)
        {
            if (i.C > 1e-6) Dfs(i.V, used_flg);
        }
    }
}

CodinGame - Ghost in the Cell 参加日記

CodinGameのコンテストに初参加してみた。ゲームAIを作ってその強さを競うものなのだが、面倒な環境構築が不要でなかなか楽しかった。対戦動画も観ていて面白い。

https://www.codingame.com/replay/194505045
黄色が私。最終的にCyborgの数が多いほうが勝ち

ランキングはリーグ制。最初はウッドリーグ3部からスタートし、リーグボスを倒すごとにウッド2→ウッド1→ブロンズ→シルバー→ゴールドとランクアップする。また、途中でルールが追加されることもある。

ゲームルール概略

  • ターン制
  • マップ上にいくつかの工場がある
  • 工場間は長さの違う道で繋がれている
  • 工場は味方・敵・中立のいずれか
  • 工場は1ターンごと0~3体のCyborgを自動生産する
  • 1ターンごと、味方・敵同時に行動を起こす
  • 自工場からほかの工場にCyborg部隊を送ることができる
  • 敵または中立の工場にCyborg部隊が到着したら戦いが起こる
  • 戦いはCyborg数の多いほう勝利し、数の差分だけ生き残る
  • 戦いに勝ったら工場を占領できる
  • 最終的に相手を全滅させるか、400ターン後にcyborgの多いほうが勝ち
  • 1ターンに複数の部隊を送ることができる*
  • Cyborgを10消費して、工場のCyborg生産数を増やすことができる(3まで)*
  • 2回まで爆弾を送ることができる*
  • 爆弾を被弾すると、工場のCyborg数が半分、または10まで減る(小さいほう)*

(*はリーグが上がるごとに追加されたルール)

実装
1ターンの制限時間が50msしかないので、深く手を読む方針はとらなかった。基本的に、(1)危ない自工場があったら助ける(2)生産力のある中立工場があったら占領しようとする(3)敵に爆弾を送ってみる(4)敵工場を占領しようとする(4)遊んでる工場があったら前線に兵を送る、の優先順位で手の候補をいくつか作成し、そこから21手くらい先までシミュレートして局面評価がベストのものを採用した。

反省
序盤にいろいろ考えすぎて実装が遅れたのが良くなかった。Topcoderのマラソンマッチと違い途中でルールが変わるし、またリーグが落ちることは(たぶん)ない仕組みなので、軽いコードをどんどん書いてSubmitしていったほうがよさそうだ。シミュレーション中の手や評価関数がまったく詰められなかったのも反省点。

結果はぎりぎりシルバーリーグの103位/311人だった。次回はシルバー上位を目標にしよう。