目次

今日から始める基本情報技術者試験のアルゴリズム問題からの続きです。

お手元にトランプをご用意ください。今回のアルゴリズムはトランプを実際に並び替えてみて乗り越えましょう！百聞は一見に如かず！

選択法

計算量 $O(n^{2})$

選択法で意識することは次の2点です。

比較して実際に保持しておく情報は配列のインデックス
交換するのは配列を走破した後

これを意識すれば交換法と選択法が混ざることがありません。では具体的な流れを説明します。今回は昇順に並べてみます。降順の場合はどこを変えたらいいのか考えてみましょう。

先頭のインデックス：head
最小の値のインデックス:min
配列の長さ:N

head=1, n = 2, min = head
配列[min] < 配列[n]の場合
1. n = n + 1 にして 2.に戻る
配列[min] ≧ 配列[n]の場合
1. min = n, n = n + 1 にして 2.に戻る
n > N の場合
1. 配列[head] と配列[min] を入れ替える
2. head = 2, n = 3, min = head　として 2.に戻る

さて、例のごとく良さそげな記事を発掘してきました。リンク先はソートアルゴリズムのリンクをまとめて解説しています。解説してあるアルゴリズムは10種類と、基本情報に出てくるもの以外もたくさんありますが、アルゴリズムの流れのGIF動画が貼っている記事もありますので眺めてみるのも勉強になると思います。

ちなみに選択法はこちらです。GIF動画を見てきましょう！

雰囲気がつかめたら実際にトランプを5～6枚取り出して上記の流れに沿って一度手を動かしてみましょう。

計算量の話をここで少ししておきます。選択法では最小値（最大値）のインデックスを探すのに配列すべてを走破します。中のループは二回目以降からは整列した部分は飛ばすので、ループ回数が減っていくことがわかります。まずはこれを書き出してみます。

ループ1回目：N回
ループ2回目：N-1回
ループ3回目：N-2回

このまま続けていくと $1+2+ ... + N-1 + N$ となります。等差数列の和を考えればループ回数は $\frac{1}{2} N(1 + N) = \frac{1}{2}N^{2} + \frac{1}{2}N$ となります。最高次以外は切り捨てて、係数も捨てるので計算量は $O(n^2)$ ということになります。
なんで切り捨てていいのかは、前回の記事で紹介した計算量のリンク先で説明されています。

selection_sort.jl

function selection_sort(list)
    N = length(list)
    for i in 1:N
        min = i
        for j in i+1:N
            if list[j] ≤ list[min]
                min = j
            end
        end
        list[i], list[min] = list[min], list[i]
    end
    list
end

交換法、バブルソート

計算量 $O(n^{2})$

選択法が理解できていればバブルソートはとっても簡単です。ただ流れが少しだけ似ているので、バブルソートを学んだあとに選択法のポイントをもう一度見てみると違い理解できると思います。

さっそくバブルソートを見ていきましょう。バブルソートの流れは選択法において、最小の値を探すために値を比較するとこまでは同じです。選択法ではより小さい値の インデックス を保持して配列を__走破した後__に __交換__を行いましたね。

バブルソートでは値を比較し、より小さいのならば__その場__で__交換__ してしまいます。そして交換した値と隣の値を比べて、また交換する。といったことを繰り返していきます。配列を走破した後は整列済みの部分を飛ばすのでループ回数が減っていくことも選択法と同じです。計算量が同じなのはここからきていますね。

なので重要なのは、選択法→交換は最後だけ、バブルソート→毎回交換する。これをきちんと分けて理解することです。

先ほどとは違う記事ですが、バブルソートのGIFがありますのでこちらをみて雰囲気をつかんでください。
そしてトランプを取り出して（以下略）

bubble_sort.jl

function bubble_sort(list)
    N = length(list)
    for i in N-1:-1:1
        for j in 1:i
            if list[j+1] < list[j]
                list[j], list[j+1] = list[j+1], list[j]
            end
        end
    end     
    list
end

bit全探索を使ってAtCoderのC問題を解いてみた【おまけ】

前回は全探索を2進数にすればうまくいくということを学びました。今回はそれを使って実際に問題を解いてみます。

方針

bit全探索を使う問題なのでどこを2進数にするかを考える。

2進数で表せそうなのはスイッチの[on / off] ですね。それぞれのスイッチの状態を総当たりするために、bitという関数を作りました。前回の記事で実装した関数を少しだけ変えたものです。

さて、次は各電球が点灯するということをどうやって表すかです。これは二進数で表したスイッチの状態の和を取り、その余りを考えればいいです。具体的には次のようになります。

ある電球はスイッチの{1, 2}を使用しています。このとき、[01010]という状態のスイッチの状態について考えると、電球に関わるスイッチは頭から2つまでです。[01]このスイッチの和を取ると1になります。これを2で割った余りが1のとき電球が点灯するのか、0のとき点灯するのかは入力で与えられているのでそこを比較するだけでいいわけですね。

実装ではこの部分に当たります。binがスイッチの状態で、Kが電球に関わるスイッチのインデックスを表わしています。点灯の条件はPが保持しています。

ex.jl

if sum( bin[:,n][k] for k in K[m][2:end] ) % 2 == P[m]
    cnt += 1
end

最終的に全灯しているかを知りたいので、電球の点灯数を保持して置き全電球数と比較すれば答えが出ます。

C_plob.jl

# 二進数ベクトルの作成
function bit( N )
    res = zeros( N, 2^N )
    for n in 0:2^N - 1
        bin = string( n, base=2 )
        tmp = length(bin) < N ? "0"^(N-length(bin)) * bin : bin
        res[:,n+1] = parse.( Int, split( tmp, "" ) )[end:-1:1]
    end
    res
end

function main()
　　# 入力受け取り
    N, M = parse.( Int, split( readline() ) )
    K = [ parse.( Int, split( readline() ) )  for m=1:M ]
    P = parse.( Int, split( readline() ) ) 
    
    res = 0
    bin = bit(N)
    for n in 1:2^N
        cnt = 0
        for m in 1:M
            if sum( bin[:,n][k] for k in K[m][2:end] ) % 2 == P[m]
                cnt += 1
            end
        end
        # 全灯
        if cnt == M
            res += 1
        end
    end
    println(res)
end
main()