前回に引き続いて、今回は 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問の解法について説明しました。
全体的に解答を関数型プログラミングのパラダイムで作成してきましたが、実務でもデータの加工・集計に関して簡潔に書ける場面が多いと思います。

前回に引き続いて、今回は 2～3 問目の解説です。

(2) ABC 143 C – Slimes (難易度 34) 解答例 (Java 8, JavaScript)

同じ色を持つ隣接するスライムが融合すると、最終的に存在するスライムは何匹となるか。

同じ文字が連続した区間の数だけをカウントします。SQL でいうところの distinct に近いのですが、文字列全体に対しての distinct ではなく、連続した部分だけ distinct する必要があります。

方針としては、1文字ずつ読み込んで、直前と異なる文字ならカウントすればよいです。これを実現するために以下の方法が考えられます。

• 直前の文字を変数にキャッシュして比較
• 各 i に対して s[i] と s[i – 1] を比較 (範囲に注意)

前者は少し長くなるので後者だけコードを示します。
for 文を使う人が多いとは思いますが、今回もやはり Java で Stream を使います。( import java.util.stream.*; )
Java で String から char を取り出すには、charAt メソッドまたは toCharArray メソッドを使います。

char[] s = sc.next().toCharArray();
System.out.println(IntStream.range(1, s.length).filter(i -> s[i - 1] != s[i]).count() + 1);

※ sc.next() に文字列が渡されます。

他の考え方として、

• “xxx…xxx” を “x” に置き換える

という方針でもできます。
Ruby では、このように連続した部分だけ distinct できる squeeze メソッドがあるためとても簡単に書けます。実は Java でも、正規表現のパターンに一致した文字列を置換する replaceAll メソッドを使えば同様のことができます。

System.out.println(sc.next().replaceAll("(.)\\1*", "$1").length());

(3) CF 2017 A – AKIBA (難易度 42) 解答例 (Java 8, JavaScript)

与えられた文字列の好きな位置に好きなだけ文字 "A" を挿入して "AKIHABARA" に変えることはできるか。

この問題では多くの解法が考えられます。
適合するケースが 2⁴ = 16 通りしかないことがわかれば効率的に全探索することも可能です。

• 1文字ずつ比較してなんやかんや
• わからん読めん
• 16通りを全列挙
• “KIHBR”, “KIHBRA” などを直書き
• 16通りを全探索
• 4重ループ
• 正規表現
• 処理速度は落ちるが圧倒的な保守性

1文字ずつ比較する方針の人が多かったです。しかしこの解法では人によってコードの違いが大きすぎて、本人以外はコードの意味を理解できないという状態に陥りました。
業務でこのタイプの要件が現れたら、他に単純化する方法がない限りは正規表現を利用することをお薦めします。

System.out.println(sc.next().matches("^A?KIHA?BA?RA?$") ? "YES" : "NO");

他の考え方として、

• “A” があるはずのところに “A” を挿入してみて、最終的に “AKIHABARA” となるか

という方針でもできます。つまり「1文字ずつ比較しながら “A” を挿入」の代わりに「”A” を挿入してみて、最後に全体を比較」と考えても同じです。

StringBuilder sb = new StringBuilder(sc.next());
int[] ai = { 0, 4, 6, 8 };
for (int i : ai) {
    if (i < sb.length() && sb.charAt(i) != 'A' || i == sb.length()) {
        sb.insert(i, "A");
    }
}
System.out.println(sb.toString().equals("AKIHABARA") ? "YES" : "NO");

次回は 4～5 問目の解説です。