AOJ #0067 The Number of Island (島の数)
問題の概要
問題文: AIZU ONLINE JUDGE #0067 The Number of Island (島の数)
0 / 1 で表現される 12 x 12 の領域内に、1つ以上の 1 が隣接して形成される島の数をカウントする問題。 隣接の条件は上下左右いずれかに対して接していることとしている。
解答例
隣接して構成される領域の数を数える典型的な問題と言える。 深さ優先探索により、全地点を探索し 1 が格納されている数をカウントする。この時、一度探索した部分とその隣接した部分を全て 0 に置き換えることでダブルカウントしてしまうのを防ぐことができる。
2次元上のグリッド探索については、以下を参考にして欲しい。 farma-11.hatenablog.com
#include <iostream> using namespace std; char mp[12][13]; // 12x12の平面図 (mp[][12]は'\0'用) // 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'; // 探索済みの部分を '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; } }
以上のソースコードは以下のGithub上にて参照可能です。 github.com
その他の解説サイト
2次元グリッド上探索 まとめ
グリッド上探索の概要
ここでは以下のような4方位もしくは8方位上の探索についてまとめる。
dx[] や dy[] などの配列を用いて各方位1マス先の座標を計算し、順にそのマスにおける処理をしていく。
探索法としては、先に深度の大きい側を優先しているため、深さ優先探索 (DFS: Depth-First Search)を用いていることとなる。
コーディング例
4方位の場合 ver.1
int dx[4]={ 0, 1, 0,-1}; // x軸方向への変位 int dy[4]={ 1, 0,-1, 0}; // y軸方向への変位 int dfs(int x, int 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}; // x軸方向への変位 int dy[8]={ 1, 0,-1, 0, 1,-1, 1,-1}; // y軸方向への変位 int dfs(int x, int y){ // 周囲8方位のマスを探索 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次元ベクトル空間上の格子点走査であったとしても応用しやすいとても基本的で実用的であると思います。 競技プログラミングを始めて、初めて覚えるテクニックのひとつなのかもしれません。
練習問題
Alan Turing's "Computing Machinery and Intelligence"
論文の紹介
論文: A. M. Turing (1950) Computing Machinery and Intelligence. Mind 49: 433-460.
この論文にあるイミテーションゲームは2014年のアメリカドラマ映画のタイトルにもなっています。
イミテーション・ゲーム／エニグマと天才数学者の秘密(字幕版)
- 発売日: 2015/10/02
- メディア: Amazonビデオ
- この商品を含むブログ (3件) を見る
Can machines think? （機械は考えることができるか？）
と作中でチューリング博士が尋ねられた質問は、この論文にとって非常に重要な問いです。 この問いに対して、人間の身体的能力と知的能力の間を区別して論じるため、 「イミテーションゲームをこなせる機械が存在するかどうか」という問いに置き換えて議論している。 イミテーションゲームは、別名「チューリングテスト」とコンピュータが知的かどうかを判定するテストとして有名です。
同様に、論文中では「機械」を「デジタルコンピュータ (digital computer)」に限定して議論している。 このデジタルコンピュータの一種として、チューリングが考案した計算機構モデルである「チューリング機械 (Turing Machine; TM)」が有名です。 （ただし、この論文中ではチューリング機械について言及しているわけではない。）
チューリング博士の考えでは、イミテーションゲームをこなすことのできる機械が実現可能であると述べている。 これは、論文が出版された1950年の技術に限定せず、デジタルコンピュータがその万能性を十分に発揮できるという条件を満たす場合について考察している。 つまり、1950年からみた未来の技術発展も考慮に入れている。
I believe that in about fifty years' time it will be possible, [...] , to make them play the imitation game so well [...]. The original question, "Can machines think?" I believe to be too meaningless to deserve discussion.
（私は約50年後にはイミテーションゲームをこなすことができると信じている。元の「機械は考えることはできるか？」という問いは、議論するに値しない意味のないものになると信じている。）
以上からも、現在の人工知能（Artificial Intelligence; AI）や認知科学といった現在の分野の先駆者であることは見て取れる。 数学的な反論、意識に関する立場からの反論だけではなく、神学的な反論や超能力を信じる立場からの反論など、 当時の人々の様々な反論に対して議論をしていることも特徴である。
そのチューリング博士は論文の最後に、こう締めくくっている。
We can only see a short distance ahead, but we can see plenty there that needs to be done.
（我々は少し先の未来しか見通すことができないが、やるべきことはたくさんあることはわかる）
論文を読んだ感想
2014年に、チューリングテストを合格したというニュースが飛び込んできた。 Turing Test 2014において、スーパーコンピュータ Eugene が、判定者の33％から「人間かコンピュータかを判別出来ない」と評価された。 これは情報工学における歴史的快挙であるが、この合格に異議を唱えている学者もいるとのこと。
論文では、出版年である1950年から50年後、つまり2000年以降（21世紀）について、 平均的な質問者が 5分間やりとりしても 70% 以上の 確率で正しい判断はできなくなると述べている。 チューリング博士が予測した未来には、未だ到達をしているわけではないが、知性を持った機械の登場は今後現れる予兆の一つではないかと思う。
参考文献
AOJ #0033 Ball (玉)
問題の概要
問題文: AIZU ONLINE JUDGE #0033 Ball (玉)
最初に与えられた1数値の入った10個の玉を、2つの筒に順に振り分ける問題。
振り分ける際に、各筒の最上部の玉の値より大きくなければならないとした時、振り分けられるかどうかを判定する。
解答例
1. 貪欲法（グリーディー法; greedy algorithm）を用いた解法
1つ目の玉から順に見ていき、筒B→筒Cの順番で入れられる時点で入れていく方針。 この時、各筒の最上部の値を確認すると、筒Cより筒Bの方が値が常に大きくなる。 どちらの筒にも玉を入れられる時には、常に値の大きい筒Bの方に入れることとなるため、筒Cの値を常に最小の値にし続けることができる。
2. 全探索を用いた解法
筒は2本、玉は10個しかないため全組合せでも 
通りしかない。したがって、全探索を用いても速度的な問題は一切ない。
2.1 深さ優先探索（DFS: Depth-First Search）を用いた解法（再帰関数版）
配列balls[]に入力された玉の順序が格納されており、それを引数idxによって順に指定し、条件を満たす限り再帰を続けている。 引数b,cは筒B,Cそれぞれの最上部の玉の数値を保持しており、それよりballs[idx]が大きければ問題の条件をみたす。 筒BまたはCのいずれかでも成り立つことが分かった場合、trueを返し、どちらも満たさなければfalseを返すようになっている。
2.2 深さ優先探索（DFS: Depth-First Search）を用いた解法（スタック版）
現在の状態として現在取り扱っている玉のidxと、筒B,Cの最上位の玉の値を tuple<int, int, int> より表現している。
それらの状態をスタック stack<tuple<int, int, int> > states に積むことでそれぞれの状態を格納している。
条件を満たす限り筒に玉を入れていき、最後まで入れることができる状態が一つでもあれば探索を終了し、YESを出力している。
また全ての状態を探索し、どの状態についても最後まで入れることができなかった場合はループを終了し、NOを出力している。
2.3 Bitを利用した二分木に対する全列挙を用いる解法
10個の玉を筒BとCへ順番に入れていき、現在の各筒の一番上の玉より値が大きいかどうかを確認するという手法で実装している。 どの玉をどちらに入れるかは変数bitの2進数によるフラグを利用し、0は筒Bを、1は筒Cを意味している。 配列top[]に保持している現在の各筒の一番上の玉の値と比較し、それより小さかった場合は満たさないため次の状態へ移行している。
3. その他の解説サイト
- [貪欲法版] Ball (AOJ 0033) by Respect2D
- [再帰関数版DFS] aoj 0033 - Ball - srupのメモ帳
- [スタック版DFS] AOJ 0033 Ball - 無気力な大学生の痴れ事
- [Bitを利用した二分木に対する全列挙] AOJ 0033 - Ball - ゴリラ系情報系男子高校生の日記
総評
基本的な問題のため、様々な解法がある。 競技プログラミング初心者にとって、うってつけの練習問題だと思う。
以上のソースコードは以下のGithub上にて参照可能です。 https://gist.github.com/farma11/c34af9de7c9a184dc7a0a576455851f1
