AtCoder Beginner Contest 253

A - Median?

O(1)
aとcを比べて低い方を左、大きい方を右側へ配置。
aとbとcを比較することで答えになります。

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, c;
    cin >> a >> b >> c;
    if(c < a) swap(a, c);
    if(a <= b && b <= c) cout << "Yes" << endl;
    else  cout << "No" << endl;
    return 0;
} 

B - Distance Between Tokens

O(H*W)
マンハッタン距離を求める問題です。

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> S(H);
    for(auto &s:S) cin >> s;

    vector<P> pos;
    for(int y=0; y<H; y++){
        for(int x=0; x<W; x++){
            if(S[y][x] == 'o'){
                pos.push_back(P(y,x));
            }
        }
    }
    int dis = abs(pos[0].first - pos[1].first) + abs(pos[0].second - pos[1].second);
    cout << dis << endl;

    return 0;
} 

C - Max - Min Query

O(Q)
これはクエリ処理の問題です。
クエリ処理は2*10^5なのでループで間に合います。
queryが3の時、一番小さい値と大きい値を判定するときにどのようにするのかが問われています。
C++ならmapかmultisetを使うのが良いと思います。

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

    map<int, int> mp;
    for(int i=0; i<Q; i++){
        int query, x, c;
        cin >> query;
        if(query == 1){
            cin >> x;
            mp[x]++;
        }else if(query == 2){
            cin >> x >> c;
            mp[x] = max(mp[x]-c, 0);
            if(mp[x] == 0) mp.erase(x);
        }else if(query == 3){
            int l, r;
            for(auto itr = mp.begin(); itr != mp.end(); itr++){
                if(itr->second > 0){
                    l = itr->first;
                    break;
                }
            }
            for(auto itr = mp.rbegin(); itr != mp.rend(); itr++){
                if(itr->second > 0){
                    r = itr->first;
                    break;
                }
            }
            cout << r - l << endl;
        }
    }

    return 0;
} 

D - FizzBuzz Sum Hard

O(1)
等差数列の和、最小公倍数の問題です。
最小公倍数は,AとBの最大公約数gcdのGを求め、lcm=A/G*Bの経験結果から求めることができます。
等差数列の公式は、

n項あるかは、n=N/A \\
n項目の値は、l=A+(n-1)*A \\
初項からn項目までの和は、S=n*(A+l)/2 \\

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; }

template <class T>
T vlcm(T m, T n) {
    return lcm(m, n);
}

void solve(ll N, ll A, ll B){
    ll sum = N * (N + 1) / 2;
 
    ll n1 = N / A;
    ll l1 = A + (n1 - 1) * A;
    ll S1 = n1 * (A + l1) / 2;
    
    ll n2 = N / B;
    ll l2 = B + (n2 - 1) * B;
    ll S2 = n2 * (B + l2) / 2;
 
    ll C = vlcm(A, B);
    ll n3 = N / C;
    ll l3 = C + (n3 - 1) * C;
    ll S3 = n3 * (C + l3) / 2;
 
    cout << sum - (S1+S2) + S3 << endl; 
}
 
int main() {
    ll N, A, B;
    cin >> N >> A >> B;
    solve(N, A, B);
    return 0;
}