接着剤の精進日記

競プロでの精進や研究に関係したことを書いていきます。

AtCoder Beginner Contest 203(Sponsored by Panasonic)

https://atcoder.jp/contests/abc203atcoder.jp

A - Chinchirorin

$ a = b $、$ b = c $、$ a = c $ のどれかを満たせばその残りを、そうでないなら0を出力
提出コード

void solve(){
    int a, b, c;
    cin >> a >> b >> c;
    if(a == b) cout << c << endl;
    else if(b == c) cout << a << endl;
    else if(a == c) cout << b << endl;
    else cout << 0 << endl;
}

B - AtCoder Condominium

実際に全部加算していき、その総和を出力
提出コード

void solve(){
    int N, K;
    cin >> N >> K;
    int sum = 0;
    for(int i=1;i<=N;i++){
        for(int j=1;j<=K;j++) sum += 100 * i + j;
    }
    cout << sum << endl;
}

C - Friends and Travel costs

$ A $ の昇順に村を訪れる事ができるかどうかを実際にシミュレートする
提出コード

void solve(){
    int N, K;
    cin >> N >> K;
    map<ll, ll> mp;
    REP(i,N){
        ll A, B;
        cin >> A >> B;
        cmp.add(A);
        mp[A] += B;
    }

    ll res = K;
    ll cur = 0;
    for(auto [k, v] : mp){
        if(res < k - cur){
            cur += res;
            res = 0;
            break;
        }
        else{
            res += v;
            res -= (k - cur);
            cur = k;
        }
    }
    if(res > 0) cur += res;
    cout << cur << endl;
}

D - Pond

難しい
ある整数 $ x $ 以下の整数が $ \lceil \frac{K ^ 2}{2} \rceil $ 以上を満たすもののうち、最小の $ x $ が中央値になり、二分探索で求めることが出来る
$ K \times K $ の区画に対して、$ x $ 以下の整数は $ 1 $ 、そうでないものは $ 0 $ とした総和を高速に求めることができればいい
これは、二次元累積和を用いることで各区画 $ \mathcal{O}(1) $ で求めることができ、全体で $ \mathcal {O}(N^2 \log (\max(A_i))) $ で解くことが出来る
提出コード

void solve(){
    ll N, K;
    cin >> N >> K;
    vector<vector<ll>> A(N, vector<ll>(N));
    REP(i,N) REP(j,N) cin >> A[i][j];
    auto check = [&](int m){
        vector<vector<ll>> cum(N + 1, vector<ll>(N + 1));
        REP(i,N) REP(j,N) cum[i+1][j+1] = cum[i][j+1] + cum[i+1][j] - cum[i][j] + (A[i][j] <= m);
        for(int i=K;i<=N;i++) for(int j=K;j<=N;j++){
            if(cum[i][j] - cum[i][j-K] - cum[i-K][j] + cum[i-K][j-K] >= (K * K + 1) / 2) return true;
        }
        return false;
    };
    ll l = -1, r = 2*INF;
    while(r - l > 1){
        ll m = (l + r) >> 1;
        if(check(m)) r = m;
        else l = m;
    }
    cout << r << endl;
}

E - White Pawn

今、操作1のみを行ったときに移動できる列の番号をsetで管理をする
操作2、3が行えるのは黒のポーンがある場所のみなので、行の昇順に黒のポーンがある行ごとに操作を行えばいい
操作によって増える要素集合をadd、減る要素集合をdelとしたときに、黒のポーンがある行を見終わったあとに、管理しているsetにaddを追加し、delを削除すればいい
最後まで操作を行ったときのsetのsizeが答え
提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    map<int, vector<int>> mp;
    REP(i,M){
        int X, Y;
        cin >> X >> Y;
        mp[X].emplace_back(Y);
    }
    set<int> st;
    st.insert(N);
    for(auto [k, v] : mp){
        set<int> add, del;
        for(auto y : v){
            if(st.count(y - 1)) add.insert(y);
            if(st.count(y + 1)) add.insert(y);
            if(st.count(y) and !st.count(y-1) and !st.count(y+1)) del.insert(y);
        }
        for(auto &y : add) st.insert(y);
        for(auto &y : del) st.erase(y);
    }
    cout << st.size() << endl;
}