そのアルゴリズム、貪欲につき――貪欲法のススメ最強最速アルゴリズマー養成講座(2/3 ページ)

» 2010年09月04日 00時00分 公開
[高橋直大,ITmedia]

今回の問題

 TopCoder Openの時期ですので、去年のTopCoderOpenのRound2Hard問題から出題します。Hard問題なのでかなり難しいのですが、じっくりと考えてみてください。

In the kingdom of Absurdistan there are N airports, and in the far away country of Utopia there are M airports. Currently, there is no air traffic on any of these airports. Each airport has some capacity - i.e., a limit on the number of flights it can handle. Capacities may be different for different airports.

The citizens of the two countries would like to connect them by new flights. The schedule must follow these rules:

* Each flight is a two-way service that directly connects an airport in Absurdistan and an airport in Utopia.

* No pair of airports can be connected by more than one flight.

* Together, the flights must exactly meet the capacities of all airports. That is, for each airport the number of flights scheduled from it to another airports must be exactly the same as the capacity for this airport.

* If there are multiple schedules that satisfy the previous rules, the lexicographically smallest one (definition follows) must be chosen.

Each possible schedule can be represented as a matrix with N rows and M columns. The rows correspond to airports in Absurdistan (in alphabetical order), the columns to airports in Utopia (again, in alphabetical order). The cell at (r,c) contains the number 1 if the two airports are connected by a flight and 0 otherwise.

To compare two schedules, find the first row in which they differ, and in that row find the first column in which they differ. The one that contains a zero in this cell is lexicographically smaller.

You are given two int[]s: capacityA and capacityU. The int[] capacityA contains the capacities of all the airports in Absurdistan in alphabetical order. The int[] capacityU describes the Utopian airports in the same way. If there is no valid schedule, return an empty String[]. Otherwise, find the lexicographically smallest valid schedule and return it formatted as a String[].

 問題文だけでやる気をそがれそうですが、いつものようにオレオレ日本語訳すると、次のようになります。

国AにはN個の空港があり、国UにはM個の空港がある。国Aから飛び立つ飛行機の数が配列capacityA、国Uに到着する飛行機の数が配列capacityUで与えられる。同じ空港からは2機以上同じ空港に飛び立たないものとする。これを満たす組み合わせが存在する場合、その中で辞書順最小のものを答えよ。存在しない場合は空の配列を返せ。なお、どちらの国にも空港は50以下しかないものとする。

 問題文が分かりにくいので、少し解説をしていきましょう。以下の図のように、国Aと国Uがあり、それぞれの空港に対して、飛行機が飛び立つ数または到着する数が与えられ、適当な組み合わせを見つけます。

 ここで、国Aの空港iから国Uの空港jに飛び立つ経路を経路ijとし、i番目の文字列のj文字目に対して、経路ijを使用する飛行機が存在する場合は1、存在しない場合は0として表現します。

 よって、上記の図を答えの形式の文字列にすると、以下のようになります。

0111

0101

0100

1000


 こうした組み合わせのうち、辞書順で最小のものを求めるのが今回の問題です。辞書順というのは、辞書で並べたときに若い順、という意味で、例えば「0010」と「0100」があれば、前者のほうが辞書順で小さいものとなります。さて、どのように考えればよいのでしょうか。

今回の問題のヒント

 本連載では、「最小限の知識と柔軟な頭でさまざまな問題に対応する」ことを目指しているため、今回は貪欲法を用いて解きますが、読者の中には別の解法が思い浮かぶ方も多いでしょう。本連載ではまだしばらく取り扱う予定はありませんが、情報工学を学ばれた人であれば、最大流または最小費用流といえばピンとくるかと思います。こうしたアルゴリズムを知っていて、なおかつある程度早く適切なアルゴリズムが選択できるのであれば、この問題はそちらで解くのが正統派のアプローチといえます。

 今回の問題のポイントは「辞書順最小」である点です。単に成立する解を出力するだけでは辞書順最小となりません。正解を導き出すには、出力される順序が早い経路から、「その経路を通らなくても成立する回答が存在する場合は、その経路を使わず、どうしても使わなければならない場合は使用する」といった方法を採る必要があります。

 つまり、必要なのは、「条件を満たす組み合わせが存在するかを調べる関数」であり、この関数は両空港の数の積だけ呼び出されるので、「空港は50以下」という条件から最大2500回呼び出されることになります。「オーダーを極める思考法」で解説したように、 TopCoderにおける1つのテストケースの制限時間は2000ミリ秒なので、この関数が最大2500回呼び出されることを踏まえて言い換えれば、「ある組み合わせが条件を満たすかどうかを1ミリ秒未満で求められる関数を作れるかどうか」が今回の鍵となります。

 なお、今回の問題も、気軽に挑戦できるように、テンプレートと簡単なテストケースをつけたソースコードを、C++/C#/Javaの3つの言語で用意しました。今回の問題はかなり難しいのですが、やはり実際に自分で解いてみるのが、実力をつける一番の近道です。途中まででも構いませんので、ぜひ挑戦してください。

 それでは、次のページから解答に移ります。

Copyright © ITmedia, Inc. All Rights Reserved.

注目のテーマ