ABC255

Published on Saturday, 11 June 2022

Updated on Saturday, 11 June 2022

atcoder csharp

はじめに

AtCoder Beginner Contest 255の復習記事です。

記事におけるScannerクラスは、自作の入力クラスです。

コンテスト

https://atcoder.jp/contests/abc255

問題A

コンテスト提出

RとCの値ごとに場合分けして答えることもできますが(4通り)、2*2の行列Mとして値を保持してM[R][C]の値を答えることもできます。

public static void Solve()
{
    var (R, C) = Scanner.Scan<int, int>();
    R--; C--;
    var M = new int[2][];
    for (var i = 0; i < 2; i++)
    {
        M[i] = Scanner.ScanEnumerable<int>().ToArray();
    }

    var answer = M[R][C];
    Console.WriteLine(answer);
}

ある人を照らすために必要なRは、何れかの明かりを持つことができる人の位置からの最小距離であり、そのRの最大値を求めることで全ての人をカバーすることができます。
距離Dは二点のXの差分dxとYの差分をdyとしたとき、D = Sqrt(dx^2 + dy^2)で求めることができますが、D < D'ならば、D^2 < D'^2なので、距離の二乗の値で走査することで、最後に答えを求めるときを除いて実数による誤差を無視することができます。

public static void Solve()
{
    var (N, K) = Scanner.Scan<int, int>();
    var A = Scanner.ScanEnumerable<int>().Select(x => x - 1).ToArray();
    var P = new (long X, long Y)[N];
    for (var i = 0; i < N; i++)
    {
        var (x, y) = Scanner.Scan<long, long>();
        P[i] = (x, y);
    }

    var answer = 0L;
    for (var i = 0; i < N; i++)
    {
        var min = inf;
        for (var i = 0; i < N; i++)
        {
            var dx = P[a].X - P[i].X;
            var dy = P[a].Y - P[i].Y;
            var d = dx * dx + dy * dy;
            min = Math.Min(min, d);
        }

        answer = Math.Max(answer, min);
    }

    Console.WriteLine(answer);
}

答えRの二部探索でも答えを求めることができます。

public static void Solve()
{
    var (N, K) = Scanner.Scan<int, int>();
    var A = Scanner.ScanEnumerable<int>().Select(x => x - 1).ToArray();
    var P = new (long X, long Y)[N];
    for (var i = 0; i < N; i++)
    {
        var (x, y) = Scanner.Scan<long, long>();
        P[i] = (x, y);
    }

    bool F(long x)
    {
        var ok = new bool[N];
        foreach (var a in A)
        {
            for (var i = 0; i < N; i++)
            {
                var dx = P[a].X - P[i].X;
                var dy = P[a].Y - P[i].Y;
                var d = dx * dx + dy * dy;
                ok[i] |= d <= x;
            }
        }

        return ok.All(x => x);
    }

    const long inf = (long)1e18;
    var answer = Math.Sqrt(BinarySearch(-1, inf, F));
    Console.WriteLine(answer);
}

public static long BinarySearch(long ng, long ok, Func<long, bool> func)
{
    while (Math.Abs(ok - ng) > 1)
    {
        var m = (ok + ng) / 2;
        if (func(m)) ok = m;
        else ng = m;
    }
    return ok;
}

問題C

コンテスト提出
 復習提出

D=0のときは明らかに、Abs(X-A)となります。以下それ以外のときにd=(X-A)/Dとし、xを初項を除く項数の数としてF(x)=Abs(X-(A+D*x))としたとき、

0<=d<=N-2のとき、初項+d項目と初項+(d+1)項目の間にXが存在するため、F(d)とF(d+1)の回数が小さいほうが答えとなります。
d=N-1のとき、N項より大きな項にすることができないため、F(N-1)となります。
d<0のとき、1項より小さな項にすることができないため、F(0)となります。

このことから、dを0<=d<=N-1に制限したときのF(d)とd+1<=N-1ならばF(d+1)の回数が小さいほうが答えとなります。

public static void Solve()
{
    var (X, A, D, N) = Scanner.Scan<long, long, long, long>();

    long F(long n)
    {
        return Math.Abs(X - (A + n * D));
    }

    if (D == 0)
    {
        Console.WriteLine(F(0));
        return;
    }

    var n = Math.Max(0, Math.Min(N - 1, (X - A) / D));
    var answer = F(n);
    if (n + 1 <= N - 1) answer = Math.Min(answer, F(n + 1));
    Console.WriteLine(answer);
}

問題D

コンテスト提出
 復習提出

クエリごとにAの値を走査してしまうと、O(QN)かかってしまい、実行時間制限に間に合いません。そこで、Aの値をソートし、AにおいてX以上が現れる位置i (0-indexed)において左右に二つに分けた場合、左側の操作に必要な回数はX*左側の個数 - A[0..i)の合計となり、右側の操作に必要な回数はA[i..N)の合計 - X*右側の個数となることがわかります。
そのため、あらかじめAの累積和を求めておき、クエリごとにAにおいてX以上が現れる位置を二部探索で求めることで、位置を求めることにO(logN)、左側の合計と右側の合計を求めることにO(1)で対応することができ、全体でO(QlogN)で求めることができるようになります。

public static void Solve()
{
    var (N, Q) = Scanner.Scan<int, int>();
    var A = Scanner.ScanEnumerable<long>().ToArray();
    Array.Sort(A);
    var cum = new long[N + 1];
    for (var i = 0; i < N; i++)
    {
        cum[i + 1] = cum[i] + A[i];
    }

    while (Q-- > 0)
    {
        var X = Scanner.Scan<long>();
        var l = LowerBound(A, X);
        var r = N - l;
        var answer = Math.Abs(cum[l] - X * l) + Math.Abs((cum[N] - cum[l]) - X * r);
        Console.WriteLine(answer);
    }
}

public static int LowerBound<T>(ReadOnlySpan<T> source, T key) where T : IComparable<T>
{
    var (l, r) = (-1, source.Length);
    while (r - l > 1)
    {
        var m = l + (r - l) / 2;
        if (source[m].CompareTo(key) >= 0) r = m;
        else l = m;
    }
    return r;
}

問題E

復習提出

public static void Solve()
{
    var (N, M) = Scanner.Scan<int, int>();
    var S = Scanner.ScanEnumerable<long>().ToArray();
    var X = Scanner.ScanEnumerable<long>().ToArray();

    var B = new long[N];
    for (var i = 0; i < N - 1; i++)
    {
        B[i + 1] = S[i] - B[i];
    }

    var dict = new Dictionary<long, long>();
    for (var i = 0; i < N; i++)
    {
        for (var j = 0; j < M; j++)
        {
            var c = X[j] - B[i];
            if (i % 2 == 1) c *= -1;
            if (!dict.ContainsKey(c)) dict[c] = 0;
            dict[c]++;
        }
    }

    var answer = dict.Values.Max();
    Console.WriteLine(answer);
}

はじめに

コンテスト

問題A

問題B

問題C

問題D

問題E