はじめに
今回は自分がちょっと感動した有名アルゴリズム問題からの一問です。問題の中にアリが出てくるのでアリゴリズムなんちゃって(笑)
URLもarigorithmにしちゃった。ではどうぞ。
問題
シーソーに\(n\)匹のアリが乗っています。全てのアリは東西方向に一定の速度で進んでおり、他のアリとぶつかれば180度方向転換をして、また進み始めます。シーソーの端までたどり着くと、アリはシーソーから落ちてしまいます。
では任意の数のアリをランダムに配置したとき、全てのアリが落ちるまでの時間を求めるアリゴリズムを考えなさい。
※ シーソーに厚みは考えないでください。
※ アリの動く速さなど、必要に応じて変数をたててください。
解説
では答えです！一見難しそうなこの問題ですが、あることに気がつけばすぐにわかっちゃうんです。
一番ややこしいのはアリがぶつかれば逆向きに進み始まるところですよね。いろんなアリがぶつかりあえば何度方向転換するかがわかりません。しかし、2匹のアリの衝突に注目して注目してみましょう。
これがアリがぶつかったときに方向転換する流れになるのですが、これってよく見るとただアリが衝突せずにすれ違ったときと同じ流れをしていませんか？？
つまり\(n\)匹のアリが全て落ちるまでの時間は、最初の配置からアリの衝突を考えずに全てのアリがシーソーから落ちるまでの時間と等しくなります。そしてその場合は、向いている方向への崖への距離が最も遠いアリが落ちるまでの時間が全てのアリが落ちる時間となります。
正確に答えると、全てのアリの向いている方向の崖への距離を調べ、その長さが最も大きいものを\(L\)とし、アリが動くは速さを\(s\)とすると、かかる時間は\(t = L/s\)が答えとなります。
終わりに
気づけばめちゃくちゃ簡単でしたが、気づきましたか？？解けた人も解けなかった人も美しい問題だと感じたのではないでしょうか。
ていうか、解けたか解けなかったかとポチッと答えられるアンケートを作りたいなぁ。javascript使えばできそうだけど、、だれかやり方知っている人いたら教えてほし。。
コメント