LoginSignup
0
0

More than 1 year has passed since last update.

@swapman

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

Last updated at Posted at 2022-10-09

こんにちは。swapmanです。第4回swapコンで取り扱ったABC268のA-D問題の解説を書いていきます。
僕は毎日夜21時からswapコンというバーチャルコンテストを開いており、そこで解けた問題と、解けなかった問題を分けて解説を書いています！swapコンへの参加もぜひよろしくお願いいたします！みんなで強くなりましょう！
それでは、本編です！



【A問題】Five Integers

少しオーバーキルな気がしますが、mapを用いて数字の種類を管理しましょう。コードは以下です。

#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 yes {puts("Yes"); return;}
# define no {puts("No"); return;}
# define dame {puts("-1"); return;}
# define yn {puts('Yes');} else{puts('No');}
# define ret(x) {cout << (x) << endl; return 0;}
# define ll long long
# define fi first
# define se second
# define vi vector<int>
# define vl vector<long long>
# define vs vector<string>
# define vb vector<bool>
# define vvi vector<vector<int>>
# define vvl vector<vector<long long>>
# define vvb vector<vector<bool>>
# define vpi vector<pair<int, int>>
# define vpl vector<pair<ll, ll>>
# define pb push_back
# define ps push
# define eb emplace_back
# define em emplace
# define pob pop_back
# define rep(i,n) for(int i = 0; i < n; i++)
# 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
# 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);
    vector<int> a(5);
    map<int,int> mp;
    for(int i = 0; i < 5 ; i++) {
        cin >> a[i];
        mp[a[i]]++;
    }
    cout << mp.size() << endl;
}


【B問題】Prefix?

substrを知っているかどうかで大きく難易度が変わりそうですね。知らない人はドキュメントを読むなりしてください。SがTの接頭辞かどうかを判定することを考えるなら、Sの長さがTの長さより長い場合は明らかにNoです。この場合はif文か何かで弾いておくといいでしょう。ここでSの長さをnとします。substrを使ってTの先頭n文字を取ってきて、それがSと全く同じ場合は明らかにYes、そうでない場合はNoと出力しましょう。コードは以下です

#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 yes {puts("Yes"); return;}
# define no {puts("No"); return;}
# define dame {puts("-1"); return;}
# define yn {puts('Yes');} else{puts('No');}
# define ret(x) {cout << (x) << endl; return 0;}
# define ll long long
# define fi first
# define se second
# define vi vector<int>
# define vl vector<long long>
# define vs vector<string>
# define vb vector<bool>
# define vvi vector<vector<int>>
# define vvl vector<vector<long long>>
# define vvb vector<vector<bool>>
# define vpi vector<pair<int, int>>
# define vpl vector<pair<ll, ll>>
# define pb push_back
# define ps push
# define eb emplace_back
# define em emplace
# define pob pop_back
# define rep(i,n) for(int i = 0; i < n; i++)
# 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
# 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);
    string s,t;
    cin >> s >> t;
    if(sz(s) > sz(t)) {
        cout << "No" << endl;
        return 0;
    }    
    int n = sz(s);
    string u = t.substr(0,n);
    cout << (u == s ? "Yes" : "No") << endl;
}


【C問題 Chinese Restaurant】

この問題は発想の転換が必要になります。普通なら回す回数を試すと思いますが、それをするとO(N^2)になってしまい、間に合いません。ここで発想を転換して、各料理をどれだけ回せば満足するのかを考えます。これは各料理が最初に存在する場所と、人iを満足させることができる場所との距離、すなわち何回回転させればいいのかをmapか何かで管理するのはO(1)とかO(logN)とかその辺でできるので、十分高速にこの問題を解くことができました。配列外参照だけは気をつけましょう。余りの性質を理解していればそこまで苦労しないと思います。コードは以下です。

#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 yes {puts("Yes"); return;}
# define no {puts("No"); return;}
# define dame {puts("-1"); return;}
# define yn {puts('Yes');} else{puts('No');}
# define ret(x) {cout << (x) << endl; return 0;}
# define ll long long
# define fi first
# define se second
# define vi vector<int>
# define vl vector<long long>
# define vs vector<string>
# define vb vector<bool>
# define vvi vector<vector<int>>
# define vvl vector<vector<long long>>
# define vvb vector<vector<bool>>
# define vpi vector<pair<int, int>>
# define vpl vector<pair<ll, ll>>
# define pb push_back
# define ps push
# define eb emplace_back
# define em emplace
# define pob pop_back
# define rep(i,n) for(int i = 0; i < n; i++)
# 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
# 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;
    //場所iに料理p[i]がある
    vector<int> p(n);
    rep(i,n) cin >> p[i];
    //料理iが場所c[i]にある
    vector<int> c(n);
    rep(i,n) c[p[i]] = i;
    map<int,int> mp;
    rep(i,n) {
        int j = c[i];
        mp[((j-((i-1+n)%n))+n)%n]++;
        mp[((j-((i+1+n)%n))+n)%n]++;
        mp[((j-((i+n)%n))+n)%n]++;
    }    
    int ans = -1;
    for(auto p : mp) chmax(ans, p.se);
    cout << ans << endl;
}


【D問題 Unique Username】

これ難しくないですか？ コンセプトとしては「上手に全探索を書くことができますか？」です。ユーザーネームを構成するための文字列たちをセグメントと呼びことにします。セグメント同士の間には少なくとも1つのアンダースコアを入れる必要があるので、あと何個アンダースコアを入れる必要があるかを最初にカウントしておきます。セグメントの並び替え方は、next_permutationで全探索すればいいです。あとはこれを管理しながらDFSを実装すればいいです。言葉にすれば簡単そうに見えますが、実際はすごく難しいと思います。あと、コーナーケースにも気をつけましょう。僕はこれでめちゃくちゃペナくらいました。コードは以下です。

#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 yes {puts("Yes"); return;}
# define no {puts("No"); return;}
# define dame {puts("-1"); return;}
# define yn {puts('Yes');} else{puts('No');}
# define ret(x) {cout << (x) << endl; return 0;}
# define ll long long
# define fi first
# define se second
# define vi vector<int>
# define vl vector<long long>
# define vs vector<string>
# define vb vector<bool>
# define vvi vector<vector<int>>
# define vvl vector<vector<long long>>
# define vvb vector<vector<bool>>
# define vpi vector<pair<int, int>>
# define vpl vector<pair<ll, ll>>
# define pb push_back
# define ps push
# define eb emplace_back
# define em emplace
# define pob pop_back
# define rep(i,n) for(int i = 0; i < n; i++)
# 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
# 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<string> s(n);
    rep(i,n) cin >> s[i];
    set<string> is_exist;
    vector<string> t(m);
    rep(i,m) {
        cin >> t[i];
        is_exist.insert(t[i]);
    }
    if (n == 1 && s[0].size() < 3) {
        cout << -1 << endl;
        return 0;
    }
    else if (n == 1) {
        cout << (is_exist.count(s[0])? "-1": s[0]) << endl;
        return 0;
    }
    vector<int> perm(n);
    iota(all(perm), 0);
    auto dfs = [&](auto& f, int cnt, string x) -> void {
        if(x.size() > 16) return;
        if(cnt == n) {
            if(is_exist.count(x)) return;
            cout << x << '\n';
            exit(0);
        }
        x += '_';
        rep(i,16) {
            if(sz(x) >= 16) break;
            f(f,cnt+1,x+s[perm[cnt]]);
            x += '_';
        }
    };
    do{
        dfs(dfs,1,s[perm[0]]);
    } while(next_permutation(all(perm)));
    cout << -1 << endl;
}


【終わりに】

DFSは何回書いても綺麗に実装するのが難しいですね。再帰の考え方は絶対身につける必要があるので、繰り返し練習を積んでいきたいと思います。E,Fの解説も理解できしだい更新していきます。swapコンへの参加もお待ちしております！それでは！

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