ABC, ARC 灰diff問題埋め

B - Iron Bar Cutting

O(N)

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, sum=0;
    cin >> N;

    vector<ll> A(N);
    rep(i, N){
        cin >> A[i];
        sum += A[i];
    }
    ll l=0, r=0, res=NUM_MAX;
    rep(i, N){
        l += A[i];
        sum -= A[i]; 
        res = min(res, abs(l-sum));
    }
    cout << res << endl;

    return 0;
}

A - Table Tennis Training

O(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() {
    ll N, A, B;
    cin >> N >> A >> B;

    if(A==B){
        cout << 0 << endl;
        return 0;
    }

    if(abs(A-B) % 2 == 0){
        cout << abs(A-B) / 2 << endl;
    }else{
        cout << min(N-B, A-1) + 1 + (B - A - 1) / 2 << endl;
    }

    return 0;
}

B - 仲良しうさぎ

O(N)

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);
    rep(i, N) cin >> a[i];

    int ans=0;
    rep(i, N){
        int j = a[i];
        if(i == a[j-1]-1) ans++;
    }
    cout << ans / 2 << endl;

    return 0;
}

B - Similar Arrays

O(N)

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 N, ans;

void dfs(vector<int> A, int cnt, int v){
    if(N==cnt){
        if(v%2==0) ans++;
        return;
    }

    dfs(A, cnt+1, v * (A[cnt]-1));
    dfs(A, cnt+1, v * A[cnt]);
    dfs(A, cnt+1, v * (A[cnt]+1));
}

int main() {

    cin >> N;
    vector<int> A(N);
    rep(i, N) cin >> A[i];
    dfs(A, 0, 1);
    cout << ans << endl;

    return 0;
}

C - Same Integers

O(N)

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() {
    vector<int> V(3);
    rep(i, 3) cin >> V[i];

    int odd=0, even=0;
    rep(i, 3){
        if(V[i]%2==1) odd++;
        else even++;
    }

    int res=0;
    if(odd==2){
        res++;
        rep(i, 3) if(V[i]%2==1) V[i]++;
    }
    if(even==2){
        res++;
        rep(i, 3) if(V[i]%2==0) V[i]++;
    }

    int ma = max(max(V[0], V[1]), V[2]);
    rep(i, 3) res += (ma-V[i]) / 2;
    cout << res << endl;

    return 0;
}

A - Ice Tea Store

O(N)

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 Q, H, S, D, N;
    cin >> Q >> H >> S >> D >> N;

    vector<tuple<ll, ll, ll>> vec;
    vec.push_back(tuple<ll, ll, ll>(Q*8, 1, Q));
    vec.push_back(tuple<ll, ll, ll>(H*4, 2, H));
    vec.push_back(tuple<ll, ll, ll>(S*2, 4, S));
    vec.push_back(tuple<ll, ll, ll>(D, 8, D));

    sort(vec.begin(), vec.end());

    ll cnt=0, res=0;
    N = N * 4;
    while(N>1){
        if(N % get<1>(vec[cnt]) == 0){
            res += N / get<1>(vec[cnt]) * get<2>(vec[cnt]);
            break;
        }else{
            res += N / get<1>(vec[cnt]) * get<2>(vec[cnt]);
            N = N % get<1>(vec[cnt]);
            cnt++;
        }
    }
    cout << res << endl;

    return 0;
}

B - Ringo's Favorite Numbers

O(1)
Nが100の時、分岐処理が入ります。

C++

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; 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; }
const long long INF = 1LL << 60;

int main(int argc, const char * argv[]) {
    ll D, N;
    cin >> D >> N;
    if(N==100) N++;

    ll X = powl(100, D);
    cout << X * N << endl;

    return 0;
}

A - AtCoder Group Contest

O(N)

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;
    int NN = N*3;
    vector<ll> A(NN);
    rep(i, NN) cin >> A[i];
    sort(A.begin(), A.end(), greater<ll>());

    ll res=0;
    rep(i, N) res += A[i*2+1];
    cout << res << endl;

    return 0;
}

B - Exponential

O(N)

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 X;
    cin >> X;

    int m = 1;
    repx(i, 2, X+1){
        int sum=i, cnt=1;
        while(sum * i <=X){
            sum *= i;
            cnt++;
        }
        if(cnt>1)m = max(m, sum);
    }
    cout << m << endl;

    return 0;
}

B - 文字列大好きいろはちゃんイージー

O(N)

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, L;
    cin >> N >> L;

    vector<string> S(N);
    rep(i, N) cin >> S[i];
    sort(S.begin(), S.end());

    string res;
    rep(i, N) res += S[i];
    cout << res << endl;

    return 0;
}

C - 100 to 105

O(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 X;
    cin >> X;

    if(X < 100){
        cout << "0" << endl;
        return 0;
    }

    int A = X / 100;
    int N = X % 100;

    if((N+A-1) / A <=5) cout << "1" << endl;
    else cout << "0" << endl;

    return 0;
}

A - Dividing a String

O(N)

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<string> str;
    str.push_back(s.substr(0, 1));
    repx(i, 1, s.size()){
        if(str[str.size()-1] == s.substr(i, 1)){
            if(i == s.size() - 1){
                if(str[str.size()-2] == s.substr(i-1, 2)){
                    str[str.size()-2] += s.substr(i-1, 1);
                    str[str.size()-1] = s.substr(i, 1);
                }else{
                    str[str.size()-1] += s.substr(i, 1);
                }
            }else{
                str.push_back(s.substr(i, 2));
                i++;
            }
        }else{
            str.push_back(s.substr(i, 1));
        }
    }
    cout << str.size() << endl;

    return 0;
}

A - Wanna go back home

O(N)

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;

    map<char, int> mp;
    rep(i, s.size()) mp[s[i]]++;

    int ok=1;
    if(0<mp['N'] && mp['S']==0) ok=0;
    if(0<mp['S'] && mp['N']==0) ok=0;
    if(0<mp['W'] && mp['E']==0) ok=0;
    if(0<mp['E'] && mp['W']==0) ok=0;

    if(ok) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}

B - A to Z String

O(N)

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();

    int res=0, ok=0, cnt=0;
    rep(i, n){
        if(s[i] == 'A') ok = 1;
        if(ok) cnt++;
        if(s[i] == 'Z') res = max(res, cnt);
    }
    cout << res << endl;

    return 0;
}

B - ∵∴∵

O(N)

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 o, e;
    cin >> o >> e;

    int n = min(o.size(), e.size());
    string ans;
    rep(i, n){
        ans += o[i];
        ans += e[i];
    }
    if(n<o.size()) ans += o[n];
    cout << ans << endl;

    return 0;
}

B - たてなが

O(N)

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;

    vector<string> C(H);
    rep(y, H) cin >> C[y];

    rep(y, H){
        cout << C[y] << endl;
        cout << C[y] << endl;
    }

    return 0;
}

B - Contest with Drinks Easy

O(N)

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, sum=0;
    cin >> N;

    vector<int> T(N);
    rep(i, N) cin >> T[i];
    rep(i, N) sum += T[i];

    cin >> M;
    vector<int> P(M);
    vector<int> X(M);
    rep(i, M) cin >> P[i] >> X[i];
    rep(i, M) cout << sum - T[P[i]-1] + X[i] << endl;

    return 0;
}

B - AcCepted

O(N)

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 ok = 1;
    if(s[0] != 'A') ok = 0;
    if(s[1]-'0' < 49 || 74 < s[1]-'0') ok = 0;
    if(s[s.size()-1]-'0' < 49 || 74 < s[s.size()-1]-'0') ok = 0;

    int sum=0, csum=0;
    repx(i, 2, s.size()-1){
        int n = s[i] - '0';
        if(49<=n && n<=74) sum++;
        if(n==19) csum++;
    }

    if(ok && csum == 1 && sum == s.size() - 4) cout << "AC" << endl;
    else cout << "WA" << endl;

    return 0;
}

B - Palace

O(N)

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;
    double T, A;
    cin >> N >> T >> A;

    vector<pair<double,int>> H(N);
    rep(i, N){
        double h;
        cin >> h;
        H[i].first = abs(A - (T - h * 0.006));
        H[i].second = i + 1;
    }
    sort(H.begin(), H.end());

    cout << H[0].second << endl;

    return 0;
}

B - Small and Large Integers

O(N)

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 a, b, k;
    cin >> a >> b >> k;

    set<int> st;
    repx(i, a, (a+k)){
        if(a<=i && i<=b) st.insert(i);
    }
    repx(i, b-k+1, b+1){
        if(a<=i && i<=b) st.insert(i);
    }

    for(auto s:st){
        cout << s << endl;
    }

    return 0;
}

B - Counting Roads

O(N)

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;

    vector<vector<int>> A(N);
    rep(i, M){
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        A[a].push_back(b);
        A[b].push_back(a);
    }

    rep(i, N) cout << A[i].size() << endl;

    return 0;
}

B - Comparison

O(N)

C++

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; 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 a, b;
    cin >> a >> b;

    if(a.size()>b.size()){
        cout << "GREATER" << endl;
        return 0;
    }else if(a.size()<b.size()){
        cout << "LESS" << endl;
        return 0;
    }

    int n = min(a.size(), b.size());
    rep(i, n){
        int aa = stoi(a.substr(i, 1));
        int bb = stoi(b.substr(i, 1));
        if(aa>bb){
            cout << "GREATER" << endl;
            return 0;
        }else if(aa<bb){
            cout << "LESS" << endl;
            return 0;
        }
    }
    cout << "EQUAL" << endl;

    return 0;
}

B - Picture Frame

O(N)

C++

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; 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; }

char hw[103][103];

int main() {
    int h, w;
    cin >> h >> w;

    rep(i, w+2) hw[0][i] = '#';
    rep(i, w+2) hw[h+1][i] = '#';
    rep(i, h+2) hw[i][0] = '#';
    rep(i, h+2) hw[i][w+1] = '#';

    rep(i, h){
        string s;
        cin >> s;

        rep(j, w){
            hw[i+1][j+1] = s[j];
        }
    }

    rep(i, h+2){
        rep(j, w+2){
            cout << hw[i][j];
        }
        cout << endl;
    }

    return 0;
}

B - Lucas Number

O(N)

C++

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; 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; }

ll dp[100];

int main() {
    ll N;
    cin >> N;

    dp[0] = 2;
    dp[1] = 1;

    for(int i=2; i<=N; i++){
        dp[i] = dp[i-1] + dp[i-2];
    }
    cout << dp[N] << endl;

    return 0;
}

C - Coloring Colorfully

O(N)

C++

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; 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 sum1=0;
    int sum2=0;
    rep(i, s.size()){
        if(i%2==0){
            if(s[i] != '0') sum1++;
            if(s[i] != '1') sum2++;
        }else{
            if(s[i] != '1') sum1++;
            if(s[i] != '0') sum2++;
        }
    } 
    cout << min(sum1, sum2) << endl;

    return 0;
}

B - 美しい文字列

O(N)

C++

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; 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;

    map<char, int> mp;
    rep(i, s.size()){
        mp[s[i]]++;
    }

    int res=0;
    for(auto m:mp){
        if(m.second % 2 == 0){
            res++;
        }
    }

    if(res == mp.size()) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}

C - *3 or /2

O(N)

C++

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; 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; }
const long long INF = 1LL << 60;

int main(int argc, const char * argv[]) {
    int N;
    cin >> N;

    int res=0;
    rep(i, N){
        int a;
        cin >> a;

        while(a % 2 == 0){
            a = a / 2;
            res++;
        }
    }
    cout << res << endl;

    return 0;
}

B - Foods Loved by Everyone

O(N)

C++

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; 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;

    vector<int> food(M);
    rep(i, N){
        int K;
        cin >> K;
        rep(j, K){
            int a;
            cin >> a;
            a--;
            food[a]++;
        }
    }

    int res=0;
    rep(i, M){
        if(food[i] == N) res++;
    }
    cout << res << endl;

    return 0;
}

A - Range Product

O(1)

C++

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; 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 a, b;
    cin >> a >> b;

    if(0<a) cout << "Positive" << endl;
    else if(a<=0 && 0<=b ) cout << "Zero" << endl;
    else{
        if((a - b + 1) % 2 == 0) cout << "Positive" << endl;
        else cout << "Negative" << endl;
    }

    return 0;
}

B - Five Dishes

O(N)

C++

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; 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() {
    vector<int> V(5);
    rep(i, 5) cin >> V[i];

    sort(V.begin(), V.end(), [](const auto lhf, const auto rhf){
        return lhf % 10 < rhf % 10;
    });

    int ok=0, t=0;
    rep(i, 5){
        if(V[i]%10>0 && ok==0){
            ok=1;
            t+=V[i];
        }else{
            if(V[i]%10>0) t+=(10-V[i]%10) + V[i];
            else t+=V[i];
        }
    }
    cout << t << endl;

    return 0;
}

B - Not Found

O(N)

C++

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; 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;

    map<char, int> mp;
    rep(i, 26){
        char a = (char)(i+97);
        mp[a]=0;
    }
    rep(i, s.size()){
        mp[s[i]]++;
    }
    for(auto m:mp){
        if(m.second==0){
            cout << m.first << endl;
            return 0;
        }
    }
    cout << "None" << endl;

    return 0;
}

B - Postal Code

O(N)

C++

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; 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 a, b;
    cin >> a >> b;

    string s;
    cin >> s;
    rep(i, s.size()){
        if((s[i] == '-' && a!=i) || (s[i] != '-' && a==i)){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;

    return 0;
}

B - Increment Decrement

O(N)

C++

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; 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;
    string s;
    cin >> N >> s;

    int sum=0, res=0;
    rep(i, s.size()){
        if(s[i] == 'I') sum++;
        else sum--;
        res = max(res, sum);
    }
    cout << res << endl;

    return 0;
}

B - Varied

O(N)

C++

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; 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;

    map<char, int> mp;
    rep(i, s.size()){
        mp[s[i]]++;
    }

    for(auto m:mp){
        if(m.second >1){
            cout << "no" << endl;
            return 0;
        }
    }

    cout << "yes" << endl;
    return 0;
}

B - 754

O(N)
文字列をintに変換できるか
絶対値の関数を知っているか

C++

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; 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 res=999;
    rep(i, s.size()-2){
        string t = s.substr(i, 3);
        int X = atoi(t.c_str());
        res = min(abs(X-753), res);
    }
    cout << res << endl;

    return 0;
}

B - Nice Shopping

O(N)
数列Aの最小値aを取得。
数列Bの最小値bを取得。
xとyの組み合わせからcを引いた金額の最小値c。
min(c, a+b)が解答。

C++

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; 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 A, B, M, mina=200010, minb=200010;
    cin >> A >> B >> M;

    vector<int> a(A), b(B);
    rep(i, A){ cin >> a[i]; mina = min(mina, a[i]);}
    rep(i, B){ cin >> b[i]; minb = min(minb, b[i]);}

    vector<int> x(M), y(M), c(M);
    rep(i, M) cin >> x[i] >> y[i] >> c[i];

    int res=200010;
    rep(i, M){
        res = min(res, a[x[i]-1] + b[y[i]-1] - c[i]);
    }

    cout << min(res, mina+minb) << endl;

    return 0;
}

D - ModSum

C++

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; 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; }
const long long INF = 1LL << 60;

int main() {
    int N;
    cin >> N;

    ll res=0;
    for(int i=1; i<N; i++) res += i;
    cout << res << endl;

    return 0;
}

A - Sum and Product

C++

#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>
#include<set>
#include<bitset>

#define rep(i,n) for(int i=0; i<(n); i++)
#define fixed_setprecision(n) fixed << setprecision((n))
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;


int main() {
    ll S, P;
    cin >> S >> P;

    bool res=false;
    for(ll i=1; i*i<=P; i++){
        ll M = P/i;
        if(S == M+i) res=true;
    }
    if(res) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}

D - Brick Break

C++

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; 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; }
const long long INF = 1LL << 60;

int main() {
    int N;
    cin >> N;

    vector<int> A(N);
    rep(i, N) cin >> A[i];

    int cnt=1;
    rep(i, N) if(A[i] == cnt) cnt++;

    if(N==cnt-1 ) cout << 0 << endl;
    else if(N-(cnt-1)==N ) cout << -1 << endl;
    else cout << N-cnt+1 << endl;

    return 0;
}

A - Simple Math

C++

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; 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; }
const long long INF = 1LL << 60;

int main() {
    ll A, B, C;
    cin >> A >> B >> C;
    A = ((A * (A+1) / 2) % 998244353);
    B = ((B * (B+1) / 2) % 998244353);
    C = ((C * (C+1) / 2) % 998244353);
    ll res = (A * B) % 998244353 * C % 998244353;
    cout << res << endl;

    return 0;
}

A - Plus Minus

C++

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; 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; }
const long long INF = 1LL << 60;

int main() {
    int A, B;
    cin >> A >> B;
    int x = (A + B) / 2;
    int y = A - x;
    cout << x << ' ' << y << endl;

    return 0;
}

A - Fourtune Cookies

C++

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; 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; }
const long long INF = 1LL << 60;

int main() {
    vector<int> A(4);
    rep(i, 4) cin >> A[i];
    sort(A.begin(), A.end());

    if(A[0] + A[3] == A[1] + A[2] || A[0] + A[1] + A[2] == A[3]) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}

A - 106

C++

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; 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; }
const long long INF = 1LL << 60;

int main() {
    ll N;
    cin >> N;
    int x_max=0;
    int y_max=0;
    for(x_max=0; pow(3, x_max)<=N; x_max++){}
    for(y_max=0; pow(5, y_max)<=N; y_max++){}

    bool res=false;
    ll res_x=0, res_y=0;;
    for(int x=1; x<=x_max; x++){
        for(int y=1; y<=y_max; y++){
            if(powl(3, x) + powl(5, y) == N) { res=true; res_x = x; res_y = y; break; }
        }
    }

    if(res) cout << res_x << ' ' << res_y << endl;
    else cout << "-1" << endl;

    return 0;
}