前書き
AtCoder Beginner Contest 097 を解いてみた．解けなかった問題の備忘録．
B問題
[ポイント]
・for文を2回使うことを恐れすぎて余計に考えてしまったが，for文の終了条件を適切に定めておけば別に良い
・今回は$x \leqq 1000$という条件だったので，$2^9<1000<2^{10}$，$31^{2} < 1000 < 32^2$であるため，以下のように設定した．
以下はACのコード：
main.cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <set>
#include <sstream>
#include <bitset>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
typedef long long ll;
using namespace std;
int main() {
int x;
cin >> x;
int ans=1;
FOR(b, 2, 32){
FOR(p, 2, 10){
if((pow(b, p)>ans)&&(pow(b, p)<=x)){
ans = pow(b, p);
}
}
}
cout << ans << endl;
return 0;
}
C問題
[ポイント]
・またまたfor文を2回使うことを恐れすぎて余計に考えてしまったが，for文の終了条件を適切に定めておけば別に良い．今回は$0 \leqq k \leqq 5$であることを活かす(出力する単語は絶対5文字以下となる)．
・文字列系はvectorを使いこなせれば良さそう．
vectorの使い方はこちらを参照．
以下はACのコード：
main.cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <set>
#include <sstream>
#include <bitset>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
typedef long long ll;
using namespace std;
int main() {
string s;
cin >> s;
int k;
cin >> k;
int n = s.size();
vector<string> vec;
FOR(j, 1, min(n,5)+1){
FOR(i, 0, n-j+1){
vec.push_back(s.substr(i,j));
}
}
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());
cout << vec[k-1] << endl;
return 0;
}
D問題
[ポイント]
・実はグラフの問題．いかにグラフに帰着できたか．
・$x_k$と$y_k$ ($1 \leqq k \leqq M$) を枝でつなぎ，$p_i$と$i$ ($1 \leqq i \leqq N$)が同じ木にあれば良い．
・木の作成の際にUnion-Find木を作成する．
https://qiita.com/ofutonfuton/items/c17dfd33fc542c222396 に詳しく解説した．
以下はACのコード：
main.cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
struct UnionFind {
vector<int> par; // par[i]:iの親の番号 (例) par[3] = 2 : 3の親が2
UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
for(int i = 0; i < N; i++) par[i] = i;
}
int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
if (par[x] == x) return x;
return par[x] = root(par[x]);
}
void unite(int x, int y) { // xとyの木を併合
int rx = root(x); //xの根をrx
int ry = root(y); //yの根をry
if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
}
bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
int rx = root(x);
int ry = root(y);
return rx == ry;
}
};
int main() {
int N, M;
cin >> N >> M;
vector<int> P(N);
for(int i = 0; i < N; i++){
cin >> P[i];
}
UnionFind tree(N);
for(int i = 0; i < M; i++) {
int x, y;
cin >> x >> y;
tree.unite(x-1, y-1); // x-1の木とy-1の木を併合する
}
int cnt = 0;
for(int i = 0; i < N; i++) {
if (tree.same(i, P[i]-1)) { //iとP[i]-1が同じ木に属するなら，カウンタに1追加
cnt++;
}
}
cout << cnt << endl;
return 0;
}
あとがき
精進します．