ABC262

はじめに

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

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

コンテスト

https://atcoder.jp/contests/abc262

問題A

コンテスト提出

Yが4の倍数ならば2年後、Yが4の倍数+1ならば1年後、Yが4の倍数+2ならばその年、Yが4の倍数+3ならば3年後が答えとなります。 Yを4で割った余りが4の倍数+nのnなので、その値によって答えを求めます。

public static void Solve()
{
    var Y = Scanner.Scan<int>();
    var answer = Y;
    if (Y % 4 == 0) answer += 2;
    if (Y % 4 == 1) answer += 1;
    if (Y % 4 == 3) answer += 3;
    Console.WriteLine(answer);
}

問題B

コンテスト提出

UとV間に辺があるかどうかを二次元配列Gで表現し、G[a,b]、G[b,c]、G[c,a]のすべてに辺が存在するときの総数を数え上げます。

public static void Solve()
{
    var (N, M) = Scanner.Scan<int, int>();
    var G = new bool[N, N];
    for (var i = 0; i < M; i++)
    {
        var (u, v) = Scanner.Scan<int, int>();
        u--;
        v--;
        G[u, v] = G[v, u] = true;
    }

    var answer = 0;
    for (var a = 0; a < N; a++)
    {
        for (var b = a + 1; b < N; b++)
        {
            for (var c = b + 1; c < N; c++)
            {
                if (G[a, b] && G[b, c] && G[c, a]) answer++;
            }
        }
    }

    Console.WriteLine(answer);
}

問題C

コンテスト提出

条件となるiとjを全探索してしまうと、時間計算量がO(N^2)となり、実行時間制限内に答えを求めることはできません。 条件を満たす要素を考えてみると、(i==A[i], j==A[j])と(i==A[j], j==A[i])となる組み合わせが対象となります。 前者の場合、[1, x, x, 4, 5]のようなAがあったとすると、(1,4)、(1,5)、(4,5)が答えとなり、i==A[i]となる要素から2つ選ぶ組み合わせとなるので、i==A[i]の個数をCとすると、C*(C-1)/2が前者の組み合わせの数となります。 一方、後者の場合、i<jよりA[i]>iかつA[A[i]]==iとなるものがペアとして成り立ち、その総和が後者の組み合わせの数となります。 よって、これらの総和が答えとなります。 Nが最大5*10^5なので、intでは収まらないので注意が必要です。

public static void Solve()
{
    var N = Scanner.Scan<int>();
    var A = Scanner.ScanEnumerable<int>().Select(x => x - 1).ToArray();
    var answer = 0L;
    var same = 0L;
    for (var i = 0; i < N; i++)
    {
        if (A[i] == i) same++;
        else if (A[i] > i && A[A[i]] == i) answer++;
    }

    answer += same * (same - 1) / 2;
    Console.WriteLine(answer);
}

問題D

復習提出

Aの項を選ぶ個数を1つ決めたときの和の余りを動的計画法で求め、全て求めたときのあまりが0の数の1からNまでの総和が答えとなります。

public static void Solve()
{
    var N = Scanner.Scan<int>();
    var A = Scanner.ScanEnumerable<long>().ToArray();
    mint answer = 0;

    for (var c = 1; c <= N; c++)
    {
        var dp = new mint[N + 1, N + 1, N];
        dp[0, 0, 0]++;
        for (var i = 0; i < N; i++)
        {
            for (var j = 0; j < N; j++)
            {
                for (var k = 0; k < N; k++)
                {
                    dp[i + 1, j + 1, (k + A[i]) % c] += dp[i, j, k];
                    dp[i + 1, j, k] += dp[i, j, k];
                }
            }
        }

        answer += dp[N, c, 0];
    }

    Console.WriteLine(answer);
}