SQL勉強メモ

SQL関連で勉強したことのまとめ記事。
長くなってきたのでリンク集として使っていきたい。

SQL実行順序

FROM
JOIN
WHERE
GROUP BY
SUM, MAXなど
HAVING
SELET,DISTINCT
ORDER BY
LIMIT

ちなみにサブクエリは内側から最初に実行される。

小技集

select 1

select 1 from table～という謎のSQLに出会った。

exists文で使われるものらしい。

存在するかどうかだけがわかればよくて、データは要らないよって時に使う。

ただ、select 1 より select * のほうが早いらしい↓
COUNT(*)とCOUNT(1)の処理速度検証結果

もっと言うとexistsよりjoinのほうが早いらしい↓
EXISTSとSQLの高速化について - 猫好きモバイルアプリケーション開発者記録

-- A.name = B.nameである行だけ抽出
select * from Atable AS A
where
exists(
    select 1 from Btable AS B
    where
    A.name = B.name
    )

-- -- A.name = B.nameではない行だけ抽出
select * from Atable AS A
where
not exists(
    select 1 from Btable AS B
    where
    A.name = B.name
    )

where 1 = 1

where はtrueかfalseかで判定している。

1 = 1なら常にtrue。

使い所はwhere句かand句かの分岐の時。

よく複数単語検索なんかで使う。

検索条件が増える度にAND句で追加したいんだけど、最初はWHERE句じゃないといけないのでめんどくさい。

そこで WHERE句を1＝1にして、AND句の追加だけで良いようにする。

select * from
where 1= 1
and~ // ここに追加していく

・参考サイト
「WHERE 1=1」は条件付きSQL文が書きやすくなる魔法の言葉 | キノコログ

OFFSET FETCH

MySQLのLMIT OFFSETと同じで取得する行数を指定できる。

OFFSETでスキップする行数を指定。
FETCH NEXT ○ ROWS ONLYで何行取得するかを指定。

select user_id, name from account_table
order by user_id
OFFSET 10 ROWS
FETCH NEXT 5 ROWS ONLY;

11行～15行を取得。

・参考

sql-oracle.com

count(*)over()

window関数。

ページングの時にとても便利！

selectで総レコード数を取得しつつ、1ページ分のselect結果も欲しいときに使える。

secect count(*)over() , account_name
from account
limit 0 rows
fetch 100 rows

・参考記事

resanaplaza.com

テーブルデータ増殖技(Insert Select)

増殖テーブル

・SQL
id = A　を　id = B　にしてそれ以外の列はそのままで増殖する。

insert into increse
select 
name,
'B'
from increse
where
id = 'A'

増殖後

イメージとしては下記SQLを実行している感じ。
INSERT INTO table (name, id) VALUES (SELECT文)

insert into increse
(name, id)
values
(select name, 'C' AS 'id' from increse
where 
id = 'B')

GROUP BY句にないカラムも表示させたい

Group By句にないカラムを表示させたい - okinawa

テーブル同士の比較

【SQL】テーブル同士の比較 - okinawa

基礎知識

GROUP BYってなんなの？

部分集合に切り分ける。
GROUP BYってなんなの？ - okinawa

NULLとの四則演算は必ずNULLになる

1 + NULL = NULL
5 * NULL = NULL

集合指向言語と手続き型言語の違い

集合指向言語：まとめて処理
手続き型言語：１件ずつ処理
集合指向言語と手続き型言語の違い - okinawa

HAVING句を理解すると集合志向が理解できるらしい

HAVING句をマスターすると集合志向が理解できるらしい - okinawa

３値論理

普通は TRUE/FALSEの２つ
SQLは TRUE / FALSE / UNKNOWN の３つ
真理値の優先順位は下記↓

• AND：FALSE > UNKNOWN > TRUE
• OR： TRUE > UNKNOWN > FALSE

【SQL】３値論理とは - okinawa

バッファプールとログバッファ

• バッファプール：ストレージ（HDD)にあるRDBのデータの一部を保持している。
• ログバッファ：更新処理のときに更新情報をログバッファ上にためて、コミット時にまとめて行うための領域。

バッファプールとログバッファ - okinawa

豆知識

COUNT(＊)とCOUNT(列名)の違い

• COUNT(＊)：NULLも含む全行カウント
• COUNT(列名)：NULLではない行数カウント

ちなみにAVG()はNULLの行はカウントしないで計算する。

相関名（AS～）の有効範囲

（）内の名前は（）の内側のみで使用可能。
外側では使用不可。

これは実行順序の問題。
サブクエリは内側から実行される。
実行された後は実行結果しか残らないので名前はもう残っていない。。。
なんかかっこいい。

ほかにもSELECT句でつけたAS名がWHERE句で使えないのもSELECT句の方が実行順序が後だから。

UNIONの使い所

異なるテーブルをまとめて集計したいとき。
UNIONの使い所 - okinawa

CASE式のELSE句は必ず書くべし！

ELSEは省略するとNULLが入ってしまうので。
SQL CASE式について - okinawa

サブクエリの実行順序と相関サブクエリ

サブクエリは内側から実行される。
SQL サブクエリについてのメモ - okinawa

特性関数とは

ある値が集合に含まれるか調べる関数。
集合に対する条件判定や集計に便利な関数です。
【SQL】特性関数とは - okinawa

SQLチューニング

実行計画の見方。

• MySQLはSQL文の頭に　explain　を付けるだけ。
• SQLServerはSQL文の頭に　SET STATISTICS PROFILE ON　を付ける。

GUIで見る方法もある↓

実際の実行プランの表示 - SQL Server | Microsoft Learn

チューニングについては過去記事も参照↓

GMOのDBチューニング課題やってみた - okinawa

インデックスって何なの？

DB勉強メモ - okinawa

SQLチューニング方法一覧

SQLチューニングの一覧 - okinawa

統計情報とは

実行計画を練るためのネタ元

統計情報とは - okinawa

テーブル結合関連

inner join と outer joinの違いはベン図で表すとわかりやすい

ベン図

・参考記事
SQL Joinサンプル集 Joinで遅いSQLの原因を調べる方法 | ポテパンスタイル

Isn't SQL A left join B, just A? - Stack Overflow

on句が一部合致するとどうなるの？

下記の2テーブルをleft outer joinで実験。

Shohinテーブル

Zaikoテーブル

select * from Shohin
left outer join Zaiko
on Zaiko.name = Shohin.shohin_mei
and Zaiko.category = Shohin.shohin_bunrui;

・結果

on句が全部合致した行だけ値が入って結合されている。1行目と3行目。

on句が一部合致した行は全部nullで結合されている。4行目。

すべて合致した行のみ結合され、それ以外はNULLで出力されるということ。

結果

on句をwhere句っぽく使うときの注意点

・torihikijiyuテーブル

取引事由テーブル

・haishi_kouzaテーブル

廃止口座テーブル

・SQL文(right outer join)

select * from haishi_kouza
right outer join
torihikijiyu as tor
on
tor.torihikijiyumei = '契約' --where句っぽいところ

結合後2

上記のように取引事由が「契約」以外の行も出力されてしまう。
right joinの場合は右側のテーブルは結合条件に合致しなくても全て出力される。
そのためtorihikijiyuテーブルの行はすべて出力。

この場合は、leftかinner joinにすれば取引事由が「契約」の行のみ出力される。

あれ？どゆこと？ where句と同じことになると思ってたけどそうじゃないようで。
どうやらouter側のテーブルは全部返ってくる。
でも inner joinの時はwhere句みたいな動きをしている。（SQL1） ま、where句みたいに使いたいならwhere句を使いましょう。
→where句よりjoin句で絞り込んだほうが処理が早いらしい。

・SQL文1(left join)

select * from haishi_kouza
left join
torihikijiyu as tor
on
tor.torihikijiyumei = '契約'

結合後

結果は廃止口座テーブルの全ての行に取引事由テーブルの「契約」の行だけが結合される。

ここのまとめ

結合の向きに注意する。

・tableA left join tableB
tableB.columnB = '契約' にすると「契約」の行のみ結合して出力。

・tableA right join tableB
tableB.columnB = '契約' にすると「契約」以外の行も全て出力されてしまう。

テーブル結合ってなんなの？（重要）

無条件テーブル結合をやってみたらわかりやすかった。

・torihikijiyuテーブル

取引事由テーブル

・haishi_kouzaテーブル

廃止口座テーブル

・SQL（無条件結合）

select * from haishi_kouza
inner join
torihikijiyu as tor
on
1 = 1

・結果

結合後

テーブル結合ってのは
列は、tableA + tableB
行は、tableA × tableB
になるんだなあ。

外部結合ミスの見つけ方

外部結合が上手くいってなくて不要な行が出力されたり、nulで出力されて困った時に。

• nullではないはずのカラムがnullだったら外部結合ミスを怪しもう。ON句の結合ができない行はnullを含んで出力される。
• 妙なところにMAXやMINが使われていたら外部結合ミスを取り繕っている可能性あり

テーブル結合で行を増殖させないポイント

ON句の条件を

• 1対1で結合
• 1対多で結合

【SQL】テーブル結合で行を増殖させないポイント - okinawa

集合演算をテーブル結合でやってみる

SQLの集合演算をテーブル結合でやってみる

テーブル結合ハマったこと

テーブル結合でハマったこと - okinawa

SQLを読むときのポイント

• 最初にSELECT行を見て何を取得するか把握する
• 最初のFrom句のテーブルがメインテーブル
• group byやsumなどの集約関数を見ると何を集計したいのかわかる
• ネストの深いところから見ていくと割とわかりやすい

SQLテストサイト

ブラウザでSQLを実行できる便利サイト↓
sqlfiddle.com

その他

DISTINCTとNOT EXISTSでハマった話

NOT EXISTSとDISTINCTでハマった話 - okinawa

ユークリッドの互除法

放送大学の授業でユークリッドの互除法を見て、その後にちょうとAtCoderでユークリッドの互除法を使う問題に出会った。

ということで備忘録として。

atcoder.jp

ユークリッドの互除法とは

最大公約数を求めるもの。

大きい方から小さい方を引いていき、同じ値になったらそれが最大公約数。

放送大学の折り紙を使った説明がわかりやすかった。

例：126と35の最大公約数

126	91	56	21	21	7	7
35	35	35	35	14	14	7

最初は126から35を3回引いて21

次に35-21＝14

21-14＝７

14-7＝7

7が最大公約数。

プログラム（引き算バージョン）

int a = 126;
int b = 35;
        //ユークリッドの互除法1(引き算バージョン）
        while (a != b) {

            
            if (a >= b) {
                a = a - b;
            } else {
                b = b - a;
            }

プログラム２（余りバージョン）

やってることは引き算と同じ。

int a = 126;
int b = 35;
        //ユークリッドの互除法2
        while (Math.min(a, b) > 0) {

            
            if (a >= b) {
                a = a % b;
            } else {
                b = b % a;
            }
        }
        long ans = Math.max(a, b);

参考サイト

qiita.com

【初心者向け】Notionでタグライブラリを作る

タグライブラリが便利らしいので、Notionに初挑戦してみたら大変だったので、自分と同じような誰かのためになればと。

参考サイト

こっちを見たほうが早い⇩
www.youtube.com

タグライブラリの作り方

画像が見づらくなってしまった・・・。

・左サイドバーのページを追加を選択

ページを追加

・その他→ギャラリーを選択して、名前をTags Databaseにする

・右サイドバーの新規データベースを選択

・右上の「・・・」からレイアウトを選択

レイアウト

・カードプレビューなし、カードサイズ小に変更する

・ページ１・ページ２・ページ３は削除する

削除

・タグを新規作成する

タグ新規作成

・作ったタグ

・左サイドバーのページを追加を選択

ページを追加

・テーブルを選択

・右サイドバーの新規データベースを選択

・タグ列の右にある「・・・」を選択

・右サイドバーの新しいプロパティを選択

新しいプロパティ

・リレーションを選択

リレーション

・先程作ったTags Databaseを選択

・Tags Databaseに表示をONにする⇨リレーションを追加

・Tags Database列を選択すると、さっき作ったタグが表示される

・Tags Databseの方でタグを選択すると、Master Notesのところにリンクが表示されている。これで完了。

新しいタグはTags Databaseからでも、Master Notesからでも作れる。

・Master Notesで新しくタグを作ると

・Tags Databaseにも作られている

タグライブラリを作ると何が嬉しいのか

• メモに複数のタグを付けられる
• 全部のメモを１つのDBに入れて、タグだけで分類できる

多重for文を再帰関数で書く

この問題が解けなかったので、再帰関数を勉強した。⇩

atcoder.jp

参考サイト

drken1215.hatenablog.com

使い所

全探索・順列全探索・階乗通り列挙

2重・3重for文を再帰関数で書いてみた

import java.util.ArrayList;
import java.util.List;

//多重for文を再帰で作る練習
public class RecursiveFunctionPractice {
    private static List<Integer> list = new ArrayList<>();
    private static boolean[] seen = new boolean[3];
    
    // 2重for文。2桁の数列を全通り作る
    private static void recursion() {
        //ベース条件（終了条件）
        // 2桁になったら終了
        if(list.size() == 2) {
            for(int num : list) {
                System.out.print(num + " ");// (0,0) (0,1) (1,0) (1,1)
            }
            System.out.println();
            return;
        }
        
        for(int i = 0; i < 2; i++) {
            list.add(i);
            recursion();
            list.remove(list.size()-1);// 末尾を削除。ここがポイント
        }
        
    }
    
    // 3重for文。順列の並び替え全通りやる。3の階乗通りになる。
    private static void rotate() {
        //ベース条件（終了条件）
        // 3桁になったら終了
        if(list.size() == 3) {
            for(int num : list) {
                System.out.print(num + " ");//( 1, 2, 3 ) ( 1, 3, 2 ) ( 2, 1, 3 ) ( 2, 3, 1 ) ( 3, 1, 2 ) ( 3, 2, 1 )
            }
            System.out.println();
            return;
        }
        
        for(int i = 0; i < 3; i++) {
            if(seen[i] == false) {
                list.add(i+1);
                seen[i] = true;
                rotate();
                list.remove(list.size()-1);// 末尾を削除。ここがポイント
                seen[i] = false;
            }

        }
        
    }
    
    public static void main(String[] args) {
        // TODO 自動生成されたメソッド・スタブ
        recursion();
        rotate();
    }

}

処理の流れイメージ

・recursionメソッド

再帰処理イメージ

listに0を加える。リストの中身→(0)

⇩再帰呼出し

listに0を加える (0, 0)

⇩再帰呼出し

listのサイズが2なのでreturn

⇩

list.remove(list.size()-1)でリストの末尾を削除 (0)

⇩for文が1個進む

listに1を加える。(0,1)

⇩再帰呼び出し

listのサイズが2なのでreturn

⇩

list.remove(list.size()-1)でリストの末尾を削除 (0)

⇩

for文終了して、1つ前のスレッドへ戻る。

⇩

list.remove(list.size()-1)でリストの末尾を削除 ()

⇩for文が1個進む

listに1を加える(1)

⇩再帰呼出し

listに0を加える（1,0)

⇩処理が終わるまで続く

再帰処理のスレッドとは？

こっちの「再帰関数の面白い所」に書きました⇩

dodosu.hatenablog.jp

ABC302-C Almost Equalの解答

冒頭の問題の解答コード

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class AlmostEqual {
    private static int n;
    private static int m;
    private static boolean answer = false;
    private static boolean[] seen;
    private static List<char[]> charList = new ArrayList<>();
    private static List<char[]> surveyTarget = new ArrayList<>();
    
    private static void recursion() {
        if(answer) {
            return;
        }
        // ベース条件（再帰を終了する条件）
        // 配列数がNと同じなら比較処理に飛ぶ
        if(surveyTarget.size() == n) {
            // 比較処理にとんでTRUEなら終了。FALSEなら処理継続
            if(compareCharList()) {
                answer = true;
                return;
            }
        }
        
        // 未探索なら配列に加える
        for(int i = 0; i < n; i++) {
            if(seen[i] == false) {
                surveyTarget.add(charList.get(i));
                seen[i] = true;
                recursion();//再帰
                surveyTarget.remove(surveyTarget.size()-1);
                seen[i] = false;
            }
        }
    }
    
    // 文字列同士の比較。
    // 隣り合う文字列同士が全て一文字違いならTRUE
    private static boolean compareCharList() {
        
        boolean result = true;
        for(int i = 0; i < n-1; i++) {
            char[] c1 = surveyTarget.get(i);
            char[] c2 = surveyTarget.get(i+1);
            
            int count = 0;
            for (int j = 0; j < m; j++) {
                if(c1[j] != c2[j]) {
                    count++;
                }
            }
            if(count != 1) {
                result = false;
                return result;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        seen = new boolean[n];
        
        for(int i = 0; i < n; i++) {
            char[] c = sc.next().toCharArray();
            charList.add(c);
        }
        
        //再帰処理開始
        recursion();
        
        if(answer) {
            System.out.println("Yes");
        }else {
            System.out.println("No");
        }
        
        
//　旧回答。バケット法ではダメだった。いけそうな気もするんだけど。
//     List<int[]> list = new ArrayList<>();
//     List<char[]> charList = new ArrayList<>();
//
//     for (int i = 0; i < n; i++) {
//         char[] arr2 = sc.next().toCharArray();
//         charList.add(arr2);
//
//         int[] arr = new int[26];
//
//         for (char c : arr2) {
//             arr[(int) (c - 'a')]++;
//         }
//
//         list.add(arr);
//     }
//
//     // 2つだけ違えばOK。２重で全探索
//     int count = 0;
//     for (int i = 0; i < list.size(); i++) {
//         int[] arr3 = list.get(i);
//         for (int j = i + 1; j < list.size(); j++) {
//             int[] arr4 = list.get(j);
//
//             int sai = 0;
//             for (int k = 0; k < 26; k++) {
//                 sai = sai + Math.abs(arr3[k] - arr4[k]);
//             }
//             if (sai == 2) {
//                 count++;
//             }
//         }
//     }
//     if (count >= n-1) {
//         System.out.println("Yes");
//     } else {
//         System.out.println("No");
//     }

    }
}

深さ優先探索のお勉強

深さ優先探索を理解するために、写経したり実装したりしてみた。

参考サイト

DFS (深さ優先探索) 超入門！ 〜 グラフ・アルゴリズムの世界への入口 〜【前編】 - Qiita

うさぎでもわかる2分探索木 後編 2分探索木における4つの走査方法 | 工業大学生ももやまのうさぎ塾

深さ優先探索とは

形式的には、深さ優先探索は、探索対象となる木の最初のノードから、目的のノードが見つかるか子のないノードに行き着くまで、深く伸びていく探索である。

その後はバックトラックして、最も近くの探索の終わっていないノードまで戻る。非再帰的な実装では、新しく見つかったノードはスタックに貯める。 引用元：深さ優先探索 - Wikipedia

使い所

１．迷路問題。

スタート地点からゴール地点まで行くルートがあるかを探索する問題など。

ただし、最短ルートの探索はできない。

最短ルート探索は幅優先探索でやる。

グラフを隣接リスト表現で作ってみる

画像の引用元：DFS (深さ優先探索) 超入門！ 〜 グラフ・アルゴリズムの世界への入口 〜【前編】 - Qiita

上図の有向グラフを作ってみた。

package atcoder;

import java.util.ArrayList;
import java.util.List;

public class DirectdGraph {

    //有向グラフを写経。隣接リスト表現
    public static void main(String[] args) {
        // グラフ
        List<List<Integer>> graph = new ArrayList<>();
        
        // 頂点
        List<Integer> vertex0 = new ArrayList<>();
        vertex0.add(5);//頂点0 数値は頂点０から向かう別の頂点。頂点０→頂点５に向かう辺を表す。
        graph.add(vertex0);// 頂点０と辺をグラフに格納
        
        List<Integer> vertex1 = new ArrayList<>();
        vertex1.add(3);//頂点1から頂点３に向かう辺
        vertex1.add(6);//頂点1から頂点６に向かう辺
        graph.add(vertex1);// 頂点１と辺をグラフに格納
        
        
        List<Integer> vertex2 = new ArrayList<>();
        vertex2.add(5);//頂点2
        vertex2.add(7);//頂点2
        graph.add(vertex2);
        
        List<Integer> vertex3 = new ArrayList<>();
        vertex3.add(0);//頂点3
        vertex3.add(7);//頂点3
        graph.add(vertex3);
        
        List<Integer> vertex4 = new ArrayList<>();
        vertex4.add(1);//頂点4
        vertex4.add(2);//頂点4
        vertex4.add(6);//頂点4
        graph.add(vertex4);
        
        List<Integer> vertex5 = new ArrayList<>();
        graph.add(vertex5);//頂点５から向かう頂点はない
        
        List<Integer> vertex6 = new ArrayList<>();
        vertex6.add(7);//頂点6
        graph.add(vertex6);
        
        List<Integer> vertex7 = new ArrayList<>();
        vertex7.add(0);//頂点7
        graph.add(vertex7);
        
        System.out.println(graph);//[[5], [3, 6], [5, 7], [0, 7], [1, 2, 6], [], [7], [0]]
    }
}

木構造を深さ優先探索する

画像の引用元：DFS (深さ優先探索) 超入門！ 〜 グラフ・アルゴリズムの世界への入口 〜【前編】 - Qiita

再帰関数バージョン

想定通り0~14の順番で探索してくれた。

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class DepthFirstSearch {

        //再帰関数
        private void dfs(List<List<Integer>> graph, List<Boolean> seen, int vertexNumber) {
            
            // 訪れた頂点を探索済みとする
            seen.set(vertexNumber, true);
            
            System.out.print(vertexNumber+ " ");//0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
            
            // 深さ優先で探索する
            for (int i = 0; i < graph.get(vertexNumber).size(); i++) {//辺の数分繰り返す
                //行き先
                int destination = graph.get(vertexNumber).get(i);
                
                if (seen.get(destination)) {
                    // 探索済みならスキップ
                    continue;
                }
                dfs(graph, seen, destination);// 再帰。次の行き先を渡す。
            }
        }

        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();//頂点数


            // グラフ
            List<List<Integer>> graph = new ArrayList<>();
            // 探索済み判定用
            List<Boolean> seen = new ArrayList<>();

            //グラフを入力から受け取る
            for (int i = 0; i < n; i++) {//頂点数分繰り返す
                int m = sc.nextInt();//辺の数
                // 頂点
                List<Integer> vertex = new ArrayList<>();
                for (int j = 0; j < m; j++) {//辺の数分繰り返す

                    vertex.add(sc.nextInt());//繋がっているノードを受け取る

                }
                // 頂点の数だけ探索判定用リストも作る
                seen.add(false);
                //頂点と辺をグラフに格納
                graph.add(vertex);
            }
            
            DepthFirstSearch d = new DepthFirstSearch();
            d.dfs(graph, seen, 0);

            System.out.println(seen);//[true, true, true, true, true, true, true, true]
        }

    }

入力値

N=ノードの数

Mi=繋がるノードの数（辺の数）

Ai = 繋がっているノード

入力例：

2 ←ノードの数  
3 ←繋がるノードの数　繋がっているノード→1 4 11  
3 0 2 3  

画像の木構造に対応した入力値⇩

15  
3 1 4 11  
3 0 2 3  
1 1  
1 1  
3 0 5 8  
3 4 6 7  
1 5  
1 5
3 4 9 10
1 8
1 8
3 0 12 13
1 11
2 11 14
1 13

再帰関数の面白いところ

下図のようにノード２まで行ったら未探索のノードが繋がってなくて探索終了するのでは？

と思ったがそんなことはなかった。

デバッグモードで見るとよくわかるんだが、ノード0とノード1の探索スレッドがまだ残っている。

ノード２を探索中のデバッグモード⇩

ノード２探索スレッド

⇧
vertexNumber=探索中のノード
destination=1　が次の行き先

ノード２は次の行き先が１しか無い。
でも１はすでに探索済みだから探索終了するのでは？と思った。

ノード0とノード１の探索スレッドが残っていた

ノード１探索スレッド⇩

ノード１からノード3へはまだ行ってないので行き先が残っている。

ノード０スレッドもあるよ⇩

ノード0の探索スレッド

再帰関数の処理の流れ

ノード2の探索スレッドが終了
⇩
ノード1の探索スレッドに戻る
⇩
ノード1の探索スレッドが終了
⇩
ノード0の散策スレッドに戻る

ということでした。

さすがEclipseのデバッグモードはわかりやすい。

スタックバージョン

0 11 13 14 12 4 8 10 9 5 7 6 1 3 2 と再帰関数バージョンとは逆回りの深さ優先探索になった。

package atcoder;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
import java.util.Scanner;

// 深さ優先探索（スタックバージョン）
public class DepthFirstSearch3 {
    // Double Ended Queue(両端キュー）先入れ先出しと後入れ先出しのどちらにも対応
    private static Deque<Integer> deque = new ArrayDeque<>();
    private static List<List<Integer>> graph;
    private static List<Boolean> seen;

    private void dfs() {

        // スタックが空になるまで
        while (deque.isEmpty() == false) {
            //スタックからノードを取り出す。取り出すとスタックから削除される
            int vertexNumber = deque.pop();
            
            System.out.print(vertexNumber+ " ");//0 11 13 14 12 4 8 10 9 5 7 6 1 3 2

            // 訪れたノードを探索済みとする
            seen.set(vertexNumber, true);

            // 深さ優先で探索する
            for (int i = 0; i < graph.get(vertexNumber).size(); i++) {//繋がるノードの数分繰り返す
                //行き先
                int destination = graph.get(vertexNumber).get(i);

                if (seen.get(destination) == false) {
                    // 未探索ノードをスタック
                    deque.push(destination);
                }
            }
        }

    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();//ノード数

        // グラフ
        graph = new ArrayList<>();
        // 探索済み判定用
        seen = new ArrayList<>();

        //グラフを入力から受け取る
        for (int i = 0; i < n; i++) {//ノード数分繰り返す
            int m = sc.nextInt();//繋がるノードの数
            // ノード
            List<Integer> vertex = new ArrayList<>();
            for (int j = 0; j < m; j++) {//繋がるノードの数分繰り返す

                vertex.add(sc.nextInt());//繋がっているノードを受け取る

            }
            // ノードの数だけ探索判定用リストも作る
            seen.add(false);
            //ノード＆繋がるノードをグラフに格納
            graph.add(vertex);
        }

        DepthFirstSearch3 d = new DepthFirstSearch3();
        // スタート地点をスタック
        deque.push(0);
        d.dfs();

        System.out.println(seen);//[true, true, true, true, true, true, true, true, true, true, true, true, true, true, true]
    }

}

AtCoder Beginner Contest 301

記念すべき初rated参加。

コンテスト参加は2回めだけど前回はDDos攻撃でunratedになった。

atcoder.jp

A - Overall Winner

・改善点

過半数勝利を先にどっちがするか判定　⇨　同点なら先に過半数取ったほうが勝利としているが、そもそも過半数勝利を先にした時点で勝利確定。

過半数勝った時点でbreakしてしまえばよかった。

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String s = sc.next();

        int t = 0;
        int a = 0;
        boolean firstT = false;
        boolean firstA = false;
        for (int i = 0; i < s.length(); i++) {
            if(s.charAt(i) == 'T') {
                t++;
                if(s.length() /2 <= t && firstT == false && firstA == false) { //⇐ここで過半数勝利を先にどっちがするか判定
                    firstT = true;
                }
            }
            
            if(s.charAt(i) == 'A' ) {
                a++;
                if(s.length() /2 <= a && firstT == false && firstA == false) {
                    firstA = true;
                }
            }
        }
        if(t > a) {
            System.out.println("T");
            return;
        } else if(t == a) {
            if(firstT) {
                System.out.println("T");
            } else {
                System.out.println("A");
            }
        }else {
            System.out.println("A");
        }
    }
}

B - Fill the Gaps

かなり時間がかかったところ。

list.add(i+1+j, list.get(i)+1+j);　の部分で何を足して何を引くかこんがらがってしまった。

メモ書きしながら考えを整理しよう。

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<Integer> list = new ArrayList<>();
        
        for(int i = 0; i < n; i++) {
            list.add(sc.nextInt());
        }
        
        for(int i = 0; i < list.size()-1; i++) {
            if(Math.abs(list.get(i) - list.get(i+1)) != 1) {
                int num = list.get(i) - list.get(i+1);
                if(num < 0) {
                    // プラス方向
                    for(int j = 0; j < Math.abs(num)-1; j++) {
                        list.add(i+1+j, list.get(i)+1+j); //⇐ここで時間かかった。
                    }
//                 i = 0;
                    
                } else {
                    // マイナス方向  
                    for(int j = 0; j < Math.abs(num)-1; j++) {
                        list.add(i+1+j, list.get(i)-1-j); //⇐ここも
                    }
//                 i = 0;
                }
            }
        }
        String s = "";
        for(int nn : list) {
            s += nn + " "; 
            
        }
        System.out.println(s.trim());
    }
}

参考解答

・引用元
Submission #41350087 - パナソニックグループプログラミングコンテスト2023（AtCoder Beginner Contest 301）

上位の方の解答コード。

すごくシンプルできれいなコードで感動した。

こういうコードを書けるようになりたいなあ。

何でもかんでもfor文で書いてしまうので、while文もうまく使いたい。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        try (Scanner scanner = new Scanner(System.in)) {
            int n = scanner.nextInt();
            int from = scanner.nextInt();
            n--;
            System.out.print(from);
            for (int i=0;i<n;i++) {
                int to = scanner.nextInt();
                while (from != to) {
                    if (from > to)
                        from--;
                    else
                        from++;
                    System.out.print(" "+from);
                }
            }
            System.out.println();
        }
    }

}

C - AtCoder Cards

バケット法。

結構早く解けて満足。

ただ、小文字の a がint数値で何になるかわざわざググってしまったが、 int a = (int) ('a');　で変換してしまえばもっと早かった。

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        String t = sc.next();
        int[] arr = new int[27];
        int[] arr2 = new int[27];

        char[] sarr = s.toCharArray();
        char[] tarr = t.toCharArray();

        for (char c : sarr) {
            if (c == '@') {
                arr[26]++;
            } else {
                arr[c - 97]++;
            }
        }

        for (char c : tarr) {
            if (c == '@') {
                arr2[26]++;
            } else {
                arr2[c - 97]++;
            }
        }

        int count = 0;
        int atcount = 0;
        for (int i = 0; i < arr.length; i++) {
            if (i == arr.length - 1) {
                atcount = arr[i] + arr2[i];

            } else {
                int diff = Math.abs(arr[i] - arr2[i]);
                if (diff > 0 && i != 0 && i != 19 && i != 2 && i != 14 && i != 3 && i != 4 && i != 17) {
                    System.out.println("No");
                    return;
                }
                count += diff;
            }
        }
        if (atcount >= count) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }

    }
}

無課金ChatGPTにAtCoderの解説頼んでみた

AtCoderの解説読んでもよくわからない所があったので、ChatGPTに質問してみた。

最初にまとめ

• 無課金でもChatGPTさんは強かった。
• わからない部分を追加で質問できるのが素晴らしい。
• 解答コードだけより問題文もつけると精度上がる。しかも問題文は整形しなくてOK！
• 微妙に間違っているところもある（Before Afterの箇所）

質問文

◆ 命令
下記のC++のソースコードは問題文の答えを出力するソースコードです。 下記のソースコードの意味を教えてください。

◆ 問題文
縦 H マス横 W マスの 2 つのグリッド A,B があります。グリッドの各マスには # と . のいずれかの文字が書かれています。 A と B の上から i 行目、左から j 列目に書かれている文字をそれぞれ A i,j ​ ,B i,j ​ と呼びます。

次の 2 種類の操作をそれぞれ 縦方向のシフト, 横方向のシフト と呼びます。

j=1,2,…,W について次の操作を同時に行う。 A 1,j ​ ,A 2,j ​ ,…,A H−1,j ​ ,A H,j ​ を A 2,j ​ ,A 3,j ​ ,…,A H,j ​ ,A 1,j ​ に同時に置き換える。 i=1,2,…,H について次の操作を同時に行う。 A i,1 ​ ,A i,2 ​ ,…,A i,W−1 ​ ,A i,W ​ を A i,2 ​ ,A i,3 ​ ,…,A i,W ​ ,A i,1 ​ に同時に置き換える。 次の条件を満たす非負整数の組 (s,t) は存在しますか？存在する場合は Yes を、存在しない場合は No を出力してください。

縦方向のシフトを s 回行い、次に横方向のシフトを t 回行った時、操作後の A が B と一致する。 ここで、 A と B が一致するとは、 1≤i≤H,1≤j≤W を満たす整数の組 (i,j) すべてに対して A i,j ​ =B i,j ​ が成り立つことを言います。

◆ ソースコード

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
  int H, W;
  cin >> H >> W;
  vector<string> A(H), B(H);
  for (auto& x : A) cin >> x;
  for (auto& x : B) cin >> x;
  for (int s = 0; s < H; s++) {
    for (int t = 0; t < W; t++) {
      int ok = 1;
      for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
          if (A[(i - s + H) % H][(j - t + W) % W] != B[i][j]) ok = 0;
        }
      }
      if (ok) {
        cout << "Yes" << endl;
        exit(0);
      }
    }
  }
  cout << "No" << endl;
}

ChatGPTの回答

このC++のプログラムは、2つのH行W列のグリッドAとBが与えられ、Aを上下にシフトし、次に左右にシフトすることでBと一致するかどうかを判断する問題の解法を提供します。

プログラムは、まずグリッドAとBを入力し、次にAをs回だけ上下にシフトし、t回だけ左右にシフトしてBと一致するかどうかを判断します。ここで、シフトによってグリッドの端からはみ出した部分は、グリッドの反対側に回り込むことに注意してください。

プログラムは、BとAのシフト後のグリッドが一致するかどうかを確認するために、ネストされた4つのforループを使用しています。最初の2つのループは、sとtの値を変更するためのものであり、残りの2つのループは、AとBの対応するセルが一致するかどうかを確認するためのものです。

okという変数は、現在のsとtの値に対して、AとBのシフト後のグリッドが一致するかどうかを示すフラグです。一致していない場合、okを0に設定します。最後に、okが1のままであれば、AとBが一致していることを示す"Yes"を出力し、プログラムを終了します。okが1にならない場合は、"No"を出力します。

追加の質問

シフトによってグリッドの端からはみ出した部分は、グリッドの反対側に回り込む、というのはどうやって実現していますか？

追加の回答

このプログラムでは、シフトによってグリッドの端からはみ出した部分をグリッドの反対側に回り込ませるために、C++ の演算子 %（剰余演算子）を使っています。

具体的には、A[(i - s + H) % H][(j - t + W) % W] という部分で、%演算子を使って行と列のオフセットを計算しています。この演算は、i - s が負数になった場合でも正しいオフセットを計算するためのものです。

例えば、グリッドの高さが H=4 の場合を考えてみます。シフトを s=1 回行うと、一番上の行が一番下に移動し、他の行も上に1つずつ移動します。

Before:  After:
.#..     ....
..#.     .#..
#...     ..#.
....     ...#

この状態で、A[2][2] の要素を参照するときには、元のグリッドの A[1][2] に相当します。つまり、行のオフセットは -s になります。しかし、A[-1][2] のように負の添字を使ってしまうと、配列外参照となってしまいます。そこで、(i - s + H) % H のように、負のオフセットを正のオフセットに変換するために、% H を使って H を足してから、H で割った余りを求めます。これによって、グリッドの端からはみ出た部分が、グリッドの反対側に回り込むことができます。

列についても同様の計算を行っています。

問題文＆ソースコードの引用元

B - Same Map in the RPG World

Editorial - ユニークビジョンプログラミングコンテスト2023 春 (AtCoder Beginner Contest 300)