AtCoder Beginner Contest 293 の振り返り
- A、B問題を解くことができた
- A問題：空文字列を用意し、その文字列に
] 、
]の順で足していく
- B問題：呼ばれた人を管理する配列を用意し、その配列の要素と1~Nまでの数字を比較する。一致しない数字を保持する配列に格納、要素数とあわせて出力する
- C問題：それまでの経路の数字が重複するかの判定に
setを使うのだろうが探索方法がわからなかった
A問題
atcoder.jp
方針
- 空文字列を用意し、その文字列に] 、 ]の順で足していく
int a = 1;
int b = 2;
using std::swap;
swap(a, b);
std::cout << a << ", " << b << std::endl;
B問題
atcoder.jp
方針
- 呼ばれた人を管理する
setを用意する
人すべてが行動を終えたとき、
までの数と上のsetを比較し、一致しない数字を出力する
実装例
#include<bits/stdc++.h>
using namespace std;
int main () {
int N;
cin >> N;
vector<int> A(N+1);
for (int i = 1; i <= N; i++) cin >> A[i];
set<int> called;
for (int i = 1; i <= N; i++) {
int call = A[i];
if (!called.count(i)) {
called.insert(call);
}
}
vector<int> uncalled;
for (int a = 1; a <= N; a++) {
if (!called.count(a)) uncalled.push_back(a);
}
sort(uncalled.begin(), uncalled.end());
cout << uncalled.size() << endl;
for (auto a : uncalled) {
cout << a << " ";
}
cout << endl;
return 0;
}
C問題
atcoder.jp
- 左上から右下まで移動する経路はたかだか
なので、実行制限時間内に全探索が可能だ
- 再帰を利用する。引数に位置を示す
と今までに通った番号の集合setを渡す
実装例
#include<bits/stdc++.h>
using namespace std;
int h, w, ans;
vector<vector<int>> a;
viod dfs(int i , int j, set<int> s) {
if (s.count(a[i][j])) return;
s.insert(a[i][j]);
if (i == h-1 & j == w-1) {
ans++;
return;
}
if (i+1< w) dfs(i, j+1, s);
if (j+1< h) dfs(i+1, j, s);
}
int main () {
cin >> h >> w;
a = vector(h, vector<int>(w));
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) cin >> a[i][j];
}
dfs(0, 0, set<int>());
cout << ans << endl;
return 0;
}
