ABC259

はじめに

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

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

コンテスト

https://atcoder.jp/contests/abc259

問題A

コンテスト提出

M<Xのとき、DずつX-M年分変化したので、最終的な身長からその変化分を引いた数T-D*(X-M)が答えとなります。
X<=Mのとき、X歳にはすでにTであるため、M歳の時もTです。

public static void Solve()
{
    var (N, M, X, T, D) = Scanner.Scan<int, int, int, int, int>();
    var answer = T - D * Math.Max(X - M, 0);
    Console.WriteLine(answer);
}

問題B

コンテスト提出

ベクトル(a,b)に対してd度の回転の操作を行います。 これは、x' = x * cos(rad(d)) - y * sin(rad(d)), y' = x * sin(rad(d)) + y * cos(rad(d))で表すことができます。 度から弧度法(ラジアン)を求めるには、度 * PI / 180度で求めることができます。

public static void Solve()
{
    var (A, B, D) = Scanner.Scan<double, double, double>();
    var rad = D * Math.PI / 180.0;
    var sin = Math.Sin(rad);
    var cos = Math.Cos(rad);
    var x = A * cos - B * sin;
    var y = A * sin + B * cos;
    Console.WriteLine($"{x} {y}");
}

問題C

コンテスト提出

文字列が一致するということは、同じ文字が連続した区間ごとに分割し、区間順にみたときに次の条件を全ての文字の区間が満たすときになります。

• SとTの区間で出現する文字が一致する。
• SとTの区間で文字が連続する長さが両方とも1である。または、文字が連続する長さが両方とも2以上かつTの文字が連続する長さがSの文字が連続する長さ以上である。

public static void Solve()
{
    var S = Scanner.Scan<string>();
    var T = Scanner.Scan<string>();

    List<(char, int)> F(ReadOnlySpan<char> s)
    {
        var result = new List<(char, int)>();
        var r = 0;
        for (var l = 0; l < s.Length;)
        {
            r = l;
            while (r < s.Length && s[r] == s[l]) r++;
            result.Add((s[l], r - l));
            l = r;
        }

        return result;
    }

    var ss = F(S);
    var tt = F(T);
    var answer = ss.Count == tt.Count;
    if (answer)
    {
        for (var i = 0; i < ss.Count; i++)
        {
            var (s, cs) = ss[i];
            var (t, ct) = tt[i];
            answer &= s == t;
            answer &= cs == ct || cs > 1 && ct > 1 && cs < ct;
        }
    }

    Console.WriteLine(answer ? "Yes" : "No");
}

問題D

コンテスト提出

各円を頂点としたとき、円どうしで移動可能な場合に辺が存在すると考えると、グラフ問題として考えることができます。 ある二つの円が移動可能ということは、その二つの円が共有点を持つということになります。 共有点が存在するかどうかは、一つ目の円の半径をr1、二つ目の円の半径をr2、二つの円の中心間の距離をdとしたとき、abs(r1-r2)<=d<=r1+r2が満たされれるかどうかで判断することができます。 Disjoint Set Unionなどのデータ構造や深さ優先探索、幅優先探索などで、(sx,sy)が含まれる円と(tx,ty)が含まれる円が連結であるかの判定を行うことで、答えを求めることができます。

public static void Solve()
{
    var N = Scanner.Scan<int>();
    var (sx, sy, tx, ty) = Scanner.Scan<long, long, long, long>();
    var s = new Point(sx, sy);
    var t = new Point(tx, ty);

    var P = new (Point P, long R)[N];
    for (var i = 0; i < N; i++)
    {
        var (x, y, r) = Scanner.Scan<long, long, long>();
        P[i] = (new Point(x, y), r);
    }

    long SqD(Point p1, Point p2)
    {
        var dx = p1.X - p2.X;
        var dy = p1.Y - p2.Y;
        return dx * dx + dy * dy;
    }

    var okS = new bool[N];
    var okT = new bool[N];
    for (var i = 0; i < N; i++)
    {
        okS[i] = SqD(s, P[i].P) == P[i].R * P[i].R;
        okT[i] = SqD(t, P[i].P) == P[i].R * P[i].R;
    }

    var dsu = new DisjointSetUnion(N);

    for (var i = 0; i < N; i++)
    {
        for (var j = i + 1; j < N; j++)
        {
            var sqd = SqD(P[i].P, P[j].P);
            var rr1 = P[i].R + P[j].R;
            var rr2 = P[i].R - P[j].R;
            if (rr2 * rr2 <= sqd && sqd <= rr1 * rr1)
            {
                dsu.Merge(i, j);
            }
        }
    }

    var answer = false;
    for (var i = 0; i < N; i++)
    {
        for (var j = 0; j < N; j++)
        {

            answer |= okS[i] && okT[j] && dsu.IsSame(i, j);
        }
    }

    Console.WriteLine(answer ? "Yes" : "No");
}

public readonly struct Point
{
    public readonly long X;
    public readonly long Y;
    public Point(long x, long y) => (X, Y) = (x, y);
}