ABC291

はじめに

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

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

コンテスト

https://atcoder.jp/contests/abc291

問題A

コンテスト提出

S[i]が大文字かどうかはchar.IsUpperで調べることができ、そのiの値を出力します。

public static void Solve()
{
    var S = Scanner.Scan<string>();
    for (var i = 0; i < S.Length; i++)
    {
        if (char.IsUpper(S[i]))
        {
            Console.WriteLine(i + 1);
            return;
        }
    }
}

問題B

コンテスト提出

Xをソートし、先頭N人と末尾N人を除いた3N人の平均を求めます。

public static void Solve()
{
    var N = Scanner.Scan<int>();
    var X = Scanner.ScanEnumerable<long>().ToArray();
    Array.Sort(X);
    var s = X.Skip(N).Take(3 * N).Sum();
    var answer = (double)s / (3 * N);
    Console.WriteLine(answer);
}

問題C

コンテスト提出

既に訪れた座標を管理しながら現在の座標を遷移させることで、既に訪れたことがあるかを求めます。 訪れた座標のペアをHashSetなどのデータ構造で管理することで、時間計算量O(1)で現在の座標が訪れたことがあるかを調べることができます。

public static void Solve()
{
    var N = Scanner.Scan<int>();
    var S = Scanner.Scan<string>();
    var set = new HashSet<(int, int)>();
    var x = 0;
    var y = 0;
    set.Add((x, y));
    foreach (var c in S)
    {
        var dx = 0;
        var dy = 0;
        if (c == 'R') dx = 1;
        if (c == 'L') dx = -1;
        if (c == 'U') dy = 1;
        if (c == 'D') dy = -1;
        x += dx;
        y += dy;
        if (set.Contains((x, y)))
        {
            Console.WriteLine("Yes");
            return;
        }
        set.Add((x, y));
    }

    Console.WriteLine("No");
}

問題D

コンテスト提出

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

dp[i,j] := i番目のカードまで見たとき、i番目のカードがj(表,裏)のとき条件を満たすものの数

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

i=1のとき、
dp[1,0] = 1
dp[1,1] = 1

i>1のとき、
dp[i,0] += dp[i-1,0] (A[i]!=A[i-1])
dp[i,0] += dp[i-1,1] (A[i]!=B[i-1])
dp[i,1] += dp[i-1,0] (B[i]!=A[i-1])
dp[i,1] += dp[i-1,1] (B[i]!=B[i-1])

答えは、dp[N,0]+dp[N,1]となります。

public static void Solve()
{
    var N = Scanner.Scan<int>();
    var A = new int[N];
    var B = new int[N];
    for (var i = 0; i < N; i++)
    {
        var (a, b) = Scanner.Scan<int, int>();
        A[i] = a;
        B[i] = b;
    }

    var dp = new mint[N, 2];
    dp[0, 0] = dp[0, 1] = 1;
    for (var i = 1; i < N; i++)
    {
        if (A[i] != A[i - 1]) dp[i, 0] += dp[i - 1, 0];
        if (A[i] != B[i - 1]) dp[i, 0] += dp[i - 1, 1];
        if (B[i] != A[i - 1]) dp[i, 1] += dp[i - 1, 0];
        if (B[i] != B[i - 1]) dp[i, 1] += dp[i - 1, 1];
    }

    var answer = dp[N - 1, 0] + dp[N - 1, 1];
    Console.WriteLine(answer);
}

問題E

コンテスト提出

各整数の組について頂点Xから頂点Yの有効辺としたグラフを考えたとき、グラフをトポロジカルソートすることができ、かつ始点と終点が一意に定まるかが条件となります。
始点が一意に定まるかは、頂点の入次数が0の頂点数が1つであることで判定できます。
同様に、終点が一意に定まるかは頂点の出次数が0の頂点数が1つであることで判定できます。

誤答でした。

各整数の組について頂点Xから頂点Yの有効辺としたグラフを考えたとき、グラフをトポロジカルソートすることができ、頂点の遷移が一意であることが条件となります。

public static void Solve()
{
    var (N, M) = Scanner.Scan<int, int>();
    var G = new List<int>[N].Select(x => new List<int>()).ToArray();
    var E = new HashSet<(int, int)>();
    var deg = new int[N];

    for (var i = 0; i < M; i++)
    {
        var (x, y) = Scanner.Scan<int, int>();
        x--; y--;
        if (E.Contains((x, y))) continue;
        E.Add((x, y));
        G[x].Add(y);
        deg[y]++;
    }

    var queue = new Queue<int>();
    for (var i = 0; i < N; i++)
    {
        if (deg[i] == 0) queue.Enqueue(i);
    }

    var result = new int[N];
    var idx = 0;
    while (queue.Count > 0)
    {
        if (queue.Count > 1)
        {
            Console.WriteLine("No");
            return;
        }

        var u = queue.Dequeue();
        foreach (var v in G[u])
        {
            deg[v]--;
            if (deg[v] == 0) queue.Enqueue(v);
        }

        result[idx++] = u;
    }

    if (idx != N)
    {
        Console.WriteLine("No");
        return;
    }

    Console.WriteLine("Yes");
    var answer = new int[N];
    for (var i = 0; i < N; i++)
    {
        answer[result[i]] = i + 1;
    }

    Console.WriteLine(string.Join(" ", answer));
}

問題F

復習提出

dp1[i]を都市1から都市iまでにかかる最小の移動回数、dpN[j]を都市jから都市Nまでにかかる最小の移動回数としたとき、dp1[u]+dpN[v]+1 (1<=u<k<v<=N,v<=u+M)の最小値が都市kを通らずに都市1から都市Nへの最小の移動回数となります。

public static void Solve()
{
    var (N, M) = Scanner.Scan<int, int>();
    var S = new string[N];
    for (var i = 0; i < N; i++)
    {
        S[i] = Scanner.Scan<string>();
    }

    var dpS = new long[N];
    var dpT = new long[N];
    const long Inf = (long)1e18;
    Array.Fill(dpS, Inf);
    Array.Fill(dpT, Inf);
    dpS[0] = dpT[N - 1] = 0;
    for (var v = 1; v < N; v++)
    {
        for (var u = Math.Max(v - M, 0); u < v; u++)
        {
            if (S[u][v - u - 1] == '1') dpS[v] = Math.Min(dpS[v], dpS[u] + 1);
        }
    }

    for (var v = N - 1; v > 0; v--)
    {
        for (var u = Math.Max(v - M, 0); u < v; u++)
        {
            if (S[u][v - u - 1] == '1') dpT[u] = Math.Min(dpT[u], dpT[v] + 1);
        }
    }

    var answers = new List<long>(N - 2);
    for (var k = 1; k < N - 1; k++)
    {
        var answer = Inf;
        for (var u = Math.Max(k - M, 0); u < k; u++)
        {
            for (var v = k + 1; v < Math.Min(u + M + 1, N); v++)
            {
                if (S[u][v - u - 1] == '1') answer = Math.Min(answer, dpS[u] + dpT[v] + 1);
            }
        }

        answers.Add(answer == Inf ? -1 : answer);
    }

    Console.WriteLine(string.Join(" ", answers));
}