AtCoder Beginner Contest 347

A - Divisible

シミュレートしましょう。

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, K;
    cin >> N >> K;
    vector<int> A(N);
    rep(i, N) cin >> A[i];
    rep(i, N){
        if(A[i] % K ==0){
            cout << A[i] / K << ' ';
        }
    }
    cout << endl;

    return 0;
} 

B - Substring

O(N^2)

substrで文字列を取り出し、setに格納しましょう。

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;
    set<string> st;
    for(int i=0; i<S.size(); i++){
        for(int j=1; j<=S.size()-i; j++){
            string s = S.substr(i, j);
            st.insert(s);
        }
    }
    cout << st.size() << endl;
    return 0;
} 

C - Ideal Holidays

3 2 5
1 2 9

先頭の数にA+Bを足し、来週の最初の予定を出す。
1 + 7 = 8
来週の最初の予定と今週の最後の予定を差を求める。
8 - 2 = 6

来週の最初の予定と今週の最後の予定を差がB以上なら、
・今週の最後の予定はA+1以下になる。
・Bより感覚が空いているので、1週間の任意の日から予定を始めると休日になる。

よって、
D[i] - D[i-1] > B
が成立する時、Yesになります。

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() {
    ll N, A, B;
    cin >> N >> A >> B;
    vector<ll> D(N);
    rep(i, N) cin >> D[i];
    rep(i, N) D[i] = D[i] % (A+B);
    sort(D.begin(), D.end());
    D.push_back(D[0] + (A+B));

    repx(i, 1, D.size()){
        if(D[i] - D[i-1] > B){
            cout << "Yes" << endl;
            return 0;
        }
    }

    cout << "No" << endl;

    return 0;
}