AtCoder Beginner Contest 420

A - What month is it?

問題文

modの問題です。

ans = (x+y)\bmod{12}

が思い浮かびます。

ans = (x+y)\bmod{12} = 0

の時、

ans = ans + 12

考察が終わりましたね。

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, y;
    cin >> x >> y;
    int ans = (x+y)%12;
    if(ans == 0) ans+=12;
    cout << ans << endl;
    return 0;
} 

B - Most Minority

問題文
実装問題です。
0と1のどちらが多いか計測。
少ない方の人に加点をします。
最大の点数を探索します。
最大の点数で最も小さなindexの人が答えです。

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<string> s(n);
    rep(i, n) cin >> s[i];
    vector<int> ans(n);
    rep(i, m){
        int zero = 0, one = 0;
        rep(j, n){
            if(s[j][i] == '0') zero++;
            else one++;
        }
        rep(j, n){
            if(zero < one){
                if(s[j][i] == '0') ans[j]++;
            }else{
                if(s[j][i] == '1') ans[j]++;
            }
        }
    }
    int p = 0;
    rep(i, n){
        p = max(p, ans[i]);
    }
    rep(i, n){
        if(p == ans[i]) cout << i + 1 << ' ';
    }
    cout << endl;
    return 0;
} 

C - Sum of Min Query

問題文

前処理でsumを計算します。

C++

    ll ans = 0;
    rep(i, n){
        ans += min(a[i], b[i]);
    }

合計から更新前のmin(a_x_i, b_x_i)値を引きます。
合計へ更新後のmin(a_x_i, b_x_i)値を加算します。

C++

    rep(i, q){
        ans -= min(a[x[i]-1], b[x[i]-1]);
        if(c[i] == 'A'){
            a[x[i]-1] = v[i];
        }else if(c[i] == 'B'){
            b[x[i]-1] = v[i];
        }        
        ans += min(a[x[i]-1], b[x[i]-1]);
        cout << ans << endl;
    }

考察が終わりました。

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, q;
    cin >> n >> q;
    vector<ll> a(n), b(n);
    rep(i, n) cin >> a[i];
    rep(i, n) cin >> b[i];
    vector<char> c(q);
    vector<ll> x(q), v(q);
    rep(i, q) cin >> c[i] >> x[i] >> v[i];
    ll ans = 0;
    rep(i, n){
        ans += min(a[i], b[i]);
    }
    rep(i, q){
        ans -= min(a[x[i]-1], b[x[i]-1]);
        if(c[i] == 'A'){
            a[x[i]-1] = v[i];
        }else if(c[i] == 'B'){
            b[x[i]-1] = v[i];
        }        
        ans += min(a[x[i]-1], b[x[i]-1]);
        cout << ans << endl;
    }

    return 0;
} 

D - Toggle Maze

問題文

頂点倍化というテクニックが必要な問題です。
bfs, ダイクストラなどに使用される典型です。
スイッチの開閉を考慮すると2, h, wの3次元配列のbfsで解くことができます。

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

int main() {
    int h, w;
    cin >> h >> w;
    vector<string> a(h);
    rep(i, h) cin >> a[i];
    P st, gl;
    rep(i, h){
        rep(j, w){
            if(a[i][j] == 'S'){
                st.first = i;
                st.second = j;
            }
            if(a[i][j] == 'G'){
                gl.first = i;
                gl.second = j;
            }
        }
    }

    queue<tuple<int, int, int>> que;
    que.emplace(0, st.first, st.second);
    vector<vector<vector<int>>> graph(2, vector<vector<int>>(h, vector<int>(w, INF)));
    graph[0][st.first][st.second] = 0;

    while(que.size()){
        auto [c, y, x] = que.front();
        que.pop();

        int cc = c;
        if(a[y][x] == '?') cc = 1 ^ c;

        for(int i=0; i<4; i++){
            int xx = dx[i] + x;
            int yy = dy[i] + y;
            if(xx < 0 || w <= xx || yy < 0 || h <= yy) continue;
            if(graph[cc][yy][xx] != INF) continue;
            if(a[yy][xx] == '#') continue;
            if(a[yy][xx] == 'o' && cc == 1) continue;
            if(a[yy][xx] == 'x' && cc == 0) continue;

            graph[cc][yy][xx] = graph[c][y][x] + 1;
            que.emplace(cc, yy, xx);            
        }
    }

    int ans = min(graph[0][gl.first][gl.second], graph[1][gl.first][gl.second]);
    if(ans == INF){
        cout << -1 << endl;
    }else{
        cout << ans << endl;
    }
    
    return 0;
}