読者です 読者をやめる 読者になる 読者になる

HackerRank Week of Code - 25 参加日記

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

25位/7510人の自己ベスト。Hardの1問を正答できたのと、Hard/Expertの部分点を取れたのが大きかった。以下、難易度Easyのものは省略する。


Baby Step, Giant Step

2次元上の座標(0,0)から(d,0)に移動する最小のステップ数を求めよ。ただし、1回のステップでは距離aまたは距離bのみ進むことができる。a,b,dの組み合わせはq個与えられるので、それぞれについて答えること。
1 <= q <= 10^5
1 <= a <= b <= 10^9
0 <= d <= 10^9

x座標軸上のみで考えると、(x1,0)から(x2,0)まで移動するステップ数は、
1、x2-x1がaまたはb:1
2、x2-x1がb*2より小さい:2
3、それ以外:(x1+b,0)から(x2,0)までのステップ数+1
となる。愚直に再帰で実装するとStackOverflowになるので、3の部分はループでbを足していく。

public static int GetAns(int a, int b, int d)
{
    var ret = 0;
    if (d > 2 * b)
    {
        ret = (d - 2 * b) / b;
        d -= ret * b;
    }
    while (d > b * 2)
    {
        d -= a;
        ret++;
    }

    if (d == a || d == b)
        ret += 1;
    else if (d != 0)
        ret += 2;

    return ret;
}


Stone Division

2人のプレーヤーが次のゲームを戦う。いずれも最善手を指したときに、勝利するのはどちらか。
・n個の石でできた山が1つある
・m個の一意なInt型の集合S = {  { s_0, s_1, ..., s_{m-1} } }がある
・プレーヤーは交互に手を指す。手番では、Sから任意の{ s_i }と任意の山1つを選んで、その集まりを {s_i}個の山に分割する。このとき、分割された集合は同数である必要がある
・指せる手がないプレーヤーが負けとなる
1 <= n <= 10^18
1 <= m <= 10
2 <=  {s_i} <= 10^18

NimやGrundy数の理解が前提。本番ではWL-Algorithmで解いて部分正答だった。
参考:grundy数を習得したかった - nanikakaのAOJ航海日誌
 { g(x) } を1つの山にx個の石があるときのGrundy数とする。
xをkで割ったとき、Grungy数は
 { g(d)\,xor\,g(d)\,xor\,...\,xor\,g(d)\,\, (k\,times) }
となる。よって、kが偶数のときは0、奇数のときはg(d)に一致する。(=kが偶数なら勝ち)

class Program
{
    static List<long> s;
    static Dictionary<long, bool> dict = new Dictionary<long, bool>();

    static void Main(string[] args)
    {
        var str = Console.ReadLine().Split();
        var n = long.Parse(str[0]);
        var m = Int32.Parse(str[1]);
        s = Console.ReadLine().Split().Select(st => long.Parse(st)).ToList();
        Console.WriteLine(GetAns(n) ? "First" : "Second");
    }

    static bool GetAns(long n)
    {
        var ret = false;
        if (dict.ContainsKey(n)) return dict[n];

        foreach (var k in s)
        {
            if (n % k != 0) continue;
            ret |= k % 2 == 0;
            if (ret) break;
            ret |= !GetAns(n / k);
            if (ret) break;
        }

        dict.Add(n, ret);
        return ret;
    }
}


Good Point

二次平面上に、n個の厳密な凸多角形と、m個の楕円(Ellipse)がある。すべての多角形と楕円が重なる点を求めよ。該当点は存在することが保障されている。また、該当するものであれば、どの点を答えても良い。
1 <= n <= 500
3 <=  {v_i } <= 1500 (多角形iの頂点数)
3 <=  { \sum_{i=0}^{n-1} v_i } <= 1500
1 <= m <= 1500
各座標は[ -10^4, 10^4 ]の範囲にある
楕円のSemi Major Axisは10^4以下の整数
誤差は10^-4まで許容

本番でこれが解けたのはうれしい。
凸多角形と楕円が重なる部分は、かならず凸型の図形になる。よって、最終的な凸型図形までの距離をf(x, y)とすると、xおよびyを固定してできる関数f(A, y), f(x, B)はいずれも凹型の曲線になる。なのでXとYそれぞれで三分探索すれば解が求められる。

class Program
{
    static void Main(string[] args)
    {
        //polygon
        var polygons = new List<Polygon>();
        var n = Int32.Parse(Console.ReadLine());
        for (int i = 0; i < n; i++)
        {
            var polygon = new Polygon();
            var v = Int32.Parse(Console.ReadLine());
            for (int j = 0; j < v; j++)
            {
                var str = Console.ReadLine().Split();
                var x = Int32.Parse(str[0]);
                var y = Int32.Parse(str[1]);
                polygon.AddPoint(new Pt(x, y));
            }
            polygons.Add(polygon);
        }

        //ellipses
        var ellipses = new List<Ellipse>();
        var m = Int32.Parse(Console.ReadLine());
        for (int i = 0; i < m; i++)
        {
            var str = Console.ReadLine().Split();
            var x1 = Int32.Parse(str[0]);
            var y1 = Int32.Parse(str[1]);
            var x2 = Int32.Parse(str[2]);
            var y2 = Int32.Parse(str[3]);
            var a = Int32.Parse(str[4]);
            ellipses.Add(new Ellipse(x1, y1, x2, y2, a));
        }

        var lx = -10001.0;
        var rx = 10001.0;
        var ly = -10001.0;
        var ry = 10001.0;

        // ternary search in x
        for (int i = 0; i < 48; i++)
        {
            var x1 = lx + (rx - lx) / 3;
            var x2 = rx - (rx - lx) / 3;

            var ly_x1 = -10001.0;
            var ry_x1 = 10001.0;
            var x1Score = GetScore_TernaryY(ref ly_x1, ref ry_x1, x1, ellipses, polygons);

            var ly_x2 = -10001.0;
            var ry_x2 = 10001.0;
            var x2Score = GetScore_TernaryY(ref ly_x2, ref ry_x2, x2, ellipses, polygons);

            if (x2Score > x1Score)
            {
                //remove right
                rx = x2;
            }
            else
            {
                //remove left
                lx = x1;
                ly = ly_x2;
                ry = ry_x2;
            }
        }

        Console.WriteLine(lx);
        Console.WriteLine(ly);
    }

    static double GetScore_TernaryY(ref double ly, ref double ry, double x, List<Ellipse> ellipses, List<Polygon> polygons)
    {
        var score = GetScore(x, ly, ellipses, polygons);
        for (int i = 0; i < 48; i++)
        {
            var y1 = ly + (ry - ly) / 3;
            var y2 = ry - (ry - ly) / 3;

            var y1Score = GetScore(x, y1, ellipses, polygons);
            var y2Score = GetScore(x, y2, ellipses, polygons);

            if (y2Score > y1Score)
            {
                //remove right
                ry = y2;
            }
            else
            {
                //remove left
                ly = y1;
                score = y2Score;
            }
        }
        return score;
    }

    static double GetScore(double x, double y, List<Ellipse> ellipses, List<Polygon> polygons)
    {
        return GetScore(new Pt(x, y), ellipses, polygons);
    }

    static double GetScore(Pt pt, List<Ellipse> ellipses, List<Polygon> polygons)
    {
        return ellipses.Sum(e => e.GetDist(pt)) + polygons.Sum(p => p.GetDist(pt));
    }
}


public class Polygon
{
    public List<Edge> Edges;

    List<Pt> _points;

    public Polygon()
    {
        Edges = new List<Edge>();
        _points = new List<Pt>();
    }

    public void AddPoint(Pt point)
    {
        _points.Add(point);
        if (_points.Count >= 2)
        {
            Edges.Add(new Edge(_points[_points.Count() - 2], _points[_points.Count() - 1]));
        }
    }

    public double GetDist(Pt pt)
    {
        double minDist = Double.MaxValue;
        var inside = true;

        for (int i = 0; i < Edges.Count(); i++)
        {
            if (!IsCcw(pt, Edges[i].p1, Edges[i].p2))
            {
                inside = false;
            }

            minDist = Math.Min(minDist, Edges[i].Dist(pt));
        }

        return inside ? 0 : minDist;
    }

    public bool IsCcw(Pt p, Pt p1, Pt p2)
    {
        return Pt.Ccw(p, p1, p2) == 1;
    }
}

public class Ellipse
{
    public Pt P1;
    public Pt P2;
    public double A;
    public double D;

    public Ellipse(double x1, double y1, double x2, double y2, double a)
    {
        P1 = new Pt(x1, y1);
        P2 = new Pt(x2, y2);
        A = a;
        D = 2 * a;
    }

    public double GetDist(Pt pt)
    {
        var ret = P1.Dist(pt) + P2.Dist(pt);
        return ret <= D ? 0 : (ret - D) / 2;
    }
}

PtとEdgeは個人ライブラリのもの。


DAG Queries

頂点数n、辺数mのDAGが与えられる。すべての頂点vは値として整数a[v]持ち、これの初期値は0である。次のクエリの結果を答えよ。クエリは3タイプある。
1. 1 u x: 頂点uから訪れることのできる頂点vについて、a[v]をxに更新する
2. 2 u x: 頂点uから訪れることのできる頂点vについて、a[v]>xならa[v]をxに更新する
3. u: a[u]を出力する
2 <= n <= 10^5
1 <= m, q <= 10^5 (qはクエリの数)
0 <= x <= 10^9

すべてのクエリをため込んで出力のたびにa[v]を算出する方法も、クエリが来るたびに各a[i]を算出する方法もTLEになる。平方分割を使って解決する。

  1. すべてのクエリをローカル変数に保持
  2. クエリタイプ2について、{ \sqrt{q} }くらいのブロックごとに、ブロックkの時点でクエリ2だけでa[v]の値がどうなるかの情報、type_2[k][v]を作成する
  3. クエリを最初から処理:(1)クエリ1はキューque1に入れていく。que1のサイズが{ \sqrt{q} }を超えたらその時点でクエリ1だけで値がどうなるかの情報type_1[v]を作成する(2)クエリ3が来たらtype_2とtype_1を使って出力値を計算

Editorialによると、グラフすべてを計算しようとするとメモリが足りなくなるので、グラフを3つくらいに分割して3回処理を回す必要がある。
理屈はわかるのだが、C#で実装したらTLEになってしまった・・・。