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

2020年2月の AtCoder の問題を、LINQ (C#) を使って解いていきます。全8問。
今回は Rated コンテストのほか、JOI 2019/2020 本選も対象としています。
問題文はそれぞれのリンク先を参照してください。

JOI 2019/2020 本選 A - 長いだけのネクタイ (Just Long Neckties)

2月最初の LINQ 問題はだいぶ難しめです。まず問題の意味やデータ構造を把握しなければなりません。しかし通常は Aggregate メソッドを使わずに解くでしょう。

商品の ID を記憶したうえで、数列 A, B を昇順に並べ替え、以降はその前提で考えます。試着会の奇妙さが最小となるのは、双方 N 本ずつの長さを昇順に並べ対応する順番のネクタイを試着したときだからです。
すると、 $C_{N+1}$ は $A_{N+1}$ を除いた奇妙さの最大値となります。さらに、 $C_N, \cdots , C_1$ はそれぞれ $A_N, \cdots , A_1$ を除いて前の結果をもとに順次最大値を計算していくことで求められます。

using System;
using System.Linq;

class A
{
    static void Main()
    {
        var n = int.Parse(Console.ReadLine());
        var a = Console.ReadLine().Split().Select((s, id) => (id, v: int.Parse(s))).OrderBy(x => x.v).ToArray();
        var b = Console.ReadLine().Split().Select(int.Parse).OrderBy(x => x).ToArray();

        var c = new int[n + 1];
        c[a[n].id] = a.Zip(b, (p, q) => Math.Max(p.v - q, 0)).Max();
        Enumerable.Range(0, n).Reverse().Aggregate(c[a[n].id], (t, i) => c[a[i].id] = Math.Max(t, Math.Max(a[i + 1].v - b[i], 0)));
        Console.WriteLine(string.Join(" ", c));
    }
}

ABC 154 B - I miss you...

String クラスのコンストラクターを使えば簡単なのですが、LINQ っぽい問題に見えるため LINQ を使っていきます。
入力の各文字を 'x' に変換して結合します。

using System;
using System.Linq;

class B
{
    static void Main() => Console.WriteLine(string.Join("", Console.ReadLine().Select(_ => 'x')));
}

ABC 154 C - Distinct or Not

数列の重複を排除した要素の個数が N に等しいかどうかを求めます。
なお、整数型に変換しなくてもかまいません。

using System;
using System.Linq;

class C
{
    static void Main() => Console.WriteLine(int.Parse(Console.ReadLine()) == Console.ReadLine().Split().Distinct().Count() ? "YES" : "NO");
}

ABC 155 A - Poor

前問とよく似ています。
重複を排除した整数の個数 (つまりグループ数) が 2 に等しいかどうかを求めます。

using System;
using System.Linq;

class A
{
    static void Main() => Console.WriteLine(Console.ReadLine().Split().Distinct().Count() == 2 ? "Yes" : "No");
}

ABC 155 B - Papers, Please

入力の全ての整数が「2で割り切れない」「3で割り切れる」「5で割り切れる」のいずれかを満たしていれば承認します。

using System;
using System.Linq;

class B
{
    static void Main()
    {
        Console.ReadLine();
        Console.WriteLine(Console.ReadLine().Split().Select(int.Parse).All(x => x % 2 != 0 || x % 3 == 0 || x % 5 == 0) ? "APPROVED" : "DENIED");
    }
}

ABC 155 C - Poll

書かれた文字列をキーとしてグループ化し、さらにそれを要素の個数をキーとしてグループ化し、そのキーで降順に並べ替えて最初のグループの要素を昇順に並べ替えます。

using System;
using System.Linq;

class C
{
    static void Main()
    {
        var n = int.Parse(Console.ReadLine());
        var q = new int[n].Select(_ => Console.ReadLine())
            .GroupBy(x => x)
            .GroupBy(g => g.Count(), g => g.Key)
            .OrderByDescending(g => g.Key)
            .First()
            .OrderBy(x => x);
        Console.WriteLine(string.Join("\n", q));
    }
}

ABC 156 B - Digits

LINQ を使わなくても Log 関数などで解ける問題ですが、気にせずに LINQ を使っていきます。
N を K で割り続け、その値が 0 となるまでの回数を求めます。
逆に 1 から開始して K を掛け続ける別解もあります。

using System;
using System.Linq;

class B
{
    static void Main()
    {
        var h = Console.ReadLine().Split().Select(int.Parse).ToArray();
        int n = h[0], k = h[1];
        Console.WriteLine(Enumerable.Range(1, 30).First(i => (n /= k) == 0));
    }
}

ABC 156 C - Rally

(解法 1) P の候補は 1 から 100 までの整数です。
そこで、これらの場合を全探索し、消費する体力の総和の最小値を求めます。

using System;
using System.Linq;

class C
{
    static void Main()
    {
        Console.ReadLine();
        var x = Console.ReadLine().Split().Select(int.Parse).ToArray();
        Console.WriteLine(Enumerable.Range(1, 100).Min(p => x.Sum(v => (v - p) * (v - p))));
    }
}

(解法 2) 消費する体力の総和が最小となる P は $X_i$ の平均値 (に最も近い整数) であることが二次方程式の考察でわかります。これなら計算量は $O(N)$ で済みます。

using System;
using System.Linq;

class C
{
    static void Main()
    {
        Console.ReadLine();
        var x = Console.ReadLine().Split().Select(int.Parse).ToArray();
        var p = Math.Round(x.Average());
        Console.WriteLine(x.Sum(v => (v - p) * (v - p)));
    }
}

バージョン

C# 8.0
- .NET Core 3.1.201 で提出
- 現行の AtCoder では、3種類の C# を選べる
- 今回のコードは、JOI 2019/2020 本選 A 以外は C# 6 でも可

Avant-Garde Code

アバンギャルド・コード is 前衛的算譜.

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

バージョン