0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@RubyLrving(ruby lrving)

AtCoder Beginner Contest 447

0
Posted at

A - Seats 2

問題文

(n+1)/2 >= m

上記の判定を問題文から読み解いてください。

C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    int n, m;
    cin >> n >> m;

    if((n + 1) / 2 >= m) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}

B - mpp

問題文

26文字が何回出現するかカウントを取りましょう。

cnts_{s_i}

その最大値の文字だけ非表示にします。

C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    string s;
    cin >> s;
    vector<int> cnts(26, 0);
    int n = s.size();
    rep(i, n){
        cnts[s[i] - 'a']++;
    }
    int m = 0;
    rep(i, 26) m = max(m, cnts[i]);
    rep(i, n){
        if(cnts[s[i] - 'a'] < m) cout << s[i];
    }
    cout << endl;
    return 0;
}

C - Insert and Erase A

問題文

問題文からAを除いた文字列が一致するか判定することがわかります。
その後に差分のAの数が答えになります。

実際のコンテストではシミュレーションで解きました。
文字列を結合するとTLEになるのでint型の変数で加算を行っています。
下記のコードです。

C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    string s, t;
    cin >> s >> t;
    int ans = 0;
    int cnt = 0;
    int n = t.size();
    rep(i, n){
        if(t[i] == 'A' && s[cnt] != t[i]){
            ans++;
        }else{
            while(cnt < s.size() && s[cnt] != t[i]){
                if(s[cnt] == 'A'){
                    cnt++;
                    ans++;
                }else{
                    cout << -1 << endl;
                    return 0;
                }
            }
            if(s.size() <= cnt){
                cout << -1 << endl;
                return 0;
            }
            if(s[cnt] != t[i]){
                cout << -1 << endl;
                return 0;
            }
            cnt++;
        }
    }
    for(int i=cnt; i<s.size(); i++){
        ans++;
        if(s[i] != 'A'){
            cout << -1 << endl;
            return 0;            
        }
    }
    cout << ans << endl;
    return 0;
}

コードを見ると何をしているか分からないですね。
もっと良いコーディング方法を探しましょう。

１、Aを除いた文字列が等しいか
２、各区間においてAの数の差分を判定する

上記の順でコーディングしてみましょう。

C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

string removeA(string s){
    string ret;
    for(int i=0; i<s.size(); i++){
        if(s[i] != 'A') ret += s[i];
    }
    return ret;
}

vector<int> f(string s){
    vector<int> ret;
    ret.push_back(0);
    for(int i=0; i<s.size(); i++){
        if(s[i] == 'A') ret.back()++;
        else ret.push_back(0);
    }
    return ret;
}

int main() {
    string s, t;
    cin >> s >> t;
    
    if(removeA(s) != removeA(t)){
        cout << -1 << endl;
    }else{
        vector<int> fs = f(s);
        vector<int> ft = f(t);
        int ans = 0;
        for(int i=0; i<fs.size(); i++){
            ans += abs(fs[i] - ft[i]);
        }
        cout << ans << endl;
    }

    return 0;
}

D - Take ABC 2

問題文

iをAのindex
jをBのindex
kをCのindex
のindexとした時、i<j<kが成立する組み合わせを文字列から取り除く。
これが何回できるかを問われています。
i<j<kの数を数えましょう。
実際のコンテストではqueueを使用しました。
下記のコードです。

C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    string s;
    cin >> s;
    int n = s.size();
    queue<int> a, b;
    int ans = 0;
    rep(i, n){
        if(s[i] == 'A'){
            a.push(i);
        }
        if(s[i] == 'B'){
            if(0 < a.size()){
                b.push(i);
            }
        }
        if(s[i] == 'C'){
            while(b.size() && a.front() > b.front()){
                b.pop();
            }
            if(0 < a.size() && 0 < b.size()){
                a.pop();
                b.pop();
                ans++;
            }
        }        
    }
    cout << ans << endl;
    return 0;
}

ACしましたが、コーディングとしては誤っていますね。
貪欲法でコーディングしてみましょう。

C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    string s;
    cin >> s;
    int n = s.size();
    vector<vector<int>> dp(n+1, vector<int>(3, 0));
    rep(i, n){
        if(s[i] == 'A'){
            dp[i][0]++;
        }
        if(s[i] == 'B' && dp[i][0] > dp[i][1]){
            dp[i][1]++;
        }
        if(s[i] == 'C' && dp[i][1] > dp[i][2]){
            dp[i][2]++;
        }  
        rep(j, 3){
            dp[i+1][j] = dp[i+1][j] + dp[i][j];
        }      
    }
    cout << dp[n][2] << endl;
    return 0;
}

綺麗なコードになりましたね。

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

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?