ABC318

Published on
Updated on
atcoder csharp

はじめに

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

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

Scannerクラス 
public static class Scanner
{
    public static T Scan<T>() where T : IConvertible => Convert<T>(ScanStringArray()[0]);
    public static (T1, T2) Scan<T1, T2>() where T1 : IConvertible where T2 : IConvertible
    {
        var input = ScanStringArray();
        return (Convert<T1>(input[0]), Convert<T2>(input[1]));
    }
    public static (T1, T2, T3) Scan<T1, T2, T3>() where T1 : IConvertible where T2 : IConvertible where T3 : IConvertible
    {
        var input = ScanStringArray();
        return (Convert<T1>(input[0]), Convert<T2>(input[1]), Convert<T3>(input[2]));
    }
    public static (T1, T2, T3, T4) Scan<T1, T2, T3, T4>() where T1 : IConvertible where T2 : IConvertible where T3 : IConvertible where T4 : IConvertible
    {
        var input = ScanStringArray();
        return (Convert<T1>(input[0]), Convert<T2>(input[1]), Convert<T3>(input[2]), Convert<T4>(input[3]));
    }
    public static (T1, T2, T3, T4, T5) Scan<T1, T2, T3, T4, T5>() where T1 : IConvertible where T2 : IConvertible where T3 : IConvertible where T4 : IConvertible where T5 : IConvertible
    {
        var input = ScanStringArray();
        return (Convert<T1>(input[0]), Convert<T2>(input[1]), Convert<T3>(input[2]), Convert<T4>(input[3]), Convert<T5>(input[4]));
    }
    public static (T1, T2, T3, T4, T5, T6) Scan<T1, T2, T3, T4, T5, T6>() where T1 : IConvertible where T2 : IConvertible where T3 : IConvertible where T4 : IConvertible where T5 : IConvertible where T6 : IConvertible
    {
        var input = ScanStringArray();
        return (Convert<T1>(input[0]), Convert<T2>(input[1]), Convert<T3>(input[2]), Convert<T4>(input[3]), Convert<T5>(input[4]), Convert<T6>(input[5]));
    }
    public static IEnumerable<T> ScanEnumerable<T>() where T : IConvertible => ScanStringArray().Select(Convert<T>);
    private static string[] ScanStringArray()
    {
        var line = Console.ReadLine()?.Trim() ?? string.Empty;
        return string.IsNullOrEmpty(line) ? Array.Empty<string>() : line.Split(' ');
    }
    private static T Convert<T>(string value) where T : IConvertible => (T)System.Convert.ChangeType(value, typeof(T));
}

コンテスト

https://atcoder.jp/contests/abc318

問題A

コンテスト提出

N日間のうちM日目以降の期間はN-M日間であり、この期間にFloor(N-M)/P回満月を見ることができます。
これにM日目を加えた、Floor(N-M)/P+1が答えとなります。
N-Mが負数になることがあるので注意が必要です。

public static void Solve()
{
    var (N, M, P) = Scanner.Scan<int, int, int>();
    var answer = (N - M + P) / P;
    Console.WriteLine(answer);
}

問題B

コンテスト提出

シートは最大でも0<=x<=100かつ0<=y<=100なので、100*100のグリッドを用意し、その領域がシートで覆われているかを判定します。

public static void Solve()
{
    var N = Scanner.Scan<int>();
    var H = 100;
    var W = 100;
    var G = new bool[H + 1, W + 1];
    for (var i = 0; i < N; i++)
    {
        var (a, b, c, d) = Scanner.Scan<int, int, int, int>();
        for (var x = a; x < b; x++)
        {
            for (var y = c; y < d; y++)
            {
                G[x, y] = true;
            }
        }
    }

    var answer = 0;
    for (var i = 0; i <= H; i++)
    {
        for (var j = 0; j <= W; j++)
        {
            if (G[i, j]) answer++;
        }
    }

    Console.WriteLine(answer);
}

問題C

コンテスト提出

周遊パスは好きな日に使うことができるので、Fをソートしても問題ありません。
次のような動的計画法を解きます。

dp[i] := i日間の旅行でかかる最小金額

遷移は次のようになります。

// i日目の運賃を通常料金で払うとき
dp[i+1] = Min(dp[i+1], dp[i]+F[i])

// i日目の運賃を周遊パスで払うとき
dp[i+D] = Min(dp[i+D], dp[i]+P)

i+DがNより大きい場合はNにまとめることができ、dp[N]が答えとなります。

public static void Solve()
{
    var (N, D, P) = Scanner.Scan<int, int, long>();
    var F = Scanner.ScanEnumerable<long>().ToArray();
    Array.Sort(F);
    var cum = new long[N + 1];
    const long Inf = (long)1e18;
    Array.Fill(cum, Inf);
    cum[0] = 0;
    for (var i = 0; i < N; i++)
    {
        cum[i + 1] = Math.Min(cum[i + 1], cum[i] + F[i]);
        var x = Math.Min(i + D, N);
        cum[x] = Math.Min(cum[x], cum[i] + P);
    }

    var answer = cum[N];
    Console.WriteLine(answer);
}

問題D

コンテスト提出

次のような動的計画法を解きます。

dp[s] := 既に選んだ頂点集合がsのときの選んだ重みの総和の最大値

遷移は次のようになります。

i番目の頂点とj番目の頂点がsに含まれていないとき、sにiとjを含んだ頂点集合をtとする。
dp[t] = Max(dp[t], dp[s]+D[i][j])

全ての頂点集合のうち、総和の最大値が答えとなります。

public static void Solve()
{
    var N = Scanner.Scan<int>();
    var D = new long[N, N];
    for (var i = 0; i < N - 1; i++)
    {
        var d = Scanner.ScanEnumerable<int>().ToArray();
        for (var j = 0; j < d.Length; j++)
        {
            D[i, i + j + 1] = d[j];
        }
    }

    var dp = new long[1 << N];
    dp[0] = 0;
    for (var s = 0; s < 1 << N; s++)
    {
        for (var i = 0; i < N; i++)
        {
            for (var j = i + 1; j < N; j++)
            {
                if ((s >> i & 1) == 1 || (s >> j & 1) == 1) continue;
                var t = s | (1 << i) | (1 << j);
                dp[t] = Math.Max(dp[t], dp[s] + D[i, j]);
            }
        }
    }

    long answer = 0;
    for (var s = 0; s < 1 << N; s++)
    {
        answer = Math.Max(answer, dp[s]);
    }

    Console.WriteLine(answer);
}

問題E

復習提出

L[x]を現在左側にあるxの個数、R[x]を現在右側にあるxの個数とします。
jを固定したとき、jに対して条件を満たすi,kの組み合わせの個数は、1<=y<=Nかつy!=A[j]のL[y]*R[y]の総和になります。
これにより、各jに対して時間計算量O(N)で組み合わせの個数を求めることができますが、全体時間計算量がO(N^2)になり、実行時間制限に間に合いません。
そこで、jを1つずらしたとき、L[A[j]]が1つ増え、R[A[j]]が1つ減ることから、組み合わせの個数を累積和として管理し、各jにおける差分のみを計算することで、各jに対して時間計算量O(1)で組み合わせの個数を求めることができるようになり、全体時間計算量O(N)で答えを求めることができます。

public static void Solve()
{
    var N = Scanner.Scan<int>();
    var A = Scanner.ScanEnumerable<int>().ToArray();
    var L = new long[N + 1];
    var R = new long[N + 1];

    foreach (var a in A) R[a]++;

    long answer = 0;
    long cum = 0;
    foreach (var a in A)
    {
        cum -= L[a] * R[a];
        answer += cum;
        R[a]--;
        L[a]++;
        cum += L[a] * R[a];
    }

    Console.WriteLine(answer);
}