プログラミングコンテストチャレンジブックのAnts問題が面白い！

tech

最近友達3人でRubyの勉強会を週一回しています。「プログラミング言語 Ruby」を20ページくらいみんなで読んでいきます。読み終えたらRubyで一つプログラムを書いて、みんなで検討するというゆるい感じの勉強会です。


最近は「プログラミングコンテストチャレンジブック」の問題を題材にすることが多いのですが、今回やった「Ants」という問題が非常に面白かったので紹介します。
（ちなみに僕は良解を思いつくことができなかったです。友達は惜しいところまでいったのですが、後一歩のところでした）

Ants(POJ No.1852)
長さLcmの竿の上をn匹のアリが毎秒1cmのスピードで歩いています。アリが竿の端に到達すると竿の下
に落ちていきます。また、竿の上は狭くてすれ違えないので、二匹のアリが出会うと、それぞれ反対を向い
て戻っていきます。各アリについて、現在の竿の左端からの距離x[i]はわかりますが、どちらの方向を向いて
いるのかはわかりません。すべてのアリが竿から落ちるまでにかかる最小の時間と最大の時間をそれぞれ求
めなさい。


制約
1 <= L <= 10^6
1 <= n <= 10^6
0 <= x[i] <= L


↓↓解答↓↓

まず最小の時間は、すべてのアリが近いほうの端に向かうとしてしまえばよさそうです。実際、この
ような場合に二匹のアリが出会うことなく、また、これよ短い時間で端に到達することはできません。


次に最大の場合を考えるために、アリが出会った場合にどうなるかをよく考えてみましょう。
実は、二匹のアリはすれ違ってそのまま進んでいったと思ってしまっても何も問題ないことがわかります。この
ように考えると、すべてのありは独立に動けるようになるので、最大の時間を求めるためには端までの距離の最
大値を求めれば良いことになります。


どうでしょうか？この解答を思いつきましたか？この問題は、発想力が問われるタイプの最たる例として紹介されています。僕は無理でした(汗)
（アリがぶつかる時間を求めていき、愚直に処理していくアルゴリズムしか思いつきませんでした）
この解答を見たときに、「すげー！！( ﾟдﾟ)」と大興奮しましたｗ頭柔らかくなりたいですねー。


ちなみにこの解答を僕がRubyで実装してみたのはこんな感じです。

#!/usr/bin/ruby

def solve(length , ants)
  min = 0;
  max = 0;

  ants.each do |i|
    dist0 , dist1 = i , length - i;

    #アリ[i]が端に到達する最大時間と最小時間
    ant_max , ant_min = (dist0 > dist1 ? [dist0 , dist1] : [dist1 , dist0]);

    max = ant_max if ant_max > max;
    min = ant_min if ant_min > min;
  end
  
  return [min , max];
end

length = 10;
ants = [2 , 6 , 7];

min , max = solve(length , ants);
puts "min = #{min} , max = #{max}";