AtCoder Beginner Contest 293 参加記録 (C++) - 茶処・まっちゃら亭の一休みばしょ

お、久しぶりです。
昨日(2023/03/11)に行われた、Atcoder Beginner Contest 293 の参加記録を、初めて書いてみます。

今回の記録

この参加記録始めたてで申し訳ない(?)ですが、この回で初めて入緑しました。ありがとう...(泣
ABCD4完です。個人的に緑diffのDが解けたので、もう多分この世で一番おもしろいコンテストだと思いました※。

perfは 1027 と、目標にしていた 960 くらいを無事に超えることができました。そしてレート差分は +28 で、緑になりました。(後ほど、入緑記事は書きます)

※個人の意見です。異論は認めません。

ざっくり解説

A

問題はこちら。

普通に $i=0,1,...,N-1$ で $S_{2i-1} ,S_{2i}$ を入れ替えればいいと思います。ここで怖いのが、 $2i$ が文字列 $S$ の長さ $|S|$ を超えることですが、私はなんか通りました (原因は不明)。

Submissionは以下のようになります。

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++) //[0,n)
#define srep(i,a,b) for(int i = a; i <= b; i++) //[a,b]
#define all(A) (A).begin(),(A).end()
#define rall(A) (A).rbegin(),(A).rend()
#define pmt(A) next_permutation(all(A))
using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<ll,ll>;
using pq = priority_queue<ll,vector<ll>,greater<ll>>;
const ll inf = 8e18;
const int iinf = (int)1e9;
const int mod9 = 998244353;
const int mod1 = 1000000007;
struct Edge { int to; ll cost; int from; };
bool compe(const Edge &e,const Edge &e2){ return e.cost < e2.cost; }
template <class T>
using Graph = vector<vector<T>>;
template <class T>
using SGraph = vector<set<T>>;
template <typename T>
ll siz(T& a){return (ll)a.size();}

int main(void){
    string s; cin >> s;
    rep(i,siz(s)) swap(s[2*i+1],s[2*i]);
    cout << s;
}

B

問題はこちら。

まあ、これも問題と同じようにしていけばいいです。私は人 $i$ が既に呼ばれているかどうかを表す配列 seen を使って管理しました。
ただし！！！！ $A_j$ は 1-indexedであることに注意です。過去の私ならそれに気づかなくて殺されていると思います。

Submissionは以下のようになります。(コードの ll siz = ... 以上の行はAとまったく同じなので省略しています)

int main(void){
    int n; cin >> n;
    vector<int> A(n),seen(n,0); rep(i,n) cin >> A[i];
    rep(i,n){
        if(seen[i]) continue;
        seen[A[i]-1] = 1;
    }
    vector<int> ans;
    rep(i,n) if(!seen[i]) ans.push_back(i);

    cout << siz(ans) << endl;
    for(int a : ans) cout << a+1 << " ";
}

C

問題はこちら。

とりかかった当初は、 $h,w$ の長さの配列をそれぞれ作って方向をbit全探索でやろうとしました。
しかしいまいち実装方法がわからなかったので、一回保留。そして再帰DFSの宇宙に旅立ちました。

再帰の方法はけんちょん様の記事をお借りして基づいて頑張ってやりました(語彙力)。
最初は set で保持しようと思いましたが、eraseだと全部消える※ので断念。

次にmultisetを使いました。これもバグり散らかして断念。なんでやろうね...

そして最終的に、誰もが愛する map(連想配列) を使い、個数保持として使い、なんとかACすることができました。
でも40分経過。再帰大好きなのに、これは痛い...と思いました。(もちろんですが、何を使ってもどんだけ時間を使っても解けたときはめちゃくちゃ嬉しいです)

Submissionは以下のようになります。

int ans = 0,h,w;
void dfs(const vector<vector<int>>&A,map<ll,ll> &mp,int ny,int nx){
    if(ny == h-1 && nx == w-1){
        bool ok = 1;
        for(auto& [k,v]:mp){
            if(v != 1) ok = 0;
        }
 
        if(siz(mp) == h+w-1 && ok) ans++;
        return;
    }
 
    if(ny+1 < h){
        mp[A[ny+1][nx]]++;
        dfs(A,mp,ny+1,nx);
        if(--mp[A[ny+1][nx]] == 0) mp.erase(A[ny+1][nx]);
    }
    if(nx+1 < w){
        mp[A[ny][nx+1]]++;
        dfs(A,mp,ny,nx+1);
        if(--mp[A[ny][nx+1]] == 0) mp.erase(A[ny][nx+1]);
    }
}
 
int main(void){
    cin >> h >> w;
    vector<vector<int>> A(h,vector<int>(w));
    rep(i,h) rep(j,w) cin >> A[i][j];
 
    map<ll,ll> mp; mp[A[0][0]]++;
    dfs(A,mp,0,0);
    cout << ans;
}

※例えば集めた整数が $(1,2,3,3,5)$ とすると、set では $(1,2,3,5)$ となります。再帰で、これはもう条件を満たしてないから無理！！となった後に要素を一つ消したいですが、erase 関数を使うと要素そのものが消えてしまいます。
これはどういうことかというと、「 $3$ は $2$ つ持っていたはずなのに、 $2$ つとも消えてしまった」という最悪なことが起こります。こういうときは、デバッグ大臣をして確かめてみるのは、一種のACへの手段だと思われます。

D

問題は(こちら)https://atcoder.jp/contests/abc293/tasks/abc293_d。

最初は、ロープの色と番号で、なんか二次元配列で頑張ろうとしました。しかしそれだと、例えば $3$ 本以上で環状になっていたら...？と思い、やめました。
で、もう一回考えてみます。すると、急にグラフの入力の仕方を思いだしたのです。~~これがグラフに愛されている人の恋愛...！！！~~

「これ、 $2$ 頂点 $(A_i,B_i),(C_i,D_i)$ を相互につなげ合わせたグラフになるのでは...！？」

そう、私の親友、UnionFind くんに呼ばれた気がしたのです。するとこれはロープの色ごとに頂点番号を新たに振り分けるのが、いいと思いました。
そして、 $2N$ 頂点 $M$ 辺の無向グラフとみなし、閉路検出※ $_1$ を行い、連結成分※ $_2$ の個数を数えた結果、ACしたのです。

UnionFind 君に、またもや救われたコンテストと、確信しました。ほんとうにありがとう...！！！！！

Submissionは以下のようになります。

struct UnionFind {
    vector<int> par,rank,siz;
    UnionFind(int n):par(n,-1),rank(n,0),siz(n,1) {}
 
    int root(int x){
        if(par[x] == -1) return x;
        return par[x] = root(par[x]);
    }
 
    bool same(int x,int y){
        int rx = root(x),ry = root(y);
        return rx == ry;
    }
 
    bool unite(int x,int y){
        int rx = root(x),ry = root(y);
        if(rx == ry) return 0;
 
        //union by rank
        if(rank[rx] < rank[ry]) swap(rx,ry);
        par[ry] = rx;
        if(rank[ry] == rank[rx]) rank[rx]++;
        siz[rx] += siz[ry];
        return 1;
    }
 
    int size(int x){ return siz[root(x)]; }
};
 
int main(void){
    int n,m; cin >> n >> m;
    vector<vector<int>> R(n);
    UnionFind uf(2*n);
 
    rep(i,n) uf.unite(2*i,2*i+1);
 
    int ans = 0;
    rep(_,m){
        int a,c; char b,d; cin >> a >> b >> c >> d;
        a--; c--;
        a *= 2,c *= 2;
        if(d == 'R') a++;
        if(c == 'R') c++;
 
        if(uf.root(a) == uf.root(c)) ans++;
        uf.unite(a,c);
 
    }
 
    int cnt = 0;
    rep(i,2*n) if(uf.root(i) == i) cnt++;
    cout << ans << " " << cnt-ans;
    //R:2i+1,L:2i
 
}

※ $_1$ 「ロープが環状になっている」-> 「 $2N$ 頂点のうちいくつかの頂点を結んだ辺でサイクル(閉路)が作られている」だと思いました
※ $_2$ すべてのロープの状態を数え、その「状態数」と「ロープが環状になっている数」の差分が「ロープが環状になっていない数」に等しいためです

※上のコードにおいて、

a--; c--;
a *= 2,c *= 2;
if(d == 'R') a++;
if(c == 'R') c++;

となっているのは、私が勝手に「 $C_i,D_i=$ R のときは頂点 $2A_i+1,2B_i+1$ と、 $C_i,D_i=$ L のときは頂点 $2A_i,2B_i$ とみなしている(かつ 0-indexedに直している)」ためです。

総括

本当にすばらしいコンテストでした。今までのperfの最高は 1300 くらいと劣ってはいますが、最高でした。何より緑diffを本番ACできるとは、本当に思ってもいませんでした。

Epilogue

よし...こっから本番です。記事を、も一回書きます。頑張ります。