LoginSignup
0
0

More than 1 year has passed since last update.

@swapman

【ABC262 A-D問題を分かりやすく解説 ！C++】

Last updated at Posted at 2022-10-19

みなさんこんにちは。swapmanです。最近記事の投稿をサボってしまっていたので、取り返していきます。ってことでABC262のA-E問題の解説をしていきます。それでは本編です！

【A問題】World Cup

この問題は冷静に考えましょう。4で割った時の余りで場合分けしましょう。余りが0の場合は後2年で開催、余りが1の時は後1年で開催され、余りが2の時はその年に開催されます。余りが3の時だけ気をつけしょう。この時だけ3年後に開催です。コードは以下です。

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


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int y;
    cin >> y;
    int d = y%4;
    if(d == 0) cout << y+2 << endl;
    if(d == 1) cout << y+1 << endl;
    if(d == 2) cout << y << endl;
    if(d == 3) cout << y+3 << endl;
}


【B問題】Triangle (Easier)

陽にグラフを持たないですが、B問題でグラフが出題されるのはインフレの影響を感じますね。グラフは隣接行列で持ってあげればいいです。
あとはfor文を3回回して判定しましょう。コードは以下です。

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


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m;
    cin >> n >> m;
    vector<vector<bool>> to(n, vector<bool>(n));
    rep(i,m) {
        int u,v;
        cin >> u >> v;
        --u;--v;
        to[u][v] = true;
        to[v][u] = true;
    }    
    int ans = 0;
    rep(a,n) {
        for(int b = a+1; b < n; b++) {
            for(int c = b+1; c < n; c++) {
                if(to[a][b] && to[b][c] && to[c][a]) ans++;
            }
        }
    }
    cout << ans << endl;
}


【C問題】Min Max Pair

この問題は少々頭を使います。まず問題文が難しいです。要約すると次の2パターンだけ考えればいいです。
① i < jとなるような(i,j)の組みで、a[i] < a[j]となる、すなわちi == a[i] かつ j == a[j]となる
② i < jとなるような(i,j)の組みで、a[j] < a[i]となる、すなわちi == a[j] かつ j == a[i]となる
①は簡単に求められます。インデックスと値が等しい数字の中から2つを選べばいいです。インデックスと値が等しい集合の大きさをnとすると、①の場合の数は、nC2で求められます。
②の場合は簡単には求まりません。これに関しては工夫した全探索する必要があります。配列の値は重複を含むのでこれを固定します。
配列の値からその値になっているインデックスを逆引きできるものを作っておいて、②のようになるケースだけ数えましょう。逆引き辞書はmapで実装するといいと思います。ここで計算量が心配になる人がいるかもしれませんが、②のケースを数える時にかかる計算量は、mapの計算量を含めてO(NlogN)なので、余裕で間に合います。私のコードだと各ケースについて、一度ずつ重複するので2で割っています。
コードは以下です。

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


ll comb2(ll x) { return x*(x-1)/2; }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n;
    cin >> n;
    vector<ll> a(n);
    rep(i,n) cin >> a[i];    
    //val, ids
    map<ll, vector<ll>> mp;
    rep(i,n) mp[a[i]].push_back(i+1);
    ll cnt = 0;
    rep(i,n) if(i+1 == a[i]) cnt++;
    ll ans = comb2(cnt);
    ll pre = 0;
    for(auto p : mp) {
        ll val = p.fi;
        auto f = p.se;
        for(auto g : f) {
            if(val == g) continue;
            for(ll k : mp[g])  {
                if(val == k) pre++;
            }
        }
    }
    cout << ans + pre/2 << endl;
}


【D問題】I Hate Non-integer Number

特にいい性質もなく、制約的にも全探索して欲しそうなので、DPを疑いましょう。ただDP配列内に値の総和を持つのは無理なので少し工夫が必要ですね。よく考えてみると、欲しい情報というのは今の総和ではなく平均値が整数かどうかだけです。すなわち選んだ数字の個数で数列の総和を割った時の余りが何であるかだけもっておけば良いです。DP配列を次のように持ちましょう。
dp[i][j][k]：i個目まで見て、今既にj個選んでいて、その時の数列の総和を選んだ数字の個数で割った時の余りがkとなるような場合の数
これだとMLEが怖いので、1つ目の要素を消してin-line化しましょう。私のコードだとp -> dpの遷移を考えています。コードの意味を説明したいので、一旦コードを載せます。

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


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i,n) cin >> a[i];
    mint ans;
    rep(m,1,n+1) {//m個選ぶ
        //dp[i][j][k]：今i項目まで見て、既にj個選んでいてその総和を選んだ個数で割った余りがkとなるような場合の数    
        //1つ目の要素を無視してswap
        vector<vector<mint>> dp(n+1, vector<mint>(m));
        dp[0][0] = 1;
        rep(i,n) {
            vector<vector<mint>> p(n+1, vector<mint>(m));
            swap(dp, p);
            rep(j,i+1) {
                rep(k,m) {
                    {//not use
                        dp[j][k] += p[j][k];
                    }
                    {//use
                        dp[j+1][(k+a[i])%m] += p[j][k];
                    }
                }
            }
        }
        ans += dp[m][0];
    }
    cout << ans.val() << endl;
}

まず数列の中からm個選ぶことを考えましょう。今見ている要素を使わない場合はの遷移は以下のようになります。
dp[j][k] += p[j][k];
今見ている要素を使う場合の遷移は、少し考える必要があります。まず使う数字は1つ増えるのでjからj+1に遷移します。i個目の要素をj+1個目として選ぶので、kから(k+a[i])%mに遷移します。これを全て回したあとは、m個選んで余りが0になる、すなわちdp[m][0]をansに足し込んでいけばいいです。in-line化は難しいので、僕もまだ勉強中です。一緒に頑張りましょう。



【終わりに】

このセットは非常にいい問題が多かったと思います。Dで水色が出るようになってきているので、インフレを感じますがアベレージ5完するために日々精進していきます。皆さんも一緒に頑張りましょう！それでは！

0
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
0
0