【ABC259のA-E問題をわかりやすく解説！ C++】

皆様こんにちは。swapmanです。最近実験が忙しくてレポートに追われていたのですが、ようやくひと段落したので投稿を再開したいと思います。お待たせしていた方々、大変申し訳ございませんでした。謝罪はここまでにして早速本編に入ります！それではいきましょう。あと最近マクロを変えました。CodeForcesに対応したものにしたので、若干見づらかったらすみません。snukeさんのを参考にしました。

ABC259のリンク：https://atcoder.jp/contests/abc259

【A問題】Growth Record

言われたことをやりましょう。MがXからNの間に存在しているならTを出力。そうでないならDずつ減らして出力するだけです。コードは以下です。

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using namespace std;
using mint = modint998244353;
using C = complex<double>;
const int mod = 998244353;
const long long LINF = 1001002003004005006;
const int INF = 1001001001;
const double PI = acos(-1);
const double EPS = 1e-10;
const int di[4] = {-1,0,1,0};
const int dj[4] = {0,-1,0,1};
const int dx[8] = {1,1,1,0,0,-1,-1,-1};
const int dy[8] = {1,0,-1,1,-1,1,0,-1};
# define sz(x) (int)(x).size()
# define rsz(x,n) x.resize(n)
# define ret(x) {cout << (x) << endl; return;}
# define ll long long
# define fi first
# define se second
# define GET_MACRO(_1, _2, _3, NAME, ...) NAME
# define _rep(i, n) _rep2(i, 0, n)
# define _rep2(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
# define rep(...) GET_MACRO(__VA_ARGS__, _rep2, _rep)(__VA_ARGS__)
# define srep(i, a, b) for(int i = a; i <= b; ++i)
# define all(obj) (obj).begin(), (obj).end()
# define rall(obj) (obj).rbegin(), (obj).rend()
# define _GLIBCXX_DEBUG
inline void YesNo(bool f) { std::cout << (f? "Yes": "No") << std::endl; }
# define Pll pair<ll, ll>
# define P pair<int,int>
# define bit(x,i) (((x) >> (i)) & 1)
# define equals(a, b) (fabs((a) - (b)) < EPS) // 誤差を考慮した同値判定
template<class T>bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }
template<typename T>istream& operator>>(istream&i,vector<T>&v){rep(j,v.size())i>>v[j];return i;}
template<typename T>string join(vector<T>&v){stringstream s;rep(i,v.size())s<<' '<<v[i];return s.str().substr(1);}
template<typename T>ostream& operator<<(ostream&o,vector<T>&v){if(v.size())o<<join(v);return o;}
template<typename T>ostream& operator<<(ostream&o,vector<vector<T>>&vv){if(vv.size())o<<join(vv);return o;}


struct Solver {
  void solve() {
    int n,m,x,t,d;
    cin >> n >> m >> x >> t >> d;
    if(x <= m and m <= n) ret(t);
    int dif = (x-m)*d;
    cout << t-dif << endl;
  }
};

int main() {
    int ts = 1;
    // scanf("%d", &ts);
    rep(ti,ts) {
        Solver solver;
        solver.solve();
    }
    return 0;
}

【B問題】Counterclockwise Rotation

B問題にしては難しいと思いますが、複素数で扱うのがオススメです。ここでは詳しくは説明しませんがベクトルの回転として捉えるのが一番すっきり解くことができると思います。コードは以下です。

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using namespace std;
using mint = modint998244353;
using C = complex<double>;
const int mod = 998244353;
const long long LINF = 1001002003004005006;
const int INF = 1001001001;
const double PI = acos(-1);
const double EPS = 1e-10;
const int di[4] = {-1,0,1,0};
const int dj[4] = {0,-1,0,1};
const int dx[8] = {1,1,1,0,0,-1,-1,-1};
const int dy[8] = {1,0,-1,1,-1,1,0,-1};
# define sz(x) (int)(x).size()
# define rsz(x,n) x.resize(n)
# define ret(x) {cout << (x) << endl; return;}
# define ll long long
# define fi first
# define se second
# define GET_MACRO(_1, _2, _3, NAME, ...) NAME
# define _rep(i, n) _rep2(i, 0, n)
# define _rep2(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
# define rep(...) GET_MACRO(__VA_ARGS__, _rep2, _rep)(__VA_ARGS__)
# define srep(i, a, b) for(int i = a; i <= b; ++i)
# define all(obj) (obj).begin(), (obj).end()
# define rall(obj) (obj).rbegin(), (obj).rend()
# define _GLIBCXX_DEBUG
inline void YesNo(bool f) { std::cout << (f? "Yes": "No") << std::endl; }
# define Pll pair<ll, ll>
# define P pair<int,int>
# define bit(x,i) (((x) >> (i)) & 1)
# define equals(a, b) (fabs((a) - (b)) < EPS) // 誤差を考慮した同値判定
template<class T>bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }
template<typename T>istream& operator>>(istream&i,vector<T>&v){rep(j,v.size())i>>v[j];return i;}
template<typename T>string join(vector<T>&v){stringstream s;rep(i,v.size())s<<' '<<v[i];return s.str().substr(1);}
template<typename T>ostream& operator<<(ostream&o,vector<T>&v){if(v.size())o<<join(v);return o;}
template<typename T>ostream& operator<<(ostream&o,vector<vector<T>>&vv){if(vv.size())o<<join(vv);return o;}

C input_complex() {
    double x, y;
    cin >> x >> y;
    return C(x,y);
}

struct Solver {
  void solve() {
    C ab = input_complex();
    double d;
    cin >> d;
    double deg = d*PI/180.0;
    C rot = C(cos(deg), sin(deg));
    C res = rot*ab;
    printf("%.10lf %.10lf\n", res.real(), res.imag());    
  }
};

int main() {
    int ts = 1;
    // scanf("%d", &ts);
    rep(ti,ts) {
        Solver solver;
        solver.solve();
    }
    return 0;
}

【C問題】XX to XXX

典型的なランレングス圧縮の問題ですが、コーナーケースを踏まないように気をつけましょう。とは言っても最後のサンプルがコーナーケースなのでこのサンプルのおかげでWAを踏まないで済んだ人は多いはずです。ランレングス圧縮についてはここでは既知のものとして説明します。知らない人は一度どこかで学んでからここに帰ってきてください！ランレングス圧縮して文字が異なる場合や作成した文字列集合の長さが違う場合は即Noと出力すればいいです。またSに文字を挿入してTに合わせたいので、最初からSの方が文字が多い場合やSの方が少なくても1文字しかない場合は挿入できないのでNoと言えばいいです。それ以外はYesと言いましょう。コードは以下です。

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using namespace std;
using mint = modint998244353;
using C = complex<double>;
const int mod = 998244353;
const long long LINF = 1001002003004005006;
const int INF = 1001001001;
const double PI = acos(-1);
const double EPS = 1e-10;
const int di[4] = {-1,0,1,0};
const int dj[4] = {0,-1,0,1};
const int dx[8] = {1,1,1,0,0,-1,-1,-1};
const int dy[8] = {1,0,-1,1,-1,1,0,-1};
# define sz(x) (int)(x).size()
# define rsz(x,n) x.resize(n)
# define ret(x) {cout << (x) << endl; return;}
# define ll long long
# define fi first
# define se second
# define GET_MACRO(_1, _2, _3, NAME, ...) NAME
# define _rep(i, n) _rep2(i, 0, n)
# define _rep2(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
# define rep(...) GET_MACRO(__VA_ARGS__, _rep2, _rep)(__VA_ARGS__)
# define srep(i, a, b) for(int i = a; i <= b; ++i)
# define all(obj) (obj).begin(), (obj).end()
# define rall(obj) (obj).rbegin(), (obj).rend()
# define _GLIBCXX_DEBUG
inline void YesNo(bool f) { std::cout << (f? "Yes": "No") << std::endl; }
# define Pll pair<ll, ll>
# define P pair<int,int>
# define bit(x,i) (((x) >> (i)) & 1)
# define equals(a, b) (fabs((a) - (b)) < EPS) // 誤差を考慮した同値判定
template<class T>bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }
template<typename T>istream& operator>>(istream&i,vector<T>&v){rep(j,v.size())i>>v[j];return i;}
template<typename T>string join(vector<T>&v){stringstream s;rep(i,v.size())s<<' '<<v[i];return s.str().substr(1);}
template<typename T>ostream& operator<<(ostream&o,vector<T>&v){if(v.size())o<<join(v);return o;}
template<typename T>ostream& operator<<(ostream&o,vector<vector<T>>&vv){if(vv.size())o<<join(vv);return o;}


vector<pair<char, int>> runLengthEncoding(string s) {
    int n = s.length();
    vector<pair<char, int>> res;
    char pre = s[0];
    int cnt = 1;
    rep(i, 1, n) {
        if (pre != s[i]) {
            res.push_back({ pre, cnt });
            pre = s[i];
            cnt = 1;
        }
        else cnt++;
    }

    res.push_back({ pre, cnt });
    return res;
}

struct Solver {
  void solve() {
    string s,t;
    cin >> s >> t;
    auto vs = runLengthEncoding(s), vt = runLengthEncoding(t);
    int n = sz(vs), m = sz(vt);
    if(n != m) ret("No");
    rep(i,n) {
        auto [c1, ns] = vs[i];
        auto [c2, nt] = vt[i];
        if(c1 != c2 || ns > nt) ret("No");
        if(c1 == c2 && ns < nt) {
            if(ns == 1) ret("No");
        }
    } 
    cout << "Yes" << endl;
  }
};

int main() {
    int ts = 1;
    // scanf("%d", &ts);
    rep(ti,ts) {
        Solver solver;
        solver.solve();
    }
    return 0;
}

【D問題】Circumferences

典型的なUnion-Findの問題ですが実装が少し面倒です。ユークリッド距離を扱うときは少数で扱うことは避けて二乗した状態で扱うというのは割とハマりやすいポイントではあるので気をつけましょう。円が接したり交点を持つときの条件はゆっくり神に書いて考えればできると思います。ググっても出てきそうなのでどうしてもわからないなら一度数学を勉強しましょう。やっていることは(si,sj)と(ti,tj)がどの円上に存在しているかを求めて、O(N^2）かけて全ての縁の組み合わせをみて、交点を持ったり接しているかを確認しmergeしています。
ということでコードは以下です。

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using namespace std;
using mint = modint998244353;
using C = complex<double>;
const int mod = 998244353;
const long long LINF = 1001002003004005006;
const int INF = 1001001001;
const double PI = acos(-1);
const double EPS = 1e-10;
const int di[4] = {-1,0,1,0};
const int dj[4] = {0,-1,0,1};
const int dx[8] = {1,1,1,0,0,-1,-1,-1};
const int dy[8] = {1,0,-1,1,-1,1,0,-1};
# define sz(x) (int)(x).size()
# define rsz(x,n) x.resize(n)
# define ret(x) {cout << (x) << endl; return;}
# define ll long long
# define fi first
# define se second
# define GET_MACRO(_1, _2, _3, NAME, ...) NAME
# define _rep(i, n) _rep2(i, 0, n)
# define _rep2(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
# define rep(...) GET_MACRO(__VA_ARGS__, _rep2, _rep)(__VA_ARGS__)
# define srep(i, a, b) for(int i = a; i <= b; ++i)
# define all(obj) (obj).begin(), (obj).end()
# define rall(obj) (obj).rbegin(), (obj).rend()
# define _GLIBCXX_DEBUG
inline void YesNo(bool f) { std::cout << (f? "Yes": "No") << std::endl; }
# define Pll pair<ll, ll>
# define P pair<int,int>
# define bit(x,i) (((x) >> (i)) & 1)
# define equals(a, b) (fabs((a) - (b)) < EPS) // 誤差を考慮した同値判定
template<class T>bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }
template<typename T>istream& operator>>(istream&i,vector<T>&v){rep(j,v.size())i>>v[j];return i;}
template<typename T>string join(vector<T>&v){stringstream s;rep(i,v.size())s<<' '<<v[i];return s.str().substr(1);}
template<typename T>ostream& operator<<(ostream&o,vector<T>&v){if(v.size())o<<join(v);return o;}
template<typename T>ostream& operator<<(ostream&o,vector<vector<T>>&vv){if(vv.size())o<<join(vv);return o;}


struct Solver {
  void solve() {
    ll n;
    cin >> n;
    ll sx, sy, tx,ty;
    cin >> sx >> sy >> tx >> ty;
    vector<ll> x(n), y(n), r(n);
    rep(i,n) cin >> x[i] >> y[i] >> r[i];
    int si = -1, ti = -1;
    rep(i,n) {
        if((sx-x[i])*(sx-x[i])+(sy-y[i])*(sy-y[i]) == r[i]*r[i]) si = i;
        if((tx-x[i])*(tx-x[i])+(ty-y[i])*(ty-y[i]) == r[i]*r[i]) ti = i;
    }
    dsu uf(n);
    rep(i,n) {
        rep(j,i+1,n) {
            ll dx = x[i]-x[j];
            ll dy = y[i]-y[j];
            ll R = dx*dx+dy*dy;
            ll rsum = r[i]+r[j];
            ll rdif = r[i]-r[j];
            if(rdif*rdif <= R && R <= rsum*rsum) uf.merge(i,j);
        }
    }
    YesNo(uf.same(si,ti));
  }
};

int main() {
    int ts = 1;
    // scanf("%d", &ts);
    rep(ti,ts) {
        Solver solver;
        solver.solve();
    }
    return 0;
}

【E問題】LCM on Whiteboard

この辺から難しいですね。結論から言うとLCMは各因数のmax個乗の積で表すことができ、max個持っていない因数を削除してもLCMに変化はありません。また、max個のものを消したとしても他の数字によってそれがカバーされているならその場合も変化はありません。すなわち各因数を見たときにその数字を消すことでどれかの因数のmax個が変わる、すなわちmax個の因数を保持している数字が1種類しかない場合だけLCMが変わります。でもこれだけではダメで、どの因数を消してもLCMが変わる場合は、最後にインクリメント(このインクリメントはどれも消さなかったときのLCMの分です。)してはダメです。どれを消してもLCMが変わるのはans == nかどうかで判定できます。コードは以下です。

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using namespace std;
using mint = modint998244353;
using C = complex<double>;
const int mod = 998244353;
const long long LINF = 1001002003004005006;
const int INF = 1001001001;
const double PI = acos(-1);
const double EPS = 1e-10;
const int di[4] = {-1,0,1,0};
const int dj[4] = {0,-1,0,1};
const int dx[8] = {1,1,1,0,0,-1,-1,-1};
const int dy[8] = {1,0,-1,1,-1,1,0,-1};
# define sz(x) (int)(x).size()
# define rsz(x,n) x.resize(n)
# define ret(x) {cout << (x) << endl; return;}
# define ll long long
# define fi first
# define se second
# define GET_MACRO(_1, _2, _3, NAME, ...) NAME
# define _rep(i, n) _rep2(i, 0, n)
# define _rep2(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
# define rep(...) GET_MACRO(__VA_ARGS__, _rep2, _rep)(__VA_ARGS__)
# define srep(i, a, b) for(int i = a; i <= b; ++i)
# define all(obj) (obj).begin(), (obj).end()
# define rall(obj) (obj).rbegin(), (obj).rend()
# define _GLIBCXX_DEBUG
inline void YesNo(bool f) { std::cout << (f? "Yes": "No") << std::endl; }
# define Pll pair<ll, ll>
# define P pair<int,int>
# define bit(x,i) (((x) >> (i)) & 1)
# define equals(a, b) (fabs((a) - (b)) < EPS) // 誤差を考慮した同値判定
template<class T>bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }
template<typename T>istream& operator>>(istream&i,vector<T>&v){rep(j,v.size())i>>v[j];return i;}
template<typename T>string join(vector<T>&v){stringstream s;rep(i,v.size())s<<' '<<v[i];return s.str().substr(1);}
template<typename T>ostream& operator<<(ostream&o,vector<T>&v){if(v.size())o<<join(v);return o;}
template<typename T>ostream& operator<<(ostream&o,vector<vector<T>>&vv){if(vv.size())o<<join(vv);return o;}


struct Solver {
  void solve() {
    int n;
    cin >> n;
    vector<vector<Pll>> pe(n);
    rep(i,n) {
        ll m;
        cin >> m;
        rep(j,m) {
            ll p,e;
            cin >> p >> e;
            pe[i].push_back({p,e});
        }
    }
    map<ll,ll> maxs;
    rep(i,n) for(auto [p,e] : pe[i]) chmax(maxs[p], e);
    map<ll,ll> cnt;
    rep(i,n)for(auto [p,e] : pe[i]) if(maxs[p] == e) cnt[p]++;
    int ans = 0;
    rep(i,n) {
        bool fl = false;
        for(auto [p,e]: pe[i]) if(maxs[p] == e && cnt[p] == 1) fl = true;;
        
        if(fl) ans++;
    }
    if(ans < n) ans++;
    cout << ans << endl;
  }
};

int main() {
    int ts = 1;
    // scanf("%d", &ts);
    rep(ti,ts) {
        Solver solver;
        solver.solve();
    }
    return 0;
}

【終わりに】

久しぶりにやった割には良くできたと思います。F問題の解説もあげるのでそちらも是非！今日はこの辺で！