ABC231

はじめに

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

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

コンテスト

https://atcoder.jp/contests/abc231

問題A

コンテスト提出

入力とって浮動小数点に変換100で割ります。 誤差は10e-3なので特に気にしなくてもよさそう。

public static void Solve()
{
    var D = Scanner.Scan<double>();
    var answer = D / 100;
    Console.WriteLine(answer);
}

問題B

コンテスト提出

ディクショナリで数え上げます。

public static void Solve()
{
    var N = Scanner.Scan<int>();
    var dict = new Dictionary<string, int>();
    for (var i = 0; i < N; i++)
    {
        var s = Scanner.Scan<string>();
        if (!dict.ContainsKey(s)) dict[s] = 0;
        dict[s]++;
    }

    var answer = "";
    var curr = 0;
    foreach (var (k, v) in dict)
    {
        if (v >= curr)
        {
            curr = v;
            answer = k;
        }
    }

    Console.WriteLine(answer);
}

問題C

コンテスト提出

愚直に探索を行うと、時間計算量がO(N^2)となり、TLEになってしまいます。
そこで、入力された身長をあらかじめソートしておき、クエリごとに二部探索をすることで、クエリあたり時間計算量O(logN)で求めることができ、全体として時間計算量O(NlogN)で求めることができます。

public static void Solve()
{
    var (N, Q) = Scanner.Scan<int, int>();
    var A = Scanner.ScanEnumerable<long>().ToArray();
    Array.Sort(A);

    while (Q-- > 0)
    {
        var x = Scanner.Scan<long>();
        var answer = N - LowerBound(A, x);
        Console.WriteLine(answer);
    }
}

LowerBound関数は、ソート済みの配列において与えられた値以上が現れる初めてのインデックスを返します。

public static int LowerBound(long[] source, long key)
{
    var (l, r) = (-1, source.Length);
    while (r - l > 1)
    {
        var m = l + (r - l) / 2;
        if (source[m] >= key) r = m;
        else l = m;
    }
    return r;
}

問題D

コンテスト提出

グラフとして扱うと、一列に並べるということは、隣り合う頂点は2つ以下である必要があります。また、ループがある場合は一列に並べることはできません。
そのため、各頂点の辺の数とグラフのループ判定を行うことで解くことができます。
ループ判定はDFSでおこない、既に訪れた頂点があればループがあるという判定を行います。

public static void Solve()
{
    var (N, M) = Scanner.Scan<int, int>();
    var G = new List<int>[N].Select(x => new List<int>()).ToArray();
    var deg = new int[N];
    for (var i = 0; i < M; i++)
    {
        var (a, b) = Scanner.Scan<int, int>();
        a--; b--;
        G[a].Add(b);
        G[b].Add(a);
        deg[a]++;
        deg[b]++;
    }

    var used = new bool[N];

    bool Dfs(int u, int p)
    {
        var result = true;
        foreach (var v in G[u])
        {
            if (v == p) continue;
            if (used[v]) return false;
            used[v] = true;
            result &= Dfs(v, u);
        }
        return result;
    }

    var answer = deg.All(x => x <= 2);
    for (var i = 0; i < N && answer; i++)
    {
        if (used[i] || deg[i] == 0) continue;
        used[i] = true;
        answer &= Dfs(i, -1);
    }

    Console.WriteLine(answer ? "Yes" : "No");
}

問題E

復習提出

コンテスト中の考察では、

• それぞれの硬貨の選び方は、Ceil(X/A)またはFloor(X/A)の2通りを大きな硬貨から選ぶことができる。
• 大きな硬貨から値を引いていき、0になるまでの距離として考えることができるので、絶対値で考えられる。

void Dfs(long curr, long count, int idx)
{
    if(curr == 0)
    {
        answer = Math.Min(answer, count);
        return;
    }
    if(idx < 0) return;
    
    var ceil = (curr + A[idx] - 1) / A[idx];
    var floor = curr / A[idx];
    Dfs(Math.Abs(curr - A[idx] * ceil), count + ceil, idx + 1);
    Dfs(Math.Abs(curr - A[idx] * floor), count + floor, idx + 1);
}

メモ化がうまくできずF問題に移りました。

解説を見たところ、考え方はあっていたので、ディクショナリを使ったdpをしました。

public static void Solve()
{
    const long inf = (long)1e18;
    var dp1 = new Dictionary<long, long>();
    dp1[X] = 0;
    for (var i = N - 1; i >= 0; i--)
    {
        var dp2 = new Dictionary<long, long>();
        foreach (var (x, c) in dp1)
        {
            var ceil = (x + A[i] - 1) / A[i];
            var a = Math.Abs(x - ceil * A[i]);
            if (!dp2.ContainsKey(a)) dp2[a] = inf;
            dp2[a] = Math.Min(dp2[a], c + ceil);
    
            var floor = x / A[i];
            var b = Math.Abs(x - floor * A[i]);
            if (!dp2.ContainsKey(b)) dp2[b] = inf;
            dp2[b] = Math.Min(dp2[b], c + floor);
        }
    
        dp1 = dp2;
    }

    var answer = dp1[0];
    Console.WriteLine(answer);
}

問題F

復習提出

コンテスト中の考察では、

• 求めるものはA[i] >= A[j] && B[i] <= B[j]となるiとjの組み合わせの数。
• 何かしらのソートの後にFenwickTreeでどうにかできそう。
• 値が大きいが圧縮すればよさそう。

頭の中で考えがまとまらず、実装ができずに時間切れになりました。

復習時の考察では上記に加えて、

• AとBをセットにしたとき、Aの降順かつBの昇順でソートすればよさそう。
• AとBの値が同じものが複数あった場合の処理が必要そう。

AとBを圧縮後、ABをタプルとしてディクショナリで数え上げます。 Aの降順かつBの昇順でソートし、順番に見ていくことでそれ以前のAの値は現在のAの値よりも大きく、FenwickTreeでBの個数を管理することで、現在のBの値より小さいBの個数を数え上げることができます。その値にABタプルの個数を掛けることで、同じABの組み合わせが複数あった場合に対処できるようになります。

public static void Solve()
{
    var N = Scanner.Scan<int>();
    var A = Scanner.ScanEnumerable<int>().ToArray();
    var B = Scanner.ScanEnumerable<int>().ToArray();
    var (ca, _) = Compress(A);
    var (cb, _) = Compress(B);
    var dict = new Dictionary<(int A, int B), int>();
    for (var i = 0; i < N; i++)
    {
        var ab = (ca[A[i]], cb[B[i]]);
        if (!dict.ContainsKey(ab)) dict[ab] = 0;
        dict[ab]++;
    }

    var ABC = dict.Select(x => (A: x.Key.A, B: x.Key.B, C: x.Value)).ToArray();
    Array.Sort(ABC, (x, y) =>
    {
        var result = y.A.CompareTo(x.A);
        return result == 0 ? x.B.CompareTo(y.B) : result;
    });

    var answer = 0L;
    var ft = new FenwickTree(N);
    foreach (var (a, b, c) in ABC)
    {
        ft.Add(b, c);
        answer += ft.Sum(b + 1) * c;
    }

    Console.WriteLine(answer);
}