2
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@_HaRLMa_

HaRLMaの精進日記　AtCoder Beginner Contest 213

2
Last updated at Posted at 2025-07-07

はじめに

これはABC212~ABC318を埋めようとしている茶コーダーHaRLMaの日記です．
アルゴリズムの理解，テンプレートの作成，実装力の強化を目的としています．
最初はDifficulty: 0~1999までを埋めていこうと考えています!!
もっと効率の良い方法，別解,解いたほうが良い問題などがあれば教えていただけると幸いです．

ABC213

A - Bitwise Exclusive Or

  • xorの性質
    非負整数Aに対して，A XOR A=0 が成り立ちます．したがって両辺にAをXORすることで、
    $$
    \begin{align}
    A \ XOR \ A \ XOR \ C &= A \ XOR \ B \\
    C &= A \ XOR \ B
    \end{align}
    $$
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using mint = modint998244353;
#define REP(i, a, b) for (ll i = (a); i < (ll)(b); i++)
#define FORE(i,a) for(auto &i:a)
#define ALL(a)  (a).begin(),(a).end()
#define ll  long long
#define str string
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;}
const ll infl = 1LL << 60;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int a,b;
    cin>>a>>b;

    cout<<(a^b);
    /*これでも良き
    REP(c,0,256){
        if((a^c)==b){
          cout<<c;
          return 0;
        }
    }
    */
}

B - Booby Prize

  • sort
  • pair
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using mint = modint998244353;
#define REP(i, a, b) for (ll i = (a); i < (ll)(b); i++)
#define FORE(i,a) for(auto &i:a)
#define ALL(a)  (a).begin(),(a).end()
#define ll  long long
#define str string
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;}
const ll infl = 1LL << 60;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n;
    cin>>n;
    vector<pair<ll,ll>>a(n);
    
    REP(i,0,n){
        ll tmp;cin>>tmp;
        a[i]={tmp,i};
    }
    sort(ALL(a));
    auto tmp=a[n-2];
    cout<<tmp.second+1;
}

C - Reorder Cards

座標圧縮の典型らしい．知らなかった

  • 座標圧縮
  • 重複の削除 X.erase(unique(ALL(X)),X.end());
  • lower_bound,upper_boundなどの二分探索library
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using mint = modint998244353;
#define REP(i, a, b) for (ll i = (a); i < (ll)(b); i++)
#define FORE(i,a) for(auto &i:a)
#define ALL(a)  (a).begin(),(a).end()
#define ll  long long
#define str string
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;}
const ll infl = 1LL << 60;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    ll h,w,n;
    cin>>h>>w>>n;
    vector<ll>a(n),b(n);
    REP(i,0,n)cin>>a[i]>>b[i];

    auto tmp1=a,tmp2=b;//配列のコピー
    sort(ALL(tmp1));
    sort(ALL(tmp2));
    tmp1.erase(unique(ALL(tmp1)),tmp1.end());
    tmp2.erase(unique(ALL(tmp2)),tmp2.end());
    REP(i,0,n){
        a[i] = upper_bound(ALL(tmp1), a[i]) - tmp1.begin();
        b[i] = upper_bound(ALL(tmp2), b[i]) - tmp2.begin();
        cout<<a[i]<<" "<<b[i]<<endl;
    }
}

D - Takahashi Tour

出力するものはオイラーツアーというものらしい．部分木クエリ，パスクエリ，LCA(最近共通祖先)???などが取得でき，とても便利らしい．いつか勉強します...

  • DFS
  • オイラーツアー

追加したテンプレート

  • Graph
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using mint = modint998244353;
using Graph = vector<vector<long long>>;//**********
#define REP(i, a, b) for (ll i = (a); i < (ll)(b); i++)
#define FORE(i,a) for(auto &i:a)
#define ALL(a)  (a).begin(),(a).end()
#define ll  long long
#define str string
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;}
const ll infl = 1LL << 60;

Graph G(210000);
vector<bool>seen(210000);
void dfs(ll now)
{
    cout<<now<<" ";
    seen[now]=true;
    FORE(nxt,G[now]){
        if(!seen[nxt]){
            dfs(nxt);
            cout<<now<<" ";
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n,a,b;
    cin>>n;

    REP(i,0,n-1){
        cin>>a>>b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    REP(i,1,n+1)sort(ALL(G[i]));//REP(i,0,n)でWAくらった．

    dfs(1);
}

E - Stronger Takahashi

ダイクストラ法，01-BFSなどで解ける.
01-BFSのほうが計算量は小さい．

参考

追加したテンプレート

  • const ll dx[] = {0, 1, 0, -1, 1, -1, 1, -1};
  • const ll dy[] = {1, 0, -1, 0, 1, 1, -1, -1};

解答１: ダイクストラ法

  • BFS
  • ダイクストラ法
  • priority_queue
AC:ダイクストラ法
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using mint = modint998244353;
using Graph = vector<vector<long long>>;
#define REP(i, a, b) for (ll i = (a); i < (ll)(b); i++)
#define FORE(i,a) for(auto &i:a)
#define ALL(a)  (a).begin(),(a).end()
#define ll  long long
#define str string
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;}
const ll infl = 1LL << 60;
const ll dx[] = {0, 1, 0, -1, 1, -1, 1, -1};
const ll dy[] = {1, 0, -1, 0, 1, 1, -1, -1};
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int h,w;
    cin>>h>>w;
    vector<str>s(h);
    vector<vector<ll>>ans(h,vector<ll>(w,infl));
    vector<vector<bool>>seen(h,vector<bool>(w,false));
    min_priority_queue<pair<ll,ll>>que;//(殴った回数，一次元にした座標)

    REP(i,0,h)cin>>s[i];
    que.push({0,0});
    ans[0][0]=0;

    while(!que.empty()){//ダイクストラ法
        auto p=que.top();que.pop();

        ll cst=p.first;//コスト(使わない)
        ll y=p.second/w;//値更新時はy座標*w+x座標とするから/wをすることでy座標の値が出てくる．
        ll x=p.second%w;//値更新時はy座標*w+x座標とするから%wをすることでx座標の値が出てくる．

        if(seen[y][x])continue;
        seen[y][x]=true;

        REP(d,0,4){//ただの移動:コスト0
            ll xx=x+dx[d];
            ll yy=y+dy[d];
            if(0<=xx && xx<w && 0<=yy && yy<h){
                if(s[yy][xx]=='.'){
                    if(chmin(ans[yy][xx],ans[y][x])){
                        que.push({ans[yy][xx],yy*w+xx});
                    }
                }
            }
        }

        REP(yy,y-2,y+3){//壁破壊:コスト1
            REP(xx,x-2,x+3){
                if(abs(x-xx)+abs(y-yy)==4)continue;
                if(0<=xx && xx<w && 0<=yy && yy<h){
                    if(chmin(ans[yy][xx],ans[y][x]+1)){
                        que.push({ans[yy][xx],yy*w+xx});
                    }
                }
            }
        }

    }
    cout<<ans[h-1][w-1]<<endl;
}

解答２: 01-BFS

コストが0,1の時のみ使える01-BFS
dequeを使う

  • コスト:0の時，dequeにpush_front
  • コスト:1の時，dequeにpush_back
  • dequeは追加の計算量はO(1)だからはやい❗❗❗
    参考

AC:01-BFS
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using mint = modint998244353;
using Graph = vector<vector<long long>>;
#define REP(i, a, b) for (ll i = (a); i < (ll)(b); i++)
#define FORE(i,a) for(auto &i:a)
#define ALL(a)  (a).begin(),(a).end()
#define ll  long long
#define str string
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;}
const ll infl = 1LL << 60;
const ll dx[] = {0, 1, 0, -1, 1, -1, 1, -1};
const ll dy[] = {1, 0, -1, 0, 1, 1, -1, -1};
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int h,w;
    cin>>h>>w;
    vector<str>s(h);
    vector<vector<ll>>ans(h,vector<ll>(w,infl));
    vector<vector<bool>>seen(h,vector<bool>(w,false));
    deque<pair<ll,ll>>que;//(コスト，一次元にした座標)

    REP(i,0,h)cin>>s[i];
    que.push_front({0,0});
    ans[0][0]=0;

    while(!que.empty()){//ダイクストラ法
        auto p=que.front();que.pop_front();

        ll y=p.first;//y座標
        ll x=p.second;//x座標

        if(seen[y][x])continue;
        seen[y][x]=true;

        REP(d,0,4){
            ll xx=x+dx[d];
            ll yy=y+dy[d];
            if(0<=xx && xx<w && 0<=yy && yy<h){
                if(s[yy][xx]=='.'){
                    if(chmin(ans[yy][xx],ans[y][x])){
                        que.push_front({yy,xx});
                    }
                }
            }
        }

        REP(yy,y-2,y+3){
            REP(xx,x-2,x+3){
                if(abs(x-xx)+abs(y-yy)==4)continue;
                if(0<=xx && xx<w && 0<=yy && yy<h){
                    if(chmin(ans[yy][xx],ans[y][x]+1)){
                        que.push_back({yy,xx});
                    }
                }
            }
        }

    }
    cout<<ans[h-1][w-1]<<endl;
}

F - Common Prefixes 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
using str = string
using pll = pair<ll, ll>;
using mint = modint998244353;
using Graph = vector<vector<ll>>;
#define REP(i, a, b) for (ll i = (a); i < (ll)(b); i++)
#define FORE(i,a) for(auto &i:a)
#define ALL(a)  (a).begin(),(a).end()
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;}
const ll infl = 1LL << 60;
const ll dx[] = {0, 1, 0, -1, 1, -1, 1, -1};
const ll dy[] = {1, 0, -1, 0, 1, 1, -1, -1};

おわりに・まとめ

頭いいやつが多すぎる
あと，座標圧縮テンプレにしてもいいかもなぁ
よかったらフォローしてください．
https://x.com/_HaRLMa_

2
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
2
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?