トップページに戻る    次のSQLパズルへ    前のSQLパズルへ

11-11 川渡り 船の移動

SQLパズル

今、川のこちら岸に4隻の船A,B,C,Dがあります。
今回の目的は、この4隻の船を全て向こう岸に運ぶことです。

      川

船A | ~ ~ ~ ~|
   | ~ ~ ~ ~|
船B | ~ ~ ~ ~|
   | ~ ~ ~ ~|
船C | ~ ~ ~ ~|
   | ~ ~ ~ ~|
船D | ~ ~ ~ ~|
   | ~ ~ ~ ~|

船は1隻ずつ運ぶこともできるし、2隻を同時に運ぶこともできます。
ただし、2隻を同時に運ぶ場合は、遅いほうの船と同じ時間がかかります

船が川を渡るには、それぞれ1分、3分、6分、9分かかるとします。
さて、船を全て運ぶのにかかる最短時間を求めてください。
また、その手順を示してください。


SQL

with Hune as(
select 1 as Speed from dual
union select 3 from dual
union select 6 from dual
union select 9 from dual),
List as (select a.Speed,b.Speed,c.Speed,d.Speed,
e.Speed,f.Speed,g.Speed,h.Speed,
greatest(a.Speed,b.Speed)+c.Speed+
greatest(d.Speed,e.Speed)+f.Speed+
greatest(g.Speed,h.Speed) as TimeSum,
min(greatest(a.Speed,b.Speed)+c.Speed+
    greatest(d.Speed,e.Speed)+f.Speed+
    greatest(g.Speed,h.Speed)) over() as MinTimeSum,
to_char(a.Speed) || '分の船と' || to_char(b.Speed) || '分の船で渡る' as 行動1,
to_char(c.Speed) || '分の船で戻る' as 行動2,
to_char(d.Speed) || '分の船と' || to_char(e.Speed) || '分の船で渡る' as 行動3,
to_char(f.Speed) || '分の船で戻る' as 行動4,
to_char(g.Speed) || '分の船と' || to_char(h.Speed) || '分の船で渡る' as 行動5
  from Hune a,Hune b,Hune c,Hune d,Hune e,Hune f,Hune g,Hune h
 where a.Speed < b.Speed
   and d.Speed < e.Speed
   and g.Speed < h.Speed
   and c.Speed in(a.Speed,b.Speed)
   and d.Speed !=(select a.Speed from dual
            union select b.Speed from dual
            minus select c.Speed from dual)
   and e.Speed !=(select a.Speed from dual
            union select b.Speed from dual
            minus select c.Speed from dual)
   and f.Speed in(select a.Speed from dual
            union select b.Speed from dual
            minus select c.Speed from dual
            union select d.Speed from dual
            union select e.Speed from dual)
   and g.Speed not in(select a.Speed from dual
                union select b.Speed from dual
                minus select c.Speed from dual
                union select d.Speed from dual
                union select e.Speed from dual
                minus select f.Speed from dual)
   and h.Speed not in(select a.Speed from dual
                union select b.Speed from dual
                minus select c.Speed from dual
                union select d.Speed from dual
                union select e.Speed from dual
                minus select f.Speed from dual))
select 行動1,行動2,行動3,行動4,行動5,'合計は' || to_char(MinTimeSum) || '分' as 合計
  from List
 where TimeSum = MinTimeSum;


解説

集合演算を使って、船の存在チェックをしてます。