「ミックの楽しいSQLパズル」
https://book.impress.co.jp/books/1124101140
を購入し、
SQLパズルの本として、すごくいい技術書だと思うので、
副読する記事的な位置づけとして、
私が考えた別解を、まとめてみました。(著者からは承認いただいてます)
別解1 113ページ
下界との連結有無を求め、累計でグループ化する別解があります。
https://oraclesqlpuzzle.ninja-web.net/mysql/codezine-moto/03-puzzle.html#59
別解2 125ページ
リスト3-20のWhere句は、
下記のように、簡略化できます。
start_date <= 終了日 AND 開始日 <= end_date
直感的には、
お盆期間中にホテルに滞在するには、
お盆終了より前に、チェックインし、
お盆開始してから、チェックアウトしたら
お盆期間中にホテルに滞在したと言えます。
338ページと341ページのWhere句も同様に、簡略化できます。
AtCoderに似た問題があります。
ABC207-C Many Segments
https://atcoder.jp/contests/abc207/tasks/abc207_c
第23回PAST J オフィス
https://atcoder.jp/contests/past23-open/tasks/past23_j
別解3 137ページ
Oracle10gから、こんな時用の
「Partitioned Outer Join」という機能があります。
https://oraclesqlpuzzle.ninja-web.net/oow2009-olap-model.html#2-6
-- https://dbfiddle.uk/ の
-- 「Oracle Database 11g Express Edition Release 11.2.0.2.0 - 64bit Production」で確認
with Flavors(flavor) as(
select 'コットンキャンディ' from dual union all
select 'ティーオーレ' from dual union all
select '抹茶' from dual union all
select 'ラムレーズン' from dual union all
select 'チョコミント' from dual union all
select 'マスクメロン' from dual union all
select 'オレンジソルベ' from dual),
Icecreams(sale_date,flavor,sale_amt) as(
select date '2026-01-01', 'コットンキャンディ' , 12000 from dual union all
select date '2026-01-01', 'ティーオーレ' , 8000 from dual union all
select date '2026-01-01', '抹茶' , 32000 from dual union all
select date '2026-01-01', 'ラムレーズン' , 45000 from dual union all
select date '2026-01-01', 'チョコミント' , 17000 from dual union all
select date '2026-01-02', 'ティーオーレ' , 20000 from dual union all
select date '2026-01-02', 'マスクメロン' , 3000 from dual union all
select date '2026-01-02', '抹茶' , 8000 from dual union all
select date '2026-01-02', 'チョコミント' , 29000 from dual union all
select date '2026-01-02', 'オレンジソルベ' , 45000 from dual union all
select date '2026-01-03', '抹茶' , 21000 from dual union all
select date '2026-01-03', 'コットンキャンディ' , 9000 from dual union all
select date '2026-01-03', 'ラムレーズン' , 8900 from dual union all
select date '2026-01-04', 'チョコミント' , 7600 from dual union all
select date '2026-01-04', 'オレンジソルベ' , 7600 from dual union all
select date '2026-01-04', 'ラムレーズン' , 50000 from dual)
select b.sale_date , a.flavor
from Flavors a
Left Outer Join Icecreams b
partition by (b.sale_date)
on (a.flavor = b.flavor)
where b.flavor IS NULL
order by b.sale_date,a.flavor;
SALE_DATE FLAVOR
---------- -------
2026-01-01 オレンジソルベ
2026-01-01 マスクメロン
2026-01-02 コットンキャンディ
2026-01-02 ラムレーズン
2026-01-03 オレンジソルベ
2026-01-03 チョコミント
2026-01-03 ティーオーレ
2026-01-03 マスクメロン
2026-01-04 コットンキャンディ
2026-01-04 ティーオーレ
2026-01-04 マスクメロン
2026-01-04 抹茶
別解4 158ページ
PostgreSQLの配列型のように
DFSやBFSでの、ノードの再訪問を防ぐのは、あまりいい方法ないですね。
OracleとMySQLで
下記の2つの方法が考えられますが、
計算量的には、手続き型言語でダイクストラ法を使うのが現実的だと思います。
Oracleでの解
Oracleの階層問い合わせには、noCycleという再訪防止の機能があります。
枝にRow_Number関数でサロゲートキーを振り、
sys_connect_by_path関数で使用した枝を覚えつつ、深さ優先探索し、
最後にスカラーサブクエリで経路の合計を求めてます。
-- https://dbfiddle.uk/ の
-- 「Oracle Database 11g Express Edition Release 11.2.0.2.0 - 64bit Production」で確認
with Routes(source_city, destination_city, distance) as(
select 'Chicago' , 'Boston' , 985 from dual union
select 'Boston' , 'Chicago' , 985 from dual union
select 'Boston' , 'New York' , 215 from dual union
select 'New York' , 'Boston' , 215 from dual union
select 'New York' , 'Philadelphia' , 95 from dual union
select 'Philadelphia' , 'New York' , 95 from dual union
select 'Philadelphia' , 'Washington' , 140 from dual union
select 'Washington' , 'Philadelphia' , 140 from dual union
select 'Washington' , 'Atlanta' , 640 from dual union
select 'Atlanta' , 'Washington' , 640 from dual union
select 'Atlanta' , 'Miami' , 660 from dual union
select 'Miami' , 'Atlanta' , 660 from dual union
select 'New York' , 'Chicago' , 800 from dual union
select 'Chicago' , 'New York' , 800 from dual union
select 'Philadelphia' , 'Miami' , 550 from dual union
select 'Miami' , 'Philadelphia' , 550 from dual),
tmp1 as(
select Row_Number() over(order by source_city,destination_city) as EdgeID ,
source_city , destination_city , distance
from Routes),
tmp2 as(
select source_city , destination_city , sys_connect_by_path(a.EdgeID , ',') || ',' as path
from tmp1 a
start with source_city = 'New York'
connect by noCycle prior destination_city = source_city),
tmp3 as(
select source_city , destination_city ,
(select sum(b.distance)
from tmp1 b
where InStr(a.path , ',' || b.EdgeID || ',' ) > 0) as distanceSum
from tmp2 a)
select destination_city , min(distanceSum) as min_distanceSum
from tmp3
where destination_city != 'New York'
group by destination_city
order by min(distanceSum)
destination_city min_distanceSum
---------------- ---------------
Philadelphia 95
Boston 215
Washington 235
Miami 645
Chicago 800
Atlanta 875
MySQLでの解
枝にRow_Number関数でサロゲートキーを振り、
再帰With句で、Find_IN_Set関数で、枝の再使用を防いでます。
-- https://dbfiddle.uk/ の「MySQL 8.0.36」で確認
with recursive Routes(source_city, destination_city, distance) as(
select 'Chicago' , 'Boston' , 985 union
select 'Boston' , 'Chicago' , 985 union
select 'Boston' , 'New York' , 215 union
select 'New York' , 'Boston' , 215 union
select 'New York' , 'Philadelphia' , 95 union
select 'Philadelphia' , 'New York' , 95 union
select 'Philadelphia' , 'Washington' , 140 union
select 'Washington' , 'Philadelphia' , 140 union
select 'Washington' , 'Atlanta' , 640 union
select 'Atlanta' , 'Washington' , 640 union
select 'Atlanta' , 'Miami' , 660 union
select 'Miami' , 'Atlanta' , 660 union
select 'New York' , 'Chicago' , 800 union
select 'Chicago' , 'New York' , 800 union
select 'Philadelphia' , 'Miami' , 550 union
select 'Miami' , 'Philadelphia' , 550),
tmp as(
select Row_Number() over(order by source_city,destination_city) as EdgeID ,
source_city , destination_city , distance
from Routes),
rec as(
select source_city , destination_city , cast(EdgeID as char(200)) as path , distance as distanceSum
from tmp
where source_city = 'New York'
union all
select b.source_city , b.destination_city , concat(a.path , ',' , b.EdgeID) , a.distanceSum + b.distance
from rec a Join tmp b
on a.destination_city = b.source_city
where Find_IN_Set(b.EdgeID , a.Path) = false)
select destination_city , min(distanceSum) as min_distanceSum
from rec
where destination_city != 'New York'
group by destination_city
order by min(distanceSum)
destination_city min_distanceSum
---------------- ---------------
Philadelphia 95
Boston 215
Washington 235
Miami 645
Chicago 800
Atlanta 875
別解5 215ページ
max(num) over(order by num rows between 2 following and 2 following)
は
Lead(num,2) over(order by num)
で簡略化できます。
別解6 326ページ
Oracleでは、12cから、FETCH FIRST句が使用可能です。