2020-08-03

ハイパー 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 でも可

2020-07-31

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

ハイパー LINQ 集

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

第6回ドワンゴからの挑戦状予選 A - Falling Asleep

曲のリストを列挙し、曲名が X に一致するまでスキップします。
その一致した曲1つをスキップして、残りの再生時間の和を求めます。

using System;
using System.Linq;

class A
{
    static void Main()
    {
        var n = int.Parse(Console.ReadLine());
        var ms = new int[n].Select(_ => Console.ReadLine().Split()).ToArray();
        var x = Console.ReadLine();
        Console.WriteLine(ms.SkipWhile(m => m[0] != x).Skip(1).Sum(m => int.Parse(m[1])));
    }
}

ABC 151 A - Next Alphabet

本来は LINQ を使わずに解く問題なのですが、前問と同様にして解けます。
文字 a ～ z を列挙し、C に一致するまでスキップします。
その一致した文字1つをスキップして、最初に現れる文字を求めます。

using System;
using System.Linq;

class A
{
    static void Main()
    {
        var c = Console.ReadLine()[0];
        Console.WriteLine(Enumerable.Range('a', 26).Select(x => (char)x).SkipWhile(x => x != c).Skip(1).First());
    }
}

ABC 151 B - Achieve the Goal

N * M から得点の合計を引いた値が最後のテストで必要となる点数です。
この値が K 以下であれば達成可能で、負である場合は 0 点でも達成可能です。

using System;
using System.Linq;

class B
{
    static int[] Read() => Console.ReadLine().Split().Select(int.Parse).ToArray();
    static void Main()
    {
        var h = Read();
        int n = h[0], k = h[1], m = h[2];
        var x = n * m - Read().Sum();
        Console.WriteLine(x <= k ? Math.Max(x, 0) : -1);
    }
}

ABC 151 C - Welcome to AtCoder

入力を問題 ID でグループ化して提出結果に "AC" が含まれるものだけに絞り込み先頭から "WA" が続く回数を求めます。
このグループ数が正答数を、回数の和がペナルティ数を表します。

using System;
using System.Linq;

class C
{
    static void Main()
    {
        var h = Console.ReadLine().Split().Select(int.Parse).ToArray();
        var gs = new int[h[1]].Select(_ => Console.ReadLine().Split()).GroupBy(x => x[0], x => x[1]).Where(g => g.Contains("AC")).Select(g => g.TakeWhile(x => x == "WA").Count()).ToArray();
        Console.WriteLine($"{gs.Length} {gs.Sum()}");
    }
}

キーエンスプログラミングコンテスト 2020 C - Subarray Sum

LINQ で簡潔に記述できる問題の中では難易度が高めです。
S を K 個並べ、その後ろに $10^{9}$ を N - K 個並べれば条件を満たします。
ただし、 $S=10^{9}$ の場合は後ろに 1 を並べます。

using System;
using System.Linq;

class C
{
    static void Main()
    {
        var h = Console.ReadLine().Split().Select(int.Parse).ToArray();
        int n = h[0], k = h[1], s = h[2], M = 1000000000;

        var a = Enumerable.Repeat(s, k).Concat(Enumerable.Repeat(s == M ? 1 : M, n - k));
        Console.WriteLine(string.Join(" ", a));
    }
}

ABC 152 C - Low Elements

本来は LINQ を使わずに解く問題だと思いますが、別解として載せておきます。LINQ 力高め。
$P_1, \cdots , P_j$ の最小値を順に求めて $M_j$ に格納していきます。
そして $P_i \leq M_i$ を満たす i の個数を求めます。

using System;
using System.Linq;

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

        var m = new int[n];
        var j = 0;
        p.Aggregate(int.MaxValue, (a, x) => m[j++] = Math.Min(a, x));
        Console.WriteLine(Enumerable.Range(0, n).Count(i => p[i] <= m[i]));
    }
}

ABC 153 B - Common Raccoon vs Monster

必殺技のダメージ量の和が H 以上となれば勝ちです。

using System;
using System.Linq;

class B
{
    static int[] Read() => Console.ReadLine().Split().Select(int.Parse).ToArray();
    static void Main()
    {
        var p = Read();
        var h = p[0];
        Console.WriteLine(Read().Sum() >= h ? "Yes" : "No");
    }
}

ABC 153 C - Fennec vs Monster

モンスターの体力を降順に並べ替えて先頭から K 回必殺技でスキップして残りの和を求めます。

using System;
using System.Linq;

class C
{
    static long[] Read() => Console.ReadLine().Split().Select(long.Parse).ToArray();
    static void Main()
    {
        var p = Read();
        var k = (int)p[1];
        Console.WriteLine(Read().OrderByDescending(x => x).Skip(k).Sum());
    }
}

バージョン

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

2020-07-29

競技プログラミング典型問題集

典型問題アルゴリズム実技検定

競技プログラミングにおける典型問題は、新たに学習したアルゴリズムを実装して試すとき、
あるいはライブラリを作成して試すときなどに利用すると最適です。
これまでに経験した範囲で、分野ごとに典型問題と思われるものを以下にまとめました。
AtCoder の緑～水ランク前後の人であれば利用する機会が多いのではないでしょうか。

サイト

Courses | Aizu Online Judge
- AOJ のコースには典型問題が分野ごとに用意されています。
- 書籍プログラミングコンテスト攻略のためのアルゴリズムとデータ構造に詳しい解説があります。
AtCoder Tags
- 分野から問題を探すにはこちらのサイトが便利です。

典型問題が多く出題されたコンテスト

アルゴリズム別

データ構造

最長増加部分列 (LIS)

動的計画法 (DP)

bit DP

PAST 201912 I - 部品調達

木 (Tree)

Union-Find 木

ATC 001 B - Union Find

優先度付きキュー (priority queue)

PAST 202004 F - タスクの消化

区間木 (セグメント木, segment tree)

最短経路問題

深さ優先探索 (DFS) および幅優先探索 (BFS)

Dijkstra 法

Codeforces 20 C. Dijkstra?

巡回セールスマン問題

PAST 202005 M - 行商計画問題

最大流問題

最大流・最小カット

QUPC 2014 H - お風呂は気持ちいい
- 有向グラフ
- 一部の言語では入力データに空行 (?) が含まれており、RE (実行時エラー) になるため注意
ABC 010 D - 浮気予防
- 無向グラフ

二部マッチング

ABC 091 C - 2D Plane 2N Points

グラフ (その他)

最小全域木

PAST 201912 L - グラデーション

Euler Tour

PAST 201912 K - 巨大企業

2020-06-07

ビット演算で減算を実装する【アルゴリズム実技検定解説】

Re:イチから始めるシリーズアルゴリズム実技検定ビット演算

第二回アルゴリズム実技検定 (2020年4月) の問題 A - エレベーターのコードをいくつか書きましょう。

atcoder.jp

問題文 (抜粋)

下から順に B9, B8, ..., B1, 1F, 2F, ..., 9F と呼ばれる 18 のフロアを持つ建物があります。
エレベーターが S から T へ移動するには最短で何秒を要するでしょうか。

問題文から、減法演算 (引き算、差) を使って解けそうだと判断できます。
実際の仕事現場であれば減法演算子 - を利用するだけでしょう。

しかし、アルゴリズム実技検定 (PAST) では

1からプログラムを作成する能力を問う

と標榜しているわけですから、
そんな飛び道具に頼った実装は許されないと容易に想像できます。
すなわち、ビット演算 (AND、OR、XOR、NOT、シフト、等値比較) を駆使して
この問題に取り組むのです。

その前にまず、普通に実装したときのソースコードを示しておきましょう。
前回に引き続き、使用言語は C# です。
B1 を -1、1F を 0、2F を 1、・・・と考えれば次のように書けます。

using System;

class A
{
    static void Main()
    {
        var f = Array.ConvertAll(Console.ReadLine().Split(), s => s[1] == 'F' ? s[0] - '1' : '0' - s[1]);
        Console.WriteLine(Math.Abs(f[0] - f[1]));
    }
}

上記のコードには、減算が3回のほか、絶対値 Math.Abs が1回含まれています。
これらをビット演算で置き換えます。

前回 (加算) と同様に、再帰を使って減算のコードを書いてみます。
使用言語は C# ですが、他のプログラミング言語でも同様のことができると思います。

using System;

class A
{
    static void Main()
    {
        var f = Array.ConvertAll(Console.ReadLine().Split(), s => s[1] == 'F' ? Subtract(s[0], '1') : Subtract('0', s[1]));
        Console.WriteLine(Abs(Subtract(f[0], f[1])));
    }

    static int Subtract(int x, int y)
    {
        var xor = x ^ y;
        var carry = (xor & y) << 1;
        return carry == 0 ? xor : Subtract(xor, carry);
    }

    static int Abs(int x) => (x & 1 << 31) == 0 ? x : ~Subtract(x, 1);
}

carry は繰り下げを表しています。

1 << 31 は int.MinValue と同義であり、コンパイル時に定数として埋め込まれます。
その値は $-2^{31}$ (16進数表記では 80000000) です。

2の補数 (-1倍) については、「1の補数に1を足したもの」の代わりに
「1を引いたものの1の補数」としています。

なお、x - y を x + (-y) と考えれば、
前回 (加算) で作成した Add 関数を用いて Add(x, Add(~y, 1)) としてもよいでしょう。

これで真の AC (正解) が得られました。

また、再帰を使わず、while や for を使って次のようにも書けます。

using System;

class A
{
    static void Main()
    {
        var f = Array.ConvertAll(Console.ReadLine().Split(), s => s[1] == 'F' ? Subtract(s[0], '1') : Subtract('0', s[1]));
        Console.WriteLine(Subtract(f[0], f[1]).ToString().Replace("-", ""));
    }

    static int Subtract(int x, int y)
    {
        while (y != 0) y = ((x ^= y) & y) << 1;
        return x;
    }
}

Subtract の中で変数を消費していません。
さらに、文字 - を除去することで絶対値を得ています。

前回: ビット演算で加算を実装する

バージョン

C# 8.0
- Mono-csc 3.5.0 で提出
- 現行の AtCoder では、3種類の C# を選べる
- 今回のコードは C# 6 でも可

参照

2020-06-04

ビット演算で加算を実装する【アルゴリズム実技検定解説】

Re:イチから始めるシリーズアルゴリズム実技検定ビット演算

第一回アルゴリズム実技検定 (2019年12月) の問題 A - 2 倍チェックのコードをいくつか書きましょう。

atcoder.jp

問題文 (抜粋)

S が 3 桁の整数である場合 (0 で始まる場合を含む) はその 2 倍の値を出力し、
そうでなければ error と出力するプログラムを作成せよ。

2 倍の値を求める部分については、普通に考えれば 2 * n あるいは n + n のような
四則演算のコードを書くだけにも見えます。

しかし、アルゴリズム実技検定 (PAST) のキャッチフレーズは

1からプログラムを作成する能力を問う

です。
したがって、そんな単純な実装で許されるはずはなく、
出題者の想定解法は「ビット演算を使って四則演算を実装する」です (断言)。
すなわち、AND、OR、XOR、NOT、シフト、等値比較を駆使してこの問題を解くのです。

というわけで以下では、ビット演算で加法演算 (足し算、和) を自作し、
n + n と同等のコードを実現していきます。
使用言語は C# ですが、他のプログラミング言語でも同様のことができると思います。

using System;

class A
{
    static void Main()
    {
        int n;
        Console.WriteLine(int.TryParse(Console.ReadLine(), out n) ? $"{Add(n, n)}" : "error");
    }

    static int Add(int x, int y)
    {
        var xor = x ^ y;
        var carry = (x & y) << 1;
        return carry == 0 ? xor : Add(xor, carry);
    }
}

上記のように、再帰でシンプルに書けます。 carry は繰り上げを表しています。
これで真の AC (正解) が得られました。

また、再帰を使わず、while や for を使って次のようにも書けます。

using System.Linq;
using static System.Console;

class A
{
    static void Main() => Solve(ReadLine());
    static void Solve(string s) => WriteLine(s.All(char.IsNumber) ? $"{Twice(int.Parse(s))}" : "error");
    static int Twice(int x) => Add(x, x);

    static int Add(int x, int y)
    {
        while (y != 0)
        {
            var carry = (x & y) << 1;
            x ^= y;
            y = carry;
        }
        return x;
    }
}

ちなみに、この問題の場合は 2 倍するだけなので、
実は左シフト演算 n << 1 で達成できます。

using System;

class A
{
    static void Main()
    {
        int n;
        Console.WriteLine(int.TryParse(Console.ReadLine(), out n) ? $"{n << 1}" : "error");
    }
}

次回: ビット演算で減算を実装する

バージョン

C# 6
- 2020年3月以前の AtCoder では Mono 4.6.2

参照

2020-06-01

About This Blog

一般

This Blog's Concept

In programming, the solution is not always unique for something you want to achieve.

I usually try multiple implementations when I find them.
In competitive programming such as Codeforces and AtCoder, I think that submitting many solutions is one of the ways to enjoy.
If you have experienced many types of patterns in practical tasks, you can think of 3 or more solutions for a frequent problem.

So in this blog, I will show multiple solutions for the target problem, and also implement primitive functions.

2020-06-01

このブログについて

一般

このブログのコンセプト

プログラミングにおいては、何か実現したい対象があったとして、それを実現する方法は一つだけとは限りません。

筆者は普段から、複数の実装方法を見つけた場合には試すようにしています。
AtCoder や Codeforces のような競技プログラミングにおいては、多くの解法を提出することも楽しみ方の一つと考えています。
実務でも頻出のパターンで類型を多く経験していると、だいたい3通り以上の解法が思い浮かぶものです。

そこでこのブログでは、対象の問題に対して複数の実装方法を示したり、原始的な機能を自作したりしていきます。

Avant-Garde Code

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

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

バージョン

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

バージョン

競技プログラミング典型問題集

サイト

典型問題が多く出題されたコンテスト

アルゴリズム別

データ構造

動的計画法 (DP)

木 (Tree)

最短経路問題

最大流問題

グラフ (その他)

ビット演算で減算を実装する【アルゴリズム実技検定解説】

バージョン

参照

ビット演算で加算を実装する【アルゴリズム実技検定解説】

バージョン

参照

About This Blog

This Blog's Concept

このブログについて

このブログのコンセプト