はじめに

これは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_