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

2020年3月の AtCoder の問題を、LINQ (C#) を使って解いていきます。全11問。
問題文はそれぞれのリンク先を参照してください。

ABC 157 B - Bingo

選ばれた数をハッシュセット HashSet<int> に格納しておきます。
縦 (3種類) ・横 (3種類) ・斜め (2種類) のいずれかについて、
3つの数がすべてハッシュセットに含まれているかどうかを判定します。

using System;
using System.Linq;

class B
{
    static void Main()
    {
        var a = new int[3].Select(_ => Console.ReadLine().Split().Select(int.Parse).ToArray()).ToArray();
        var n = int.Parse(Console.ReadLine());
        var b = new int[n].Select(_ => int.Parse(Console.ReadLine())).ToHashSet();

        var r3 = new[] { 0, 1, 2 };
        Console.WriteLine(r3.Any(j => a.All(ai => b.Contains(ai[j]))) || a.Any(ai => ai.All(b.Contains)) || r3.All(i => b.Contains(a[i][i])) || r3.All(i => b.Contains(a[i][2 - i])) ? "Yes" : "No");
    }
}

ABC 157 C - Guess The Number

0 から 999 までの整数を文字列に変換し、そのうち最初に長さが N で $s_i$ と $c_i$ の条件をすべて満たすものを求めます。それが存在しなければ "-1" とします。

using System;
using System.Linq;

class C
{
    static int[] Read() => Console.ReadLine().Split().Select(int.Parse).ToArray();
    static void Main()
    {
        var h = Read();
        int n = h[0], m = h[1];
        var scs = new int[m].Select(_ => Read()).ToArray();

        var r = Enumerable.Range(0, 1000)
            .Select(i => i.ToString())
            .FirstOrDefault(x => x.Length == n && scs.All(sc => x[sc[0] - 1] - '0' == sc[1]));
        Console.WriteLine(r ?? "-1");
    }
}

ABC 158 A - Station and Bus

出現する文字の種類数が2なのか1なのかを判定します。

using System;
using System.Linq;

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

ABC 158 C - Tax Increase

1 から 1009 までの整数のうち、最初にその 8% が A, 10% が B となるものを求めます。
なお、浮動小数点数型では誤差が生じる可能性があるため、整数型または10進数型を使います。

using System;
using System.Linq;

class C
{
    static void Main()
    {
        var h = Console.ReadLine().Split().Select(int.Parse).ToArray();
        var r = Enumerable.Range(1, 1009).FirstOrDefault(x => x * 8 / 100 == h[0] && x / 10 == h[1]);
        Console.WriteLine(r > 0 ? r : -1);
    }
}

日立製作所社会システム事業部プログラミングコンテスト2020 A - Hitachi String

"hi" を $[|S|/2]$ 回繰り返して結合したものが S に一致するかどうかを判定します。
長さが奇数のときは自動的に不一致となります。

using System;
using System.Linq;

class A
{
    static void Main()
    {
        var s = Console.ReadLine();
        Console.WriteLine(string.Join("", Enumerable.Repeat("hi", s.Length / 2)) == s ? "Yes" : "No");
    }
}

日立製作所社会システム事業部プログラミングコンテスト2020 B - Nice Shopping

「各割引券を使う場合」のほかに「最安の冷蔵庫と最安の電子レンジを買う場合」を追加し、それら M + 1 種類の支払総額の最小値を求めます。

using System;
using System.Linq;

class B
{
    static int[] Read() => Console.ReadLine().Split().Select(int.Parse).ToArray();
    static void Main()
    {
        var h = Read();
        var a = Read();
        var b = Read();
        Console.WriteLine(new int[h[2]].Select(_ => Read()).Select(v => a[v[0] - 1] + b[v[1] - 1] - v[2]).Append(a.Min() + b.Min()).Min());
    }
}

ABC 159 B - String Palindrome

S が回文であり、かつ前方の $[|S|/2]$ 文字と後方の $[|S|/2]$ 文字が一致するかどうかを判定します。

using System;
using System.Linq;

class B
{
    static void Main()
    {
        var s = Console.ReadLine();
        var h = s.Length / 2;
        Console.WriteLine(string.Join("", s.Reverse()) == s && s[..h] == s[^h..] ? "Yes" : "No");
    }
}

ABC 159 D - Banned K

まず、書かれた整数ごとにグループ化し、それぞれの個数を求めて辞書化します。
次に N 個すべてから選び出す方法の数 M を求めておきます。
すると各 k に対して、 $A_k$ の個数が r であったとすると、
N - 1 個から選び出す方法の数は $M- {}_r C_2+ {}_{r-1} C_2$ となります。

using System;
using System.Linq;

class D
{
    static void Main()
    {
        var n = int.Parse(Console.ReadLine());
        var a = Console.ReadLine().Split().Select(int.Parse).ToArray();

        var d = a.GroupBy(x => x).ToDictionary(g => g.Key, g => g.LongCount());
        var M = d.Sum(p => p.Value * (p.Value - 1) / 2);
        Console.WriteLine(string.Join("\n", a.Select(x => M - d[x] + 1)));
    }
}

ABC 160 C - Traveling Salesman around Lake

家の位置情報を N + 1 軒目 (2周目の1軒目) まで延長しておきます。
1周の長さ K から隣同士の家の間隔の最大値を引いた値を求めます。

using System;
using System.Linq;

class C
{
    static void Main()
    {
        var h = Console.ReadLine().Split().Select(int.Parse).ToList();
        int k = h[0], n = h[1];
        var a = Console.ReadLine().Split().Select(int.Parse).ToList();
        a.Add(k + a[0]);
        Console.WriteLine(k - Enumerable.Range(0, n).Max(i => a[i + 1] - a[i]));
    }
}

ABC 160 D - Line++

本来は二重ループを使って解ける問題ですが、LINQ のクエリ式を使ってみます。
整数の組 $(i,j) (i \lt j)$ に対して、X と Y の間の辺を通らない場合と通る場合の距離の最小値を求め、それをキーにして辞書化します。あとは各 k に対してその個数を出力します。

using System;
using System.Linq;

class D
{
    static void Main()
    {
        var h = Console.ReadLine().Split().Select(int.Parse).ToArray();
        int n = h[0], x = h[1], y = h[2];

        var q =
            from i in Enumerable.Range(1, n)
            from j in Enumerable.Range(i + 1, n - i)
            select Math.Min(j - i, Math.Abs(i - x) + 1 + Math.Abs(j - y));
        var d = q.ToLookup(v => v);
        Console.WriteLine(string.Join("\n", Enumerable.Range(1, n - 1).Select(v => d[v].Count())));
    }
}

ABC 160 E - Red and Green Apples

「 $p_i$ の大きい順に先頭から X 個」「 $q_i$ の大きい順に先頭から Y 個」「 $r_i$ のすべて」を結合したもののうち、大きい順に先頭から X + Y 個の和を求めます。

using System;
using System.Linq;

class E
{
    static int[] Read() => Console.ReadLine().Split().Select(int.Parse).ToArray();
    static void Main()
    {
        var h = Read();
        int x = h[0], y = h[1];
        var p = Read();
        var q = Read();
        var r = Read();
        Console.WriteLine(p.OrderByDescending(v => v).Take(x).Concat(q.OrderByDescending(v => v).Take(y)).Concat(r).OrderByDescending(v => v).Take(x + y).Sum(v => (long)v));
    }
}

バージョン

C# 8.0
- .NET Core 3.1.201 で提出
- 現行の AtCoder では、3種類の C# を選べる
- 今回のコードは、ABC 159 B 以外は C# 6 でも可

Avant-Garde Code

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

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

バージョン