一介のCS人の綴り

トップ > プログラミング > プログラミングTips
Tweet

プロコンテクを学ぼう!とは?

私は、2014年のICPC国内予選に参加するため競技プログラミングに触れ始め、マイペースに不定期に参加しているだけであるため、実力は本格的に参加している方々と比べると見劣りする部分が多いかと思います。 しかし、参加の主旨として自身のプログラミングスキルの向上を第一に置いているため、プログラミングテクニックとして学ぶべきものをまとめていき、知識を整理していきたいと思います。

ここでは、競技プログラミング初心者が実力を高めていくのに必須かつ基本的なプログラミングテクニックをまとめていく記事となります。

what's new

2015/12/25
プロコンテクを学ぼう! - No.2 を投稿
2015/12/14
プロコンテクを学ぼう! - No.1 を投稿

プロコンテクを学ぼう! - No.1

グリッド(格子)上走査

ここでは以下のような4方位もしくは8方位上の探索についてまとめる。

グリッド(格子)上走査

画像上の赤い点からそれぞれの方位に1区画の部分に移動する際のことを考える。 このとき、以下のようにdx[]やdy[]などの配列を用いて各方位1マス先の座標を計算し、順にそのマスにおける処理をしていく。 探索法としては、先に深度の大きい側を優先しているため、深さ優先探索 (DFS)を用いていることとなる。

// 4方位の場合 ver.1
int dx[4]={ 0, 1, 0,-1};
int dy[4]={ 1, 0,-1, 0};
int dfs(int x, int y){
    // (x,y)における処理

    // 周囲4方位のマスを探索
    for(int i = 0; i < 4; i++){
        int nx = x + dx[i], ny = y + dy[i];
        dfs(nx, ny);
    }
}

// 4方位の場合 ver.2
int d[5]={ 0, 1, 0,-1, 0};
int dfs(int x, int y){

    for(int i = 0; i < 4; i++){
        int nx = x + d[i], ny = y + d[i+1];
        dfs(nx, ny);
    }
}

// 4方位の場合 ver.3
int d[4]={ 0, 1, 0,-1};
int dfs(int x, int y){

    for(int i = 0; i < 4; i++){
        int nx = x + d[i], ny = y + d[(i+1) & 3];
        dfs(nx, ny);
    }
}
        

4方位の場合は上記の通り、いくつかパターンが存在している。versionが進むにつれ、使用するメモリ量が小さくなっていくが、 個人的にはどれもメモリ量に差は大きくなく、ver.1が一番わかりやすくミスを防ぎやすいと考えているためver.1をいつも利用している。

//8方位の場合 ver.1
int dx[8]={ 0, 1, 0,-1, 1, 1,-1,-1};
int dy[8]={ 1, 0,-1, 0, 1,-1, 1,-1};
int dfs(int x, int y){

    for(int i = 0; i < 8; i++){
        int nx = x + dx[i], ny = y + dy[i];
        dfs(nx, ny);
    }
}

//8方位の場合 ver.2
int d[9]={ 0, 1, 0,-1, 1, 1,-1,-1, 0};
int dfs(int x, int y){

    for(int i = 0; i < 8; i++){
        int nx = x + d[i], ny = y + d[i+1];
        dfs(nx, ny);
    }
}

// 8方位の場合 ver.3
int dfs(int x, int y){

    for(int dx = -1; dx <= 1; dx++){
    	for(int dy = -1; dy <= 1; dy++){
        	int nx = x + dx, ny = y + dy;
        	dfs(nx, ny);
        }
    }
}
        

このテクニックは、将棋の桂馬の動きであったとしても、3次元ベクトル空間上の格子点走査であったとしても応用しやすいとても基本的で実用的であると思います。 競技プログラミングを始めて、初めて覚えるテクニックのひとつなのかもしれません。

例題: AOJ0067 The Number of Island

問題リンク

AIZU ONLINE JUDGE #0067 The Number of Island

他の解説サイト

この問題は、与えられた12x12の0(海)または1(陸)のデータから、島がいくつあるかを求める問題です。 島である判定は、1つ以上陸が連結している場合であり、連結とは上下左右に対する四方に隣接する1マスが連続して1である場合です。

つまり、左上から順に探索していき、そのマスが1であった場合に島の個数を1加算した上、 深さ優先探索をしてその島を構成する1をすべて0に塗り替えていくことで、2重加算を防ぐという処理を加えるだけです。

#include <iostream>
using namespace std;

// 12x12の平面図 (mp[][12]は'\0'用)
char mp[12][13];

// 4方位探索用
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { 1, 0, -1, 0 };
// 深さ優先探索
void dfs(int x, int y){
	mp[x][y] = '0';
	for (int i = 0; i < 4; i++){
		int nx = x + dx[i], ny = y + dy[i];
		if (mp[nx][ny] == '1') dfs(nx, ny);
	}
}

int main() {
    // 平面図の1行目の入力がある限りループをまわす
	while (cin >> mp[0]){
        // 平面図の残り2行目~12行目の入力
		for (int i = 1; i < 12; i++){
			cin >> mp[i];
		}

		int islands = 0; // 島の個数を保持
        // 平面図を(0,0)から順に探索
		for (int x = 0; x < 12; x++){
			for (int y = 0; y < 12; y++){
                // 島を発見したら
				if (mp[x][y] == '1'){
					islands++;
					dfs(x, y);
				}
			}
		}
		cout << islands << endl;
	}
}
        

練習問題

参考

Comments

Top