前回に引き続いて、今回は 4～5 問目の解説です。だいぶ難易度が上がってきました。
前回までは Java 8 と JavaScript で解答を作成していましたが、今回は筆者が普段使っている C# で作成しています。
(4) ABC 128 B – Guidebook (難易度 198) 解答例 (C#)
市名の辞書順、点数が高い順にレストランの番号を出力してください。
これはもう実務そのまま、典型的なデータ加工のスキルが問われています。
次の手順に分解するとよいでしょう。
1. 入力データを整形
- レストランの番号をデータとして追加
- 扱いやすいように、メモリ上でデータベースを構築するイメージ
2. ソート
- 市名の昇順、点数の降順
- SQL で考えると
select Id from Restaurants order by City, Point desc - 実装はプラットフォームごとのライブラリに左右される
ソートは次の方法が考えられます。
- ソート条件を一度に指定
- 市名、点数の順
- 2回のソート
- 点数、市名の順
- 安定ソート (マージソートなど) であれば可能、不安定ソート (クイックソートなど) では不可能
ソートを実装するには、各言語プラットフォームで用意されているライブラリを使うことになると思います。ソート条件を引数で指定する方法もライブラリごとに異なるためそれに従ってください。
- キーを指定
r => r.Point
- 「負, 0, 正」の3つの状態を返す
(r1, r2) => r1.Point - r2.Point
C# での実装は次のようになります。
まるで業務のように手堅く書くなら、エンティティ型を用意するとよいでしょう。
また、ここでは C# のクエリ式を使っています。普段はクエリ式をそれほど使わないのですが、where や orderby を使う程度で済む場合は見やすいコードになると思います。
using System;
using System.Linq;
class B
{
static void Main()
{
var n = int.Parse(Console.ReadLine());
var restaurants = Enumerable.Range(0, n)
.Select(i => Console.ReadLine().Split())
.Select((x, i) => new Restaurant { Id = i + 1, City = x[0], Point = int.Parse(x[1]) });
var query =
from r in restaurants
orderby r.City, r.Point descending
select r.Id;
Console.WriteLine(string.Join("\n", query));
}
}
class Restaurant
{
public int Id { get; set; }
public string City { get; set; }
public int Point { get; set; }
}
この問題の場合はとくにエンティティ型を作成しなくても、匿名型で間に合います。
次の解答例では通常の LINQ で実装しています。慣れればメソッドチェーンでつなげて書けます。
using System;
using System.Linq;
class B
{
static void Main()
{
var n = int.Parse(Console.ReadLine());
var query = Enumerable.Range(0, n)
.Select(i => Console.ReadLine().Split())
.Select((x, i) => new { Id = i + 1, City = x[0], Point = int.Parse(x[1]) })
.OrderBy(r => r.City)
.ThenByDescending(r => r.Point)
.Select(r => r.Id);
Console.WriteLine(string.Join("\n", query));
}
}
他にトリッキーな解法も存在しますが、データ加工は手堅い方法で実装するのがよいでしょう。
(5) ABC 016 C – 友達の友達 (難易度 1008 とあるけど今だともっと低いはず) 解答例 (C#)
各ユーザの「友達の友達」の人数を求めてください。
ただし、自分自身や友達は、「友達の友達」に含みません。
前問と同様、まずは入力データをいい感じの形式にしておきます。
1. 入力データを整形
- 各ユーザの友達のリストを作る
- 隣接者へのマップ (グラフ化)
2. 集計
- マップを辿って友達の友達のリストを作る
- さらに重複を排除
- そこから友達と自分を排除
集計するための具体的な実装方法は、次の通りいくつか考えられます。
- 関数型パラダイムのライブラリを使う (簡単)
- コレクションのコレクション (入れ子構造) を平坦化
- 孫データを一列にする
- コレクションのコレクション (入れ子構造) を平坦化
- フラグの配列
- 重複を排除して管理できる
- ハッシュセットのようなコンテナーも同様
- 幅優先探索
- グラフ理論っぽい解法
- 最短距離が2となるユーザの数
C# で関数型っぽい実装をすると次のようになります。
ToLookup メソッドでグルーピングができます。 また、SelectMany メソッドで入れ子構造を平坦化し、Except メソッドで集合の差を求めています。
Func<int[]> read = () => Console.ReadLine().Split().Select(int.Parse).ToArray();
var h = read();
var paths = new int[h[1]].Select(_ => read()).ToArray();
var map = paths.Concat(paths.Select(x => new[] { x[1], x[0] })).ToLookup(x => x[0], x => x[1]);
for (int i = 1; i <= h[0]; i++)
{
var f2 = map[i].SelectMany(j => map[j]).Distinct();
var f1 = map[i].Concat(new[] { i });
Console.WriteLine(f2.Except(f1).Count());
}
フラグの配列で実装すると次のようになります。
Func<int[]> read = () => Console.ReadLine().Split().Select(int.Parse).ToArray();
var h = read();
var paths = new int[h[1]].Select(_ => read()).ToArray();
var map = paths.Concat(paths.Select(x => new[] { x[1], x[0] })).ToLookup(x => x[0], x => x[1]);
for (int i = 1; i <= h[0]; i++)
{
var f = new bool[h[0] + 1];
foreach (var j in map[i])
foreach (var k in map[j])
f[k] = true;
foreach (var j in map[i])
f[j] = false;
f[i] = false;
Console.WriteLine(f.Count(x => x));
}
以上、利きコード選手権で出題した5問の解法について説明しました。
全体的に解答を関数型プログラミングのパラダイムで作成してきましたが、実務でもデータの加工・集計に関して簡潔に書ける場面が多いと思います。
