AtCoder Beginner Contest 097 解説備忘録

16749 ワード
競技プログラミング abc AtCoder C++ ABC097 C++ テキストリンク

前書き

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;
}

あとがき

精進します．