ABC237

Published on Sunday, 30 January 2022

Updated on Monday, 31 January 2022

atcoder csharp

はじめに

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

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

コンテスト

https://atcoder.jp/contests/ABC237

問題A

コンテスト提出

C#含めほとんどの言語では、1 << xのようなビットシフト計算が備わっており、2のx乗を表現することができます。例えば、1 << 2は、1を2進数で表すと1であり、2つ左にシフトすると100になって、10進数では4を表現します。

public static void Solve()
{
    var N = Scanner.Scan<long>();
    const long inf = 1L << 31;
    Console.WriteLine(-inf <= N && N < inf ? "Yes" : "No");
}

問題B

コンテスト提出

転置行列は、i行j列目をj行i列目にしたものなので、そのまま添え字を入れ替えたものを結果として出力します。

public static void Solve()
{
    var (H, W) = Scanner.Scan<int, int>();
    var A = new int[H, W];
    for (var i = 0; i < H; i++)
    {
        var AA = Scanner.ScanEnumerable<int>().ToArray();
        for (var j = 0; j < W; j++)
        {
            A[i, j] = AA[j];
        }
    }

    var B = new int[W, H];
    for (var i = 0; i < H; i++)
    {
        for (var j = 0; j < W; j++)
        {
            B[j, i] = A[i, j];
        }
    }

    Printer.Print2D(B, " ");
}

あらかじめ、文字列前方と後方の連続するaを無視した文字列が回文であれば元の文が回文である可能性があります。このとき、文字列前方の連続するaの個数が文字列後方の連続するaの個数以下場合は、足りないaを前方に追加することで回文にすることができますが、それ以外(前方>後方)の場合は後方にaを追加することはできないので、回文にすることはできません。例えば、aabcbaaaでは、前方と後方の連続したaを無視するとbcbとなり回文になり、前方(2)は後方(3)以下なので、回文にすることができます。一方で、 aaabcbaaでは、同様に無視するとbcbとなり回文になりますが、前方(3)は後方(2)より大きいため、回文にすることはできません。

public static void Solve()
{
    var S = Scanner.ScanLine();
    var (l, r) = (0, S.Length - 1);
    while (r >= 0 && S[r] == 'a') r--;
    while (l < r && S[l] == 'a') l++;

    var lc = l;
    var rc = S.Length - r - 1;
    if (lc > rc)
    {
        Console.WriteLine("No");
        return;
    }

    var t = S[l..(r + 1)];
    var answer = t == new string(t.Reverse().ToArray());
    Console.WriteLine(answer ? "Yes" : "No");
}

問題D

コンテスト提出復習提出

数字をノードとしてみたときに、0をルートとするツリーを作成し、深さ優先探索の通りがかり順(左部分木->自分->右部分木)で見ていった結果が答えとなります。

public static void Solve()
{
    var N = Scanner.Scan<int>();
    var S = Scanner.ScanLine();
    var nodes = new Node[N + 1];
    for (var i = 0; i <= N; i++)
    {
        nodes[i] = new Node();
    }
    
    foreach (var (c, i) in S.Select((x, i) => (x, i)))
    {
        if (c == 'L')
        {
            nodes[i].Left = i + 1;
        }
        else
        {
            nodes[i].Right = i + 1;
        }
    }
    
    var answer = new List<int>();
    
    void Dfs(int curr)
    {
        if (curr < 0) return;
        Dfs(nodes[curr].Left);
        answer.Add(curr);
        Dfs(nodes[curr].Right);
    }
    
    Dfs(0);
    
    Console.WriteLine(string.Join(" ", answer));
}

Nodeは左側と右側を持つクラスです。

public class Node
{
    public int Left { get; set; } = -1;
    public int Right { get; set; } = -1;
}

Dequeを使った場合は、文字列を逆順から見て、反対側に追加すればよいです。 C#にはDequeというクラスはありませんが、LinkedList<T>という連結リストがあるため、それを使うことで代用することができます。

public static void Solve()
{
    var N = Scanner.Scan<int>();
    var S = Scanner.ScanLine();
    var deq = new Deque<int>();
    deq.PushBack(N);
    foreach (var (c, i) in S.Select((x, i) => (x, i)).Reverse())
    {
        if (c == 'L') deq.PushBack(i);
        else deq.PushFront(i);
    }
    
    Console.WriteLine(string.Join(" ", deq));
}

問題E

コンテスト提出復習提出

頂点Uと頂点Vをつなぐ辺にそれぞれ重みを付けてグラフを作成したときの、拡張ダイクストラ法で解くことを考えます。楽しさの変化量を辺の重みとしてみたとき、Hを頂点の高さ、dを高さの差の絶対値とすると、H[U]<H[V]であればU->Vの辺はdの重み、H[U]>H[V}であればU->Vの辺は-2dの重み、H[U]=H[V]であれば0の重みをそれぞれの辺につけます。
その重み付きグラフを用いて、頂点0から優先度付きキューを用いて幅優先探索を行い、各頂点のコストを最大化したときの最大の値が答えとなります。

嘘解放でした。この実装では、after_contestでTLEになります。

競技プログラミングをするフレンズ E問題after_contest

楽しさの減少を標高差のまま考えたとき、U->Vに至る経路がどうであれ、楽しさはH[U]-H[V]を得ることができます。楽しさの減少が標高差の2倍のときは、U->Vに至る経路のうちH[X]<H[Y]の移動を行ったときに、楽しさがH[X]-H[Y]減少します。言い換えれば、減少分を辺のコストとしたときの単一始点最短経路問題として考えることができます。そして、各頂点の得られる楽しさから最小化された頂点のコストを引くことで、頂点に対する楽しさの最大化を行うことができます。

public static void Solve()
{
    var (N, M) = Scanner.Scan<int, int>();
    var H = Scanner.ScanEnumerable<long>().ToArray();
    var G = new List<(int, long)>[N].Select(x => new List<(int, long)>()).ToArray();
    for (var i = 0; i < M; i++)
    {
        var (u, v) = Scanner.Scan<int, int>();
        u--; v--;
        G[u].Add((v, Math.Max(0, H[v] - H[u])));
        G[v].Add((u, Math.Max(0, H[u] - H[v])));
    }

    var costs = new long[N];
    Array.Fill(costs, long.MaxValue);
    costs[0] = 0;
    var queue = new PriorityQueue<(int U, long Cost)>((x, y) => x.Cost.CompareTo(y.Cost));
    queue.Enqueue((0, 0));

    while (queue.Count > 0)
    {
        var (u, cu) = queue.Dequeue();
        if (costs[u] < cu) continue;
        foreach (var (v, cv) in G[u])
        {
            var c = costs[u] + cv;
            if (costs[v] <= c) continue;
            costs[v] = c;
            queue.Enqueue((v, c));
        }
    }

    var answer = 0L;
    for (var i = 0; i < N; i++)
    {
        answer = Math.Max(answer, H[0] - H[i] - costs[i]);
    }

    Console.WriteLine(answer);
}

2022年1月31日現在のAtCoderのC#(.NET Core 3.1.201)ではPriorityQueueは標準ライブラリにないため、自作する必要があります。 C#(.NET 6.0)以降であれば、PriorityQueueが標準ライブラリに追加されるので、言語アップデートを待ちましょう。

問題F

復習提出

コンテスト中の考察です。

NMMMのdp?
部分増加列a1、a2、a3を固定したときのa1とa2の間の数、a2とa3の間の数、a3以降の数の組み合わせの数え上げ?
www(a1)xxx(a2)yyy(a3)zzzのような数列の時、www:1通り、xxx:長さc1、yyy:長さc2、zzz:長さc3で組み合わせ?

for(var a1 = 1; a1 <= M; a1++)
for(var a2 = a1 + 1; a1 + a2 <= M; a2++)
for(var a3 = a2 + 1; a1 + a2 + a3 <= M; a3++)
for(var c1 = 0; c1 <= N; c1++)
for(var c2 = 0; c1 + c2 <= N; c2++)
{
    var c3 = N - 3 - c1 - c2;
    // 組み合わせ?
}

解説では、部分増加列の最後尾として考えられる最小値の数列の状態数を求めるdpでした。

dp[i][a1][a2][a3] := 長さがiで、長さjの部分増加列の最後尾として考えられる最小値がajであるような数列の状態数

public static void Solve()
{
    var (N, M) = Scanner.Scan<int, int>();
    var dp = new mint[N + 1, M + 2, M + 2, M + 2];
    dp[0, M + 1, M + 1, M + 1] = 1;
    for (var i = 0; i < N; i++)
    {
        for (var a1 = 0; a1 <= M + 1; a1++)
        {
            for (var a2 = 0; a2 <= M + 1; a2++)
            {
                for (var a3 = 0; a3 <= M + 1; a3++)
                {
                    for (var x = 1; x <= M; x++)
                    {
                        if (x <= a1) dp[i + 1, x, a2, a3] += dp[i, a1, a2, a3];
                        else if (x <= a2) dp[i + 1, a1, x, a3] += dp[i, a1, a2, a3];
                        else if (x <= a3) dp[i + 1, a1, a2, x] += dp[i, a1, a2, a3];
                    }
                }
            }
        }
    }

    mint answer = 0;
    for (var a1 = 1; a1 <= M; a1++)
    {
        for (var a2 = a1 + 1; a2 <= M; a2++)
        {
            for (var a3 = a2 + 1; a3 <= M; a3++)
            {
                answer += dp[N, a1, a2, a3];
            }
        }
    }

    Console.WriteLine(answer);
}

はじめに

コンテスト

問題A

問題B

問題C

問題D

問題E

問題F