LoginSignup
0
0

More than 1 year has passed since last update.

@swapman

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

Last updated at Posted at 2022-10-31

みなさんこんにちは。swapmanです。ABC258のA-D問題の解説を行います。言語はC++です。
それでは本編に行きましょう。

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

【A問題】When?

この問題は60以上なら1時間以上経っていることを示すので, 60で割った余りを22時代で出力すればいいです。printfを使うと0埋めが楽なのでオススメです。コードは以下です。

#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 k;
    cin >> k;
    if(k >= 60) printf("22:%02d\n", k%60);
    else printf("21:%02d\n", k);
  }
};

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


【B問題】Number Box

これは始点を決め打ちして, 8方向全てに探索をかければいいです。8方向全てに探索をかける時, dx[], dy[]のような配列を持っておくと楽に実装することができます。詳しくはコードを参照してください。

#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<string> s(n);
    cin >> s;
    vector<string> st;
    rep(i,n) rep(j,n) {
        rep(dir,8) {
            int ni = i;
            int nj = j;
            string now = "";    
            rep(k,n) {
                int nxi = (ni+dx[dir]+n)%n;
                int nxj = (nj+dy[dir]+n)%n;
                char c = s[nxi][nxj];
                now += c;
                ni = nxi;
                nj = nxj;
            }
            st.push_back(now);
        }
    }
    sort(all(st));
    cout << st.back() << endl;
  }
};

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


【C問題】Rotation

この問題を愚直に実装することを考えます。一番最初に思いつく方法としては、dequeを使った実装を思いつくと思います。dequeはpush及びpopの計算量はO(1)で行うことができます。しかし、各クエリの処理にO(N)かかると、全体計算量はO(NQ)tなってしまい、TLEします。ここでクエリ数は変えることはできないので、各クエリをより高速に処理することを考えます。各クエリの操作は末尾の数字を先頭に追加すると言う単純なのもので、仮に数列をvectorで持つことを考えると、数列の中身自体に変化がないことが分かり、その数列の長さをNとすると、N回Rotateを繰り返せば、元の数列に戻ることに気づきます。すなわちN回以上の操作は無意味であり、これはNで割った余り回数分だけRotateしたことと同値です。これを用いてあげると各クエリをO(1)で処理することができ、全体でO(Q)となり、十分高速に動作します。コードは以下です。

#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,q;
    cin >> n >> q;
    string s;
    cin >> s;
    int cnt = 0;
    rep(qi,q) {
        int tt,x;
        cin >> tt >> x;
        if(tt == 1) {
            cnt += x;
            cnt %= n;
        } else {
            --x;
            cout << s[(x-cnt+n)%n] << endl;
        }
    }
  }
};

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


【D問題】Trophy

この問題は典型的な累積和の問題です。まず、「初めてステージをクリアするためにはストーリー映像の視聴とゲームプレイを両方行う必要があるが、二回目以降はゲームプレイのみでクリアすることができる。」と言う特殊ルールを無視して考えます。では特殊ルール有りの場合で考えます。結論から言うと、2周目以降は最も早くクリアできるゲームプレイだけを周回すればいいです。この結論に辿り着ければ、あとはもう簡単です。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;}
# 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,x;
    cin >> n >> x;
    vector<ll> a(n), b(n), c(n), m(n);
    rep(i,n) cin >> a[i] >> b[i];
    rep(i,n) c[i] = a[i] + b[i];
    m = b;
    rep(i,n-1) chmin(m[i+1], m[i]);
    vector<ll> s(n+1);
    rep(i,n) s[i+1] = s[i]+c[i];
    ll ans = LINF;
    rep(i,n) {
        ll now = s[i+1] + (x-i-1)*m[i];
        chmin(ans, now);
    }
    cout << ans << endl;
  }
};

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


【終わりに】

最近コンテストでも3、4完が安定してきましたが、水色に上がるには5完安定が必須なので頑張ります。
近々EDPCの解説や典型の解説もレベルごとに解説していきたいと思います。それでは！

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