HaRLMaの精進日記　AtCoder Beginner Contest 212

Last updated at 2025-07-12Posted at 2025-07-06

はじめに

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

ABC212

A - Alloy

ガチでやるだけ

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
#define REP(i, a, b) for (ll i = (a); i < (ll)(b); i++)
#define ll  long long
#define str string
const ll infl = 1LL << 60;
int main()
{
    int a,b;
    cin>>a>>b;

    if(b==0)cout<<"Gold";
    else if(a==0)cout<<"Silver";
    else cout<<"Alloy";
}

B - Weak Password

ASCIIコード

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
#define REP(i, a, b) for (ll i = (a); i < (ll)(b); i++)
#define ll  long long
#define str string
const ll infl = 1LL << 60;
int main()
{
    str s;
    cin>>s;
    
    bool fg1=true;
    bool fg2=true;
    REP(i,0,3){
        ll x=s[i]-'0';
        ll y=s[i+1]-'0';
        if(x!=y)fg1=false;
        if((x+1)%10!=y)fg2=false;
    }
    
    if(fg1 or fg2)cout<<"Weak";
    else cout<<"Strong";
}

C - Min Difference

この問題は尺取り法，二分探索などいろいろな解法がある．今回は二分探索法

二分探索
尺取り法
lower_bound/upper_boundでもよさそう

追加したテンプレート

chmin
chmax
ALL(a)

二分探索

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
#define REP(i, a, b) for (ll i = (a); i < (ll)(b); i++)
#define ALL(a)  (a).begin(),(a).end()
#define ll  long long
#define str string
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()
{
    int n,m;
    cin>>n>>m;
    vector<ll>a(n),b(m);
    REP(i,0,n)cin>>a[i];
    REP(i,0,m)cin>>b[i];
    
    
    ll ans=infl;
    sort(ALL(a));
    sort(ALL(b));
    
    REP(i,0,n){  
        int ok=m-1,ng=-1;
        while(abs(ok-ng)>1){
            int mid=(ok+ng)/2;
            if(a[i]<=b[mid])ok=mid;
            else ng=mid;
        }
        if(ok!=m)chmin(ans,abs(a[i]-b[ok]));
        if(ng!=-1)chmin(ans,abs(a[i]-b[ng]));
    }
    COUT(ans);
}

尺取り法

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
#define REP(i, a, b) for (ll i = (a); i < (ll)(b); i++)
#define ALL(a)  (a).begin(),(a).end()//**********
#define ll  long long
#define str string
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()
{
    ll n,m;
    cin>>n>>m;
    vector<ll>a(n),b(m);
    REP(i,0,n)cin>>a[i];
    REP(i,0,m)cin>>b[i];

    sort(ALL(a));
    sort(ALL(b));

    ll ans=infl;
    ll cnt=0;
    REP(i,0,n){
        while(cnt<m){
            chmin(ans,abs(a[i]-b[cnt]));
            if(a[i]<=b[cnt])break;
            cnt++;
        }
    }
    COUT(ans);
}

lower_bound

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
#define REP(i, a, b) for (ll i = (a); i < (ll)(b); i++)
#define ALL(a)  (a).begin(),(a).end()
#define ll  long long
#define str string
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()
{
    ll n,m;
    cin>>n>>m;
    vector<ll>a(n),b(m);
    VCIN(a);
    VCIN(b);

    sort(ALL(a));
    sort(ALL(b));

    ll ans=infl;

    REP(i,0,n){
        ll tmp=lower_bound(ALL(b),a[i])-b.begin();
        chmin(ans,abs(a[i]-b[tmp]));
        if(tmp!=0){
            chmin(ans,abs(a[i]-b[tmp-1]));
        }
    }
    COUT(ans);
}

D - Querying Multiset

クエリを処理する問題
priority_queueを知っているか
すべて加える処理の工夫(僕の場合はadd)

追加したテンプレート

min_priority_queue

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
#define REP(i, a, b) for (ll i = (a); i < (ll)(b); i++)
#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()
{
    ll Q;
    cin>>Q;

    ll q;
    min_priority_queue<ll>p;
    ll add=0,x=0;
    REP(i,0,Q){
        cin>>q;
        if(q==1){
            cin>>x;
            p.push(x-add);
        }else if(q==2){
            cin>>x;
            add+=x;
        }else{
            cout<<p.top()+add<<endl;
            p.pop();
        }
    }
}

E - Safety Journey

動的計画法の問題
それの工夫

TLE

day1~kまでのシミュレーション
都市1~n(lst)から都市1~n(nxt)への移動
条件としてlst!=nxt&&橋が壊れていない

追加したテンプレート

ios::sync_with_stdio(false);
cin.tie(nullptr);
この二行を追加すると入出力が速くなるらしい
$$計算量：O(kn^2)$$

TLE

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
#define REP(i, a, b) for (ll i = (a); i < (ll)(b); i++)
#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 MOD=998244353;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    ll n,m,k;
    vector<ll>e[5050];
    ll dp[5050][5050];

    cin>>n>>m>>k;
    REP(i,0,m){
        int u,v;
        cin>>u>>v;
        u--;v--;
        e[u].push_back(v);
        e[v].push_back(u);
    }

    dp[0][0]=1;
    REP(day,0,k){
        REP(lst,0,n){
            REP(nxt,0,n){
                if(lst!=nxt && find(ALL(e[lst]),nxt)==e[lst].end()){
                    dp[day+1][nxt]=(dp[day+1][nxt]+dp[day][lst])%MOD;
                }
            }
        }
    }
    COUT(dp[k][0]);
}

AC

atcoderlibraryのmintを使用 MODをとるのが楽に!!!
dp[day+1][nxt]=移動を始める都市の数totから移動を始める都市nxtだった場合の数を引いていく
e[nxt]にある壊れた橋，つまり渡れない橋をdp[day+1][nxt]から引いていく．

追加したテンプレート

mint
FORE(i,a)

$$計算量：O(k(n+m))$$

#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,m,k;
    vector<ll>e[5050];
    mint dp[5050][5050];
    cin>>n>>m>>k;
    REP(i,0,m){
        int u,v;
        cin>>u>>v;
        u--;v--;
        e[u].push_back(v);
        e[v].push_back(u);
    }

    dp[0][0]=1;
    REP(day,0,k){
        mint tot=0;
        REP(lst,0,n){
            tot+=dp[day][lst];
        }
        REP(nxt,0,n){
            dp[day+1][nxt]=tot-dp[day][nxt];
            FORE(lst,e[nxt])dp[day+1][nxt]-=dp[day][lst];
        }
    }
    cout<<dp[k][0].val()<<endl;
}

F - Greedy Takahashi

追加したテンプレート

ダブリング

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

ダブリング+二分探索

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

dfs

グラフが根付き木の形の利用：dfs

#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;
#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 UNIQ(a) sort(ALL(a));a.erase(unique(ALL(a)),(a).end())
template<typename T> using Graph = vector<vector<T>>;
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};
struct Edge {
    ll weight;
    ll to;
    Edge(ll w, ll t) : weight(w), to(t) {}
};

int main()
{
    ll n,m,q;
    vector<ll>a(m),b(m),s(m),t(m);
    Graph<pll>bus(n+1);
    REP(i,0,n){
        cin>>a[i]>>b[i]>>s[i]>>t[i];
        bus[a[i]].push_back({s[i],i});
    }

    for(auto& p:bus)sort(ALL(p));
    Graph<ll>edge(m);
    vector<bool>isroot(m);
    REP(i,0,m){
        auto itr=lower_bound(ALL(bus[b[i]]),make_pair(t[i],-1));
        if(itr==bus[b[i]].end())isroot[i]==true;
        else edge[(*itr).second].push_back(i);
    }

    vector<ll> x(q),y(q),z(q);
    vector<vector<ll>> ans(q),mem(m);
    REP(i,0,n){
        cin>>x[i]>>y[i]>>z[i];
        auto itr=lower_bound(ALL(bus[y[i]]),make_pair(x[i],-1));
        if(itr==bus[y[i]].end() || z[i] <= (*itr).first) ans[i]={y[i]};
        else mem[(*itr).second].push_back(i);
    }
    
    vector<ll>time,city;
    
    function<void(int)> dfs = [&](int now){
        time.push_back(t[now]);
        time.push_back(s[now]);
        city.push_back(b[now]);
        city.push_back(a[now]);
        for(auto i: mem[now]){
            //ll idx=upper_bound(ALL(time),z[i])-time.begin();
            int idx = lower_bound(time.rbegin(),time.rend(),z[i])-time.rbegin();
            if(idx == time.size()) ans[i] = {*city.begin()};
            else if(idx%2 == 0) ans[i] = {*(city.rbegin()+idx)};
            else ans[i] = {*(city.rbegin()+idx-1),*(city.rbegin()+idx)};
        }
        for(auto next:edge[now]){
            dfs(next);
        }
        time.pop_back();
        time.pop_back();
        city.pop_back();
        city.pop_back();
    };
    REP(i,0,m){
        if(!isroot[i])continue;
        dfs(i);
    }
    
    for(auto p:ans){
        for(auto q:p)cout<<q<<" ";
        cout<<endl;
    }
}

おわりに・まとめ

はまやんさんは神👍👍👍
F問題笑えない...
よかったらフォローしてください．
https://x.com/_HaRLMa_

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up

HaRLMaの精進日記 AtCoder Beginner Contest 212

はじめに

ABC212

A - Alloy

B - Weak Password

C - Min Difference

二分探索

尺取り法

lower_bound

D - Querying Multiset

E - Safety Journey

TLE

AC

F - Greedy Takahashi

ダブリング

ダブリング+二分探索

dfs

おわりに・まとめ

HaRLMaの精進日記　AtCoder Beginner Contest 212