ホーム
BLOG
【SQL】
【SQL】ゲームで実際に学べる？paizaのゲームをやっ…

【SQL】ゲームで実際に学べる？paizaのゲームをやってみた

はじめに
ゲーム内容
SQL問題
Dランク問題
Bランク問題
Aランク問題
コード問題
Bランク問題
Aランク問題
Sランク問題
さいごに

はじめに

最近、SQLの学習を始めてみました。

こちらの教材をもとに学習をしています。
SQL 第2版ゼロからはじめるデータベース操作 (プログラミング学習シリーズ) | ミック |本 | 通販 | Amazon

しかし、本を読んでいるだけだと本当に身になっているのか分かりませんよね。
目的意識が無いと学習も進みにくいものです…

そこでpaizaが配信している「エンジニア騎士とクエリの魔女」というゲームを見つけました。
エンジニア騎士とクエリの魔女

こちらはゲーム感覚でプログラミングの問題を解いていくもので、その問題内容が面白かったので今回はこちらを紹介していきます。

ゲーム内容

このゲームでは、普通のコード問題とタイトルにもある通りSQLのクエリ問題を解くことができます。
また様々な難易度が用意されており、D級～S級まであるようです。

私は学習するのが楽しくて、全問解いてしまいました。(笑)

ゲーム内容を解説するのは問題無いようなので、問題と解法を掲載していきます。
もし自分で解きたい方は、paizaアカウントがあればできるようなのでやってみてください！
【解答例つき】新作ゲーム『エンジニア騎士とクエリの魔女』でPythonとSQLを学んでみた！ –

SQL問題

SQL問題では以下のようなテーブルが渡されます。
全問、このテーブルに基づいて問題を解いていきます。

メインのテーブルがHellで、ここにいろんなモンスターの情報が入っているわけですね。
そのHell情報のElementやGradeは平文で入っているのではなくIDで入っているので、Elementテーブルなどを参照することで名前が分かるようになるわけですね！

Dランク問題

一番初級の問題ですね。
SELECTとFROMの使い方確認からですね。

SELECT id, name
FROM Hell

またこちらのサイト内で、コードを提出する前に動作確認することができます。
実行環境がなくても試せるのは嬉しいですね。

ORDER BYの降順とLIMIT句ですね。
LIMIT句は本には書いてなかったので調べる必要がありました。

Bランク問題

テーブルの2重結合ですね。
HellテーブルにElementテーブルのIDとGradeテーブルのIDがあるのでそれぞれ結びつけます。
その後WHEREで「風属性」兼「ボス」を絞り込みます。
またテーブルを表示する時に別名化する必要がありますね。

SELECT Hell.id, Hell.name, Element.name AS element, Grade.name AS grade
FROM Hell INNER JOIN Element
ON Hell.element_id = Element.id
    INNER JOIN Grade
    ON Hell.grade_id = Grade.id
WHERE Element.name = 'Air'
AND Grade.name = 'Boss';

ちょっとレベルが上がってきましたね。

Aランク問題

今度は、弱点属性を取得した後に、Hellテーブルから絞り込む必要がありますね。
弱点属性はElementCompatibilityテーブルに格納されているようですね。

初めてテーブル図を見た時はよく分からなかったのですが、ElementCompatibilityには属性と弱点属性が登録してあり、それは平文ではなくIDで登録されているわけですね。

SELECT *
FROM Element
Join ElementCompatibility 
ON Element.id = ElementCompatibility.element_id;

なのでFireの弱点はfb0f42(Water)だということがわかります。

ではGraffiacaneの弱点を求めましょう。

SELECT ElementCompatibility.Weakness_element_id
FROM Hell INNER JOIN Element
ON Hell.element_id = Element.id
    INNER JOIN ElementCompatibility
    ON Element.id = ElementCompatibility.element_id
WHERE Hell.name = 'Graffiacane'

これでGraffiacaneの弱点がbd1bce(IDは毎回変わります)だと分かりました。

これをサブクエリとして、WHERE句でモンスター情報から絞り込みます。

SELECT Hell.id, Hell.name, Element.name AS element, Grade.name AS grade
FROM Hell INNER JOIN Element
ON Hell.element_id = Element.id
    INNER JOIN Grade
    ON Hell.grade_id = Grade.id
WHERE Element.id = (SELECT ElementCompatibility.Weakness_element_id
    FROM Hell INNER JOIN Element
    ON Hell.element_id = Element.id
        INNER JOIN ElementCompatibility
        ON Element.id = ElementCompatibility.element_id
    WHERE Hell.name = 'Graffiacane')
    AND Grade.name = 'Boss';

絞り込んだ弱点属性を持っていて、かつボスのモンスターを表示することができました。

なかなかの難易度でしたね。
はじめは解けませんでしたが、数日かけて本を読んだら解けるようになりました！

目的もなく本を読んでいた時は若干辛かったのですが、このゲームと一緒に学び出したら「早く次の章が学びたい！」となっていました。(笑)

コード問題

続いてコード問題の方も見ていきましょう。

D、Cランク問題はif文やfor文を使った問題でした。
標準入出力に慣れる簡単なチュートリアルですね。

Bランク問題

いきなり難しくなりました。
こちらの問題は多少考察する必要がありますね。

この問題はDP法、漸化式で解くことができます。
N-1番とN番の数が分かればN+1番の数が分かる、N番とN+1番が分かったのでN+2番の数も分かる、…
といった感じですね。

また初期値として1番の子の数を渡されるようですし、その子の左は居ないようです。
これらを初期値とすることでDPが回せます。

これらを実装するだけですね。

#include <iostream>
using namespace std;
int main(void){
    int N,x;
    cin >> N >> x;

    int d[N], a[N];
    for(int i=0; i<N; i++){
        cin >> d[i];

        if(i == 0){
            a[0] = x;
            a[1] = d[0] - a[0];
        }else if(i == N-1){

        }else{
            a[i+1] = d[i] - a[i-1] - a[i];
        }

        cout << a[i];
        if(i != N-1){
            cout << " ";
        }
    }
}

Aランク問題

続いては平面図の問題ですね、黒の塊かつ四角形のものがいくつあるかという問題です。

大抵は黒色のマスが何枚あるか？とかだと楽なのですが…
今回のは一癖ある問題ですね！

このような平面図で範囲を求める場合は、2次元の累積和アルゴリズムが有効です。
2次元の累積和とは、簡単に言えば「指定した範囲内に黒マスが何枚あるか」をfor文を使わずに求めることができます。

今回の長方形の条件では、検索範囲の総数＝累積和となっており、上下左右がすべて白だったら長方形として数えればいいわけですね。

これで解決…と思いきや不正解になってしまいました！

今のままのアルゴリズムだと、上から下まで重複しながら全てを探索するわけですね。
1行から2行に長方形はあるか、1行から3行に長方形はあるか、1行から4行、…、2行から3行、2行から4行、……
1~3行分の長方形は1~2行の探索では判定できないのでこのようにしらみつぶしに探索する必要があるわけですね。

つまり計算量はO(H^2W^2)で、300^4 = (3 × 10^2)^4 = 81 × 10^8 = 81億回となるわけですね。
一般的な計算速度は1秒に1億回なので、3秒には間に合いませんね…

なのでもっと賢い方法を考えましょう。

左上から順に探索していき、

黒いマスを見つけた場合、そこから下方向と右方向に何マス繋がっているか探索します。
連結した黒マスを再度探索しなくていいように、幅優先探索で連結した黒マスは探索済みにします。
1で取得した範囲と累積和の値を比較して、条件に合えば長方形1個とカウントします。

この方法ならマスの数だけの探索で良くなるのでO(HW)ですね！

続いて累積和を使った長方形の判定方法です。

以下の図にある通り、
上下に1増やした範囲の黒の総数＝左右に1増やした範囲の黒の総数＝元の範囲の黒の総数＝元の範囲の最大値
となっていれば長方形ですね。

これならお手軽に判定できますね。

#include <bits/stdc++.h>
using namespace std;

int H, W;
vector<vector<int>> grid;
vector<vector<int>> sum;

pair<int, int> dfs(int x, int y) {
    if (x < 1 || x > W || y < 1 || y > H || grid[y][x] != 1) {
        return {-1, -1};
    }

    grid[y][x] = 2; // 探索済み

    pair<int, int> down = dfs(x, y+1);
    pair<int, int> up = dfs(x, y-1);
    pair<int, int> right = dfs(x+1, y);
    pair<int, int> left = dfs(x-1, y);

    int max_x = max({x, down.first, up.first, right.first, left.first});
    int max_y = max({y, down.second, up.second, right.second, left.second});
    return {max_x, max_y};
}

int get_sum(int x0, int y0, int x1, int y1) {
    return sum[y1][x1] - sum[y0 - 1][x1] - sum[y1][x0 - 1] + sum[y0 - 1][x0 - 1];
}

int main() {
    cin >> H >> W;

    grid.assign(H + 2, vector<int>(W + 2, 0));
    for (int i = 1; i <= H; ++i) {
        string row;
        cin >> row;
        for (int j = 1; j <= W; ++j) {
            if (row[j-1] == 'B') {
                grid[i][j] = 1; // Bを1 Wを0
            }
        }
    }

    // 2次元累積和
    sum.assign(H + 2, vector<int>(W + 2, 0));
    for (int i = 1; i <= H+1; ++i) {
        for (int j = 1; j <= W+1; ++j) {
            sum[i][j] = grid[i][j] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
        }
    }

    int ans = 0;
    for(int x = 1; x <= W; ++x) {
        for(int y = 1; y <= H; ++y) {
            if(grid[y][x] != 1) {
                continue;
            }
            int x1, y1;
            tie(x1, y1) = dfs(x, y);
            if (x1 == -1 || y1 == -1) {
                continue;
            }

            int h = y1 - y + 1;
            int w = x1 - x + 1;
            if(
                get_sum(x, y, x1, y1) == h * w && 
                get_sum(max(1, x-1), y, x1+1, y1) == h * w && 
                get_sum(x, max(1, y-1), x1, y1+1) == h * w
            ) {
                ans++;
            }
        }
    }

    cout << ans << endl;
    return 0;
}

とても難しかったですね…
複数のアルゴリズムを応用して求める必要がありました。
並のスキルチェックSランク問題より難しいと思います。