HackerRank Ad Infinitum16 参加日記

始めて参加した。数学関連の問題がでるコンテストらしい。
46位/673人だけど初回参加者用の区分だっただからレベルが低いのかも。

ad Infinitum: 無限に、永久に（ラテン語）

q個の整数が与えられる。それぞれの整数（nとする）について、集合[1,n]内で、一意な素因数の数が最も多いものを算出し、その数を出力せよ。
1 <= q <= 10^5
1 <= n <= 10^18

素数を小さい順に、nを超えるまでかけていけばよい。素数は50くらいまでしか使わないので、最初に列挙しておくと効率が良い。

var q = Int32.Parse(Console.ReadLine());
while (q > 0)
{
    var n = Int64.Parse(Console.ReadLine());
    var ret = 0;
    BigInteger x = 1;

    foreach (var p in primes) //primesは素数のリスト（昇順）
    {
        x *= p;
        if (x > n) break;
        ret++;
    }
    Console.WriteLine(ret);
    q--;
}

Russian Peasant Exponentiation

q個のクエリが与えられる。それぞれのクエリでは、整数k,m,a,bが与えられる。(a+bi)^kを求めよ（iは虚数単位）。解は、実部と虚部をそれぞれmでModしたものを出力せよ。
大きなべき乗を求める方法は次を参考にせよ
https://www.hackerrank.com/external_redirect?to=http://lafstern.org/matt/col3.pdf
1 <= q <= 10^5
0 <= k <= 10^18
2 <= m <= 10^9
0 <= a, b <= m

「ロシア農民のアルゴリズム」を複素数に応用しろというもの。複素数クラスを作成し、乗算とModを実装すれば、実数と同じコードになる。複素数クラスはNumericsのものだとオーバーフローの危険性がありそうだ。

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

    var q = Int32.Parse(Console.ReadLine());
    while (q > 0)
    {
        //a,b,k,m -> (a + bi)^k mod m
        var str = Console.ReadLine().Split();
        var a = Int64.Parse(str[0]);
        var b = Int64.Parse(str[1]);
        var k = Int64.Parse(str[2]);
        var m = Int64.Parse(str[3]);

        var comp = new MyComplex(a, b);
        var modPow = ModPow(comp, k, m);

        //mod前のmの足し忘れ注意！
        Console.WriteLine(string.Format("{0} {1}", (modPow.Real + m) % m, (modPow.Imaginary + m) % m));
        q--;
    }
    Console.Out.Flush();
}

//ロシア農民のアルゴリズム
static MyComplex ModPow(MyComplex x, Int64 n, Int64 mod)
{
    while ((n & 1) == 0)
    {
        x = (x * x) % mod;
        n >>= 1;
    }
    var ret = x;
    n >>= 1;
    while (n > 0)
    {
        x = (x * x) % mod;
        if ((n & 1) != 0)
            ret = (ret * x) % mod;
        n >>= 1;
    }

    return ret % mod;
}

class MyComplex
{
    public Int64 Real;
    public Int64 Imaginary;

    public MyComplex(Int64 real, Int64 img)
    {
        Real = real;
        Imaginary = img;
    }

    public static MyComplex operator *(MyComplex c1, MyComplex c2)
    {
        return new MyComplex(c1.Real * c2.Real - c1.Imaginary * c2.Imaginary, c1.Real * c2.Imaginary + c1.Imaginary * c2.Real);
    }

    public static MyComplex operator %(MyComplex c1, Int64 mod)
    {
        return new MyComplex((c1.Real) % mod, (c1.Imaginary) % mod);
    }
}

Xrange's Pancakes

正n角形のパンケーキが与えられる。このパンケーキは、①中心と各頂点を通るもの②中心と各頂点の中間点を通るもの、の2種類の軸が存在する（合計n本）。軸は0~n-1の番号が時計回りに連続でついている。
このとき、n個のクエリが与えられる。クエリの種類は２つ：
タイプ１：軸kで裏返す
タイプ２：パンケーキを、(360*k) / n 度だけ時計回りに回転させる
すべてのクエリが終了したときのパンケーキを、タイプ１またはタイプ２を1回だけ適用させて、初期位置に戻したい。このクエリを答えよ。
3 <= n <= 10^6
1 <= m <= 10^6
0 <= k <= n

ややこしく考えると嵌りそうだが、実際は初期に軸0にあった頂点の位置と、裏返されているか否かだけ管理すればよい。

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

var x = 2 * n; //位置（頂点＋頂点間）
var pos = 0;   //初期に軸0にあった頂点の位置
var isFlipped = false;

while (m > 0)
{
    str = Console.ReadLine().Split();
    var k = Int32.Parse(str[1]);
    switch (str[0])
    {
        case "1":   //rotate
            pos = (pos + k * 2) % x;
            break;
        default:    //flip
            pos = (pos + ((k + x - pos) % x) * 2) % x;
            isFlipped = !isFlipped;
            break;
    }
    m--;
}

if (!isFlipped)
{
    Console.WriteLine("1 " + ((x - pos) / 2).ToString());
}
else
{
    Console.WriteLine("2 " + (pos / 2).ToString());
}

Solve Equations

方程式 ${ ax + by = c }$ がｑ個与えられたとき、それぞれ次を満たす最も原点に近い点を求めよ。
・xとyは整数
・xは0より大きい
複数の解があるときは、xのより小さいものを答えよ。
1 <= q <= 10^5
1 <= a <= 10^8
1 <= b <= 10^8
1 <= c <= 10^8
a, b, cは整数

整数解が存在するといことは、cはgcd(a,b)で割り切れる。そして、拡張ユークリッドアルゴリズムを使って一組の(x, y)が計算できたとき、すべての組は次の形で表せる。ベズーの等式 - Wikipedia
${ \left(x+k{\frac {b}{\gcd(a,b)}},\ y-k{\frac {a}{\gcd(a,b)}}\right) }$
ここで、 ${ c_1 = \frac {b}{\gcd(a, b)} }$ 、 ${ c_2 = - \frac {a}{\gcd(a, b)} }$ とすると
${ x_2 = x_1 + c_1 \cdot k }$
${ y_2 = y_1 + c_2 \cdot k }$
と表すことができる。
${ (x_2)^2 + (y_2)^2 }$ を最小化するのが目的なので、上式の展開
${ (x_1 + c_1\cdot k)^2 + (y_1 + c_2 \cdot k)^2 = t^2 \cdot ((c_1)^2 + (c_2)^2) + t \cdot (2 \cdot x_1 \cdot c_1 + 2 \cdot y_1 \cdot c_2) + ( (x_1)^2 + (y_1)^2 ) }$
を最小化すればよい。
${ \alpha = (c_1)^2 + (c_2)^2 }$
${ \beta = 2 \cdot x_1 \cdot c_1 + 2 \cdot y_1 \cdot c_2 }$
${ \gamma = (x_1)^2 + (y_1)^2 }$
とおくと、
${ \alpha \cdot t^2 + \beta \cdot t + \gamma }$
になる。よって答えは以下のようになる。（実装は省略）
１. ${ - \frac{\beta}{ 2 \cdot \alpha } }$ が負のとき
${ t=0 }$ の場合
２. ${ - \frac{\beta}{ 2 \cdot \alpha } }$ が正のとき
${ t= -\frac{\beta}{ 2 \cdot \alpha } }$ または ${ t= -\frac{\beta}{ 2 \cdot \alpha } + 1 }$ の場合

Hyperspace Travel

m次元の超空間にn人が存在している。この人達は、次元のグリッド線上だけを動くことができる。全員の総移動距離が最小になるよう、空間のある地点に集まりたい。この地点を求めよ。
各人の初期位置は、次元0、次元1...の順にx0,x1...の形で与えられる。
1 <= n <= 10^4
1 <= m <= 10^2

10^9 <= xi <= 10^9　（整数のみ）

集合地点の位置は整数

グリッド線上のみ動くことができる（次元間をナナメに移動することはできない）ということは、各次元内で移動が完結しているということになる。よって、次元ごとに集合地点を求めればよい。
ある次元について、移動距離が最小になるのは、真ん中にいる人に集まる場合なので、ソートしてIndexが中点のものが答えになる。

static void Main(string[] args)
{
    var str = Console.ReadLine().Split();
    var n = Int64.Parse(str[0]);
    var m = Int64.Parse(str[1]);

    var friends = new List<List<Int64>>();
    for (int i = 0; i < n; i++)
    {
        friends.Add(Console.ReadLine().Split().Select(v => Int64.Parse(v)).ToList());
    }

    for (int i = 0; i < m; i++)
    {
        Console.Write(Get(i, friends));
        if (i != m - 1) Console.Write(" ");
    }
    Console.WriteLine();
}

static Int64 Get(int dimension, List<List<Int64>> friends)
{
    var values = new List<Int64>();
    foreach (var friend in friends)
    {
        values.Add(friend[dimension]);
    }
    values.Sort();

    return values[(values.Count() - 1) / 2];
}