はじめに

情報系の学科でCSを学習している学部2年のDot-P (@DotP_engineer) です。

今年も残すところあと少しになりました

そこで、今年に入ってから出会ったアルゴリズムで感動したものを取り上げたいと思います！

あえて、累積和や動的計画法、DFSといった有名どころのアルゴリズムは一切紹介しません。めちゃくちゃわかりやすい記事がたくさんQiitaにあがっていると思うのでそちらを参考にしてください

今回は、Atcoderなどの競技プログラミングでは典型であるものの、名称がついていないものを紹介します！

複雑なデータ構造は紹介せず、あくまでも美しいロジックが組み込まれているコードを取り上げるので、今まで競プロをしていない人でも気軽に読むことができると思います！

何か聞きたいことがあれば、気軽にTwitter(X)のDM (@DotP_engineer) までお願いします。

自己紹介

工学部の情報系学科２年。　普段は、C++やLinuxを触ることが多いです。

アルゴリズムや深層学習を学習中

競プロ、データ分析、人工知能、Web開発に関心があり、さまよっています (笑)

最近は、焼きなまし法、遺伝的アルゴリズムといったヒューリスティック解法を学習してます

SNS

・Twitter: @DotP_engineer (←モチベーションの増加になるので、フォローしてね)
・Qiita: https://qiita.com/DotP_engineer
・Github: https://github.com/Dot-P
・Atcoder: https://atcoder.jp/users/Dot_P (今年の2月から始めました！)

四方探索

四方探索と勝手に名前をつけているのですが、これはグリッド（二次元のマス）に対して上下左右のマスに何が格納されているのかを確かめる手法になります。

この手法は度々登場し、例えば、迷路の最短距離の計測などに利用できたりします。
詳しくは以下の問題を見てみるといいかもしれません。

四方探索は、グラフとも相性が良く非常に使い勝手がいいです。

しかし、初学者が四方探索のコードを書くと大体以下のコードになりがちです。

このコードは100×100のグリッドに「#」と「.」が存在するときに「#」が隣接するマスが存在するかどうかを確かめるものになります。ただし、隣接とは上下左右のマスのことを言うとします。（範囲外参照は、今回は考えないものとします）

シンプルな四方探索

for(int i = 0; i < 100; i++){
    for(int j = 0; j < 100; j++){
        if(Grid[i][j] == "#"){
            if(Grid[i+1][j] == '#') ans = true;
            if(Grid[i][j+1] == '#') ans = true;
            if(Grid[i-1][j] == '#') ans = true;
            if(Grid[i][j-1] == '#') ans = true;
        }
    }
}

正直、めんどくさい

そうは言いつつも駆け出しの頃はずっとこれを書いてました。

しかし、配列をうまく使えば効率的に処理することができます。

効率的な四方探索

vector<int> xi = { 1, 0, -1, 0 }
vector<int> yi = { 0, 1, 0, -1 }

for(int i = 0; i < 100; i++){
    for(int j = 0; j < 100; j++){
        if(Grid[i][j] == "#"){
            for(int k = 0; k < static_cast<int>(xi.size); k++){
                if(Grid[i+xi[k]][j+yi[k]] == '#') ans = true;
            }
        }
    }
}

この書き方を知ったときに衝撃を受けましたね

競プロ界隈ではかなり常識だったらしく、今まで人生の大切な時間を無駄にしていたと感じました（笑）

さらに、パワーアップして八方向探索などにも利用することができます。

八方向のときは以下のコードを変更するのみでいいです。

八方向探索

vector<int> xi = { 1, 1, 1, 0, 0, -1, -1, -1 }
vector<int> yi = { -1, 0, 1, -1, 1, -1, 0, 1 }

単純にコードを書くとより煩雑になり分かりにくいコードになるので、このようにまとめた方が見やすく、タイポもしにくいと思います。

この手法は度々登場するので知っていて損はないと思います！

アンド演算子を利用したビット全探査

ビット全探索は、アンド演算子を利用すると効率的にコードを書くことができます。

「二進数に変換するコードを書いて、それぞれの桁を配列に格納して...」

なんてことを昔はしていたのですが、ビット演算子を使えばその必要はありません

例えば、ナップザック問題に対してビット全探索を行う場合、以下のようになります！
(本当は、動的計画法で解くのがメジャーだけども)

ただし、Nはアイテム数であるとし、limit_wightをナップザックに詰めることのできる重量の最大値であるとします。item構造体には、priceとweightがあり、それぞれが各商品の価格と重量を表しているとします。

ビット全探査

# define rep (i , x , n ) for ( int i = x ; i < n ; i ++)

int max_value = -1;

rep (i , 0 , (1 << N ) ) {
    int price_sum = 0;
    int weight_sum = 0;
    rep (j , 0 , N ) {
        if ( i & (1 << j ) ) {
        price_sum += items [ j ]. value ;
        weight_sum += items [ j ]. weight ;
        }
    }
    if ( weight_sum > limit_weight ) continue ;
    if ( max_value < price_sum ) max_value = price_sum ;
}

cout << max_value << endl ;

まず、一番外側(インデックスが i ) の rep は各アイテムを含むかどうかを 0 か 1 の2ビットで表したものを全列挙しています。例えば、Nが5であれば、00000 ~ 11111 (0 ~ (2^5)-1)までを全列挙していることになります。

また、( 1 << j ) を 2 進数に変換すると、j桁目だけが 1 になり、他の桁は 0 となる二進数に変換することができます。

よって、アンド演算子で計算することで i を二進数変換したときの第 j 桁目を抽出できます。

例えば、i = 01010 ( Item2 と Item4 を選び、他は選ばない )、j = 3 であるとき、(1 << j) = 01000 であり、i & ( 1 << j ) = 1 となります。

つまり、Item4を抽出するという情報を取り出すことができたといえます。

先ほどに比べ、ロジックが複雑であるため、一回で理解するのは難しいと思いますが、慣れてしまえばものすごく便利であることが実感できると思います

まとめ

最後まで読んでくださりありがとうございます

私もまだまだなので、もっと美しいコードが存在するかもしれません。

共に精進して、より良いプログラマーを目指しましょう