つりあわない男女問題はいつも面倒だ
ある日、Slackの#devにこんなお題が投稿されました。
Q09 つりあわない男女
あるイベント会場に男女が集まってきました。到着した順に１列に並んで
入場を待っています。イベントの主催者であるあなたは、ある位置で区切っ
て２つのグループに分けたいとおもっています。
２つのグループのいずれかは男女の数が均等になるように分けたいのです
が、到着した順番が悪い場合、どこで区切っても２つのグループで男女の数
が異なってしまいます。例えば、男性３人女性３人が「男男女男女女」の順で到着すると、どこで
区切っても男女の数が異なってしまいます。しかし、「男男女女男女」の順
で到着すると、４人目の時点で区切ることで、男女が同じ数になります。（問題）
男性２０人、女性１０人が到着した場合、どこで区切っても２つのグループ
のいずれも男女の数が異なってしまうような到着順が何通りあるかを求めて
ください。
合わせて投稿者 id:ashida_spookies の解答例。
再帰で深さ優先探索したつもり 答え合ってるけどめっちゃ遅い(自分の環境で150sぐらい)から誰か速くして
とりあえず解答例は見ないでおいて。おじさんもチャレンジしてみることにしました。
おじさんは考えた
まず、おじさんは組み合わせがどれくらいになるかを考えました。
# 30人で作られる列だから組み合わせは30の階乗だ！ (1..30).inject(:*) #=> 265252859812191058636308480000000
途方も無い数になりました。この量を1つずつ確認するなんてできません。 そしてこれは男A 男B 女A と 男B 男A 女A も別の組み合わせになってしまうので無駄が多くなります。
次に男女の列を30桁の2進数と考えると
# だいぶ減りました。 all = (2**30) #=> 1073741824 2の30乗
男20人女10人なので、男を1とする場合1が20未満のビット列は対象外となります。
男20人なので 0xF_FFFF より小さい数は対象外です。
しかしこれ以上はちょっと減らし方がわからない。。。
ということでコードを書いてみました。
実行してみると・・・目も当てられない遅さ。。。 2800s て。
id:ashida_spookies の解答例の 150s の比にもならない遅さです。
おじさんがっかり。
彗星のごとく現れた模範解答
そんな中、アルバイトの id:moritanian が彗星のごとく解答を示しました。
A地点からB地点までの最短経路の場合の数と考えられる。
# -> [1, 8, 35, 110, 275, 572, 1001, 1430, 1430] [8, 43, 153, 428, 1000, 2001, 3431, 4861, 4861] [43, 196, 624, 1624, 3625, 7056, 11917, 16778, 16778] [196, 820, 2444, 6069, 13125, 25042, 41820, 58598] [820, 3264, 9333, 22458, 47500, 89320, 147918] [3264, 12597, 35055, 82555, 171875, 319793] [12597, 47652, 130207, 302082, 621875] [47652, 177859, 479941, 1101816] [177859, 657800, 1759616] [657800, 2417416] [2417416] [Finished in 0.1s]
最短経路？地点？なにそれ美味しいの？ おじさんにはよくわかりませんよ！ 0.1s ！？ ええっ！！！
スタッフ一同からの 素晴らしいとの絶賛の嵐でした。
そしておじさんは嫉妬したのです。悔しかったなー、ちくしょう。
問題を正しく認識する
2人は何が違ったのでしょうか。
経験の差でしょうか？プログラムスキルでしょうか？
いいえちがいます。
問題に対する正しい認識です。
- おじさんは組み合わせを数える問題と捉えました。
- id:moritanian は2地点の経路問題と捉えました。
認識の違いがアルゴリズムの選択の違いとなり結果を大きく変えたのです。
この時点で結果が違うのは明白だったのです。
アルゴリズムってなんだろう
アルゴリズム（英: algorithm [ˈælgəˌrɪðəm]）とは、数学、コンピューティング、言語学、あるいは関連する分野において、問題を解くための手順を定式化した形で表現したものを言う。「算法」と訳されることもある。 「問題」はその「解」を持っているが、アルゴリズムは正しくその解を得るための具体的手順および根拠を与える。さらに多くの場合において効率性が重要となる。
アルゴリズムは仕事のやり方そのものです。
人間と同じで仕事のやり方が良いと速く成果を出せますが、
悪いといつまでたっても終わらない。
アルゴリズムの成果は処理時間で評価し、これをオーダーという式で表します。
おじさんの使ったアルゴリズムの場合は
t = O(2^n)
ですね。クソコードだ！とどやされるレベルです。
データが増えるほど処理時間も爆発的に増えていきます。
一方、最短経路アルゴリズムを使うと以下のようになります。
t = O(n log(n)) # ダイクストラ法の場合
データが増えてもさほど処理時間に影響はなさそうです。
選択するアルゴリズムが正しければ少しの力で大きな成果を出すことができます。
まるで梃子のようです。まさにイノベーションです。
最短経路アルゴリズムなんて使うことあるの？
おじさんは13年ほどIT界隈で働いてきましたが一度も使うことがありませんでした。
もしかしたら使える場面があったかもしれませんが、知らなくて困ったことはありませんでした。
これからも使う予定はありません。
しかし、だからといって知らなくていいということにはなりません。
カーナビや電車乗換なんかでは確実に使われているでしょうし、
ゲームでプレイヤーに向かってくる敵の動きでも使われていそうです。
今後これらの仕事をしないと言い切れますか？
未知に対する準備
やる気満々でプロジェクトにとりかかっている時に、仕事が続けられなくなってしまったことはないでしょうか。
ネットワークがつながらない！ハードウェアが故障した！他の人にたのんでいた仕事が上がってこない！
これらの原因の1つが準備不足です。
- 僕はフロントエンドエンジニアだからネットワークのことは知らなくてもいいや。
- 私はプログラマだからDBのチューニングは気にしないのよ。
という感じで自分の領域以外のことをないがしろにするようではプロとはいえません。 未知の問題が発生しても動じない、準備出来ているような人材こそがプロフェッショナルなのです。
準備不足のおじさんは
はい、まだまだアマチュアですね。 なので模範解答や出典元の解説、アルゴリズムクイックリファレンスを読んで勉強中です。がんばります。
こんなおじさんと働いていみよう
スプーキーズにはこんなおじさんや、おじさんを嫉妬させちゃうような若者が働いています。 さぁ、そこの君も一緒に働いてみようじゃないか。アルバイト・フリーランス・正社員など形態は問いません。
アルゴリズムだけでなくいろいろな勉強会も行っています。
書籍紹介
冒頭のお題はこちらに掲載されています。
アルゴリズムの勉強をしたい方はこちら。
スプーキーズではこの本を元にアルゴリズムの勉強会を行っています。
おじさんの得た教訓
- 問題を正しく認識する
- 準備を怠らない
- 勉強を続ける
ではみなさんごきげんよう。
