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