競技プログラマが知るべき97のこと (01/97)
この記事は Competitive Programming Advent Calendar Div2012 のために作成されました。
競技プログラミングを長年やっているうちに、「これを実装するときにはこう書くと楽」とか「問題文を読んでもアルゴリズムがさっぱりわからないときにはこう考えるといい」みたいな tips が溜まってきていることに気づきました。Tips と言っても大したものではなくて、おそらく上級者は皆同じアイデアを持っているのでしょうが、しかしそういった tips をまとめた記事はあんまり見受けられません。ICPCを引退したらそういうのをぼちぼちまとめていこうかなー、と思いつつ既に引退から2年経ってしまいましたが、Advent Calendar の勢いを借りて書いてみたいと思います。
「競技プログラマが知るべき97のこと」第1回のテーマは「許されるときはいつでも入力をソートしよう」です。企画名は完璧に nodchip 先生の同人誌のパクりです。たぶん96年後の Advent Calendar で完結します。
競技プログラマが知るべき97のこと (01/97) - 許されるときはいつでも入力をソートしよう
多くの場合、入力の値を書き換えることは何の役にも立ちません。[2, 1, 3] の最長増加部分列を求めたいときに、まずこの入力をソートして、[1, 2, 3] について思いを馳せてみる人はまずいないでしょう。しかし、幾つかの問題においては、入力の値をソートしても問題の意味が変わらないことがあります。典型的なのは、集合が与えられ、その要素の順番は考慮しないような問題です。たとえば、こんなの。
n 部屋の会議室があり、それぞれの定員は capacities[i] で表されます。 会議室を使いたいグループが m 個あり、それらの人数は members[i] で表されます。 グループに会議室を適切に割り当てて、同時に会議室を使えるグループの数を最大化してください。 1つのグループが複数の会議室を使うことも、1つの会議室に複数のグループが入ることもできません。 Sample: capacities = [3, 5, 1, 2] members = [1, 4, 2, 4] output = 3 0 番目のグループが会議室 2 を、1 番目のグループが会議室 1 を、 2 番目のグループが会議室 3 を使うことができます。
この問題では、capacity や member を並び替えても問題の意味は変わりません。このようなときは必ずソートしてからアルゴリズムを考えましょう。
なぜソートするといいことがあるのか。それは、典型的で強力な次の 3 つのアプローチを考えやすくするためです。
ソートしなくても成功するなら、ソートしたときは絶対に成功することを示す
上の問題例は説明しづらいことに気づいたので一旦忘れることにして、SRM506 SlimeXSlimesCityを見てみましょう。問題を読むと、それぞれの町の名前について、それが最終的に市の名前になれるかどうかを判定することができれば幸せになれることがすぐわかります。ある町を大きくして市にしたいとき、例えば大きさ 5 の町を併合してから大きさ 3 の町を併合することが可能だったら、逆にして 3 の町を併合してから 5 の町を併合することだってできる。この考え方を推し進めていくと、成功パターンがあるときは、小さな町から順に併合しても成功する。つまり、小さな町から順に併合したパターンだけ調べればOK。という結論に至ります。
会議室の問題も、2人グループに4人部屋を割り当てて3人グループに3人部屋を割り当てる代わりに、入れ替えて2人グループに3人部屋、3人グループに4人部屋を割り当てるなどして、より小さいグループにより小さい部屋を割り当てても最終的な答えは変わりません。この発見がアルゴリズムの設計に大いに役立ちます。
1つ1つ入力を大きくしながら答えを求めていく
input[0 .. n-1] に対する最適解を利用して、input[0 .. n] に対する最適解を求める。ここで、input[0] <= input[1] <= ... input[n-1] <= input[n] を利用する。という数学的帰納法っぽい戦略を取ることもできます。会議室の問題は、上のアプローチとこのアプローチの合わせ技みたいな感じですね。まず最初に capacities と members をソートしておくと、members[0 .. 0], members[0 .. 1], members[0 .. 2], ... に対する答えを求めていける。
このアプローチについてはじっくり語りたいのですが、簡単な例題がなかなか見つかりません・・・。情報求む。難し目な例題としてはAOJ2383 Rabbit Game Playingあたりでしょうか。
出現頻度を考える
[1, 1, 2, 2, 2, 3, 4, ...] のような入力を、「1が 2 個、2 が 3 個、3 が 1 個、...」といった出現頻度で考えるとうまくいく事もあります。
SRM499 ColorfulRabbitsとか、SRM507 CubeStickerとか。このような問題では、実装上ソートが必要になるわけではありませんが、紙の上でアルゴリズムを考えるときにはソートしておくと便利です。同じ値が一箇所に固まるので、出現頻度というアイデアが出てきやすくなります。
「可能ならいつでもソート」戦略の良い所は、外れることはあっても、邪魔になることはまずないという点です。たとえば「迷ったらDPで解けないか考える」のような戦略はうまく行かなかったときに時間のロスが大きいですが、ソートは多くの言語では1行実装するだけで済み、計算量もさほど問題にはなりません*1。「あのときソートさえしていなければ・・・！」と後悔することにはならないのです。*2
ですから、問題を読んだ瞬間に「この入力はソートしても大丈夫か？」と考えることは大事ですし、もしソートできたら上の 3 つのアプローチがうまくいく可能性が多いにあるのです。なおかつ、うまくいかなかったとしても失うものはほとんどありません。ぜひソートしましょう。
*1:TopCoder を除けば少なくとも入力に O(n) 掛かり、これを許容しながらも O( nlog(n) ) の中でも比較的速いソートを落とすような時間設定は難しいものです。
*2:ちなみに、ソートしても意味が無い問題としてはAOJ1027 A Piece of Cakeなどがあります。
