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

学内で Git・GitHub 勉強会を開催しました

2019年10月18日 (金) 17:00-18:30 に、京都コンピュータ学院・京都情報大学院大学の学生向けに「Git・GitHub 勉強会」を開催しました。
資料はこちらです。GitHub 上で作成してあります。

Git 関連の情報を検索しても、Git の各機能単体や Git コマンドの説明が多く見られますが、この勉強会では GitHub とローカルの開発環境 (Git ツールとして SourceTree) を連携させ、開発プロジェクトで実践的に使えるようになることを目標として、一連の手順をデモ中心で説明しました。
実際の開発プロジェクトでは、例えば GitHub のブランチやリリースといった機能を使うことになります。資料にはそのための手順を記載しています。

また試験的に、そのときの画面を YouTube Live で配信してアーカイブしました (ただし限定公開)。勉強会の講演を手軽に残せるのはとてもよいです。
配信はこちらのサイトの手順の通りにやればできます。配信ソフトとして OBS Studio を使いました。

参照

comments

NT京都2019に出展しました

2019年3月24日 (日) に西院春日神社・春日幼稚園で開催された NT京都2019 に、
PC 用 TAS 開発環境 Speedrunner を出展しました。

Speedrunner-2.0.4-VS

「NT」はニコニコ技術部のことで、ネタもの系ものづくりの展示会です。
2010年にニコニコ動画で 【TASさんの休日】mixiアプリ 四則演算ゲーム 92問正解 などの TAS 動画を投稿しており、そのときに開発したツールを実演しました。

なお、TAS とは Tool-Assisted Speedrun の略で、ツールの補助によりゲームを高速でプレイすることを指します。一般には各ゲーム機のエミュレーターを利用することが多いですが、これは PC (Windows) 上での TAS となっています。
最近では RPA (Robotic Process Automation) というキーワードもあり、原理的にはこれも同じです。

また、ツールをバージョンアップして、Visual Studio の GUI でワークフローを組めるようにしました。

機能:

  • PC のマウス・キーボード操作を記録
  • Visual Studio の GUI でワークフローを作成
  • ワークフローを実行
  • いちおうプログラミングもできる

次の動画は円周率を求める例です (2倍速)。最後に計算結果が表示されています。

NT京都は、今までに見た展示会の中で最もカオスでした。
発想の源が狂っているものが多いです。既存の技術なのに「そんな使い方するのか!?」という驚きがあって素晴らしいです。

IMG_20190323_175834

IMG_20190324_100804 IMG_20190324_132946

IMG_20190324_110617 IMG_20190324_101859

IMG_20190323_164516

comments