11月祭で「利きコード選手権」を開催しました (その3)

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

comments

11月祭で「利きコード選手権」を開催しました (その2)

前回に引き続いて、今回は 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" に変えることはできるか。

この問題では多くの解法が考えられます。
適合するケースが 24 = 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 問目の解説です。

comments

11月祭で「利きコード選手権」を開催しました (その1)

11月8日 (金)、KCG 11月祭の1日目に「利きコード選手権」というクレイジーなイベントを開催しました。

企画意図

匿名のソースコードを見て指摘し合ってみると盛り上がりそう、という単純な動機。
それと同時にコーディングについて学習しよう、他の人のコードを読む習慣を付けよう、という教育的効果 (後付け)。

概要

  • 準備段階であらかじめ問題を設定して、コードを学生と教員を含めて10人くらいに書いてもらう。
  • 当日の参加者は (コードを書いていなくてもかまわない)、匿名のコードを読み比べて学生のコードか教員のコードかを2択で当てる (Google フォームで解答)。
    • その際、各問題に対して20分ほどの議論時間を取り、参加者は匿名のコードに対して自由にコメントする。
  • 最も当てることができた人が利きコーダーとして表彰される。
  • 最後に各問題のいろいろな解法について解説。

Kikicode-1
壇上ではコードを書いた人同士でコメント合戦が繰り広げられるの図 ↑

結果

コンピュータの専門学校らしい企画ができました。
十人十色のコードが集まり、とても盛り上がったので各所で流行ってもいいんじゃないかと思います。
ただし、学習の面で有意義にするためにも、難易度設定、問題選択、解説を準備する必要があります (今回はかなり準備した)。

Kikicode-2

以下では詳細を書いていきます。

問題セット

問題は競技プログラミングサービスの AtCoder の過去問から出題し、プログラミング言語としては学校の授業でも使われることの多い Java 8 または JavaScript に限定しました。
AtCoder 上での実行および提出は必須とはしていません。また入出力の部分もあまり本質ではないため、引数 (args) を使うなどの別の方法でもよいこととしました。

\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
こちらの3問は必須です。
(1) 81 (難易度 5)
(2) Slimes (難易度 34)
(3) AKIBA (難易度 42)

以下は任意です。(余裕のある人向け)
(4) Guidebook (難易度 198)
(5) 友達の友達 (難易度 1008 とあるけど今だともっと低いはず)

※ 難易度: AtCoder Problems における推定値で、そのレート (戦闘力) の人が正答率 50% であることを表します。例えば、レート 5 のキャラが1問目を正解できるかどうかは半々です。
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\

問題文がシンプルで、実務に近くて、別解のパターンが多くて、、とかいろいろ検討して厳選しました。もとは3問目に「Guidebook」だったのですが、初回だし大変かなと思って「AKIBA」にして、難易度を100未満としました。

解説

とりあえず今回の記事では1問目の解法のみ書いておきます。
私は普段は C# を使っていますが、今回のために Java 8 と JavaScript で解答例を作成しました。

(1) ABC 144 B – 81 (難易度 5) 解答例 (Java 8, JavaScript)

与えられた整数 N を 1 以上 9 以下の 2 つの整数の積として表すことができるか。

ループと条件分岐が必要となる典型的な問題です。

アルゴリズム:

  • 81通りを全探索
    • 2重ループ
    • O(N2)
    • i ≦ j に制限してもオーダーは変わらず
  • 割るほうだけでループ
    • 商は自動的に決定
    • O(N)

コーディング スタイル:

  • ループの実現方法
    • for ループ
    • 関数型パラダイム、ラムダ式
  • 別メソッド化
    • for の内部で return

タイトルが「81」であることから反射的に2重ループを使いたくなります。今回の制約では全探索でも問題ありませんが、N が大きくなって「1000000以下の2つの整数の積」とかになると数秒では完了しません。
また、繰り返し処理については for 文を使う人が多いとは思いますが、Java の Stream を使う ( import java.util.stream.*; ) と、N が与えられればあとは1行で書けます。JavaScript でも Array で同様のことができます。

System.out.println(IntStream.range(1, 10).anyMatch(i -> n % i == 0 && n / i <= 9) ? "Yes" : "No");

あとはネタ枠として、キモい for 文を挙げておきます。

boolean b = false;
for (int i = 1; i <= 9 && !(b = n % i == 0 && n / i <= 9); i++) ;
System.out.println(b ? "Yes" : "No");

与太話

10年以上前のイメージでは、コードレビューといえばクラス設計やコーディングスタイルに関するものがほとんどでしたが、近年では大量のデータを扱う開発現場も増えてくるなど、実現したいことの要求が上がるにつれてアルゴリズムが相対的に重視されてきていると感じます。
例えば大量のデータ処理を現実的な制限時間以内に完了させるにも、「どのような関数がどれだけ呼び出されるか」というような精確な見積りが必要となります。リソース制約の厳しいゲーム系の開発などでは以前からそうなのだろうと想像します。

逆にコーディングスタイルに関しては、スマートデバイス、電子工作、機械学習などを扱うことも増えてプログラミング言語が多様化したこともあり、最低限の規約を守っていれば可で、各エンジニアのスタイルが尊重される風潮にあると思います。
他の言語文化にいるエンジニアにローカルの規約を守ってもらうのはなかなか酷です。

むしろ昔はアルゴリズムに触れなさすぎたという印象で、今くらいのバランスが良いのではないかと思います。コードレビューで時間を割くべきポイントが遷移してきているのですね。

Code-Review

で、それぞれの開発現場の状況に合わせて最適な実装を提供できるようになるには、

  • 複数の解法を経験しましょう
  • 他の人のコードを読みましょう

と考えています。

Consequence

さて、次回は残りの問題の解説です。

参照

comments

AtCoder を始めようかと思っている学生たちへ

現在、全国的に情報系の学生たちの間では空前の AtCoder ブームとなっていて、
「AtCoder を始めた知り合いが増えてきて、就職活動にも活用できそうだし、この機会に自分も始めてみたいけどどうしようかな」と考えている学生も増えてきているのではないでしょうか?
結論を先に言うと「なるべく早いうちから参加しましょう」となりますが、これまでに何回かコンテストに出場してみた経験からいろいろ書いていこうと思います。

AtCoder は、競技プログラミングのコンテストを Web で実施しているサービスです。
以前は競技プログラミングといえば難解でマイナーなイメージでしたが、AtCoder では難度の低い問題から段階的に用意されており、ページも見やすくカジュアルに参加できるようになっています。
初心者向けである AtCoder Beginner Contest はほぼ毎週、土曜日または日曜日の夜にオンラインで実施されています。

AtCoder の参加者のうち7割を学生が占めています。
とくにここ1年くらいの参加者の伸びが大きく、最近の AtCoder Beginner Contest では約5000人が参加しています。
しかしこのブームに乗って就職活動に役立てようと思いつつも、「実力を上げてから参加したい」と考えている人もいるのではないでしょうか?

これに対しては「なるべく早いうちから参加しましょう」が答えです。
なぜなら、コンテストへの参加回数が少ないと、実力がレートに反映されないからです。
最低でも14回以上は参加しておかないと実力よりも低いレートになる仕組みで (リセットマラソンの効果が低い)、実力証明が欲しいと思ったときに急に参加しても実力が認定されるわけではありません。

また、AtCoder におけるレートやランク (色) のレベル感を認識しておく必要があります。こちらの記事に説明が載っています。

AtCoder には日本全国・世界の強者が集まっており、水色 (1200) 以上あれば実務上カンストの上級者だろうと考えています。実社会では緑色の人に遭遇するのもなかなか難しいでしょう。
通常の学生であれば、茶色が認定されれば十分実力があると言えます。

初級者はまず AtCoder Beginner Contest に参加して、問題 A・B を解くことを目標にしましょう。
問題 C までは分岐、ループ、データ集計など、一般的な開発者が実務で書く程度のコードでクリアできます。
問題 D 以降は処理高速化のためのアルゴリズムの知識・経験が必要になってきます。
もし仕事でプログラミングをしているのであれば、問題 C までは正解しておきたいところです。

本番のコンテストに参加する前に、過去問を練習しておきましょう。
問題文や解答の体裁に慣れていないと本番で無駄な時間を使ってしまいます (標準入出力など)。
コンテスト中もコンテスト外のときもサイトの使い方はまったく同じなので、過去問で本番同様の練習ができます。
過去のコンテストの問題は全て公開されています。他の参加者のコードを読んで参考にするのもよいでしょう。
AtCoder Problems という有志のサイトもおすすめです。

プログラミング言語は好きなものを選んでください。
標準入出力などのよく使うコードを含めたテンプレートを用意しておくとよいでしょう。例えば C# ではこんな感じです。
https://gist.github.com/sakapon/a88697da54fc78f838baeadcc19b54c4

各問題にはテストケースが用意されていて、それらをすべてパスすれば正解 (Accepted) となります。
こんな感じで、エディターからコピー&ペーストで提出できます。

AtCoder-Sub

というわけでまずは2~3か月、毎週参加し続けるのです(沼

追記 (11/26):出場11回目で水色に到達しました。
ABC146-Rating

comments