AtCoder Beginner Contest 450

A - 3,2,1,GO

問題文

for文

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;
    rep(i, n){
        cout << n - i;
        if(n-i>1) cout << ',';
        else cout << endl;
    }
    return 0;
} 

B - Split Ticketing

問題文

3重ループの問題です。
2次元配列でコストを管理できると、

C++

                if(c[i][j] + c[j][k] < c[i][k]){
                    cout << "Yes" << endl;
                    return 0;
                }

が思い浮かびます。

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<vector<ll>> c(n, vector<ll>(n));
    rep(i, n-1){
        repx(j, i+1, n){
            cin >> c[i][j];
        }
    }

    for(int i=0; i<n; i++){
        for(int j=i+1; j<n; j++){
            for(int k=j+1; k<n; k++){
                if(c[i][j] + c[j][k] < c[i][k]){
                    cout << "Yes" << endl;
                    return 0;
                }
            }
        }
    }
    cout << "No" << endl;
    
    return 0;
} 

C - Puddles

問題文

O(hw)
BFSです。
通常のbfsと異なるのは2重ループです。
bfsの始点を複数見つけて判定するところがあります。
hwの外を判定した時だけカウントをやめます。

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 dx[4] = {0, -1, 0, 1};
int dy[4] = {-1, 0, 1, 0};

int main() {
    int h, w;
    cin >> h >> w;
    vector<string> s(h);
    rep(i, h) cin >> s[i];
    vector<vector<bool>> used(h, vector<bool>(w, false));

    int ans = 0;
    rep(i, h){
        rep(j, w){
            if(used[i][j]) continue;
            if(s[i][j] == '#') continue;

            queue<pair<int, int>> que;
            que.push({i, j});
            bool ok = true;
            
            while(que.size()){
                auto [y, x] = que.front();
                que.pop();

                if(used[y][x]) continue;
                used[y][x] = true;

                for(int k=0; k<4; k++){
                    int xx = x + dx[k];
                    int yy = y + dy[k];
                    
                    if(0 <= xx && xx < w && 0 <= yy && yy < h){
                        if(s[yy][xx] == '.'){
                            que.push({yy, xx});
                        }
                    }else{
                        ok = false;
                    }
                }
            }

            if(ok){
                ans++;
            }
        }
    }
    cout << ans << endl;

    return 0;
} 

D - Minimize Range

問題文

dequeの問題です。
a_iをkで割った余りを使用して判定しても結果が変わらないことに注目します。
a_i = a_i % kとして余りを取り、昇順でソートします。
これに気づけるかが大きいです。
あとは最小値にkを足したものを追加、最小値を削除。
最大値-最小値を計算して、その最小値が答えになります。

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, k;
    cin >> n >> k;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];
    rep(i, n) a[i] = a[i] % k;
    sort(a.begin(), a.end());
    deque<ll> deq;
    rep(i, n) deq.push_back(a[i]);

    ll ans = 2e18;
    rep(i, n){
        deq.push_back(deq.front() + k);
        deq.pop_front();
        ll l = deq.front();
        ll r = deq.back();
        ans = min(ans, abs(r - l));
    }
    cout << ans << endl;

    return 0;
}