ABC273

はじめに

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

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

コンテスト

https://atcoder.jp/contests/abc273

問題A

コンテスト提出

制約がN<=10と小さいので、下のような関数で解くことができます。

long F(x) => x == 0 ? 1 : x * F(x - 1);

しかし、何度も同じ関数が呼ばれてしまい、F(10)のときには10!回もの関数が呼ばれてしまいます。 そこで、あらかじめF(1), F(2), F(...)の計算結果をメモしながら次の値を求めていくことで、計算量を大幅に削減することができます。

public static void Solve()
{
    var N = Scanner.Scan<long>();
    var dp = new long[N + 1];
    dp[0] = 1;
    for (var i = 1; i <= N; i++)
    {
        dp[i] = dp[i - 1] * i;
    }

    var answer = dp[N];
    Console.WriteLine(answer);
}

問題B

コンテスト提出

四捨五入する桁(10^kの桁)の値をvとしたとき、v = X / 10^k % 10で求めることができます。
そして、vが4以下のときXの10^kの桁を0にします。
あるいは、vが5以上のときXの10^kの桁を0にし、10^(k+1)の桁を+1します。

public static void Solve()
{
    var (X, K) = Scanner.Scan<long, int>();
    var pow10 = 1L;
    for (var i = 0; i < K; i++)
    {
        var v = X / pow10 % 10;
        X -= v * pow10;
        if (v >= 5) X += pow10 * 10;
        pow10 *= 10;
    }

    Console.WriteLine(X);
}

問題C

コンテスト提出

Aの値はとても大きなものもありますが、求められるものは大小関係なので、Aを重複なしでソートしたときの順番を圧縮したものとして扱うことにします。
これにより、数値の種類数-数値を圧縮した時の順番がその数値よりも大きな数の種類数を求めることができます。
そして、全てのAにおいてその種類数を数え上げることで答えを求めることができます。

public static void Solve()
{
    var N = Scanner.Scan<int>();
    var A = Scanner.ScanEnumerable<int>().ToArray();
    var (map, _) = Compress(A);
    var count = A.Distinct().Count();
    var answer = new int[N];
    foreach (var a in A)
    {
        answer[count - (map[a] + 1)]++;
    }

    Console.WriteLine(string.Join(Environment.NewLine, answer));
}

public static (Dictionary<T, int> Map, Dictionary<int, T> ReMap) Compress<T>(IEnumerable<T> source)
{
    var distinct = source.Distinct().ToArray();
    Array.Sort(distinct);
    var map = new Dictionary<T, int>();
    var remap = new Dictionary<int, T>();
    foreach (var (x, i) in distinct.Select((x, i) => (x, i)))
    {
        map[x] = i;
        remap[i] = x;
    }

    return (map, remap);
}

問題D

復習提出

行と列の移動はそれぞれ独立しているので、行を移動するときの列、列を移動するときの行ごとにブロックの座標を管理し、移動途中にブロックが存在するかをLowerBound等で調べることで、クエリ当たり時間計算量O(logN)で求めることができます。

下記のプログラムは考え方はあっていると思いますが、テストケースが4つ落ちています。どこがバグかわからないです...
修正しました。 番兵に指定したrowsとcols、crとccのHとWが逆でした。

public static void Solve()
{
    var (H, W, cr, cc) = Scanner.Scan<int, int, long, long>();
    var N = Scanner.Scan<int>();
    var rows = new Dictionary<long, List<long>>();
    var cols = new Dictionary<long, List<long>>();
    for (var i = 0; i < N; i++)
    {
        var (r, c) = Scanner.Scan<long, long>();
        if (!rows.ContainsKey(r)) rows[r] = new List<long> { 0, (W + 1) };
        rows[r].Add(c);
        if (!cols.ContainsKey(c)) cols[c] = new List<long> { 0, (H + 1) };
        cols[c].Add(r);
    }

    foreach (var (_, v) in rows) v.Sort();
    foreach (var (_, v) in cols) v.Sort();

    var Q = Scanner.Scan<int>();
    while (Q-- > 0)
    {
        var (d, l) = Scanner.Scan<char, long>();

        if (d == 'L')
        {
            if (rows.ContainsKey(cr))
            {
                var lb = LowerBound(rows[cr], cc);
                cc = Math.Max(cc - l, rows[cr][lb - 1] + 1);
            }
            else
            {
                cc -= l;
            }
        }
        else if (d == 'R')
        {
            if (rows.ContainsKey(cr))
            {
                var ub = UpperBound(rows[cr], cc);
                cc = Math.Min(cc + l, rows[cr][ub] - 1);
            }
            else
            {
                cc += l;
            }
        }
        else if (d == 'U')
        {
            if (cols.ContainsKey(cc))
            {
                var lb = LowerBound(cols[cc], cr);
                cr = Math.Max(cr - l, cols[cc][lb - 1] + 1);
            }
            else
            {
                cr -= l;
            }
        }
        else if (d == 'D')
        {
            if (cols.ContainsKey(cc))
            {
                var ub = UpperBound(cols[cc], cr);
                cr = Math.Min(cr + l, cols[cc][ub] - 1);
            }
            else
            {
                cr += l;
            }
        }

        cr = Math.Min(Math.Max(cr, 1), H);
        cc = Math.Min(Math.Max(cc, 1), W);
        Console.WriteLine($"{cr} {cc}");
    }
}