AtCoder Beginner Contest 182（ABC182）

atcoder.jp

A - twiblr

$ B \leq 2A + 100 $ なので$ 2A + 100 - B $を出力
提出コード

void solve(){
    int A, B;
    cin >> A >> B;
    cout << max(0, 2*A+100-B) << endl;
}

B - Almost GCD

制約が小さいので$ A_i $が$2 \leq j \leq 1000 $で割り切れるならその個数をカウントしていけばいい
カウントした個数が最大の$ j $を出力
提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> A(N);
    vector<int> cnt(1001);
    REP(i,N){
        cin >> A[i];
        for(int j=2;j<=1000;j++) if(A[i] % j == 0) cnt[j]++;
    }
    int ma = 0;
    int ans = 0;
    for(int i=1000;i>=2;i--){
        if(chmax(ma, cnt[i])) ans = i;
    }
    cout << ans << endl;
}

C - To 3

桁和が3の倍数なら何も消さなくていい
各桁を$ mod $ $ 3 $上で考えた時の個数と総和を求める
$ sum = 0 $の時何も消さなくていいので$ 0 $ $ sum = 1 $の時1を1つ消すか2を2つ消せるなら消せばいい
$ sum = 2 $の時1を2つ消すか2を1つ消せるなら消せばいい
提出コード

void solve(){
    ll N;
    cin >> N;
    vector<int> cnt(3);
    ll sum = 0;
    int k = 0;
    while(N > 0){
        int num = N % 10;
        num %= 3;
        cnt[num]++;
        sum += num;
        N /= 10;
        k++;
    }
    if(sum % 3 == 0) cout << 0 << endl;
    else if(sum % 3 == 1){
        if(cnt[1] >= 1 and k > 1) cout << 1 << endl;
        else if(cnt[2] >= 2 and k > 2) cout << 2 << endl;
        else cout << -1 << endl;
    }
    else{
        if(cnt[2] >= 1 and k > 1) cout << 1 << endl;
        else if(cnt[1] >= 2 and k > 2) cout << 2 << endl;
        else cout << -1 << endl;
    }
}

D - Wandering

$ A_i $の累積和を考える
各操作ごとに最終的に加算される値は決まっている
$ A_j $を見ている時、$ A_1 + A_2 + ... + A_{j-1} $を順番に足していく時、その累積和がmaxになる時点が最大となる可能性がある
そのため、累積和とそのmaxを求めながら最大になる座標を求めればいい
提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> A(N);
    REP(i,N) cin >> A[i];
    ll cum = 0, cur = 0;
    ll ans = 0, ma = 0;
    REP(i,N){
        chmax(ans, cur + ma);
        cur += cum + A[i];
        cum += A[i];
        chmax(ma, cum);;
        chmax(ans, cur);
        // dumps(ans, cur, ma);
    }
    cout << ans << endl;
}

E - Akari

各マスにたいして、ランプからの光が上下左右のどの方向から来たかを状態に持ってBFSをする
そうすると、ある1マスに対して最大4方向からの状態しかないので最大でも$ 4HW $で状態数が抑えられる
提出コード

void solve(){
    int H, W, N, M;
    cin >> H >> W >> N >> M;
    vector<vector<bool>> fi(H, vector<bool>(W, true));
    queue<tuple<int, int, int>> q;
    vector<int> A(N), B(N);
    vector<int> C(M), D(M);
    REP(i,N){
        cin >> A[i] >> B[i];
        --A[i], --B[i];
    }
    REP(i,M){
        cin >> C[i] >> D[i];
        --C[i], --D[i];
        fi[C[i]][D[i]] = false;
    }
    vector<vector<vector<bool>>> used(4, vector<vector<bool>>(H, vector<bool>(W)));
    REP(i,N){
        used[0][A[i]][B[i]] = true;
        used[1][A[i]][B[i]] = true;
        used[2][A[i]][B[i]] = true;
        used[3][A[i]][B[i]] = true;
        REP(d,4){
            int nh = A[i] + dx[d], nw = B[i] + dy[d];
            if(nh < 0 or nh >= H or nw < 0 or nw >= W or !fi[nh][nw]) continue;
            q.emplace(d, nh, nw);
        }
    }
    while(!q.empty()){
        auto [dir, h, w] = q.front(); q.pop();
        if(used[dir][h][w]) continue;
        used[dir][h][w] = true;
        int nh = h + dx[dir], nw = w + dy[dir];
        if(nh < 0 or nh >= H or nw < 0 or nw >= W or !fi[nh][nw]) continue;
        if(used[dir][nh][nw]) continue;
        q.emplace(dir, nh, nw);
    }
    int ans = 0;
    REP(i,H) REP(j,W){
        bool ok = false;
        REP(k,4) if(used[k][i][j]) ok = true;
        if(ok) ans++;
    }
    cout << ans << endl;
}