競技SQL部 MISQUERY ONLINE WriteUp
MISQUERY ONLINE
「競技SQL部 MISQUERY ONLINE」というページがあります。
「競技プログラミング」×「SQL」という、競技プログラミングは一般的にC言語などのプログラミング言語を用いるのに対して、SQLのみを用いて競技プログラミングを行う一風変わったサイトです。
この度作者様からWriteUpを書く許可が得られましたので、書き残しときます。
https://t.co/bwGGKMaSeg
— 馬 (@Goryudyuma) 2017年11月10日
全部解けた！！！
これwrite upとか書いてもいいんだろうか。めっちゃ書きたい。作者さん探し出して、許可求めてみるかー！
競技SQL部
SQL × 競技プログラミング 「MISQUERY ONLINE」
おめでとうございます🎉 じゃんじゃんWriteup書いてください
— nkhrlab (@nkhrlab) 2018年2月14日
注意:ここから先はネタバレになります。まずは自分の力で解きたい、などの方は見ない方が良いかと思います。
制約
まずは制約の確認を行いましょう。競技プログラミングにおいて、制約の確認を怠ると、とてもひどい目に遭います。
制約はそれぞれ問題文に書いてあるので、しっかりと目を通しておくこと。
それから全体的な制約として、実行環境は「PostgreSQL 9.2.18」が使われています。PostgreSQLにない関数や、このバージョンより新しいPostgreSQLで加わった関数などは使えません。もうEOLを迎えてしまっているので手元に環境を用意するのは少し難しいかもしれません。
該当バージョンは既に無くなっていましたが、PostgreSQLを用意するだけならDockerが便利です。
https://hub.docker.com/_/postgres/
SQLの文法ミスでも、9.2.18の時点ではなかった関数を書いても、サイト上では「SQL ERROR」と出るだけなので、エラー文を見るためにできるだけ同じ環境を手元に用意した方がやりやすいとは思います・・・。試行錯誤もしやすいですしね。
ここから本格的にネタバレ
QUERY1: HOW ORDER YOU
典型問題ですね(←言いたかっただけ)。
SQLにおいて、昇順などのSortして出力するには、「ORDER BY」を使います。
QUERY2: REPRESENTATIVE
SQLで基本的な集約関数ですね。
「AS」で名前をつけることができるのですが、関数名と被っていてもつけられます。まあ今回は区別のために大文字小文字で分けてますけど。
QUERY3: FIZZBUZZ
SQLでFizzBuzz書いたことある人なんて、あんまりいないんじゃないでしょうか。
まず、二つの数a,bが与えられるので、aからbまでの連番データを作る必要があります。
PostgreSQLでは「GENERATE_SERIES(from, to)」関数を使うことで、fromからtoまでの連番データを作成できます。
次に「CASE WHEN」で条件分けすることができます。
条件式に当てはまれば「THEN」を、当てはまるものがなく最後までくれば「ELSE」を返します。ここで重要なことは、返すものは型が全て同じでないといけないことで、「CAST」関数で数字からtext型に変換しています。
QUERY4: ROT13
SQLでROT13の処理を行います。
文字コードで変換していくのもありですが(C言語でROT13しろって言われたら文字コードで足したり引いたりする)、私は「TRANSLATE」関数で変換テーブルを作りました。
QUERY5: SOLVE
ここから再帰クエリが必要になるので、難易度が上がります。
PostgreSQLでは「WITH RECURSIVE」で再帰クエリを書けます。
基本的な再帰クエリの考え方は、
- 初期状態を作る
- ある状態があれば、次の状態への遷移を書く
- ある状態の集合から、遷移できるものが全てその状態に含まれれば、再帰が終わりテーブルとなる
みたいな感じです。
今回の問題は、制約からこの関数は単調増加であることがわかります。
なので関数の答えが0となるときのxを求めるときには二分探索を行えばいいことがわかります。
また、誤差が1e-6未満なので、100回も探索すれば十分であることもわかります。
初期状態として、制約にある通り答えは1.0以上2.0以下なので、初期制約は1.0と2.1、それから今何回探索を行ったかを表す0とします。
次に遷移です。
本当は関数を定義したり変数を定義したりしてまとめた方がいいのかもしれませんが、競技プログラミングライクに埋め込みで対応しています。一回のSQLで出す、変数はSQLの世界ではあまり使いたくない、みたいな感じの制約をかけている感じです。(もし変数を使えば、二回同じ条件でCASEを通しているので、もう少しわかりやすくなるかも。)
また、ネイピア数も埋め込んでます。
条件に従い、minまたはmaxを更新しています。毎回探索範囲は半分になっていっています。
終了条件は、再帰回数を表すnが100を超えた時です。
最後に値を取り出します。n=100の時の値とかでもいいです。今回は「あり得る最小値として一番大きいもの」を条件にしています。
QUERY6: PRIME NUMBER
まずは2から10000までの数を生成します。再帰で書いてますけど、「GENERATE_SERIES」でもいいと思います。
次に、与えられた数列と、生成した2から10000までの数とをJOINします。条件は、与えられた数字が生成した数字で割り切れるかどうかです。
ここで集約関数のCOUNTを使うことで、何個とくっついたのかを判定します。くっついた数が1なら素数ですし、2以上なら約数が他にも存在するということです。今回は素数判定なので、1のものを取り出しています。
最後に昇順に出力しています。
QUERY7: BRACKETS
カッコの対応が合っているかどうかを判定する問題ですねー。
まず、「()」「{}」「[]」を文字列として消去すれば、対応は崩れないことを利用します。
方針としては、初期状態に与えられた文字列全部入れて、遷移条件として対応付いているカッコを削除していき、終了条件としてもう変更できなくなるまでやります。
最後に、対応するカッコを消していった結果、文字列が空文字となったもが、文字列中のカッコが正しく対応しているということなので、CASEで場合分けして出力します。
QUERY8: G*
今公開されている問題の中では最終問題です。
競技プログラミング的には、最小全域木やるだけ問題なのですが(ライブラリ貼るだけとかの人もいるレベル)、SQLでとなると難易度はかなり上がります。
とはいえnは15以下なので、計算量的にはそんなに気にしなくてよくって、気楽に書けます。
まずは、点にidを振ります。これがないと操作しづらいので。
次に、全てのパスを求めます。この問題では点データとして与えられるので、パスは全部自分で作る必要があります。「CROSS JOIN」使うと便利です。同時に長さも求めておきます。そして、短い順にパスを取り出したいため、長さでsortしておきます。
今回は最小全域木を求めるアルゴリズムとしてクラスカル法を採用しました。最小全域木を求めるアルゴリズムとして、クラスカル法とは別の方法としてプリム法が挙げられますが、クラスカル法はUnionFindの実装が必要で、プリム法はPriorityQueueが必要です。どちらかというとPriorityQueueの方が難しいかなと思ったのと、UnionFindが好きだからクラスカル法にしました。あと制約でnが15以下なので、経路圧縮なども特に必要ない、愚直な実装で大丈夫なところも決め手でした。
まずはUnionFindの初期化を行なっています。単純に頂点数の、自分の親は自分である配列を作っています。
クラスカル法を行なっていきます。パスが短い順に取り出していき、パスの始点と終点の親を見て、一致して入ればそのパスは使わない、一致していなければ長さを答えに足します。その後、親を合わせるために、終点の親を親とする全ての点の親を始点の親に変えます。計算量は更新にO(n)かかりますが、常に自分の親はrootであるということが保証できます。(SQLで親の親の・・・って再帰的に辿っていかなくてもいいようにこんな風にしました。)
UNNESTとARRAY_AGGで行と配列を行き来することにより、データの操作を行いやすくしています。
最後に距離を取ってくれば、それは最小全域木の全長になっています。
これで終わればよかったんですけど、コード長制限があるせいでこのまま提出しても通りません。スペースを削除したりすれば通ります。
あとがき
まずは、「SQLは使用上の注意をよく読み、用法・用量を守って正しくお使いください」 です。正直、最後の方の問題はSQLでやる必要が全くないです。というか、メンテナンスできなくなるし、よほどの理由がない限りやるべきではないです。でも、「できるけどやらない」のと「できないからやらない」には大きく違いがあると思っていて、できるに越したことはないと思います。
再帰クエリの練習にもなったし、とてもいいコンテンツだと思いました。作者さん、ありがとう！
実はこのコンテンツ、クリアしたのは去年の11月ごろで、楽しかったので作者さんにwrite upの許可を求めてから書くつもりだったのですが、忙しくていつの間にか忘れてました。それが最近突然拾われて、許可いただけたので書いてみました。
11月ごろにクリアしたので、その時に提出したクエリは消えていました。なんとか手元の操作ログから、5~8は救出できましたが、1~4は救出できなかったので、さっき解き直しました。
あとは救出した分のテーブル名とか適当すぎたので、ちょっとだけ手直しして、整形もしたりしました。
問題追加とか、PostgreSQLのアプデとかあればもっといいなーと思います(図々しい)。
何はともあれ、とても楽しいコンテンツなので、皆さん解いてみてください！あと、解けたらWriteUp書いてください！ぜひ他の人の回答も見たいです！
