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

基本的に満足度が正の料理は１つのSubsetとして食べ、負の料理は１つずつ食べる。ただし、あまり負の値が大きくないものは、正の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)ランダム、のいずれかの条件で作成される。

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