AtCoder Beginner Contest 452

A - Gothec

問題文

条件分岐を5回しましょう。

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 m, d;
    cin >> m >> d;

    if((m == 1 && d == 7) || (m == 3 && d == 3) || (m == 5 && d == 5) || (m == 7 && d == 7) || (m == 9 && d == 9)){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
} 

B - Draw Frame

問題文

2重ループの問題です。
x == 0 || x == w-1 || y == 0 || y == h-1を判定しましょう。

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 h, w;
    cin >> h >> w;

    for(int y=0; y<h; y++){
        for(int x=0; x<w; x++){
            if(x == 0 || x == w-1 || y == 0 || y == h-1){
                cout << '#';
            }else{
                cout << '.';
            }
        }
        cout << endl;
    }

    return 0;
} 

C - Fishbones

問題文

3次元配列を使用して肋骨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() {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    rep(i, n) cin >> a[i] >> b[i];
    int m;
    cin >> m;
    vector<string> s(m);
    rep(i, m) cin >> s[i];
    vector<vector<vector<bool>>> v(11, vector<vector<bool>>(11, vector<bool>(26)));
    rep(i, m){
        int l = s[i].size();
        rep(j, l){
            v[l][j][s[i][j] - 'a'] = true;
        }
    }

    vector<bool> ans(m, false);
    rep(i, m){
        if(s[i].size() != n) continue;
        bool ok = true;
        rep(j, n){
            if(v[a[j]][b[j]-1][s[i][j] - 'a'] == false){
                ok = false;
            }
        }
        if(ok) ans[i] = true;
    }
    rep(i, m) cout << (ans[i] ? "Yes":"No") << endl;

    return 0;
} 

D - No-Subsequence Substring

問題文

数え上げ問題です。
どの文字がどの位置にあるか配列で管理します。
探索位置lを固定して、tの文字列の文字がsのどこにあるか二分探索で判定します。
「部分列として含まないものの個数」なのでtの文字列と判定できる箇所を見つけて、r-l-1を加算していくことで解答できます。

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 n = s.size();
    vector<vector<int>> isa(26, vector<int>());
    for(int i=0; i<n; i++){
        isa[s[i] - 'a'].push_back(i);
    }

    int ans = 0;
    for(int l=0; l<n; l++){
        int r = l;
        for(auto c:t){
            vector<int>& v = isa[c-'a'];
            int index = lower_bound(v.begin(), v.end(), r) - v.begin();
            if(index >= v.size()){
                r = n+1;
                break;
            }
            r = v[index]+1;
        }
        ans += r-l-1;
    }
    cout << ans << endl;

    return 0;
}