スタッフブログ

2021年12月09日 / 投稿者:Iwasaki 『ants』

竿の上を50匹のアリが等間隔に並んでいます。
竿は49cmあり、アリはそれぞれの位置から内側を向いて毎秒1cmのスピードで歩いていきます。
アリは竿の端に到達すると竿の下に落ちていきます。
また、竿の上は狭くてすれ違うことができないため、二匹のアリが出会うとそれぞれ反対を向いて戻っていきます。
すべてのアリが竿から落ちるまでにかかる時間を求めなさい。

 

これはプログラミングコンテストで有名な問題『ants』です。
プログラミングの世界においては、一定の状況を与えられてこれを演算によって解く場合に、
計算の負荷をどこまで軽くできるか、ということが能力として問われます。

この場合、最も内側にいる二匹がまずぶつかり、反対方向に歩き始めそれぞれひとつ外のアリにぶつかります。
中央のアリはまた中央でぶつかりますがひとつ外のアリはふたつ外のアリにぶつかります。
こうして、アリの稼働をすべて計算式に盛り込み演算していくわけです。

 

 

考えてみますか?
考えてみませんよね。

 

 

だって面倒くさそうだし。
ただ、この問題自体はとてつもなくシンプルに解決することができます。
上記問題文によると”アリがすれ違うことができないため”戻っていく、ということでした。
でも、最期のアリが落ちるのが何秒後かがわかればいいので、それぞれのアリについて区別する必要がありません。
つまり、アリがすれ違えずに反対に向かう場合と、すれ違って通り抜けた場合と、区別されていない以上は絵に差異が生まれません。

 

要は、どこでどのアリがぶつかって反対に向かったのかは考える必要がなく、ひたすらすり抜けて歩いていくと考えればいいわけです。

結果として、両端にいるアリがまっすぐすり抜けて落ちるのに49秒、というのが回答になります。

本当の問題では竿の長さやアリの数をふせることでもっと演算自体は難しく設定されています。

 

 

気になる方は『プログラミングコンテストチャレンジブック』で検索してみてください。

 

ではまた。

 

PAGETOP

お問い合わせ