ABC243

Published on Saturday, 12 March 2022

Updated on Sunday, 13 March 2022

atcoder csharp

はじめに

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

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

コンテスト

https://atcoder.jp/contests/abc243

問題A

コンテスト提出

Vミリリットルを使い切る周を考えるために、1周で使う量であるA+B+Cで余りを取ってから考えます。

残りの量がA未満ならば、F
残りの量がA+B未満ならば、M
それ以外ならば、T

が答えとなります。

public static void Solve()
{
    var (V, A, B, C) = Scanner.Scan<int, int, int, int>();
    V %= A + B + C;
    if (V < A) { Console.WriteLine("F"); }
    else if (V < A + B) { Console.WriteLine("M"); }
    else { Console.WriteLine("T"); }
}

問題B

コンテスト提出

あらかじめAとBの要素をキーとして、位置をそれぞれ別の辞書に保持しておきます。そして、Aの要素を順番に見ていき、Aの要素がBの辞書に存在するとき、位置が一致する場合と一致しない場合をそれぞれ数え上げます。

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

    var dictA = new Dictionary<int, int>();
    var dictB = new Dictionary<int, int>();
    for (var i = 0; i < N; i++)
    {
        dictA[A[i]] = i;
        dictB[B[i]] = i;
    }

    var ans1 = 0;
    var ans2 = 0;
    foreach (var a in A)
    {
        if (dictB.ContainsKey(a))
        {
            if (dictA[a] == dictB[a]) ans1++;
            else ans2++;
        }
    }

    Console.WriteLine(ans1);
    Console.WriteLine(ans2);
}

愚直にシミュレーションしてしまうと実行時間制限に間に合わないので、処理を高速化する必要があります。まず、動く方向は左右の2つしかないので、Yの値が同じ人が衝突する可能性があると考えられます。そこで、左に動く人たちと右に動く人たちをそれぞれYごとに分けて管理することを考えます。そして、左に動く人たちと右に動く人たちのYが同じとき、右に動く人のうち最も左の位置(RX)と、左に動く人のうち最も右の位置(LX)においてRX<=LXが成り立てば、衝突が発生します。このことから、Yの値をキーとして、左に動く人たちの最も右のXと右に動く人たちの最も左のXをそれぞれ辞書を作成し、Yの値につき計算量O(1)で衝突するかの判定をすることができ、全体で計算量O(NlogN)で答えを求めることができます。

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

    var S = Scanner.Scan<string>();
    var L = new Dictionary<int, int>();
    var R = new Dictionary<int, int>();
    const int inf = (int)1e9;
    for (var i = 0; i < N; i++)
    {
        var (x, y) = P[i];
        if (S[i] == 'L')
        {
            if (!L.ContainsKey(y)) L[y] = 0;
            L[y] = Math.Max(L[y], x);
        }
        else
        {
            if (!R.ContainsKey(y)) R[y] = inf;
            R[y] = Math.Min(R[y], x);
        }
    }

    foreach (var (y, x) in R)
    {
        if (L.ContainsKey(y) && x <= L[y])
        {
            Console.WriteLine("Yes");
            return;
        }
    }

    Console.WriteLine("No");
}

問題D

コンテスト提出

N回の移動後にいる頂点の番号は10^18以下であることが制約で保証されていますが、愚直にシミュレーションしてしまうと、制約N<=10^6より、シミュレーション中の頂点の値が最大でX*2^(N/2)になり、現在のコンピュータの整数型では正しく計算することができません。そこで、子に移動して親に戻るといった、無駄な移動を省くことで、シミュレーション中でも頂点の値が10^18を超えないようにすることを考えます。これは、Sを順にみていったときUの直前にがLまたはRが存在すれば、LU、RUの操作を省くことができます。また、S=LRUUの操作ような場合、RUを省くと、LUとしてつながり、さらに省くことができます。このことから、Stackのようなデータ構造を用いて直前の操作を保持しながらSを順にみていき、Uの操作のとき、直前にLまたはRが存在するならば直前の操作を削除し、そうでなければ直前の操作を更新します。そして、Stackに残った操作をシミュレーションすることで、10^18の値を超えないように操作することができるようになります。

public static void Solve()
{
    var (N, X) = Scanner.Scan<int, long>();
    var S = Scanner.Scan<string>();
    var stack = new Stack<char>();
    foreach (var c in S)
    {
        if (stack.Count > 0 && stack.Peek() != 'U' && c == 'U')
        {
            stack.Pop();
        }
        else
        {
            stack.Push(c);
        }
    }

    var T = stack.ToArray();
    Array.Reverse(T);

    var answer = X;
    foreach (var c in T)
    {
        if (c == 'U')
        {
            answer /= 2;
        }
        else if (c == 'L')
        {
            answer *= 2;
        }
        else
        {
            answer *= 2;
            answer++;
        }
    }

    Console.WriteLine(answer);
}

問題E

復習提出

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

ワーシャルフロイド法で最短距離を求める?
最小全域木の頂点ごとの最短距離が元のグラフの頂点ごとの最短距離より大きいならば、一致するような辺を追加する?

TLEと時間切れでした。

ワーシャルフロイド法で最短距離を求め、辺を見ていったとき、頂点uと頂点vを結ぶ辺のコストがcだった場合、頂点kを中継点とするu->k->vとなるルートのコストがc以下だった場合、その辺は不要ということがわかります。

public static void Solve()
{
    var (N, M) = Scanner.Scan<int, int>();
    const long inf = (long)1e18;
    var G = new long[N, N];
    for (var i = 0; i < N; i++)
    {
        for (var j = 0; j < N; j++)
        {
            G[i, j] = inf;
        }
    }

    var E = new (int U, int V, long C)[M];
    for (var i = 0; i < M; i++)
    {
        var (a, b, c) = Scanner.Scan<int, int, long>();
        a--; b--;
        G[a, b] = G[b, a] = c;
        E[i] = (a, b, c);
    }

    for (var k = 0; k < N; k++)
    {
        for (var i = 0; i < N; i++)
        {
            for (var j = 0; j < N; j++)
            {
                G[i, j] = Math.Min(G[i, j], G[i, k] + G[k, j]);
            }
        }
    }

    var answer = 0;
    foreach (var (i, j, c) in E)
    {
        var unused = false;
        for (var k = 0; k < N; k++)
        {
            if (i == k || j == k) continue;
            unused |= G[i, k] + G[k, j] <= c;
        }

        if (unused) answer++;
    }

    Console.WriteLine(answer);
}

はじめに

コンテスト

問題A

問題B

問題C

問題D

問題E