LoginSignup
0
1

More than 1 year has passed since last update.

@swapman

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

Last updated at Posted at 2022-10-23

皆さんこんにちは。swapmanです。第12回swapコンで取り扱ったABC260のA-D問題の解説を書いて行きたいと思います。
それでは本編です。

ABC260のリンク：https://atcoder.jp/contests/abc260

【A問題】A Unique Letter

各アルファベットの出現回数を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 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);
    string s;
    cin >> s;
    int n = sz(s);
    map<char,int> mp;
    rep(i,n) mp[s[i]]++;
    for(auto p : mp) {
        if(p.se == 1) {
            cout << p.fi << endl;
            return 0;
        }
    }
    cout << -1 << endl;
}


【B問題】Better Students Are Needed!

言われたことをするだけのように思いますが、同じ点数のものがいるときは出席番号が小さい順に順位をつけるという制約が面倒です。高順にソートするときに、そのままpair型を作ってソートしてしまうと、出席番号が大きい人の順位が高くなってしまいます。これを解決するために、出席番号に-1をかけてあげれば、絶対値が大きいほど値は小さくなるという負の数を使って、思うようにソートすることができます。コードは以下です。

#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,x,y,z;
    cin >> n >> x >> y >> z;
    vector<bool> used(n, false);
    vector<int> math(n), eng(n);
    rep(i,n) cin >> math[i];
    rep(i,n) cin >> eng[i];
    vector<pair<int,int>> d1(n);
    rep(i,n) d1[i] = make_pair(math[i], -i);
    sort(rall(d1));
    rep(i,x) {
        int id = abs(d1[i].se);
        used[id] = true;
    }
    vector<pair<int,int>> d2(n);
    rep(i,n) d2[i] = make_pair(eng[i], -i);
    sort(rall(d2));
    int i = 0;
    while(y > 0) {
        int id = abs(d2[i].se);
        if(used[id]) {
            i++;
            continue;
        }
        used[id] = true;
        i++;
        y--;
    }
    vector<pair<int,int>> d3(n);
    rep(i,n) {
        int tot = math[i] + eng[i];
        d3[i] = make_pair(tot,-i);
    }
    sort(rall(d3));
    i = 0;
    while(z > 0) {
        int id = abs(d3[i].se);
        if(used[id]) {
            i++;
            continue;
        }
        used[id] = true;
        i++;
        z--;
    }
    rep(i,n) {
        if(used[i] == true) {
            cout << abs(i)+1 << '\n';
        }
    }
}


【C問題】Changing Jewels

典型的な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);
    ll n,x,y;
    cin >> n >> x >> y;
    vector<ll> red(n+1), blue(n+1);
    red[n] = 1;
    for(int i = n; i >= 2; i--) {
        {//red veersion
            red[i-1] += red[i];
            blue[i] += red[i] * x;
        }
        {//blue version
            red[i-1] += blue[i];
            blue[i-1] += blue[i] * y;
        }
    }    
    cout << blue[1] << endl;
}


【D問題】Draw Your Cards

この問題は少し難しいと思うので、真面目に解説します。場に見えるカードとして置かれているのは、各山高々1枚だけでその見えているカードの中で引いたカードよりも大きいうち最小のカードをO(logN)くらいで見つけたいので、setを使う発想に至ります。しかしこれだけではダメで、カードが今何枚積まれているのかを記録する必要があります。このときパターンとしては以下の2つのパターンがあります。
①カードを新しい山として場におく。
②新しい山を作らずに、今見えているカードに重ねる。
カードを新しい山として置く場合は、lower_boundしたときに、そのイテレータがend()を指していたときです。それ以外の時は重ねます。重ねるときに、最後に見えていたカードの下にある枚数+1で枚数を更新するようにしておけば良いです。更新した後に、その山の枚数がKになっていないかどうかを確認し、なっていたら一番上になっているカードを場から削除する必要があります。これはsetのeraseを使えば良いです。制約にカードに書かれている数字は全て違うことが明記されているので、findをしてやる必要もないです。あとはその山にあるカード全てがそのターンに消去されたことをメモっておく必要があります。これを実現するために、カードを重ねるとき、自分の下にあるカードだけを覚えておけば良いです。一番下にあるカードの下は地面ですが、わかりやすいように-1とかにしておくと良いと思います。-1にしておくと、カードを食べるときwhile文を回して、-1が来るまでカードを順繰りに見ていき、ターン数を記録してやれば良いです。自分の実装の場合、自分の下にあるカードを記録する配列をnxt、ターン数を記録する配列をans、山の枚数を記録する配列をnumとしています。
コードは以下のようになります。

#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,k;
    cin >> n >> k;
    vector<int> p(n);
    rep(i,n) {
        cin >> p[i];
        --p[i];
    }
    set<int> tops;
    vector<int> ans(n,-1), num(n,-1), nxt(n, -1);
    rep(ni,n) {
        int x = p[ni];
        auto it = tops.lower_bound(x);
        if(it == tops.end()) {
            tops.insert(x);
            num[x] = 1;
        } else {
            tops.erase(it);
            int i = *it;
            num[x] = num[i] + 1;
            nxt[x] = i;
            tops.insert(x);
        }
        if(num[x] == k) {
            tops.erase(x);
            int i = x;
            while(i != -1) {
                ans[i] = ni+1;
                int nxi = nxt[i];
                i = nxi;
            }
        }
    }
    rep(i,n) cout << ans[i] << endl;
    
}


【終わりに】

最近気づきましたが、自分は緑上位の問題を解ける確率すらまだ低いので、青の問題はもう少し後でも良いのでは？と思ってきました。緑が瞬殺できるようになるにはもう少し時間がかかりそうですが、目標を下げず青色まで頑張って手を出します。いずれは到達すべきレベルなので。
ってことで今回はこの辺で！

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