ABC266

はじめに

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

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

コンテスト

https://atcoder.jp/contests/abc266

問題A

コンテスト提出

文字列Sの長さが奇数なので、SのインデックスFloor(Sの長さ/2)の文字が答えとなります。

public static void Solve()
{
    var S = Scanner.Scan<string>();
    var N = S.Length;
    Console.WriteLine(S[N / 2]);
}

問題B

コンテスト提出

N-xが998244353の倍数であるということは、Nを998244353で割ったときの余りがxになることがわかります。
また、言語によって負の数に対する余りの計算は異なり、余りが負の値になる場合があります。 aをb(!=0)で割ったときの余りがcのとき、a+bやa-bをbで割ったときの余りもcになることから、xが負の値のときは998244353を足すことで、0<=x<=998244353にすることができます。

public static void Solve()
{
    var N = Scanner.Scan<long>();
    const long M = 998244353;
    var x = N % M;
    if (x < 0) x += M;
    Console.WriteLine(x);
}

問題C

コンテスト提出
復習提出

全ての角が180度未満であるかを外積を用いて判定します。 角abcの外積はcross=(c.X-b.X)*(a.Y-b.Y)-(a.X-b.X)*(c.Y-b.Y)で計算でき、abcが反時計回りならcross>=0の場合角abcの角は180度未満になります。

public static void Solve()
{
    var N = 4;
    var P = new Point[N];
    for (var i = 0; i < N; i++)
    {
        var (x, y) = Scanner.Scan<int, int>();
        P[i] = new Point(x, y);
    }

    long Cross(Point a, Point b, Point c)
    {
        var (dx1, dy1) = (c.X - b.X, c.Y - b.Y);
        var (dx2, dy2) = (a.X - b.X, a.Y - b.Y);
        return dx1 * dy2 - dx2 * dy1;
    }

    var answer = true;
    for (var i = 0; i < N; i++)
    {
        var a = P[i];
        var b = P[(i + 1) % N];
        var c = P[(i + 2) % N];
        answer &= Cross(a, b, c) >= 0;
    }

    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);
}

問題D

コンテスト提出
復習提出

dp[t][x]:=時刻tの座標xにおける既に捕まえた大きさの最大値とした動的計画法を解きます。 これは、時刻tの座標xにおける大きさをA[t][x]としたとき、dp[t][x] = Max(dp[t-1][x-1], dp[t-1][x], dp[t-1][x+1]) + A[t][x]の遷移で求めることができます。

public static void Solve()
{
    var N = Scanner.Scan<int>();
    var A = new long[(int)1e5 + 1, 5];
    var T = 0;
    for (var i = 0; i < N; i++)
    {
        var (t, x, a) = Scanner.Scan<int, int, long>();
        A[t, x] = a;
        T = t;
    }

    const long inf = (long)1e18;
    var dp = new long[T + 1, 5];
    for (var i = 0; i <= T; i++)
    {
        for (var j = 0; j < 5; j++)
        {
            dp[i, j] = -inf;
        }
    }

    dp[0, 0] = 0;

    for (var t = 1; t <= T; t++)
    {
        for (var x = 0; x < 5; x++)
        {
            for (var p = x - 1; p <= x + 1; p++)
            {
                if (0 <= p && p < 5) dp[t, x] = Math.Max(dp[t, x], dp[t - 1, p] + A[t, x]);
            }
        }
    }

    var answer = 0L;
    for (var i = 0; i < 5; i++)
    {
        answer = Math.Max(answer, dp[T, i]);
    }

    Console.WriteLine(answer);
}

問題E

復習提出

n回目の期待値は、n-1回目の期待値と出目を比較して大きいほうを選んだときの1-6の出目の総和になります。

public static void Solve()
{
    var N = Scanner.Scan<int>();
    var answer = 0.0;
    for (var i = 0; i < N; i++)
    {
        var exp = 0.0;
        for (var x = 1; x <= 6; x++)
        {
            exp += Math.Max(x, answer) / 6.0;
        }

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

    Console.WriteLine(answer);
}