ハイパー LINQ 集 (AtCoder 2020年4月)

// Competitive Programming (1) Advent Calendar 2020 および C# その2 Advent Calendar 2020 の 12 日目の記事です。

このシリーズでは、C#、とくに LINQ で簡潔に書ける競技プログラミングの問題を集めて記事にしています。 Advent Calendar ということで、本来ならこの時点で AtCoder の2020年11月分を書くつもりでしたが、まったく追いつかなくなってしまいました。というわけで、2020年4月分の記事です。

2020年4月といえば、Judge System Update Test Contest 202004 で言語アップデートが実施され、定期開催コンテストとしては ABC 162 から C# 8.0 (.NET Core 3.1.201 など) で提出できるようになりました。

ところで、毎月分を一つの記事としているのですが、ここ数か月間の AtCoder の出題傾向を見ると、LINQ で瞬時に書けるような素直なデータ集計問題は減ってきています。
~~たぶん乱獲のせいです。~~
C# の短いコードでも茶色・緑色近辺で十分戦えるという趣旨で書いてきたのですが、このシリーズが今後どうなるかはわかりません。

さて、以下は本題で、前回までと同様の体裁です。

2020年4月の AtCoder の問題を、LINQ (C#) を使って解いていきます。全8問。
今回は第2回アルゴリズム実技検定も対象としています。
問題文はそれぞれのリンク先を参照してください。

■ ABC 161 B - Popular Vote

投票数の和 $S$ を求めておき、 $A_i$ のうち $\dfrac{S}{4M}$ 以上となるものの個数が $M$ 以上であるかどうかを判定します。
なお、小数を使うと誤差を考慮しなければならなくなるため、整数型のまま比較します。

using System;
using System.Linq;

class B
{
    static int[] Read() => Console.ReadLine().Split().Select(int.Parse).ToArray();
    static void Main()
    {
        var m = Read()[1];
        var a = Read();

        var s = a.Sum();
        Console.WriteLine(a.Count(x => 4 * m * x >= s) >= m ? "Yes" : "No");
    }
}

■ ABC 161 D - Lunlun Number

LINQ で書くのは若干気が引ける問題でも LINQ を使い込み切りましょう。
実行速度が犠牲になるコードとなっていますが、これくらいなら気にしません。

まず、i 桁のルンルン数リストから i + 1 桁のルンルン数リストを生成するためのローカル関数 Next を用意しておきます。ここでは i 桁の各ルンルン数に対し、その下1桁との差の絶対値が1以下の数字 (10種類のうちたかだか3種類) をその末尾に追加することで、i + 1 桁の新たなルンルン数を作ります。

あとはジャグ配列を用意して、各桁のルンルン数リストを順次格納していき、それらの要素をすべて列挙して K 番目を求めます。
なお、問題文の出力例 4 を見れば、制約により最大10桁で収まることがわかります。

using System;
using System.Linq;

class D
{
    static void Main()
    {
        var k = int.Parse(Console.ReadLine()) - 1;

        long[] Next(long[] a) => a.SelectMany(x => Enumerable.Range(0, 10).Where(d => Math.Abs(x % 10 - d) <= 1).Select(d => x * 10 + d)).ToArray();

        var lun = new long[10][];
        lun[0] = Enumerable.Range(1, 9).Select(i => (long)i).ToArray();
        Console.WriteLine(Enumerable.Range(0, 10).SelectMany(i => i > 0 ? lun[i] = Next(lun[i - 1]) : lun[i]).ElementAt(k));
    }
}

■ Judge System Update Test Contest 202004 B - Picking Balls

第1キーをボールの色 ("R", "B" の順)、第2キーをボールに書かれた数値としてソートし、ボールに書かれた数値を出力します。

なお、タプル型を使うと、複数キーによるソートが OrderBy だけで (ThenBy を使わずに) できます。ここでは (bool, int) 型としています。 bool 型では false, true が昇順です。

using System;
using System.Linq;

class B
{
    static void Main()
    {
        var n = int.Parse(Console.ReadLine());
        var q = new int[n]
            .Select(_ => Console.ReadLine().Split())
            .Select(x => (x[1] == "B", v: int.Parse(x[0])))
            .OrderBy(x => x)
            .Select(b => b.v);
        Console.WriteLine(string.Join("\n", q));
    }
}

■ ABC 162 B - FizzBuzz Sum

1 から N までの整数のうち、3でも5でも割り切れないものの和を求めます。

using System;
using System.Linq;

class B
{
    static void Main()
    {
        var n = int.Parse(Console.ReadLine());
        Console.WriteLine(Enumerable.Range(1, n).Where(x => x % 3 > 0 && x % 5 > 0).Sum(x => (long)x));
    }
}

■ 第2回アルゴリズム実技検定 B - Plurality Voting

候補者を表す文字をキーとしてグループ化し、その要素数の降順に並べ替えて、先頭のグループのキーを求めます。

using System;
using System.Linq;

class B
{
    static void Main() => Console.WriteLine(Console.ReadLine().GroupBy(x => x).OrderByDescending(g => g.Count()).First().Key);
}

■ ABC 163 B - Homework

遊ぶことができる日数は、 $N$ から $A_i$ の和を引いた値です。
これが負になる場合は、-1 に切り上げます。

using System;
using System.Linq;

class B
{
    static int[] Read() => Console.ReadLine().Split().Select(int.Parse).ToArray();
    static void Main()
    {
        var n = Read()[0];
        var a = Read();
        Console.WriteLine(Math.Max(n - a.Sum(), -1));
    }
}

■ ABC 163 C - management

$A_i$ の値をキーとしてグループ化し、各グループの要素数を出力します。

ToLookup で返される Lookup<TKey, TElement> クラスでは、指定されたキーが存在しない場合でも要素数 0 のコレクションを返します。 Dictionary<TKey,TValue> クラスのようなキーの存在による場合分けは必要ありません。

using System;
using System.Linq;

class C
{
    static void Main()
    {
        var n = int.Parse(Console.ReadLine());
        var d = Console.ReadLine().Split().Select(int.Parse).ToLookup(x => x);
        Console.WriteLine(string.Join("\n", Enumerable.Range(1, n).Select(i => d[i].Count())));
    }
}

■ ABC 164 C - gacha

重複を排除して要素の個数を求めます。

using System;
using System.Linq;

class C
{
    static void Main() => Console.WriteLine(new int[int.Parse(Console.ReadLine())].Select(_ => Console.ReadLine()).Distinct().Count());
}