AtCoder Beginner Contest 405

A - Is it rated?

• 問題文
  O(1)
  条件分岐の問題です。

C++

#include <bits/stdc++.h>
#include <atcoder/all>
 
#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 R, X;
    cin >> R >> X;

    if(X == 1 && (1600 <=R && R < 3000)){
        cout << "Yes" << endl;
        return 0;
    }else if(X == 2 && (1200 <=R && R < 2400)){
        cout << "Yes" << endl;
        return 0;
    }
    cout << "No" << endl;

    return 0;
} 

B - Not All

• 問題文
  O(N＊M)
  全探索の問題です。
  1、各要素がいくつあるか探索してハッシュBに保存
  2、ハッシュBを探索して要素は一つ以上あるか探索
  3、なかったらiを出力
  4、Aの最後の要素を削除して、ハッシュBから要素の数を一つ減らす

C++

#include <bits/stdc++.h>
#include <atcoder/all>
 
#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<int> A(N), B(M+1);
    rep(i, N){
        cin >> A[i];
        B[A[i]]++;
    }

    rep(i, N+1){
        int cnt = 0;
        repx(j, 1, M+1){
            if(B[j]>0) cnt++;
        }
        if(M>cnt){
            cout << i << endl;
            return 0;
        }
        B[A.back()]--;
        A.pop_back();
    }
    cout << M << endl;

    return 0;
} 

C - Sum of Product

• 問題文
  O(N)
  累積和の問題です。
  累積和だと考える要素は問題文から、

(A_1 * A_2 + A_1 * A_3 + A_1 * A_4)

(A_2 * A_3 + A_2 * A_4)

(A_3 * A_4)

を処理していきます。
（）の中身を、

A_1 * (A_2 + A_3 + A_4)

A_2 * (A_3 + A_4)

A_3 * (A_4)

と式を変形した時、（）の中身は、

A_0からA_Nまで合計 - A_0からA_iまで合計

となっている事がわかります。
よって累積和の問題と分かります。

C++

#include <bits/stdc++.h>
#include <atcoder/all>
 
#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<ll> A(N), AA(N+1);
    rep(i, N) cin >> A[i];
    rep(i, N) AA[i+1] = AA[i] + A[i]; 

    ll total = 0;
    rep(i, N){
        total += (AA[N] - AA[i+1]) * A[i];
    }
    cout << total << endl;

    return 0;
} 

D - Escape Route

• 問題文
  O(HW)
  多点BFSの問題です。
  多点BFSは定石みたいなもので知っているか知っていないかの問題です。

出口のEが複数個ほど会った時、どのマスからどのEが最も近いか判定して処理をする必要があります。
どのマスから「最も近いか判定」はBFSですね。
キューにEの座標をまとめてプッシュしましょう。

C++

#include <bits/stdc++.h>
#include <atcoder/all>
 
#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] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

char d[4] = {'>', 'v', '<', '^'};

int main() {
    int H, W;
    cin >> H >> W;
    vector<string> S(H);
    rep(i, H) cin >> S[i];

    queue<pair<int, int>> que;
    rep(y, H) rep(x, W){
        if(S[y][x] == 'E') que.push({y, x});
    }

    vector<vector<bool>> used(H, vector<bool>(W, false));
    while(que.size()){
        pair<int, int> p = que.front();
        que.pop();

        if(used[p.first][p.second]) continue;
        used[p.first][p.second] = true;

        for(int i=0; i<4; i++){
            int x = dx[i] + p.second;
            int y = dy[i] + p.first;

            if(x < 0 || W <= x || y < 0 || H <= y) continue;
            if(S[y][x] != '.') continue;

            S[y][x] = d[i];
            que.push({y, x});
        }
    }

    rep(i, H){
        cout << S[i] << endl;
    }

    return 0;
}