HackerRank Week of Code - 22 参加日記

457位/12356人。Mediumを1つ落としたのが痛い。いつも数学がネックだ・・・。

n人のゲストとm枚のクッキーがある。ゲスト全員に同じ枚数を配るためには、あと何枚クッキーを焼けばよいか。

クッキーがすでに足りているか、足りない場合はゲストの人数で割り切れるかで場合分けする。

if (m <= n)
    Console.WriteLine(n - m);
else if (m % n == 0)
    Console.WriteLine(0);
else
    Console.WriteLine((m / n + 1) * n - m);

Making Polygons

N本の棒aiが与えられる。この棒すべてを使って非退化な多角形を作るには、最少で何本の棒を折る必要があるか。折れた棒は両方使うものとする。
1 <= N <= 50
1 <= ai <= 100

「非退化」というのは重なった辺も、長さゼロの辺も存在しないという意味で、要するに普通の多角形のことらしい。
1本しかないときは、当然2回折らないと多角形にならない。
2本のときは、同じ長さなら2回、違う長さなら1回折る必要がある。
3本以上あるなら、
　最長の辺の長さ > それ以外の辺の長さ合計
に合致したら一本も折らなくてよい。それ以外のときは、最長のものを1回折る必要がある。

if (a.Count() == 1)
{
    Console.WriteLine(2);
}
else if (a.Count() == 2)
{
    if (a[0] == a[1]) Console.WriteLine(2);
    else Console.WriteLine(1);
}
else
{
    if (a[0] < a.Sum() - a[0]) Console.WriteLine(0);
    else Console.WriteLine(1);
}

理屈は簡単だが、棒が1本からという条件を見逃すとWAになってしまう。

Matching Sets

2つの整数の集合 ${ X = { x_0, x_1, ..., x_{n-1} }, Y = { y_0, y_1, ..., y_{n-1} } }$ があり、次のオペレーションが可能である。
１、XとYから1つずつ ${ x_i, x_j }$ を選ぶ( ${ i \neq j}$ )
２， ${ x_i }$ から1引き、 ${ y_j }$ に1足す
XとYが等しくなる最少のオペレーション回数を求めよ。不可能な場合は-1を返すこと。

XとYの合計が異なるときは不可能。それ以外であれば、両方ともソートして1つずつオペレーションしていけば良い。

if (x.Sum() != y.Sum())
{
    Console.WriteLine(-1);
    return;
}

Int64 diff = 0;
x.Sort();
y.Sort();
for (int i = 0; i < n; i++)
{
    diff += Math.Abs(x[i] - y[i]);
}

Console.WriteLine(diff / 2);

Number of Sequences

整数の数列が次を満足するとき、この数列はNiceであるとする
・ ${ 0 \leq a_k \leq k - 1 }$
・ ${ a_k \equiv\,a_m\,mod\,k }$ (kがmを割り切るすべてのk,mのペアについて)
一部が-1になっている整数の数列nが与えられる。-1に任意の数字を入れたとき、この数列がNiceになる組み合わせ数を求めよ。

まず、a[i]の添え字がa[p*q]と素因数分解できるものは無視することができる（中国の剰余定理によりa[p]とa[q]が決まっていれば、a[p*q]が一意に求まるため）。
そして、各素数のべき乗番目
　a[p], a[p^2], a[p^3] ... (p^x < n)
について、値が-1ならp通りのパターンがある。
たとえば、p=3のとき
　a[3]: -1 → あり得る値は { 0, 1, 2 }
　a[9]: -1 → あり得る値は { 0, 1, 2, 3, 4, 5, 6, 7, 8 }
となるが、a[3]でどの値が選ばれたとしても、a[9]で候補になる数は9/3=3個になる。

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

    var n = Int32.Parse(Console.ReadLine());
    var a = ReadLine().Split().Select(s => Int32.Parse(s)).ToList();
    a.Insert(0, 0);

    //それぞれのkの因数すべて
    var facts = Enumerable.Range(0, n + 1).Select(v => new List<int>()).ToList();
    for (var k = 2; k <= n; k++)
    {
        Int64 kp = k;
        while (kp <= n)
        {
            facts[(int)kp].Add(k);
            kp += k;
        }
    }

    //すでに値がある場合に、Niceに違反する因数がないかチェック
    for (var k = n; k > 0; k--)
    {
        if (a[k] == -1) continue;
        foreach (var fact in facts[k])
        {
            if (a[fact] != -1 && a[fact] != a[k] % fact)
            {
                Console.WriteLine(0);
                Console.Out.Flush();
                return;
            }
            a[fact] = a[k] % fact;
        }
    }

    //kが(素数^p)で表せるならその素数を取得
    var basePrimes = new int[n + 1];
    for (var k = 2; k <= n; k++)
    {
        if (facts[k].Count() == 1)
        {
            Int64 kp = k;
            while (kp <= n)
            {
                basePrimes[kp] = k;
                kp *= k;
            }
        }
    }

    //a[k]が-1かつkが(素数^p)で表せるなら、k通りの組み合わせがある
    Int64 ret = 1;
    for (var k = 2; k <= n; k++)
    {
        if (a[k] == -1 && basePrimes[k] != 0)
        {
            ret *= (Int64)basePrimes[k];
            ret %= 1000000007;
        }
    }

    Console.WriteLine(ret);
    Console.Out.Flush();
}

Submask Queries

要素数nの集合 ${ U = {1, 2, ..., n} }$ がある。Uの部分集合すべてに値0が代入されている。
この時、次の3タイプのクエリが渡される。
１. 1 x S：集合Sの部分集合すべてに値xを代入する
２. 2 x S：集合Sの部分集合すべての値についてxとXORをとる
３. 3 s：集合Sの値を出力する
クエリが連続で与えられるので、出力値を求めよ。
1 <= n <= 16
1 <= m(クエリ数) <= 10^5
0 <= x <= 2^30 - 1

最後に代入された時間と値、そしてそこからのXOR合算を効率よく求める必要がある。
各クエリごとのループ回数を少なくするため、下位8ビットと上位8ビットに平方分割する。クエリ1・2では、下位8ビットのサブセットすべてについて、以下の情報を保持していく。

var set_times = new int[1 << 8, 1 << 8];   //最後に代入した時間
var set_values = new int[1 << 8, 1 << 8];  //代入された値
var xor_time = new List<ComparablePair<int, int>>[1 << 8, 1 << 8];  // XORした時間と、そこまでのXOR合算

クエリ3では、①該当ビットに最後に代入された値を取得し、②その時間をもとにそこからのXOR合算を算出する。
たとえば、
1:XOR、2:代入、3:XOR、4:代入、5:代入、6:XOR、7:XOR
だったとしたら、最終的な値は5で代入された値へ、3までのXOR合算と7までのXOR合算をXORしたものになる。この、最後の代入の直前のXORは、時間で二分探索すれば求められる。
①②いずれも、上位8ビットのスーパーセットすべて＋下位8ビットのパターンで行えばよい。

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

    var str = Console.ReadLine().Split();
    var n = Int32.Parse(str[0]);
    var m = Int32.Parse(str[1]);

    var set_times = new int[1 << 8, 1 << 8];   //last updated time to [H, L]
    var set_values = new int[1 << 8, 1 << 8];  //[H, L] => value of mask { all subsets of H } + L
    var xor_time = new List<ComparablePair<int, int>>[1 << 8, 1 << 8];  // time of xor -> xor value of mask [H, L]

    for (int i = 0; i < 1 << 8; i++)
    {
        for (int j = 0; j < 1 << 8; j++)
        {
            set_times[i, j] = -1;
            xor_time[i, j] = new List<ComparablePair<int, int>>() { new ComparablePair<int, int>(-1, 0) };
        }
    }

    for (int i = 0; i < m; i++)
    {
        str = Console.ReadLine().Split();
        var bit = 0;
        for (int j = 0; j < n; j++)
        {
            bit *= 2;
            if (str[str[0] == "1" || str[0] == "2" ? 2 : 1][j] == '1') bit += 1;
        }
        var top = bit >> 8;
        var bottom = bit & 0xFF;

        //assign
        if (str[0] == "1")
        {
            var val = Int32.Parse(str[1]);
            var sub = bottom;
            do
            {
                set_values[top, sub] = val;
                set_times[top, sub] = i;
                sub = (sub - 1) & bottom;
            } while (sub != bottom);
        }

        //xor
        if (str[0] == "2")
        {
            var val = Int32.Parse(str[1]);
            var sub = bottom;
            do
            {
                xor_time[top, sub].Add(new ComparablePair<int, int>(i, val ^ xor_time[top, sub].Last().Item2));
                sub = (sub - 1) & bottom;
            } while (sub != bottom);
        }

        //print
        if (str[0] == "3")
        {
            //find the last updated time and its time
            var val = 0;
            var lastUpdated = -1;

            //iterate supersets of top
            var comp = ~top & 0xFF;
            for (int sub = comp; ; sub = (sub - 1) & comp)
            {
                int super_top = top | sub;  //superset of top
                if (set_times[super_top, bottom] > lastUpdated)
                {
                    lastUpdated = set_times[super_top, bottom];
                    val = set_values[super_top, bottom];
                }
                if (sub == 0) break;
            }

            //apply xors from the last updated time
            comp = ~top & 0xFF;
            for (int sub = comp; ; sub = (sub - 1) & comp)
            {
                int super_top = top | sub;  //superset of top
                var tgt_xors = xor_time[super_top, bottom];

                var right_xor = tgt_xors.Last().Item2;
                var left_xor = GetLastXor_BeforeLastUpdate(tgt_xors, lastUpdated).Item2; //get the last xor-ed value before the update time using binary search

                // getting xors from i to j: xor(0..j) ^ xor(0..i-1)
                val ^= (left_xor ^ right_xor);

                if (sub == 0) break;
            }

            Console.WriteLine(val);
        }
    }

    Console.Out.Flush();
}

//return [upper_bound() - 1], xors are sorted by item1
static ComparablePair<int, int> GetLastXor_BeforeLastUpdate(List<ComparablePair<int, int>> xors, int time)
{
    var lb = -1;
    var ub = xors.Count();

    while (ub - lb > 1)
    {
        var mid = (lb + ub) / 2;
        if (xors[mid].Item1 <= time)
        {
            lb = mid;
        }
        else
        {
            ub = mid;
        }
    }

    return xors[lb];
}