CodeIQで結城先生が出題されたCrossingが神がかっていた件

CodeIQで挑戦者数が400人超えという異例の事態になったCrossingとはどんな問題だったのか。twitterでも恐ろしい勢いで拡散され、最終日に100人を超えるチャレンジがあった、この問題。一体どこにそんな魅力があったのかについて考えてみる。

まず、このように注目されるためには満たすべき条件が二つある。

繁盛する飲食店を考えてもわかるように、まず美味しくなければならない。CodeIQで言うと、問題として良問でなければならない。解答後の達成感がなくてはならない。

次に、飲食店なら、その店に入ってみようという気にさせなければならない。入りにくそうなお店でも、料理さえ美味しければその後口コミで広がることもあるだろうが、それだと繁盛するまでに時間がかかりすぎる。だからCodeIQで言うと、まず問題を解いてみようという気にさせなければならない。

このどちらが欠けても駄目である。この問題はこの二つの条件を見事に満たしているのである。言うのは簡単だが、実際、この二つの条件を同時に満たすのは極めて難しい。

結城先生の問題は、まず、やってみようという気にさせる。「あれ？これなら俺なんかでもチョチョイのチョイで解けるぞ」と思わせる。そういう入りやすさ、取っ付きやすさにかけては天下一品である。

問題「交差点をすばやく数えよう！」

絵も凄くわかりやすい。絵を見ただけで問題が想像できる。上段に1,2,3,4,5,6,7,8,9と数字が書いてあって、それを適当に並べ替えたものが、下段にある。同じ数字同士を線でつないだときにできる交点の数を数えるんだなと。それって、下段のそれぞれの数字について、その数字の左側にある自分の数字より大きい数字の個数を合計したものなんじゃ…。

絵を見ただけで解法までわかってしまう。「おお、これなら俺でも1分でできるぜ！」そう思わせるだけの大きな釣り針が垂らされている。

そしてCodeIQにログインして挑戦ボタンを押してしまうのであるが、それが罠なのである。これが実際にやってみるととんでもない問題で、与えられる頂点数は314159個もある。314159にどんな意味があるのかは知らないが、たぶん、3.14159(円周率の一部)であり、かつ、素数ということなんだろう。

そして3秒未満で計算できないと評価5はあげませんと書いてある。314159個もあると、O(n^2)なアルゴリズムだと3秒未満に収めるのは困難を極める。(OpenMP+OpenCLで2982msで解くプログラムを書いた強者がいるようだが)

そこで、何らかの工夫をしないといけない。交差点の数は逆転数(inversion)に等しいので、逆転数の数え上げ(「counting inversions」で検索すると出てくる)に帰着する。

方法1) マージソートを使う。ソート済みの部分数列a,bがあったとして、それをマージするときに逆転数がどう増えるのか考えてみるとわかる。O(n * log(n))

方法2) 逆転表を使う。これは、自分よりも左の方に、自分よりも大きい要素が何個いるかが書かれている表である。表は普通に考えると作成にO(n^2)の時間がかかるが、うまくするとO(n * log(n))で済む。(Knuth, "The Art of Computer Programming, Vol.3", 5.1.1. Exercise 6.を参考に)

方法3) Binary Indexed Tree (Fenwick Tree)を使う。O(n * log(n))で求まる。

私は「この逆転数を求める問題、20年ぐらい前に見たことあるなぁ…」と思いながらも、アルゴリズムの教科書を開くのはルール違反かと思って、初心にかえったつもりで自力で求めるコードを書いた。上の方法1)〜3)のいずれとも違う方法だ。たぶん、名もないアルゴリズムである。(力技とも言う)

以下にそのコードを貼り付けておく。今回の問題に対しては優れた解答とは言いがたいが、この考え方はこの考えかたで汎用性があるので他のことに応用できそうである。

もちろん、これ以外にもいろいろ方法はあると思う。いずれにせよ、この問題に対しては、このように複数の解法が考えられること、そして、どのような解法で解答したとしても、ナイーブな実装では3分以上かかる処理を3秒未満で処理が完了するようになったという改善効果に対する驚き、そして、得られる達成感のようなものがある。

この意味においても、たいへん素晴らしい問題で、解いたあとに思わずツイートしたくなる。「俺はやったぞ！お前もやってみろよ！」と。

結果的に見ても、挑戦者430人中198人もの人が評価5であった。この意味において、多くの人が達成感を味わい、そして、それをまたツイートしていたことが伺える。これが、このCrossingという問題に400人以上が挑戦した理由であると思う。

※ おまけ。以下、私の書いたコード

	// 配列を256要素ごとにスライスし、そのスライスされた部分において、
	// そこより左側(配列の添字の小さいほう)にX/256以上の値の個数がいくつあるのか(簡略化された逆転表)を
	// 事前計算しておき、これを利用してカウントを高速化している。
	// (C#で書いたところ、1秒未満に収まっている。)

	var sw = new Stopwatch();
	sw.Start();

	// 配列aに値を格納。
	var a = new List<int>();
	using (var sr = new StreamReader("crossing.txt"))
	{
		while (!sr.EndOfStream)
			a.Add(int.Parse(sr.ReadLine()) - 1);
			// 0オリジンでないと気持ち悪いので0引いておく。
	}

	// aのなかで、ある数xがどの位置にあるかを与える配列を用意。
	var b = new int[a.Count];
	for (int i = 0; i < a.Count; ++i)
	{
		b[a[i]] = i;
	}

	// cはlen×lenの正方行列。部分計算した配列。
	// a[ p/256 ]より左側にある、X/256より大きな値の個数が c[ ((p>>8)+1)*len + X/256 ]に格納されているものとする。
	var len = (a.Count >> 8) + 2;
	var c = new int[len * len];

	for (int i = 0; i < a.Count; ++i)
	{
		var p = (i >> 8) + 1;
		var y = a[i] >> 8;
		c[p*len + y] ++;
	}
	// ↑で求まったのは、単に(p,y)の個数だから、これを縦方向と横方向に重層する必要がある。
	// 縦方向の重層
	for (int p = 1; p < len; ++p)
		for (int y = len -2; y >= 0; --y)
			c[p*len + y] += c[p*len + ( y + 1 )];
	// 横方向の重層
	for (int y = len - 2; y >= 0; --y)
		for (int p = 1; p < len; ++p)
			c[p * len + y] += c[(p - 1) * len + y];

	long sum = 0;
	for (int i = 0; i < a.Count; ++i)
	{
		// そこの数Xより配列の左側にあるXより大きな数の個数をカウントする。

		// step 1)  p(iを切り捨てた値)より左側にある、y(xを繰り上げた値)以上の数の個数を加算
		var x = a[i];
		var p = i >> 8;
		var y = (x >> 8)+1;

		sum += c[p*len + y];
		y <<= 8;
		p <<= 8;

		// step 2) iより左にあるx 〜 y未満の数の個数を加算
		for (int j = x + 1; j < y && j < a.Count; ++j)
			if (b[j] < i) sum++;

		// step 3) a[p]以降にある、y以上の数の個数の加算
		for (int j = p ; j < i ; ++j)
			if (a[j] >= y) sum++;
	}

	Console.WriteLine(sum + "," + sw.ElapsedMilliseconds/1000);