C - 幅優先探索
コメント歓迎です。
今回から幅優先探索を使います。
初のキューを使った解法です。
方針
この問題では、幅優先探索で座標を移動しながらその座標の手数を記録していきます。
コードの動作は問題のページにある図の通りです。
キューの動作はFIFO(First In, First Out)なので、キューに先に入れた座標から順番に処理が実行されます。
すでに訪問済みの座標は処理をスキップするようにしています。
処理の詳細はコード中のコメントに記載しましたので、それを参照してください。
コード(AC)
#include<iostream> #include<queue> using namespace std; // 宣言 string maze[50]; // 迷路データ int R; // 行数 int C; // 列数 int sy, sx; // スタート地点 int gy, gx; // ゴール地点 int score[50][50]; // 手数 bool visited[50][50]; // 訪問履歴 const int dx[] = {1, -1, 0, 0}; const int dy[] = {0, 0, 1, -1}; // 幅優先探索 void bfs(int i, int j) { // キューを準備 queue<pair<int,int> > Q; // スタート地点のスコアを0にセット score[i][j] = 0; // スタート地点の座標をキューにプッシュ Q.push(make_pair(i, j)); // キューが空になるまで処理を実行 while(!Q.empty()) { // 探索の起点となる座標を記憶してからポップ pair<int,int> q = Q.front(); Q.pop(); int x = q.first; int y = q.second; // 起点を元に座標を移動 for (int k = 0; k < 4; k++) { int nx = x + dx[k]; int ny = y + dy[k]; // 移動先が壁か訪問済みなら処理をスキップ if (maze[nx][ny] == '#' || visited[nx][ny]) { continue; } // 移動先のスコアを起点のスコア+1にする score[nx][ny] = score[x][y] + 1; // 移動先の座標を訪問済みにする visited[nx][ny] = true; // 訪問先の座標をキューにプッシュ(順番が来たら探索の起点になる) Q.push(make_pair(nx, ny)); } } } int main() { // 入力 cin >> R >> C; // 行列数 cin >> sy >> sx; // スタート地点 cin >> gy >> gx; // ゴール地点 // 迷路データ for (int i = 0; i < R; i++ ){ cin >> maze[i]; } // 幅優先探索 bfs(sy - 1, sx - 1); // 出力 cout << score[gy - 1][gx - 1] << endl; return 0; }
B - バウムテスト
コメント歓迎です。
今回も深さ優先探索を使います。
初のグラフ問題でした。
方針
この問題では、深さ優先探索で頂点を移動し、閉路があるかないかを判定します。
具体的には深さ優先探索で枝に沿って移動していき、一度訪問した頂点は訪問済みであることを記録します。
移動した先が探索済みの頂点だった場合に閉路ありと判定します。
閉路がなければ木としてカウントします。
初めてのグラフ問題で、枝情報をたどって移動する部分の実装が難しかったです。
移動するひとつ前の頂点は移動先から除外する必要がある点に注意が必要です。
処理の詳細はコード中のコメントに記載しましたので、それを参照してください。
コード(AC)
#include <iostream> #include <vector> using namespace std; // 訪問履歴を記録するベクター int N; // 頂点 int M; // 枝 int ans = 0; // 木の数 bool flag; // 閉路の有無を判定する変数 // 探索済みの頂点を記録するベクター vector<bool> visited(100, false); // 隣接行列 vector<vector<int> > connect(100,vector<int> (100, 0)); // 深さ優先探索 void dfs(int now, int previous) { // 枝に沿って移動した結果、探索済みの頂点についたら閉路有り if (visited[now]) { flag = false; return; } // 枝に沿って次の頂点へ移動 else { visited[now] = true; for (int next = 0; next < N; next++) { // ひとつ前に探索した頂点は行き先から除外 if (next != previous && connect[now][next] == 1) { dfs(next, now); } } } return; } int main() { // 入力 cin >> N >> M; // 接続関係をベクターに記録 int u, v; for (int i = 0; i < M; i++) { cin >> u >> v; connect[u-1][v-1] = 1; connect[v-1][u-1] = 1; } for (int i = 0; i < N; i++) { // 未訪問の頂点があればそこから探索開始 if (!visited[i]) { flag = true; dfs(i, -1); // 閉路があるとflagがfalseになる if (flag) ans++; } } cout << ans << endl; return 0; }
B - 埋め立て
コメント歓迎です。
深さ優先探索を使った塗りつぶしで解きました。
前回とほぼ同様のコードでACできました。
方針
この問題では、海('x')のうちひとつを埋め立てて陸('o')とし、島が陸続きになるか判定します。
島が陸続きになっているかを判定するために深さ優先探索を使います。
深さ優先探索で新たに埋め立てた陸('o')から島の部分を探索していき、移動するたびそこを('x')に置き換えてきます。
探索が終わったあとすべての位置が'x'となっていれば島は陸続きということになります。
島が陸続きでなければ、探索でたどり着けない'o'が残るからです。
陸続きになっていれば定められた"YES"、なっていなければ"NO"を出力します。
出力の一部が小文字になっていて何度かWAしました…。
処理の詳細はコード中のコメントに記載しましたので、それを参照してください。
コード(AC)
#include <iostream> using namespace std; // 変数定義 string A[10]; // 最大10行 string COPY[10]; // Aのコピー const int dx[] = {1, -1, 0, 0}; const int dy[] = {0, 0, 1, -1}; // 深さ優先探索 陸を'x'に塗り替えていく void dfs(int x, int y) { // 一度通った場所は'x'に置き換える A[x][y] = 'x'; // 上下左右1つずつ移動 for (int i = 0; i < 4; i++) { int nx = x + dx[i]; // 移動先のx座標 int ny = y + dy[i]; // 移動先のy座標 // 進んだ先がエリアからはみ出してたら処理をスキップ if (nx < 0 || nx >= 10 || ny < 0 || ny >= 10) continue; // 進んだ先が海だったら処理をスキップ if (A[nx][ny] == 'x') continue; // 進んだ先が陸だったら深さ優先探索継続 dfs(nx, ny); } // 進める先がなくなったら戻る return; } // すべて10x10のマスがすべて'x'なら島が陸続きと判断 bool judge(){ for(int i = 0; i < 10; i++) { for(int j = 0; j < 10; j++) { if (A[i][j] == 'o') return false; } } return true; } // Aを初期化 void A_init() { for (int i = 0; i < 10; i++) { A[i] = COPY[i]; } } int main() { // 入力 for (int i = 0; i < 10; i++) { cin >> A[i]; COPY[i] = A[i]; // Aの初期状態を保持 } // 島が陸続きか判定する変数 bool ans; // 'x'を'o'に埋め立てた位置をstart地点として深さ優先探索を開始 for (int i = 0; i < 10; i++) { for (int j = 0; j < 10; j++) { if (A[i][j] == 'x') { A[i][j] = 'o'; // 埋め立て dfs(i, j); // 深さ優先探索 ans = judge(); // 島が陸続きになったらループを抜ける if (ans == true) break; A_init(); } if (ans == true) break; } } // 出力 cout << (ans ? "YES" : "NO") << endl; return 0; }
A - 深さ優先探索
コメント歓迎です。
問題名の通り、今回から深さ優先探索にチャレンジします。
再帰関数の動きに慣れるまで苦戦しました。
方針
この問題では、深さ優先探索ができる再帰関数を作ることさえできれば、解答できると思います。
しかし、最初はそこに苦戦するわけです。
どうやってGOALを探していくかについては、AtCoderのchokudaiさんのスライドが参考になります。
(問題ページにある解説と同じものです。)
www.slideshare.net
今回は再帰関数のイメージがない人に向けて書いてみようと思います。
再帰関数とは、関数の処理の中で自分自身を呼び出し再帰的な動作をする関数です。
マトリョーシカ的なイメージです。
自分自身を呼び出しているので永遠に処理が終わらないのではと思われるかもしれませんが、
関数の処理の中にif文など条件を付けることで呼び出しを終えられます。
今回私が書いた関数dfs(Depth First Search)はtrueかfalseを戻り値とします。
条件により、最後に呼び出した関数dfsの戻り値が決まると芋づる式に今までに呼び出した関数dfsの戻り値も決まっていきます。
大きなものから順番に開けたマトリョーシカを、今度は小さいものから元に戻していくイメージです。
最初に呼び出した関数dfsの戻り値がGOALにたどり着けたかの答えになります。
イメージが掴めたら考えてみてほしいのですが、ちなみに芋づる式という表現は正確ではありません。
道が2つに分岐したときをマトリョーシカで言い換えるならば、開けたら小さいマトリョーシカが2個入っているということになるからです。
流れ的には片方のマトリョーシカを開けきった後、戻し始めて2つ入っている元の状態に戻ったらもう片方を開け始める感じです。
ちょっとマトリョーシカの例が良くなかった気がしますが理解の助けになれば幸いです。
処理の詳細はコード中のコメントに記載しましたので、それを参照してください。
コード(AC)
#include <iostream> using namespace std; // 変数定義 int H, W; string c[500]; // 最大500行 const int dh[] = {1, -1, 0, 0}; const int dw[] = {0, 0, 1, -1}; int count = 0; // 深さ優先探索 bool dfs(int h, int w) { // goalを見つけたらtrueを返す if (c[h][w] == 'g') return true; // 一度通った場所は'#'に置き換えてしまう c[h][w] = '#'; // 上下左右1つずつ移動 for (int i = 0; i < 4; i++) { int nh = h + dh[i]; // 移動先のh座標 int nw = w + dw[i]; // 移動先のw座標 // 進んだ先が街からはみ出してたら処理をスキップ if (nh < 0 || nh >= H || nw < 0 || nw >= W) continue; // 進んだ先が塀だったら処理をスキップ if (c[nh][nw] == '#') continue; // goalまでたどり着いた場合、呼び出したすべて関数dfsがtrueを返す if (dfs(nh, nw)) return true; } // goalまでたどり着けなかった場合は呼び出した全ての関数dfsがfalseを返す return false; } int main() { // 入力 cin >> H >> W; for (int i = 0; i < H; i++) { cin >> c[i]; } // goalにたどり着けたか判定する変数 bool judge; // start地点を探して深さ優先探索を開始 for (int i = 0; i < H; i++) { for (int j = 0; j < W; j++) { if (c[i][j] == 's') judge = dfs(i, j); } } // 出力 cout << (judge ? "Yes" : "No") << endl; return 0; }
D - 派閥
コメント歓迎です。
今回もビット全探索を使います。
方針
この問題では、派閥を作れる組み合わせをどのようにして求めるかがポイントとなります。
今回は最大人数が12人であり、全員に対して派閥に入るか入らないかの2択をビット全探索します。
そのため、最大でも通りの計算量で済みます。
今回新しく2次元配列を使いました。(ベクターの2次元配列は宣言の文法がわかりづらいですね。)
入力の情報から知り合いの場合、「1番さんから見て2番さんは知り合い」で、
「2番さんから見て1番さんも知り合い」といった形で情報をベクターに記録しておきます。
派閥が作れる条件としては、派閥に入れようとしている人(ビット全探索の"1")全員が、知り合いであればOKです。
逆に考えると、派閥に入れようとしている人で知り合いでない組み合わせがひとつでもあれば、
そのメンバーでは派閥は作れないことになります。
下のコードでは、そのような実装になっています。
コード(AC)
#include <iostream> #include <vector> #include <bitset> using namespace std; int main(){ // 入力 int N, M; cin >> N >> M; // 2次元ベクター vector<vector<int> > relation(N, vector<int> (N, 0)); // 知り合い関係を配列に記録 int x, y; for (int i = 0; i < M; i++) { cin >> x >> y; relation[x-1][y-1] = relation[y-1][x-1] = 1; } // 答えの最小値は1 int ans = 1; // ビット全探索 2^N for (int mask = 0; mask < (1 << N); mask++) { int factions = bitset<32>(mask).count(); // 派閥メンバー数が解答として保持している値よりも少ない場合は処理をスキップ if (factions < ans) { continue; } // そのメンバーで派閥が組めるか判定 bool judge = true; for (int i = 0; i < N; i++) { for (int j = 0; j < i; j++) { // 選択したメンバーで知り合いでない場合があったらNG判定 if (mask >> i & mask >> j & 1 && !relation[i][j]) { judge = false; } } } // 条件を満たしたらansに代入 if (judge) { ans = factions; } } // 出力 cout << ans << endl; }
C - All Green
コメント歓迎です。
今回もビット全探索を使います。
方針
この問題では、同じ得点の問題を全問解くとボーナス点が貰えるところがポイントになります。
合計点が目標値以上になる最小の解答数を求め、出力します。
ビット全探索を使い、「どの得点のボーナスをもらうか」を全探索します。
もちろん、ボーナスを1つももらわない場合が最小回答数になる場合もあります。
その場合は、ビット列のうち"1"がボーナスをもらう得点と定義すると、オールゼロで表現できます。
また、ボーナスをもらっても目標値に届かないことが予想できます。
その場合は他の問題を追加で解く必要がありますが、
解く問題は1問あたりの得点が一番高いものを解くのが最適解になります。
そのため、1問あたりの得点が1番高いもの以外を追加で解くことについては考える必要がありません。
追加で解く問題数を計算する式は、割り算の切り上げをしています。
便利なテクニックだと思いますので、見たことがなければ実際に数字を当てはめて考えてみてください。
コード(AC)
#include <iostream> #include <vector> using namespace std; int main(){ // 入力 int D, G; cin >> D >> G; vector<int> p(D, 0); vector<int> c(D, 0); for (int i = 0; i < D; i++) { cin >> p[i]; cin >> c[i]; } int ans = 1001; // 問題数は最大10 * 100 // ビット全探索 2^D // ある配点の問題を全問解く // 全問解く配点をビット探索 "1":その配点の問題を全問解く for (int mask = 0; mask < (1 << D); mask++) { int sum = 0; int solve_count = 0; // 解いた問題数 int rest_max = -1; // 解かない問題で最も配点が高い問題 for (int i = 0; i < D; i++) { if (mask >> i & 1) { sum += 100 * (i + 1) * p[i] + c[i]; // 全問解答＋ボーナスの点数 solve_count += p[i]; } else { rest_max = i; // 解かない問題で最も配点が高い問題を保持 } } // 合計値が目標値以下の場合 if (sum < G) { int tmp = 100 * (rest_max + 1); // 追加解答する問題の配点 int shortage = (G - sum + tmp -1) / tmp; // 追加解答する問題数(不足分) // 不足分がその配点の問題数以下なら処理を継続 if (shortage >= p[rest_max]) { continue; } solve_count += shortage; // 解答した問題数を更新 } ans = min(ans, solve_count); // 解答数が過去最小なら更新 } // 出力 cout << ans << endl; }
A - Thumbnail
コメント歓迎です。
第5回 ドワンゴからの挑戦状 予選の問題です。
方針
まず整数列aの平均値を求めます。
求めた平均値と整数列の値の差をひとつずつ計算し、差が最小のときのフレーム番号を出力します。
整数列の0番から順に差を評価していき、現時点での最小値よりも小さければ最小値を更新します。
最小値と同じ差になる場合でも、0番目から評価していくので最初に最小値となったフレーム番号を保持できます。
コード(AC)
#include <iostream> #include <vector> #include <cmath> using namespace std; int main(){ // 入力 int N; cin >> N; vector<double> a(N, 0); for (int i = 0; i < N; i++) { cin >> a[i]; } double sum = 0; // 要素の合計値 double ave = 0; // 要素の平均値 double tmp = 101; // 平均値との差を比較するための変数 int ans = 0; // 合計値の計算 for (int i = 0; i < N; i++) { sum += a[i]; } // 平均値の計算 ave = sum / N; // 全探索 for (int j = 0; j < N; j++) { // 現時点での最小値よりも小さい場合 if (abs(a[j] - ave) < tmp) { tmp = abs(a[j] - ave); // 最小値を更新 ans = j; // 更新したらそのフレーム番号を記録 } } // 出力 cout << ans << endl; }
